HDBSCAN

Run DBSCAN over every density level and keep the most stable clusters, so clusters of different densities can coexist.

17 min read2050 wordsadvanced17 viewsupdated 2026-10-07

Definition

HDBSCAN (Hierarchical DBSCAN, Campello, Moulavi & Sander 2013) builds the whole family of DBSCAN clusterings for every radius ε\varepsilon at once — a tree of clusters that split as the density threshold rises — then keeps the clusters that persist longest across density levels. Points that never belong to a persistent cluster are labelled noise.

At a glance

Task
Density-based clustering with noise detection
Input → output
points x1,…,xnx_1,\dots,x_n and a distance → a label per point (−1-1 = noise), a membership strength in [0,1][0,1], and a cluster tree
Learns
a minimum spanning tree on mutual-reachability distance, the condensed cluster tree, and the flat clustering that maximizes total stability
Training
O(n2)O(n^2) time with dense distances; about O(nlog⁡n)O(n\log n) in low dimensions with kd-tree Borůvka MST
Prediction
no native predict: refit, or attach new points to the tree approximately (nearest neighbour in mutual reachability)
Hyperparameters
min_cluster_size (smallest group worth calling a cluster), min_samples (density smoothing, defaults to min_cluster_size), cluster_selection_method, cluster_selection_epsilon
Assumes
clusters are regions denser than their surroundings; a meaningful distance metric; no number of clusters and no single density level

The problem

DBSCAN (see the DBSCAN article) defines a cluster as a region where points have at least min_samples neighbours within radius ε\varepsilon. That one ε\varepsilon is a single density level: everything denser is cluster, everything sparser is noise. Real data rarely has one density. A city map has dense downtown blocks and sparse suburbs; a cell atlas has huge common cell types and tiny rare ones.

Take the 14 points of the worked example below: two tight squares A1 and A2 (spacing about 0.6) separated by a gap of 1.75, a loose pentagon B (spacing about 2) and one stray point. Scan DBSCAN (min_samples = 3) over every ε\varepsilon from 0.3 to 4 and something is always wrong:

ε rangeA1 (0–3)A2 (4–7)B (8–12)Point 13
0.64 – 1.74clusterclusterall noisenoise
1.75 – 2.00merged with A2merged with A1all noisenoise
2.01 – 2.08mergedmerged3–4 of 5 pointsnoise
2.09 – 2.82mergedmergedclusternoise
≥ 2.83mergedmergedmerged with Anoise, then joins at ≥ 3.0
DBSCAN on the worked-example data, min_samples = 3. No single radius finds A1, A2 and B together; each row is a different density level.

A small ε\varepsilon separates the two squares but dissolves B into noise; a large ε\varepsilon rescues B but fuses the squares. OPTICS (see its article) orders the points so you can see all levels in a reachability plot, but you still have to cut it. HDBSCAN makes the cut automatic, and — the crucial part — the cut can be at different levels in different parts of the data.

The idea

Imagine sweeping ε\varepsilon from ∞\infty down to 0. At ε=∞\varepsilon=\infty everything is one cluster. As ε\varepsilon shrinks, sparse points drop out as noise and clusters break into pieces. Write the sweep as a tree: the root is "everything", each split is a cluster breaking in two, each leaf is a cluster that finally evaporates. Every DBSCAN result is one horizontal cut through this tree.

Instead of one horizontal cut, HDBSCAN picks a set of non-overlapping branches of the tree — possibly at different heights — that together last the longest. A cluster that appears early and survives a long range of densities is real structure; a cluster that appears and immediately dissolves is noise in the hierarchy. Two tricks make this cheap and robust: a mutual-reachability distance that smooths away single noisy points, and a condensing step that ignores "splits" which only shed a handful of points.

Vocabulary

Core distance
corek(x)\text{core}_k(x): distance from xx to its kk-th nearest point, counting xx itself (k=k= min_samples). Small in dense regions, large in sparse ones.
Mutual reachability distance
dmr(a,b)=max⁡(corek(a),corek(b),d(a,b))d_\text{mr}(a,b)=\max(\text{core}_k(a),\text{core}_k(b),d(a,b)). Sparse points are pushed away from everything; dense neighbours keep their true distance.
DBSCAN*
DBSCAN without border points: at radius ε\varepsilon, the clusters are the connected groups of core points (points with corek≤ε\text{core}_k\le\varepsilon); everything else is noise. HDBSCAN builds DBSCAN* for every ε\varepsilon.
Minimum spanning tree (MST)
the n−1n-1 edges of smallest total dmrd_\text{mr} that connect all points. Cutting it at ε\varepsilon gives DBSCAN* at ε\varepsilon.
Single-linkage tree
the dendrogram from adding MST edges in increasing order; its merge heights are ε values
λ (lambda)
density level λ=1/ε\lambda=1/\varepsilon. A cluster is born at the λ where it splits off its parent and dies at the λ where it splits again or evaporates.
Falling out
at a split where one side has fewer than min_cluster_size points, those points leave the cluster (they become noise at that level) and the cluster carries on — this is not a real split.
Condensed tree
the single-linkage tree with all fall-outs collapsed: only splits into two pieces of at least min_cluster_size points remain
Stability
S(C)=∑x∈C(λx−λbirth(C))S(C)=\sum_{x\in C}(\lambda_x-\lambda_\text{birth}(C)) — how much density-level "lifetime" the cluster's points accumulate; the area of its bar in the condensed-tree plot
Excess of mass (EOM)
the selection rule: keep a cluster if it is at least as stable as its selected descendants combined, otherwise keep the descendants
Membership strength
λx/λmax(C)\lambda_x/\lambda_\text{max}(C): 1 for points that stay to the end, smaller for points that fall out early; noise gets 0

The math

Step 1 — a density estimate per point. The core distance is the radius of the smallest ball around xx that holds kk points:

corek(x)=d(x,  Nk(x)),f^(x)  ≈  kn Vd corek(x)d\text{core}_k(x)=d\big(x,\;N_k(x)\big),\qquad \hat f(x)\;\approx\;\frac{k}{n\,V_d\,\text{core}_k(x)^{d}}
Nk(x)N_k(x)
the kk-th nearest point to xx in the data, xx itself counted as the first
kk
min_samples
f^(x)\hat f(x)
the kk-nearest-neighbour density estimate at xx
VdV_d
volume of the unit ball in dd dimensions

So "corek(x)≤ε\text{core}_k(x)\le\varepsilon" is the same statement as "f^(x)≥\hat f(x)\ge a threshold": shrinking ε\varepsilon means raising the density level. Larger kk averages over more neighbours — a smoother, more conservative density estimate in which isolated points get large core distances and more of them become noise.

Step 2 — mutual reachability. Define a new distance between points:

dmr(a,b)=max⁡{corek(a),  corek(b),  d(a,b)}d_\text{mr}(a,b)=\max\big\{\text{core}_k(a),\;\text{core}_k(b),\;d(a,b)\big\}
d(a,b)d(a,b)
the original distance (Euclidean here)
dmr(a,b)d_\text{mr}(a,b)
the smallest ε\varepsilon at which aa and bb are both core points and within ε\varepsilon of each other

That legend line is the whole derivation of why this works. In DBSCAN at radius ε\varepsilon, two points are directly linked iff both are core (corek≤ε\text{core}_k\le\varepsilon) and d(a,b)≤εd(a,b)\le\varepsilon — i.e. iff dmr(a,b)≤εd_\text{mr}(a,b)\le\varepsilon. So DBSCAN at ε\varepsilon = connected components of the graph whose edges have dmr≤εd_\text{mr}\le\varepsilon** (points with corek>ε\text{core}_k>\varepsilon have no edges and are noise).

Step 3 — all ε at once with one MST. Two points are connected through edges of weight ≤ε\le\varepsilon in the full graph iff they are connected through such edges in its minimum spanning tree — this is the cut property of MSTs: the MST path between two points minimizes the largest edge on the path. So we compute the MST once (n−1n-1 edges) and read off DBSCAN* for every ε\varepsilon by deleting the edges heavier than ε\varepsilon. Adding the edges from light to heavy gives the single-linkage dendrogram of dmrd_\text{mr}.

Step 4 — condense. Re-label heights by density, λ=1/ε\lambda=1/\varepsilon, and walk down the dendrogram from the root. At each merge (now read as a split, at level λ\lambda) of a cluster CC into pieces LL and RR:

{∣L∣≥m,  ∣R∣≥m:C dies; L,R are born at λ∣L∣<m≤∣R∣:points of L fall out of C at λ;  C continues as R∣L∣<m,  ∣R∣<m:C dies; all its points fall out at λ\begin{cases}|L|\ge m,\;|R|\ge m: & C \text{ dies; } L,R \text{ are born at } \lambda\\ |L|<m\le|R|: & \text{points of } L \text{ fall out of } C \text{ at } \lambda;\; C \text{ continues as } R\\ |L|<m,\;|R|<m: & C \text{ dies; all its points fall out at } \lambda\end{cases}
mm
min_cluster_size

Each point xx gets λx\lambda_x, the level at which it leaves the cluster it is in (by falling out, or because that cluster split or died). The condensed tree typically has far fewer nodes than the dendrogram — in the example, 13 merges condense to 5 clusters.

Step 5 — stability. For a density ff and level λ\lambda, the excess of mass of a cluster is how much probability mass it holds above that level. Integrating the size of the cluster over the levels where it exists gives its stability:

S(C)=∫λbirth(C)λdeath(C)∣C(λ)∣ dλ=∑x∈C(λx−λbirth(C))S(C)=\int_{\lambda_\text{birth}(C)}^{\lambda_\text{death}(C)}\big|C(\lambda)\big|\,d\lambda=\sum_{x\in C}\big(\lambda_x-\lambda_\text{birth}(C)\big)
∣C(λ)∣|C(\lambda)|
number of points still in CC at level λ\lambda
λbirth(C)\lambda_\text{birth}(C)
level at which CC split off its parent
λx\lambda_x
level at which point xx leaves CC

The second form follows by swapping sum and integral: each point contributes 1 to ∣C(λ)∣|C(\lambda)| for every λ\lambda between the birth and its own departure, so it contributes exactly λx−λbirth(C)\lambda_x-\lambda_\text{birth}(C). Geometrically, S(C)S(C) is the area of the cluster's bar in the condensed-tree plot.

Step 6 — select. We want a set of clusters, no one an ancestor of another, with maximum total stability. On a tree this is solved exactly by one bottom-up pass:

S^(C)=max⁡{S(C),  ∑C′∈children(C)S^(C′)}\hat S(C)=\max\Big\{S(C),\;\sum_{C'\in\text{children}(C)}\hat S(C')\Big\}
S^(C)\hat S(C)
best total stability achievable inside the subtree of CC
children(C)\text{children}(C)
the two clusters born when C dies (none for a leaf)

If S(C)S(C) wins, CC is selected and everything below it is discarded; otherwise its children's choices stand. Leaves are always provisionally selected. The root is excluded by default (otherwise a single blob would always win), so data with no structure comes back as all noise.

Each hyperparameter, mathematically

min_samples = k
changes corek\text{core}_k, hence every dmrd_\text{mr}. Larger kk raises core distances most for isolated points, so they join later (lower λ\lambda) and fall out sooner — more noise, smoother tree. k=1k=1 gives core=0\text{core}=0 and plain single linkage.
min_cluster_size = m
decides which splits are real. Pieces smaller than mm only fall out, so raising mm removes small clusters from the condensed tree entirely and can merge siblings into their parent.
cluster_selection_epsilon
clusters born at a distance below this value (λ>1/ϵ\lambda>1/\epsilon) are not split further — their ancestor alive at ε\varepsilon is reported. Prevents micro-clusters in very dense regions.
cluster_selection_method
"eom" maximizes total stability (above); "leaf" simply returns the leaves of the condensed tree — finer, more homogeneous clusters.
alpha
rescales distances to d/αd/\alpha inside dmrd_\text{mr}; rarely needed.

Worked example: 14 points, three densities

Use min_samples k=3k=3 (so the core distance is the distance to the 2nd nearest other point) and min_cluster_size m=3m=3. Points are numbered from 0, as in the code.

PointxyGroup2nd nearest other (distance)core₃
01.01.0A12 (0.707)0.707
11.61.1A10 (0.608)0.608
21.11.7A10 (0.707)0.707
31.71.6A12 (0.608)0.608
43.41.2A26 (0.632)0.632
54.01.0A24 (0.632)0.632
63.61.8A24 (0.632)0.632
74.11.6A25 (0.608)0.608
86.80.6B10 (2.408)2.408
98.81.2B8 (2.088)2.088
107.03.0B12 (2.236)2.236
119.03.2B10 (2.010)2.010
128.05.0B10 (2.236)2.236
134.64.8stray6 (3.162)3.162
The data and each point's core distance (k = 3). The dense squares have core distances near 0.6; B's are about 2.0–2.4; the stray point 13 has 3.162.

Core distances → mutual reachability → MST

  1. 1Core distances (table above). Example: point 8's nearest others are 9 at 2.088 and 10 at 2.408, so core3(8)=2.408\text{core}_3(8)=2.408.
  2. 2Mutual reachability. Inside a square nothing changes much: d(1,3)=0.510d(1,3)=0.510 but both cores are 0.608, so dmr(1,3)=0.608d_\text{mr}(1,3)=0.608. In B the cores dominate: d(8,9)=2.088d(8,9)=2.088, but dmr(8,9)=max⁡(2.408, 2.088, 2.088)=2.408d_\text{mr}(8,9)=\max(2.408,\,2.088,\,2.088)=2.408.
  3. 3MST. Prim's algorithm on dmrd_\text{mr} gives 13 edges (next table). The heavy ones are the bridges: 3–4 at 1.746 (A1 to A2), 5–8 at 2.828 (A to B) and 6–13 at 3.162 (the stray point).
  4. 4Dendrogram. Adding the edges from light to heavy: A1 is complete at ε=0.707\varepsilon=0.707, A2 at 0.632, A1+A2 merge at 1.746, B is complete at 2.408, A meets B at 2.828, and point 13 joins last at 3.162.
Edgedcore(a), core(b)d_mrλ = 1/d_mrEffect
1–30.5100.608, 0.6080.6081.644pair in A1
5–70.6080.632, 0.6080.6321.581pair in A2
4–50.6320.632, 0.6320.6321.581A2 grows
4–60.6320.632, 0.6320.6321.581A2 complete (4 pts)
0–10.6080.707, 0.6080.7071.414A1 grows
0–20.7070.707, 0.7070.7071.414A1 complete (4 pts)
3–41.7460.608, 0.6321.7460.573A1 + A2 → A (8 pts)
9–112.0102.088, 2.0102.0880.479pair in B
11–102.0102.010, 2.2362.2360.447B grows
11–122.0592.010, 2.2362.2360.447B grows (4 pts)
8–92.0882.408, 2.0882.4080.415B complete (5 pts)
5–82.8280.632, 2.4082.8280.354A + B (13 pts)
6–133.1620.632, 3.1623.1620.316stray point joins
The 13 MST edges in the order single linkage adds them, with λ = 1/d_mr. Highlighted: the three edges that create the true splits.

Condense, score, select

  1. 1Root (C0), from λ=0\lambda=0. The top split at λ=0.316\lambda=0.316 separates point 13 (1 point <m<m) from 13 others: point 13 falls out; the root carries on.
  2. 2λ=0.354\lambda=0.354 (edge 5–8): pieces of 8 and 5 points, both ≥3\ge 3 — a true split. C1 = A (points 0–7) and C4 = B (points 8–12) are born at λ=0.354\lambda=0.354.
  3. 3C1 at λ=0.573\lambda=0.573 (edge 3–4): pieces 4 and 4 — a true split. C2 = A1 and C3 = A2 are born at 0.573. C1's 8 points all leave at 0.573, so S(C1)=8×(0.5726−0.3536)=1.752S(\text{C1})=8\times(0.5726-0.3536)=1.752.
  4. 4C2 (A1): the next merges inside it (0.707) cut it into pieces smaller than 3, so all four points leave at λ=1.414\lambda=1.414: S(C2)=4×(1.4142−0.5726)=3.366S(\text{C2})=4\times(1.4142-0.5726)=3.366. Likewise C3 (A2) ends at 1.581: S(C3)=4×(1.5811−0.5726)=4.034S(\text{C3})=4\times(1.5811-0.5726)=4.034.
  5. 5C4 (B): point 8 falls out at λ=0.415\lambda=0.415 (edge 8–9); at 0.447 the rest breaks into pieces under 3 and the cluster dies. S(C4)=(0.4152−0.3536)+4×(0.4472−0.3536)=0.062+0.374=0.436S(\text{C4})=(0.4152-0.3536)+4\times(0.4472-0.3536)=0.062+0.374=0.436.
  6. 6Excess of mass, bottom-up. Leaves C2, C3, C4 are provisionally kept. At C1: S(C1)=1.752<S(C2)+S(C3)=7.40S(\text{C1})=1.752<S(\text{C2})+S(\text{C3})=7.40, so the two squares beat their union. The root is never selected. Result: A1 = {0–3}, A2 = {4–7}, B = {8–12}, point 13 = noise.
ClusterPointsBorn at λPoints leave at λStability SSelected
C0 (root)0–13013 at 0.316; rest at 0.354—never
C1 = A0–70.354all at 0.573 (split)1.752no (1.752 < 7.40)
C2 = A10–30.573all at 1.4143.366yes
C3 = A24–70.573all at 1.5814.034yes
C4 = B8–120.3548 at 0.415; rest at 0.4470.436yes
The condensed tree. C1's stability is far below its children's total, so HDBSCAN keeps A1 and A2 — at a high density level — and B at a low one.

Membership strength is λx/λmax\lambda_x/\lambda_\text{max} within the selected cluster: every point of A1 and A2 leaves at the cluster's last level, so all have strength 1; in B, point 8 left early, 0.415/0.447=0.9280.415/0.447=0.928; point 13 is noise with 0.

Placing a new point q = (5.5, 1.5)

  1. 1Distances from q: point 7 at 1.404, then points 5 and 8 at 1.581. Counting q itself, its core distance is the 2nd nearest data point: core3(q)=1.581\text{core}_3(q)=1.581.
  2. 2Mutual reachability to point 7: max⁡(1.581, 0.608, 1.404)=1.581\max(1.581,\,0.608,\,1.404)=1.581; to point 8 it is max⁡(1.581, 2.408, 1.581)=2.408\max(1.581,\,2.408,\,1.581)=2.408. The nearest in dmrd_\text{mr} is point 7 at 1.581, so q attaches at λq=1/1.581=0.632\lambda_q=1/1.581=0.632.
  3. 3Point 7 is in C3 (A2), which is alive from λ=0.573\lambda=0.573 to 1.581. Since 0.573≤0.6320.573\le 0.632, q lands inside A2, with strength 0.632/1.581=0.400.632/1.581=0.40 — a member, but a weak one. (Raw distance alone would also say "near A2", but if q were halfway to B with λq<0.573\lambda_q<0.573 it would land in C1, which is not selected, and be noise.)
▸ HDBSCAN · density hierarchy → stable clustersstep 1/21
min_cluster_sizemin_samples
012345678910111213single-linkage tree on d_mr (height = ε)0123013245768911101213
n = 14
  1. 1core(x) ← dist to min_samples-th nearest
  2. 2d_mr(a,b) ← max(core a, core b, d(a,b))
  3. 3T ← minimum spanning tree of d_mr
  4. 4add T's edges by weight → hierarchy
  5. 5condense: λ = 1/ε; drop pieces < mcs
  6. 6S(C) ← Σ_{x∈C} (λ_x − λ_birth(C))
  7. 7keep C if S(C) ≥ Σ S(children)
  8. 8label points; the rest are noise
  9. 9new q → MR-nearest neighbour at λ_q

14 points: two tight squares on the left, a loose pentagon on the right, one stray point. min_cluster_size = 3, min_samples = 3.

fig.The worked example, step by step. Top: the 14 points with their core-distance circles, then the MST on mutual reachability growing edge by edge (points are coloured when they belong to a group of ≥ min_cluster_size at the current ε — DBSCAN* at that level; violet = A1 and A2 fused). Bottom: the single-linkage dendrogram growing to height 3.162, then the condensed tree in λ with each bar's width = points still inside and its area = stability (C1 1.75, C2 3.37, C3 4.03, C4 0.44). EOM keeps C2, C3, C4; the last step places q = (5.5, 1.5) in A2 with strength 0.40. Change min_cluster_size or min_samples to re-run: 5 merges the squares, 6 leaves only noise.

The algorithm, step by step

HDBSCAN(X, m = min_cluster_size, k = min_samples)

  1. 1Core distances. For each point, the distance to its kk-th nearest neighbour (itself included). A kd-tree or ball tree makes this O(nlog⁡n)O(n\log n) in low dimensions; brute force is O(n2)O(n^2).
  2. 2Mutual-reachability MST. Build the minimum spanning tree of dmrd_\text{mr}. Prim on the dense matrix is O(n2)O(n^2) time and memory; dual-tree Borůvka avoids materializing the matrix and runs in roughly O(nlog⁡n)O(n\log n) for low-dimensional Euclidean data.
  3. 3Single-linkage tree. Sort the n−1n-1 edges and merge with union–find: O(nlog⁡n)O(n\log n).
  4. 4Condense. Walk the tree top-down in λ=1/ε\lambda=1/\varepsilon; splits with a side smaller than min_cluster_size become fall-outs. Record each point's leaving λ\lambda: O(n)O(n).
  5. 5Stability. S(C)=∑x∈C(λx−λbirth(C))S(C)=\sum_{x\in C}(\lambda_x-\lambda_\text{birth}(C)) for every condensed cluster: O(n)O(n).
  6. 6Select. Bottom-up: keep CC if S(C)≥∑S(C)\ge\sum of its children's best, else propagate the children's sum. Discard descendants of kept clusters. Exclude the root unless allow_single_cluster.
  7. 7Label. Every point in a kept cluster's subtree gets that label and strength λx/λmax\lambda_x/\lambda_\text{max}; all others are noise (−1-1).

The expensive part is the MST; everything after it is linear in nn. Memory is the practical limit of the naive O(n2)O(n^2) version (about 8 GB of float64 distances at n=32,000n=32{,}000); tree-based implementations handle millions of low-dimensional points. In high dimensions the trees stop helping and run time drifts back toward O(n2)O(n^2).

Variants and practical tuning

min_cluster_sizemin_samplesClusters foundNoise
2 or 32 or 3A1, A2, B13
2 or 34A1, A2, B without 8 and 128, 12, 13
44A1, A2all of B, 13
52 or 3A (= A1 ∪ A2), B13
54noneeverything
63noneeverything
Effect of the two main knobs on the worked example (all results from scikit-learn's HDBSCAN, identical to the from-scratch code).

Tuning guide

Start with min_cluster_size
set it to the smallest group you would act on (e.g. 15 customers, 50 cells). It is the most interpretable knob and usually the only one you need.
Then min_samples
defaults to min_cluster_size. Lower it (e.g. 1–5) if too many points are noise; raise it to be more conservative in noisy data. It changes the distances themselves, so results can shift a lot.
cluster_selection_epsilon
set it to a distance below which you do not care about splits. On the example, any value ≥ 1.75 (the A1–A2 merge distance) reports A as one cluster; 1.7 or less keeps the squares apart.
"eom" vs "leaf"
EOM favours a few large stable clusters (sometimes one giant cluster plus small ones); leaf gives many small, homogeneous clusters. Both give A1, A2, B here.
Soft clustering
use probabilities_ to downweight weak members; the hdbscan package also offers all-points membership vectors and GLOSH outlier scores (here 0.80 for the stray point, 0.07 for point 8).
Scaling
results are invariant to rescaling all features by one factor (λ just rescales), but not to rescaling one feature: standardize features first, as for any distance-based method.

In code

python
1import numpy as np
2
3def hdbscan(X, min_cluster_size=3, min_samples=3):
4 n = len(X)
5 D = np.sqrt(((X[:, None] - X[None]) ** 2).sum(-1))
6 core = np.sort(D, axis=1)[:, min_samples - 1] # k-th nearest, the point itself included
7 M = np.maximum(D, np.maximum(core[:, None], core[None])) # mutual reachability distance
8
9 # 1. minimum spanning tree of M (Prim, O(n^2))
10 seen, best, src, edges = np.zeros(n, bool), M[0].copy(), np.zeros(n, int), []
11 seen[0] = True
12 for _ in range(n - 1):
13 j = np.where(seen, np.inf, best).argmin()
14 edges.append((best[j], src[j], j)); seen[j] = True
15 upd = ~seen & (M[j] < best); best[upd], src[upd] = M[j][upd], j
16 edges.sort()
17
18 # 2. single-linkage tree: node = (left, right, height, points)
19 nodes, owner = [(None, None, 0.0, [i]) for i in range(n)], list(range(n))
20 for w, a, b in edges:
21 A, B = owner[a], owner[b]
22 nodes.append((A, B, w, nodes[A][3] + nodes[B][3]))
23 for p in nodes[-1][3]: owner[p] = len(nodes) - 1
24
25 # 3. condensed tree: walk down in lambda = 1/distance
26 clusters = [] # dicts: birth, leave {point: lambda}, children
27 def new(birth):
28 clusters.append(dict(birth=birth, leave={}, children=[])); return len(clusters) - 1
29 def walk(node, c):
30 left, right, h, pts = nodes[node]
31 if left is None: return
32 lam, kids = 1 / h, (left, right)
33 big = [k for k in kids if len(nodes[k][3]) >= min_cluster_size]
34 if len(big) == 2: # a true split: two clusters are born
35 for p in pts: clusters[c]["leave"][p] = lam
36 for k in kids:
37 child = new(lam); clusters[c]["children"].append(child); walk(k, child)
38 return
39 for k in kids: # small pieces fall out of c
40 if len(nodes[k][3]) < min_cluster_size:
41 for p in nodes[k][3]: clusters[c]["leave"][p] = lam
42 if big: walk(big[0], c) # c lives on as the big piece
43 walk(len(nodes) - 1, new(0.0))
44
45 # 4. stability and excess-of-mass selection (bottom-up; the root never counts)
46 S = [sum(l - c["birth"] for l in c["leave"].values()) for c in clusters]
47 best_S, keep = S[:], [False] * len(clusters)
48 for k in reversed(range(len(clusters))):
49 kids = clusters[k]["children"]
50 below = sum(best_S[ch] for ch in kids)
51 if k > 0 and (not kids or S[k] >= below):
52 keep[k] = True
53 else:
54 best_S[k] = below
55 def drop(k):
56 for ch in clusters[k]["children"]: keep[ch] = False; drop(ch)
57 for k in range(len(clusters)):
58 if keep[k]: drop(k)
59
60 labels = -np.ones(n, int)
61 def points(k):
62 return set(clusters[k]["leave"]) | set().union(*[points(ch) for ch in clusters[k]["children"]])
63 for lab, k in enumerate(k for k in range(len(clusters)) if keep[k]):
64 labels[list(points(k))] = lab
65 return labels, core, edges, clusters, S, keep
66
67X = np.array([[1.0, 1.0], [1.6, 1.1], [1.1, 1.7], [1.7, 1.6], # A1: tight square
68 [3.4, 1.2], [4.0, 1.0], [3.6, 1.8], [4.1, 1.6], # A2: tight square
69 [6.8, 0.6], [8.8, 1.2], [7.0, 3.0], [9.0, 3.2], [8.0, 5.0], # B: loose
70 [4.6, 4.8]]) # a stray point
71labels, core, edges, clusters, S, keep = hdbscan(X)
72print("core ", core.round(3))
73print("MST ", [(int(a), int(b), round(float(w), 3)) for w, a, b in edges])
74for k, c in enumerate(clusters):
75 print(f"C{k}: birth lam={c['birth']:.3f} size={len(c['leave'])} S={S[k]:.3f} keep={keep[k]}")
76print("labels ", labels)
77
78# core [0.707 0.608 0.707 0.608 0.632 0.632 0.632 0.608 2.408 2.088 2.236 2.01
79# 2.236 3.162]
80# MST [(1, 3, 0.608), (5, 7, 0.632), (4, 5, 0.632), (4, 6, 0.632), (0, 1, 0.707), (0, 2, 0.707),
81# (3, 4, 1.746), (9, 11, 2.088), (11, 10, 2.236), (11, 12, 2.236), (8, 9, 2.408),
82# (5, 8, 2.828), (6, 13, 3.162)]
83# C0: birth lam=0.000 size=14 S=4.912 keep=False
84# C1: birth lam=0.354 size=8 S=1.752 keep=False
85# C2: birth lam=0.573 size=4 S=3.366 keep=True
86# C3: birth lam=0.573 size=4 S=4.034 keep=True
87# C4: birth lam=0.354 size=5 S=0.436 keep=True
88# labels [ 0 0 0 0 1 1 1 1 2 2 2 2 2 -1]
From scratch with NumPy: core distances, Prim's MST on mutual reachability, condensed tree, stability, excess-of-mass selection.
python
1import numpy as np
2from sklearn.cluster import HDBSCAN, DBSCAN
3
4X = np.array([[1.0, 1.0], [1.6, 1.1], [1.1, 1.7], [1.7, 1.6],
5 [3.4, 1.2], [4.0, 1.0], [3.6, 1.8], [4.1, 1.6],
6 [6.8, 0.6], [8.8, 1.2], [7.0, 3.0], [9.0, 3.2], [8.0, 5.0],
7 [4.6, 4.8]])
8
9hdb = HDBSCAN(min_cluster_size=3, min_samples=3).fit(X)
10print("labels ", hdb.labels_)
11print("probabilities", hdb.probabilities_.round(3))
12
13# No single DBSCAN eps recovers all three groups:
14for eps in [1.0, 1.7, 2.05, 2.5]:
15 print(f"DBSCAN eps={eps}:", DBSCAN(eps=eps, min_samples=3).fit(X).labels_)
16
17# Variants
18print("leaf ", HDBSCAN(min_cluster_size=3, min_samples=3, cluster_selection_method="leaf").fit(X).labels_)
19print("eps=2.0 ", HDBSCAN(min_cluster_size=3, min_samples=3, cluster_selection_epsilon=2.0).fit(X).labels_)
20print("mcs=5 ", HDBSCAN(min_cluster_size=5, min_samples=3).fit(X).labels_)
21
22# labels [ 1 1 1 1 2 2 2 2 0 0 0 0 0 -1]
23# probabilities [1. 1. 1. 1. 1. 1. 1. 1. 0.928 1. 1. 1.
24# 1. 0. ]
25# DBSCAN eps=1.0: [ 0 0 0 0 1 1 1 1 -1 -1 -1 -1 -1 -1]
26# DBSCAN eps=1.7: [ 0 0 0 0 1 1 1 1 -1 -1 -1 -1 -1 -1]
27# DBSCAN eps=2.05: [ 0 0 0 0 0 0 0 0 -1 1 1 1 -1 -1]
28# DBSCAN eps=2.5: [ 0 0 0 0 0 0 0 0 1 1 1 1 1 -1]
29# leaf [ 1 1 1 1 2 2 2 2 0 0 0 0 0 -1]
30# eps=2.0 [ 0 0 0 0 0 0 0 0 1 1 1 1 1 -1]
31# mcs=5 [ 0 0 0 0 0 0 0 0 1 1 1 1 1 -1]
scikit-learn (≥ 1.3) on the same data — same partition (label numbers differ), membership strengths, and the DBSCAN comparison.

Use when

  • +Clusters have different densities, and you do not know how many there are.
  • +The data contains noise or background points that should not be forced into any cluster.
  • +You want one main knob with a plain meaning (smallest cluster size) instead of a fragile radius ε.
  • +You want a cluster hierarchy and per-point membership strengths, not just flat labels.

Avoid when

  • −Data is high-dimensional (hundreds of raw features): distances concentrate, density is meaningless and the tree speed-ups vanish — reduce dimension first (e.g. UMAP or PCA).
  • −Every point must get a cluster: HDBSCAN routinely leaves a sizeable share of real data as noise.
  • −Clusters are not density bumps (overlapping Gaussians of equal density): a Gaussian mixture is the better model.
  • −You need a cheap, stable predict() for streaming data: the model is a tree over the training set, not a function.

Where it's used

Embedding clustering (topic modelling)

BERTopic runs UMAP on sentence embeddings and then HDBSCAN to find topics, with noise documents left unassigned.

Single-cell biology

Finding cell types of very different abundance in UMAP-reduced expression data, where a rare type may have a few dozen cells.

Geospatial hotspots

Crime, taxi pick-ups or GPS stay-points: dense downtown hotspots and sparse rural ones in a single run, with haversine distance.

Astronomy and anomaly screening

Finding star clusters and stellar streams in Gaia data; GLOSH outlier scores flag points that leave their cluster unusually early.

Check yourself

With min_samples = 3, point a has core distance 0.5, point b has core distance 2.0, and d(a, b) = 1.2. What is d_mr(a, b)?

Check yourself

A cluster is born at λ = 0.5. Of its 6 points, 2 fall out at λ = 0.7 and the remaining 4 leave at λ = 1.0 when it dies. Its stability is…

Check yourself

In the worked example, why does HDBSCAN report A1 and A2 separately instead of their union A?

Check yourself

You raise min_cluster_size from 3 to 5 on the worked example (min_samples = 3). What happens?

Remember

  • ✓Core distance = distance to the kk-th nearest point (a density estimate); mutual reachability dmr=max⁡(core(a),core(b),d(a,b))d_\text{mr}=\max(\text{core}(a),\text{core}(b),d(a,b)) pushes sparse points apart.
  • ✓The MST of dmrd_\text{mr} encodes DBSCAN* for every ε\varepsilon at once: cut it at ε\varepsilon to get that level's clusters.
  • ✓Condensing walks the tree in λ = 1/ε and treats splits that shed fewer than min_cluster_size points as points falling out, not new clusters.
  • ✓Stability S(C)=∑x(λx−λbirth)S(C)=\sum_x(\lambda_x-\lambda_\text{birth}); excess of mass keeps a cluster only if it beats its descendants, so the cut can sit at different densities in different branches.
  • ✓Start tuning with min_cluster_size; min_samples controls how conservative (noisy) the result is. Noise (−1) and membership strengths are part of the answer.
← back to ML Algorithms roadmap