Connecting the Dots: Density-Connectivity Distance unifies DBSCAN, k-Center and Spectral Clustering

Anna Beer, Andrew Draganov, Ellen Hohma, Philipp Jahn, Christian M.M. Frey, Ira Assent

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

6 Citationer (Scopus)

Abstract

Despite the popularity of density-based clustering, its procedural definition makes it difficult to analyze compared to clustering methods that minimize a loss function. In this paper, we reformulate DBSCAN through a clean objective function by introducing the density-connectivity distance (dc-dist), which captures the essence of density-based clusters by endowing the minimax distance with the concept of density. This novel ultrametric allows us to show that DBSCAN, k-center, and spectral clustering are equivalent in the space given by the dc-dist, despite these algorithms being perceived as fundamentally different in their respective literatures. We also verify that finding the pairwise dc-dists gives DBSCAN clusterings across all epsilon-values, simplifying the problem of parameterizing density-based clustering. We conclude by thoroughly analyzing density-connectivity and its properties - a task that has been elusive thus far in the literature due to the lack of formal tools. Our code recreates every experiment below: https://github.com/Andrew-Draganov/dc-dist

OriginalsprogEngelsk
TitelKDD 2023 : Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Antal sider13
UdgivelsesstedNew York
ForlagAssociation for Computing Machinery
Publikationsdatoaug. 2023
Sider80-92
ISBN (Elektronisk)9798400701030
DOI
StatusUdgivet - aug. 2023
Begivenhed29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023 - Long Beach, USA
Varighed: 6 aug. 202310 aug. 2023

Konference

Konference29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023
Land/OmrådeUSA
ByLong Beach
Periode06/08/202310/08/2023
NavnProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Fingeraftryk

Dyk ned i forskningsemnerne om 'Connecting the Dots: Density-Connectivity Distance unifies DBSCAN, k-Center and Spectral Clustering'. Sammen danner de et unikt fingeraftryk.

Citationsformater