@inproceedings{5315746233f94598b9b9bf5fe02aab44,
title = "Connecting the Dots: Density-Connectivity Distance unifies DBSCAN, k-Center and Spectral Clustering",
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",
keywords = "clustering, density, minimax path, ultrametric space",
author = "Anna Beer and Andrew Draganov and Ellen Hohma and Philipp Jahn and Frey, {Christian M.M.} and Ira Assent",
note = "Publisher Copyright: {\textcopyright} 2023 Owner/Author.; 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023 ; Conference date: 06-08-2023 Through 10-08-2023",
year = "2023",
month = aug,
doi = "10.1145/3580305.3599283",
language = "English",
series = "Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining",
pages = "80--92",
booktitle = "KDD 2023",
publisher = "Association for Computing Machinery",
address = "United States",
}