Source-linked AI summary
Accelerated Hierarchical Density Clustering
Leland McInnes, John Healy
TL;DR
Traditional clustering presents difficult parameter choices, noise handling, and distributional assumptions, while exploratory analysis needs minimal assumptions and informative failure modes. The paper develops an accelerated algorithm for HDBSCAN* and reports improved asymptotic performance, comparable to DBSCAN. It concludes that HDBSCAN* combines computational scalability with variable-density clustering and intuitive parameters.
Problem
HDBSCAN* has O(N^2) runtime because core-distance computation, minimum spanning tree construction, and tree condensing are quadratic, motivating sub-quadratic acceleration.
Method
The paper accelerates HDBSCAN* by improving its core-distance, minimum spanning tree, and tree-condensing steps, while also presenting statistical, computational, and topological descriptions.
Results
The new algorithm provides comparable asymptotic performance to DBSCAN and significant average-case asymptotic improvements over reference HDBSCAN*.
Takeaways & Limitations
HDBSCAN* supports variable-density clusters with intuitive parameters and, according to the paper, should be the default choice for clustering.
Takeaways & Limitations
The accelerated algorithm trades a small loss in minimum spanning tree accuracy for speed, with the trade-off particularly relevant in higher-dimensional data.
Abstract
from arXiv · showhide
We present an accelerated algorithm for hierarchical density based clustering. Our new algorithm improves upon HDBSCAN*, which itself provided a significant qualitative improvement over the popular DBSCAN algorithm. The accelerated HDBSCAN* algorithm provides comparable performance to DBSCAN, while supporting variable density clusters, and eliminating the need for the difficult to tune distance scale parameter. This makes accelerated HDBSCAN* the default choice for density based clustering. Library available at: https://github.com/scikit-learn-contrib/hdbscan
1 Introduction
The introduction motivates density-based clustering for exploratory analysis because traditional methods require difficult parameter choices, tolerate noise poorly, or assume cluster distributions. It presents HDBSCAN* and an accelerated algorithm intended to improve computational performance while retaining support for variable-density clustering.
- Motivation: Exploratory clustering seeks interesting patterns with minimal parameter selection, few prior assumptions, and informative failure modes.The target use case includes data that may be poorly clustered or contain no clusters.
- Limitations of traditional clustering: Traditional clustering methods commonly face difficult parameter selection, weak noise robustness, and assumptions about cluster distributions.Choosing the number of clusters is often difficult and methods such as elbow and silhouette analysis can be subjective.
- Density-based clustering: Density-based methods require fewer distributional assumptions and can leave points unclustered as noise, supporting exploratory analysis.DBSCAN is also described as efficient and robust to noise, though it has parameter-selection and variable-density difficulties.
- HDBSCAN*: HDBSCAN* addresses variable-density and parameter-selection difficulties using a small set of intuitive, fairly robust parameters.Compared with K-Means, it avoids requiring the number of clusters and does not force noise into clusters.
- Contributions: The paper contributes a topological description of HDBSCAN* and a new algorithm that improves average-case asymptotic performance.The paper also evaluates the accelerated method against reference HDBSCAN* and DBSCAN.
2 HDBSCAN* Explained Three Ways
HDBSCAN* is presented through statistical, computational, and topological perspectives: it builds and simplifies density-induced cluster structures, selects persistent non-overlapping clusters, and supports broader generalizations.
- 2.1 Statistically Motivated HDBSCAN*: The statistical view models clusters as connected components of nested density level sets, forming an infinite cluster tree.As the density level λ varies, the level sets nest and define the tree structure.
- 2.1 Statistically Motivated HDBSCAN*: Robust Single Linkage constructs clusters as connected components of graphs whose vertices satisfy a density-radius condition and whose edges satisfy a scaled distance condition.The construction assumes samples from an unknown density on a metric space and uses inputs k and α.
- 2.1 Statistically Motivated HDBSCAN*: Tree simplification introduces minimum cluster size m, pruning branches with fewer than m points while recording the ε value at which their points leave.The resulting tree has fewer branches but retains point-wise information across the ε values where each branch exists.
- 2.1 Statistically Motivated HDBSCAN*: Relative excess of mass measures a cluster’s persistence after excluding the mass of descendant clusters, motivating selection of persistent clusters across distance scales.For variable-density clusters, the cut level varies through the tree, so a fixed ε cut is insufficient.
- 2.2 Computationally Motivated HDBSCAN*: The computational view interprets HDBSCAN* as searching over all ε values of DBSCAN* and selecting clusters that persist across many distance scales.This removes the need to select ε and addresses variable-density clustering, while chosen clusters are constrained not to overlap.
- 2.3 Topologically Motivated HDBSCAN*: The topological view uses sheaves to capture persistence information, providing a complete description of HDBSCAN* and enabling structures beyond ordinary cluster trees.The paper notes that multidimensional persistent homology could support persistence across ε and k simultaneously.
3 Accelerating HDBSCAN*
The paper accelerates HDBSCAN* by replacing quadratic pairwise computations with space-tree methods for core distances and minimum spanning trees. The resulting algorithm has sub-quadratic performance and can approach O(N log N) on many data sets, while trading a small amount of MST accuracy for speed.
- HDBSCAN* has O(N^2) run-time because core-distance, minimum spanning tree, and related computations contain quadratic steps.The paper targets sub-quadratic performance, with O(N log N) strongly preferred.
- Space-tree algorithms accelerate pairwise distance problems by bounding distances between nodes without computing every point-to-point distance.The bounds can be computed during tree construction, such as from the minimum distance between kd-tree regions.
- Core-distance computation is recast as a kth-nearest-neighbor query and can use kd-trees, ball-trees, or cover trees for improved performance.The exact complexity depends on the data structure and data distribution; cover-tree methods can provide O(c^16N) behavior under their expansion-constant parameterization.
- A dual-tree Borůvka procedure computes the mutual-reachability minimum spanning tree while pruning node pairs, avoiding construction of all pairwise distances.The resulting MST computation is asymptotically sub-quadratic and may approach O(N log N) on many data sets.
- The accelerated procedure may produce a close approximation to the minimum spanning tree, exchanging a small accuracy loss for substantially faster execution.The paper reports that tree condensation and flat cluster extraction smooth out minor MST differences, especially for higher-dimensional data using kd-trees or ball-trees.
- The overall algorithm is bounded by core-distance and MST stages, both of which have sub-quadratic performance and can approach O(N log N) for many data sets.The paper presents this as a significant improvement in HDBSCAN* scaling potential.
4 Performance Comparisons
The accelerated HDBSCAN* implementation is evaluated through scaling comparisons with the Java reference implementation, scikit-learn clustering algorithms, and DBSCAN. It improves substantially over reference HDBSCAN* and achieves performance comparable to DBSCAN while retaining density-based clustering advantages.
- Evaluation setup: The evaluation focuses on runtime scaling with data-set size rather than clustering quality, using benchmarks performed on a MacBook Pro and published notebooks.The study examines scaling trends and encourages verification and extension of the benchmarks.
- Comparisons with HDBSCAN* reference implementation: The accelerated Python implementation substantially outperforms reference HDBSCAN* in both absolute and asymptotic runtime.For 200,000-point data sets in both 2 and 50 dimensions, it achieves roughly two orders of magnitude better absolute runtime and shows sub O(N^2) performance.
- Comparisons among clustering algorithms: Across scikit-learn clustering implementations, DBSCAN, K-Means, and HDBSCAN* form the best-performing group in the raw scaling comparison.Affinity Propagation, Spectral Clustering, and Mean Shift perform poorly beyond a few thousand points, while Ward, Complete Linkage, and Birch scale poorly at larger sizes.
- Comparisons among clustering algorithms: On log-log plots, K-Means has approximately O(N) performance, while DBSCAN and HDBSCAN* show similar asymptotic behavior and are closest to K-Means.Mean Shift has poorer overall performance despite similar asymptotic behavior to DBSCAN and HDBSCAN*.
- Comparisons with DBSCAN: Figure 7 shows comparable asymptotic and absolute performance between accelerated HDBSCAN* and DBSCAN.The comparison uses log-log runtime plots across data dimensions, cluster counts, and random data sets.
- Comparisons with DBSCAN: Unlike DBSCAN, accelerated HDBSCAN* addresses parameter selection and variable-density clustering without sacrificing performance.A single HDBSCAN* run can also extract the DBSCAN clustering for any given ε.
5 Future work
The paper identifies several directions for extending accelerated HDBSCAN*, including approximate neighbor search, cover-tree support, and parallelization. Its main stated weakness is that the current algorithm is inherently serial, limiting use on large distributed data sets.
- Future work: Approximate nearest-neighbor methods could improve performance with a small trade-off in result accuracy.The unexplored options include spill trees, bounding adjustments, and RP-trees for core-distance computation and March’s algorithm.
- Future work: The Python implementation lacks cover-tree support, limiting scaling benefits for high ambient dimension and arbitrary distance metrics.A high-performance cover-tree implementation could address this gap.
- Future work: The algorithm is inherently serial, creating an obstacle for use on large distributed data sets.The authors propose partitioning space and building minimum spanning trees in parallel as a possible solution.
- Future work: The topological formulation opens a future path toward Persistent Density Clustering that could eliminate parameter k.That approach would not provide a condensed tree interpretation.
6 Conclusions
The paper concludes that accelerated HDBSCAN* combines HDBSCAN*’s qualitative advantages with computational scalability comparable to DBSCAN. It therefore supports variable-density clustering with more intuitive parameters while retaining comparable performance to DBSCAN.
- Accelerated HDBSCAN* provides computational performance comparable to DBSCAN while retaining HDBSCAN*’s clustering capabilities.The conclusion links the acceleration improvements to DBSCAN-comparable scalability.
- HDBSCAN* has more intuitive parameters and can identify variable-density clusters, unlike the limitations associated with DBSCAN.The paper frames these properties as qualitative advantages over DBSCAN.
- The authors conclude that accelerated HDBSCAN* should be the default choice for clustering.