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

Beer, Anna ; Draganov, Andrew ; Hohma, Ellen ; Jahn, Philipp ; Frey, Christian M.M. und Assent, Ira (2023): Connecting the Dots -- Density-Connectivity Distance unifies DBSCAN, k-Center and Spectral Clustering. 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), Long Beach, CA, 06. - 10. August 2023. Singh, Ambuj (Hrsg.): In: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, New York: Association for Computing Machinery. S. 80-92

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

• Dokumententyp: Konferenzbeitrag (Paper)
• Fakultät: Mathematik, Informatik und Statistik > Informatik
• Themengebiete: 000 Informatik, Informationswissenschaft, allgemeine Werke > 004 Informatik
• ISBN: 979-8-4007-0103-0
• Ort: New York
• Sprache: Englisch