Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

HDBSCAN: Mutual Reachability, Condensed Trees and Stable Clusters

5 minute read

Published:

TL;DR: HDBSCAN constructs a density hierarchy, removes branches that do not maintain enough members, and selects persistent clusters. It can handle varying density more flexibly than a single DBSCAN radius, but distance, minimum support, minimum cluster size and the selection rule still define the result.

A hierarchy over density scales

Suppose a dataset contains a tight group and a broader group separated by a sparse region. Instead of asking for one global radius, follow how groups connect and split as the density threshold varies. The goal is to identify branches that remain coherent over a meaningful range of scales.

HDBSCAN combines this idea with a minimum cluster-size constraint and a stability-based selection procedure. It is helpful to study those stages separately: geometry creates a hierarchy, condensation removes small branches, and selection produces the final groups. A label vector conceals these intermediate decisions.

Mutual reachability changes the geometry

Let \(c_m(x)\) be a core distance based on a chosen neighbour-count convention. Define

\[ d_{\mathrm{mr}}(a,b)=\max\{c_m(a),c_m(b),d(a,b)\}. \]\n

Unlike OPTICS reachability, this expression is symmetric. A pair in a sparse region is not treated as strongly connected merely because the two observations happen to be close: their local support requirements also matter.

For example, if the pair distance is 0.1 but the core distances are 0.2 and 0.8, mutual reachability is 0.8. For another pair with distance 0.3 and core distances 0.1 and 0.2, it is 0.3. The second pair has a larger raw separation but stronger support at a smaller density scale.

From a spanning tree to a hierarchy

A minimum spanning tree of the mutual-reachability graph preserves the connectivity information needed for single-linkage thresholding. Removing edges above a threshold reveals components. Varying the threshold constructs a hierarchy without having to retain every possible graph edge in the final representation.

The transformation raises the effective distance around sparsely supported observations, reducing the influence of thin connections. It does not guarantee that every unwanted bridge disappears. If sampling makes a bridge genuinely dense at the chosen scale, the graph can still connect populations the application considers distinct.

Efficient implementations avoid explicitly materialising a complete graph where possible. Runtime depends on the metric, dimension, neighbour search and approximation choices. A sparse output tree does not mean computing it was free.

Condensation introduces minimum cluster size

A raw hierarchy contains tiny branches and single observations. Condensation tracks whether a branch retains at least the required minimum number of members as the density threshold increases. Small branches are treated as points falling out of a larger cluster rather than as equally important candidate clusters.

Minimum cluster size and minimum samples have different roles. The former constrains which groups can persist as candidate clusters; the latter influences core distances and density conservatism. Some interfaces link their defaults. Set both explicitly when studying their separate effects.

A rare but real population smaller than the minimum cluster size cannot survive as a selected cluster under that constraint. The algorithm is following the specified model, not proving the population is nonexistent.

Stability integrates persistence

Write density scale as \(\lambda=1/\varepsilon\). A useful description of a candidate cluster’s stability is

\[ S(C)=\sum_{x\in C}\bigl(\lambda_x-\lambda_{\mathrm{birth}}(C)\bigr), \]\n

where \(\lambda_x\) is the scale at which x leaves that branch, subject to the hierarchy’s bookkeeping. Stability accounts for both persistence and retained membership.

If a branch is born at scale 2 and three members leave at 5, 6 and 7, its illustrative stability contribution is \(3+4+5=12\). A long-lived branch with many members can therefore outweigh several short-lived fragments. This is a hierarchy-selection criterion, not an externally validated scientific significance score.

Excess-of-mass selection compares eligible parent and descendant choices to select a nonoverlapping collection. Leaf selection instead favours finer terminal groups. Reporting the selection method is essential when two HDBSCAN results have different granularity.

Noise and membership strength

Some observations remain noise because no selected branch supports their assignment adequately. Membership strengths summarise how strongly assigned points belong to their selected cluster under the fitted density structure. They are not generally calibrated probabilities of a real-world class label.

An observation can have low strength because it lies near a density boundary, not because it is incorrect or malicious. A high-strength observation can belong to a cluster caused by duplicated measurements. Inspect the data-generating process before attaching semantic labels to density outcomes.

A practical comparison protocol

Use a fixed representation and compare a range of minimum support and minimum-size values. Record cluster count, noise fraction, size distribution, persistence and example observations. Compare selected branches with nearby parameter settings and resampled datasets, using a clearly defined correspondence rule.

Different packages can use different conventions for whether the point itself contributes to minimum samples. Verify conventions before expecting identical results from equal numeric arguments. Also separate approximate assignment of new points from refitting: adding observations can change the density hierarchy itself.

HDBSCAN is valuable when a stable subset of observations is preferable to forcing every point into a group. Its output still needs external and internal evaluation, especially when an attractive low-dimensional plot supplied the input geometry.

Key Insight: There are three decisions to audit: mutual-reachability geometry, minimum-size condensation and cluster selection. A single parameter sweep over the final label count cannot explain all three.
Common pitfall: Membership strength and persistence are properties of the fitted density hierarchy. Neither is a calibrated probability that a cluster corresponds to a true semantic category.

Recap

  • Distinguish symmetric mutual reachability from OPTICS reachability.
  • Set minimum samples and minimum cluster size deliberately.
  • Understand stability and parent-versus-descendant selection.
  • Inspect noise, sampling, package conventions and assignment policy.

References

  1. McInnes, Healy and Astels. hdbscan: Hierarchical density based clustering. JOSS, 2017.
  2. HDBSCAN authors. How HDBSCAN Works.
  3. scikit-learn. Clustering user guide.

You May Also Enjoy

The Standard Library Modules Worth Knowing Before You pip install

8 minute read

Published:

Python ships with a counter, a queue, a memoiser, a CLI parser, a test framework’s smaller cousin, and a JSON-safe date library already installed, most of what people reach for a package to solve is one import away.

Files and Context Managers: Why with Is Not Optional

9 minute read

Published:

A file object that falls out of scope without with does get closed eventually, but ‘eventually’ means whenever the garbage collector gets around to it, which is not a promise any program handling more than a handful of files can live with.

Errors and Exceptions: EAFP, the Hierarchy, and Reading a Traceback

9 minute read

Published:

Exceptions in Python are not exceptional. They are a normal control-flow mechanism that the language leans on so heavily that the idiomatic style is to try the operation and handle the failure, rather than check first, which is faster, shorter, and free of race conditions.