Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure

Kai Ming Ting; Ye Zhu; Mark Carman; Yue Zhu; Zhi-Hua Zhou

doi:10.1145/2939672.2939779

Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure

Kai Ming Ting, Ye Zhu, Mark Carman, Yue Zhu, Zhi-Hua Zhou

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

56 Citations (Scopus)

Abstract

This paper introduces the first generic version of data dependent dissimilarity and shows that it provides a better closest match than distance measures for three existing algorithms in clustering, anomaly detection and multi-label classification. For each algorithm, we show that by simply replacing the distance measure with the data dependent dissimilarity measure, it overcomes a key weakness of the otherwise unchanged algorithm.

Original language	English
Title of host publication	Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2016)
Subtitle of host publication	August 13-17, 2016, San Francisco, CA, USA
Editors	Alex Smola, Charu Aggarwal, Dou Shen, Rajeev Rastogi
Place of Publication	New York, New York
Publisher	Association for Computing Machinery (ACM)
Pages	1205-1214
Number of pages	10
ISBN (Electronic)	9781450342322
DOIs	https://doi.org/10.1145/2939672.2939779
Publication status	Published - 13 Aug 2016
Event	ACM International Conference on Knowledge Discovery and Data Mining 2016 - Hilton San Francisco Union Square, San Francisco, United States of America Duration: 13 Aug 2016 → 17 Aug 2016 Conference number: 22nd http://www.kdd.org/kdd2016/ https://dl.acm.org/doi/proceedings/10.1145/2939672

Conference

Conference	ACM International Conference on Knowledge Discovery and Data Mining 2016
Abbreviated title	KDD 2016
Country/Territory	United States of America
City	San Francisco
Period	13/08/16 → 17/08/16
Other	KDD 2016, a premier interdisciplinary conference, brings together researchers and practitioners from data science, data mining, knowledge discovery, large-scale data analytics, and big data.
Internet address	http://www.kdd.org/kdd2016/ https://dl.acm.org/doi/proceedings/10.1145/2939672

Keywords

Data dependent dissimilarity
Distance-based neighbourhood
Distance measure
K nearest neighbours
Probability-mass-based neighbourhood

Access to Document

10.1145/2939672.2939779

Cite this

Ting, K. M., Zhu, Y., Carman, M., Zhu, Y., & Zhou, Z.-H. (2016). Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure. In A. Smola, C. Aggarwal, D. Shen, & R. Rastogi (Eds.), Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2016): August 13-17, 2016, San Francisco, CA, USA (pp. 1205-1214). Association for Computing Machinery (ACM). https://doi.org/10.1145/2939672.2939779

Ting, Kai Ming ; Zhu, Ye ; Carman, Mark et al. / Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2016): August 13-17, 2016, San Francisco, CA, USA. editor / Alex Smola ; Charu Aggarwal ; Dou Shen ; Rajeev Rastogi. New York, New York : Association for Computing Machinery (ACM), 2016. pp. 1205-1214

@inproceedings{baa3853672ea4476a1025cb08128905b,

title = "Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure",

abstract = "This paper introduces the first generic version of data dependent dissimilarity and shows that it provides a better closest match than distance measures for three existing algorithms in clustering, anomaly detection and multi-label classification. For each algorithm, we show that by simply replacing the distance measure with the data dependent dissimilarity measure, it overcomes a key weakness of the otherwise unchanged algorithm.",

keywords = "Data dependent dissimilarity, Distance-based neighbourhood, Distance measure, K nearest neighbours, Probability-mass-based neighbourhood",

author = "Ting, {Kai Ming} and Ye Zhu and Mark Carman and Yue Zhu and Zhi-Hua Zhou",

year = "2016",

month = aug,

day = "13",

doi = "10.1145/2939672.2939779",

language = "English",

pages = "1205--1214",

editor = "Alex Smola and Charu Aggarwal and Dou Shen and Rajeev Rastogi",

booktitle = "Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2016)",

publisher = "Association for Computing Machinery (ACM)",

address = "United States of America",

note = "ACM International Conference on Knowledge Discovery and Data Mining 2016, KDD 2016 ; Conference date: 13-08-2016 Through 17-08-2016",

url = "http://www.kdd.org/kdd2016/, https://dl.acm.org/doi/proceedings/10.1145/2939672",

}

Ting, KM, Zhu, Y, Carman, M, Zhu, Y & Zhou, Z-H 2016, Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure. in A Smola, C Aggarwal, D Shen & R Rastogi (eds), Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2016): August 13-17, 2016, San Francisco, CA, USA. Association for Computing Machinery (ACM), New York, New York, pp. 1205-1214, ACM International Conference on Knowledge Discovery and Data Mining 2016, San Francisco, California, United States of America, 13/08/16. https://doi.org/10.1145/2939672.2939779

Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure. / Ting, Kai Ming; Zhu, Ye; Carman, Mark et al.
Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2016): August 13-17, 2016, San Francisco, CA, USA. ed. / Alex Smola; Charu Aggarwal; Dou Shen; Rajeev Rastogi. New York, New York: Association for Computing Machinery (ACM), 2016. p. 1205-1214.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure

AU - Ting, Kai Ming

AU - Zhu, Ye

AU - Carman, Mark

AU - Zhu, Yue

AU - Zhou, Zhi-Hua

N1 - Conference code: 22nd

PY - 2016/8/13

Y1 - 2016/8/13

N2 - This paper introduces the first generic version of data dependent dissimilarity and shows that it provides a better closest match than distance measures for three existing algorithms in clustering, anomaly detection and multi-label classification. For each algorithm, we show that by simply replacing the distance measure with the data dependent dissimilarity measure, it overcomes a key weakness of the otherwise unchanged algorithm.

AB - This paper introduces the first generic version of data dependent dissimilarity and shows that it provides a better closest match than distance measures for three existing algorithms in clustering, anomaly detection and multi-label classification. For each algorithm, we show that by simply replacing the distance measure with the data dependent dissimilarity measure, it overcomes a key weakness of the otherwise unchanged algorithm.

KW - Data dependent dissimilarity

KW - Distance-based neighbourhood

KW - Distance measure

KW - K nearest neighbours

KW - Probability-mass-based neighbourhood

UR - http://www.scopus.com/inward/record.url?scp=84984979174&partnerID=8YFLogxK

U2 - 10.1145/2939672.2939779

DO - 10.1145/2939672.2939779

M3 - Conference Paper

AN - SCOPUS:84984979174

SP - 1205

EP - 1214

BT - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2016)

A2 - Smola, Alex

A2 - Aggarwal, Charu

A2 - Shen, Dou

A2 - Rastogi, Rajeev

PB - Association for Computing Machinery (ACM)

CY - New York, New York

T2 - ACM International Conference on Knowledge Discovery and Data Mining 2016

Y2 - 13 August 2016 through 17 August 2016

ER -

Ting KM, Zhu Y, Carman M, Zhu Y, Zhou ZH. Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure. In Smola A, Aggarwal C, Shen D, Rastogi R, editors, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2016): August 13-17, 2016, San Francisco, CA, USA. New York, New York: Association for Computing Machinery (ACM). 2016. p. 1205-1214 doi: 10.1145/2939672.2939779

Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure

Abstract

Conference

Keywords

Access to Document

Other files and links

Cite this