Nearest-neighbour-induced isolation similarity and its impact on density-based clustering

Xiaoyu Qin, Kai Ming Ting, Ye Zhu, Vincent CS Lee

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

32 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationProceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence
EditorsPascal Van Hentenryck, Zhi-Hua Zhou
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages8
ISBN (Electronic)9781577358091
Publication statusPublished - 2019
EventAAAI Conference on Artificial Intelligence 2019 - Honolulu, United States of America
Duration: 27 Jan 20191 Feb 2019
Conference number: 33rd

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
PublisherAAAI Press
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468


ConferenceAAAI Conference on Artificial Intelligence 2019
Abbreviated titleAAAI 2019
Country/TerritoryUnited States of America
Internet address

Cite this