Overcoming key weaknesses of distance-based neighbourhood methods using a data dependent dissimilarity measure
- Authors: Ting, Kaiming , Zhu, Ye , Carman, Mark , Zhu, Yue , Zhi-Hua, Zhou
- Date: 2016
- Type: Text , Conference paper
- Relation: 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco; August 13th-17th, 2016 p. 1205-1214
- Full Text: false
- Reviewed:
- Description: 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.
Nearest-neighbour-induced isolation similarity and its impact on density-based clustering
- Authors: Qin, Xiaoyu , Ting, Kai , Zhu, Ye , Lee, Vincent
- Date: 2019
- Type: Text , Conference paper
- Relation: 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Annual Conference on Innovative Applications of Artificial Intelligence, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, 27 January to 1 February 2019. p. 4755-4762
- Full Text:
- Reviewed:
- Description: A recent proposal of data dependent similarity called Isolation Kernel/Similarity has enabled SVM to produce better classification accuracy. We identify shortcomings of using a tree method to implement Isolation Similarity; and propose a nearest neighbour method instead. We formally prove the characteristic of Isolation Similarity with the use of the proposed method. The impact of Isolation Similarity on density-based clustering is studied here. We show for the first time that the clustering performance of the classic density-based clustering algorithm DBSCAN can be significantly uplifted to surpass that of the recent density-peak clustering algorithm DP. This is achieved by simply replacing the distance measure with the proposed nearest-neighbour-induced Isolation Similarity in DBSCAN, leaving the rest of the procedure unchanged. A new type of clusters called mass-connected clusters is formally defined. We show that DBSCAN, which detects density-connected clusters, becomes one which detects mass-connected clusters, when the distance measure is replaced with the proposed similarity. We also provide the condition under which mass-connected clusters can be detected, while density-connected clusters cannot. © 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org).