HDBSCAN#
Hierarchical Density-Based Spatial Clustering of Applications with Noise (HDBSCAN) is a clustering algorithm proposed in [Campello2013]. It extends DBSCAN by converting it into a hierarchical clustering algorithm, then extracting a flat clustering based on the stability of clusters. Unlike DBSCAN, HDBSCAN does not require the user to choose an epsilon parameter and can find clusters of varying densities.
Operation |
Computational methods |
Programming Interface |
||
Bf, kd tree, ball tree |
||||
Mathematical formulation#
Computation#
Given the set \(X = \{x_1 = (x_{11}, \ldots, x_{1p}), \ldots, x_n = (x_{n1}, \ldots, x_{np})\}\)
of \(n\) \(p\)-dimensional feature vectors, a metric for pairwise distance computation,
and positive integers min_cluster_size and min_samples, the problem is to compute cluster
assignments for each observation.
Supported distance metrics#
The pairwise distance used for core-distance and mutual-reachability computation
is selected via the metric parameter. HDBSCAN reuses the
Minkowski distances family with configurable
degree \(p > 0\): degree = 1 yields the Manhattan (\(L_1\))
distance, degree = 2 yields the Euclidean (\(L_2\), default) distance,
and the limit \(p \to \infty\) corresponds to the
Chebyshev distance (\(L_\infty\)); the
Chebyshev distance is also exposed as its own metric value so callers do
not have to pass a very large degree. In addition, HDBSCAN supports the
Cosine distance for angular data.
The kd_tree and ball_tree methods support the Minkowski (Manhattan,
Euclidean, general \(L_p\)) and Chebyshev distances – tree pruning relies
on the triangle inequality of an \(L_p\) metric. The Cosine distance is
only supported with the brute_force method; requesting Cosine with
kd_tree or ball_tree raises invalid_argument.
HDBSCAN consists of the following steps:
(1) Core distance computation:
For each point \(x_i\), the core distance is the distance to its
\(k\)-th nearest neighbor, where \(k\) = min_samples:
(2) Mutual Reachability Distance (MRD): The mutual reachability distance between any two points \(x_i\) and \(x_j\) is defined as:
This metric upweights sparse regions, making the algorithm robust to varying densities.
(3) Minimum Spanning Tree (MST): Construct the minimum spanning tree of the complete graph where each observation is a vertex and edge weights are mutual reachability distances.
(4) Condensed cluster tree:
Convert the MST into a dendrogram (hierarchical clustering), then condense it by
removing splits where one of the child clusters has fewer than min_cluster_size
points. Points that fall out of clusters during condensation are potential noise points.
(5) Cluster extraction (Excess of Mass): Using the Excess of Mass (EOM) method [Campello2013], compute the stability of each cluster in the condensed tree, then select the set of clusters that maximizes total stability. Selected clusters provide the flat clustering output.
Each cluster gets a unique identifier, an integer from \(0\) to \(\text{cluster\_count} - 1\). Observations not belonging to any cluster are assigned \(-1\) (noise).
Computation method: brute_force#
The brute-force method computes the full \(n \times n\) pairwise distance matrix using the selected metric, then uses this matrix for core distance computation and MST construction via Boruvka’s algorithm. Euclidean and Cosine distances are GEMM-accelerated; other metrics use element-wise computation.
Core distances: For each row of the distance matrix, find the \(k\)-th nearest distance using partial sort. Parallelized across rows.
MST: Boruvka’s algorithm with \(O(n^2 \log n)\) worst-case complexity, using precomputed MRD matrix. The per-round nearest-neighbor search is parallelized across all points.
Complexity: \(O(n^2 p)\) for distances + \(O(n^2 \log n)\) for MST.
Memory: \(O(n^2)\) for the distance matrix.
Computation method: kd_tree#
The k-d tree method avoids the \(O(n^2)\) distance matrix by building a k-d tree data structure over the input data and using it for both core distance computation and MST construction via Boruvka’s algorithm. Supports Euclidean, Manhattan, Minkowski, and Chebyshev metrics (Cosine is not supported).
Core distances: For each point, perform a k-NN query on the k-d tree. Complexity: \(O(n \cdot k \cdot \log n)\).
MST: Boruvka’s algorithm with k-d tree-accelerated nearest-different-component queries, using three-level pruning (component, bounding-box MRD lower bound, near/far child ordering). Complexity: \(O(n \log^2 n)\).
Memory: \(O(n \cdot p)\) for k-d tree nodes and bounding boxes.
The k-d tree method is significantly faster for moderate-sized datasets, especially in low-to-moderate dimensions (\(p \leq 20\)).
Computation method: ball_tree#
The ball tree method is similar to the k-d tree method but uses hypersphere (ball) bounding volumes instead of axis-aligned bounding boxes. This provides better pruning in higher-dimensional spaces where k-d tree splitting planes become ineffective.
Core distances: For each point, perform a k-NN query on the ball tree. Complexity: \(O(n \cdot k \cdot \log n)\).
MST: Boruvka’s algorithm with ball-tree-accelerated nearest-different-component queries, using hypersphere distance bounds for pruning. Complexity: \(O(n \log^2 n)\).
Memory: \(O(n \cdot p)\) for ball tree nodes, centers, and radii.
The ball tree method is preferred over k-d tree when the number of features exceeds approximately 20, as it maintains effective pruning regardless of dimensionality.
Programming Interface#
Refer to API Reference: HDBSCAN.
Examples#
Batch Processing: