Efficient Computation of Multiple Density-Based Clustering Hierarchies

Antônio Cavalcante Araújo Neto, Jörg Sander, Ricardo J. G. B. Campello, Mario A. Nascimento

Abstract

HDBSCAN is a powerful density-based clustering algorithm, but its effectiveness depends heavily on the smoothing parameter mpts (minimum points). Tuning this parameter traditionally requires re-running the computationally intensive algorithm for every candidate value. This paper introduces a novel method to compute a wide range of HDBSCAN hierarchies simultaneously. By proving that a single, pruned Relative Neighborhood Graph (RNG) contains the structural information for all hierarchies up to a maximum parameter value, the authors achieve significant speedups, computing over a hundred variations in roughly the time required for two standard runs.

Introduction

Density-based clustering algorithms like HDBSCAN are favored for their ability to identify clusters of arbitrary shapes while effectively filtering noise. HDBSCAN specifically constructs a hierarchy of clusters based on the mpts parameter. However, selecting an optimal mpts is often a process of trial and error: high values highlight macro-structures, while lower values reveal fine-grained sub-clusters.

The impact of varying the `mpts` parameter on clustering results for two different datasets (A and B).

As shown in the figure above, the choice of mpts drastically alters the resulting clusters. In dataset A, increasing mpts from 5 to 25 merges distinct clusters into a single group. In the noisier dataset B, a low mpts results in fragmented, over-clustered data, whereas a higher mpts successfully identifies the underlying circular structure.

The Computational Bottleneck

The primary challenge in tuning HDBSCAN* is its reliance on computing a Minimum Spanning Tree (MST) over a complete graph of the dataset. Because the edge weights in this graph—defined by "mutual reachability distance"—change with every new mpts value, the entire MST must be recalculated from scratch. For large datasets, this $O(n^2)$ overhead makes extensive parameter exploration practically impossible.

Methodology: The RNG* Approach

The authors propose a method to avoid rebuilding the complete graph by identifying a much smaller subgraph guaranteed to contain the MST for all desired mpts values.

1. Relative Neighborhood Graphs (RNG)

The authors prove that the RNG—a proximity graph where points are connected only if no other point is closer to both—is the smallest graph guaranteed to contain the Euclidean MST. Crucially, they extend this to HDBSCAN*'s mutual reachability distance, proving a "nesting" property: the RNG constructed for a maximum parameter $k_{max}$ ($RNG^{k_{max}}$) inherently contains the MSTs for all smaller values $i < k_{max}$.

2. Efficient Graph Construction

To make this approach viable, the authors developed a multi-step pruning strategy:

  • k-NN Initialization: A single $k_{max}$-Nearest Neighbor query is performed for all points.
  • WSPD Filtering: Well-Separated Pair Decomposition is used to build a candidate graph.
  • RNG Pruning: The pre-computed k-NN distances are used to prune invalid edges in near-constant time, resulting in a sparse graph called RNG.

By running the standard HDBSCAN MST extraction on this tiny RNG graph, multiple hierarchies can be generated with minimal additional cost.

Experimental Results

The proposed method was evaluated on synthetic datasets ranging from 16,000 to 1 million points and up to 128 dimensions.

  • Efficiency: The RNG* method can compute 128 different hierarchies for the cost of approximately two standard runs.
  • Scalability: On a dataset of 1 million points, the RNG* method completed successfully while the baseline approach became computationally unfeasible.
  • Dimensionality: While the geometric bounds of WSPD weaken in high dimensions (e.g., 128D), the k-NN filtering remains highly effective at maintaining a manageable graph size.

Conclusion

This research demonstrates that the Relative Neighborhood Graph is the theoretical limit for optimizing MST-based clustering hierarchies. By leveraging the nested properties of these graphs, the authors have transformed a computationally "crippling" parameter search into an efficient, one-time operation. Future work will focus on automated tools to help users navigate and interpret the resulting multi-density cluster landscapes.

Summary updated

BibTeX
@inproceedings{neto2017efficient,
  author = {Antônio Cavalcante Araújo Neto and Jörg Sander and Ricardo J. G. B. Campello and Mario A. Nascimento},
  title = {{Efficient Computation of Multiple Density-Based Clustering Hierarchies}},
  booktitle = {ICDM},
  year = {2017},
  doi = {10.1109/icdm.2017.127},
}
Figure