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

Abstract

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 densitybased 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)
Pages4755-4762
Number of pages8
ISBN (Electronic)9781577358091
DOIs
Publication statusPublished - 2019
EventAAAI conference on Artificial Intelligence 2019 - Honolulu, United States of America
Duration: 27 Jan 20191 Feb 2019
Conference number: 33rd
https://aaai.org/Conferences/AAAI-19/

Publication series

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

Conference

ConferenceAAAI conference on Artificial Intelligence 2019
Abbreviated titleAAAI 2019
CountryUnited States of America
CityHonolulu
Period27/01/191/02/19
Internet address

Cite this

Qin, X., Ting, K. M., Zhu, Y., & CS Lee, V. (2019). Nearest-neighbour-induced Isolation Similarity and its impact on density-based clustering. In P. Van Hentenryck, & Z-H. Zhou (Eds.), Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence (pp. 4755-4762). [7564] (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 33, No. 1). Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). https://doi.org/10.1609/aaai.v33i01.33014755
Qin, Xiaoyu ; Ting, Kai Ming ; Zhu, Ye ; CS Lee, Vincent . / Nearest-neighbour-induced Isolation Similarity and its impact on density-based clustering. Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence. editor / Pascal Van Hentenryck ; Zhi-Hua Zhou. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2019. pp. 4755-4762 (Proceedings of the AAAI Conference on Artificial Intelligence; 1).
@inproceedings{e1f19eb6db8a4bdcb9029d961696b7ff,
title = "Nearest-neighbour-induced Isolation Similarity and its impact on density-based clustering",
abstract = "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 densitybased 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.",
author = "Xiaoyu Qin and Ting, {Kai Ming} and Ye Zhu and {CS Lee}, Vincent",
year = "2019",
doi = "10.1609/aaai.v33i01.33014755",
language = "English",
series = "Proceedings of the AAAI Conference on Artificial Intelligence",
publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",
number = "1",
pages = "4755--4762",
editor = "{Van Hentenryck}, {Pascal } and Zhou, {Zhi-Hua }",
booktitle = "Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence",
address = "United States of America",

}

Qin, X, Ting, KM, Zhu, Y & CS Lee, V 2019, Nearest-neighbour-induced Isolation Similarity and its impact on density-based clustering. in P Van Hentenryck & Z-H Zhou (eds), Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence., 7564, Proceedings of the AAAI Conference on Artificial Intelligence, no. 1, vol. 33, Association for the Advancement of Artificial Intelligence (AAAI), Palo Alto CA USA, pp. 4755-4762, AAAI conference on Artificial Intelligence 2019, Honolulu, United States of America, 27/01/19. https://doi.org/10.1609/aaai.v33i01.33014755

Nearest-neighbour-induced Isolation Similarity and its impact on density-based clustering. / Qin, Xiaoyu ; Ting, Kai Ming; Zhu, Ye; CS Lee, Vincent .

Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence. ed. / Pascal Van Hentenryck; Zhi-Hua Zhou. Palo Alto CA USA : Association for the Advancement of Artificial Intelligence (AAAI), 2019. p. 4755-4762 7564 (Proceedings of the AAAI Conference on Artificial Intelligence; Vol. 33, No. 1).

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

TY - GEN

T1 - Nearest-neighbour-induced Isolation Similarity and its impact on density-based clustering

AU - Qin, Xiaoyu

AU - Ting, Kai Ming

AU - Zhu, Ye

AU - CS Lee, Vincent

PY - 2019

Y1 - 2019

N2 - 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 densitybased 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.

AB - 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 densitybased 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.

U2 - 10.1609/aaai.v33i01.33014755

DO - 10.1609/aaai.v33i01.33014755

M3 - Conference Paper

T3 - Proceedings of the AAAI Conference on Artificial Intelligence

SP - 4755

EP - 4762

BT - Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence

A2 - Van Hentenryck, Pascal

A2 - Zhou, Zhi-Hua

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Palo Alto CA USA

ER -

Qin X, Ting KM, Zhu Y, CS Lee V. Nearest-neighbour-induced Isolation Similarity and its impact on density-based clustering. In Van Hentenryck P, Zhou Z-H, editors, Proceedings of AAAI19-Thirty-Third AAAI conference on Artificial Intelligence. Palo Alto CA USA: Association for the Advancement of Artificial Intelligence (AAAI). 2019. p. 4755-4762. 7564. (Proceedings of the AAAI Conference on Artificial Intelligence; 1). https://doi.org/10.1609/aaai.v33i01.33014755