# HDBSCAN

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

Source: https://www.mlfoundry.in/learn/hdbscan  
Section: ML Algorithms › Unsupervised · Clustering  
Level: advanced · 17 min read · updated 2026-10-07

**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.

- **Task:** Density-based clustering with noise detection
- **Input → output:** points $x_1,\dots,x_n$ and a distance → a label per point ($-1$ = noise), a membership strength in $[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(n^2)$ time with dense distances; about $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:

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.

| ε range | A1 (0–3) | A2 (4–7) | B (8–12) | Point 13 |
| --- | --- | --- | --- | --- |
| 0.64 – 1.74 | cluster | cluster | **all noise** | noise |
| 1.75 – 2.00 | **merged with A2** | **merged with A1** | all noise | noise |
| 2.01 – 2.08 | merged | merged | 3–4 of 5 points | noise |
| 2.09 – 2.82 | merged | merged | cluster | noise |
| ≥ 2.83 | merged | merged | **merged with A** | noise, then joins at ≥ 3.0 |

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:** $\text{core}_k(x)$: distance from $x$ to its $k$-th nearest point, counting $x$ itself ($k=$ `min_samples`). Small in dense regions, large in sparse ones.
- **Mutual reachability distance:** $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 $\text{core}_k\le\varepsilon$); everything else is noise. HDBSCAN builds DBSCAN* for every $\varepsilon$.
- **Minimum spanning tree (MST):** the $n-1$ edges of smallest total $d_\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 $\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)=\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:** $\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 $x$ that holds $k$ points:

$$
\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}}
$$

- $N_k(x)$: the $k$-th nearest point to $x$ in the data, $x$ itself counted as the first
- $k$: min_samples
- $\hat f(x)$: the $k$-nearest-neighbour density estimate at $x$
- $V_d$: volume of the unit ball in $d$ dimensions

So "$\text{core}_k(x)\le\varepsilon$" is the same statement as "$\hat f(x)\ge$ a threshold": shrinking $\varepsilon$ means raising the density level. Larger $k$ 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:

$$
d_\text{mr}(a,b)=\max\big\{\text{core}_k(a),\;\text{core}_k(b),\;d(a,b)\big\}
$$

- $d(a,b)$: the original distance (Euclidean here)
- $d_\text{mr}(a,b)$: the smallest $\varepsilon$ at which $a$ and $b$ 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 ($\text{core}_k\le\varepsilon$) and $d(a,b)\le\varepsilon$ — i.e. iff $d_\text{mr}(a,b)\le\varepsilon$. So **DBSCAN* at $\varepsilon$ = connected components of the graph whose edges have $d_\text{mr}\le\varepsilon$** (points with $\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-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 $d_\text{mr}$.

**Step 4 — condense.** Re-label heights by density, $\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 $C$ into pieces $L$ and $R$:

$$
\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}
$$

- $m$: min_cluster_size

Each point $x$ gets $\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 $f$ 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)=\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(\lambda)|$: number of points still in $C$ at level $\lambda$
- $\lambda_\text{birth}(C)$: level at which $C$ split off its parent
- $\lambda_x$: level at which point $x$ leaves $C$

The second form follows by swapping sum and integral: each point contributes 1 to $|C(\lambda)|$ for every $\lambda$ between the birth and its own departure, so it contributes exactly $\lambda_x-\lambda_\text{birth}(C)$. Geometrically, $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:

$$
\hat S(C)=\max\Big\{S(C),\;\sum_{C'\in\text{children}(C)}\hat S(C')\Big\}
$$

- $\hat S(C)$: best total stability achievable inside the subtree of $C$
- $\text{children}(C)$: the two clusters born when C dies (none for a leaf)

If $S(C)$ wins, $C$ 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.

> **Why it works for mixed densities:** The selection compares a cluster only with **its own descendants**. A sparse cluster such as B is never compared against the dense squares — it lives on a different branch. So B can be chosen at a low density level while A1 and A2 are chosen at a high one. A single horizontal cut (DBSCAN) cannot do that.

**Each hyperparameter, mathematically**

- **min_samples = k:** changes $\text{core}_k$, hence every $d_\text{mr}$. Larger $k$ raises core distances most for isolated points, so they join later (lower $\lambda$) and fall out sooner — more noise, smoother tree. $k=1$ gives $\text{core}=0$ and plain single linkage.
- **min_cluster_size = m:** decides which splits are real. Pieces smaller than $m$ only *fall out*, so raising $m$ 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 ($\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/\alpha$ inside $d_\text{mr}$; rarely needed.

## Worked example: 14 points, three densities

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

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.

| Point | x | y | Group | 2nd nearest other (distance) | core₃ |
| --- | --- | --- | --- | --- | --- |
| 0 | 1.0 | 1.0 | A1 | 2 (0.707) | 0.707 |
| 1 | 1.6 | 1.1 | A1 | 0 (0.608) | 0.608 |
| 2 | 1.1 | 1.7 | A1 | 0 (0.707) | 0.707 |
| 3 | 1.7 | 1.6 | A1 | 2 (0.608) | 0.608 |
| 4 | 3.4 | 1.2 | A2 | 6 (0.632) | 0.632 |
| 5 | 4.0 | 1.0 | A2 | 4 (0.632) | 0.632 |
| 6 | 3.6 | 1.8 | A2 | 4 (0.632) | 0.632 |
| 7 | 4.1 | 1.6 | A2 | 5 (0.608) | 0.608 |
| 8 | 6.8 | 0.6 | B | 10 (2.408) | 2.408 |
| 9 | 8.8 | 1.2 | B | 8 (2.088) | 2.088 |
| 10 | 7.0 | 3.0 | B | 12 (2.236) | 2.236 |
| 11 | 9.0 | 3.2 | B | 10 (2.010) | 2.010 |
| 12 | 8.0 | 5.0 | B | 10 (2.236) | 2.236 |
| 13 | 4.6 | 4.8 | stray | 6 (3.162) | 3.162 |

**Core distances → mutual reachability → MST**

1. **Core distances** (table above). Example: point 8's nearest others are 9 at 2.088 and 10 at 2.408, so $\text{core}_3(8)=2.408$.
2. **Mutual reachability.** Inside a square nothing changes much: $d(1,3)=0.510$ but both cores are 0.608, so $d_\text{mr}(1,3)=0.608$. In B the cores dominate: $d(8,9)=2.088$, but $d_\text{mr}(8,9)=\max(2.408,\,2.088,\,2.088)=2.408$.
3. **MST.** Prim's algorithm on $d_\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. **Dendrogram.** Adding the edges from light to heavy: A1 is complete at $\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.

The 13 MST edges in the order single linkage adds them, with λ = 1/d_mr. Highlighted: the three edges that create the true splits.

| Edge | d | core(a), core(b) | d_mr | λ = 1/d_mr | Effect |
| --- | --- | --- | --- | --- | --- |
| 1–3 | 0.510 | 0.608, 0.608 | 0.608 | 1.644 | pair in A1 |
| 5–7 | 0.608 | 0.632, 0.608 | 0.632 | 1.581 | pair in A2 |
| 4–5 | 0.632 | 0.632, 0.632 | 0.632 | 1.581 | A2 grows |
| 4–6 | 0.632 | 0.632, 0.632 | 0.632 | 1.581 | A2 complete (4 pts) |
| 0–1 | 0.608 | 0.707, 0.608 | 0.707 | 1.414 | A1 grows |
| 0–2 | 0.707 | 0.707, 0.707 | 0.707 | 1.414 | A1 complete (4 pts) |
| 3–4 | 1.746 | 0.608, 0.632 | 1.746 | 0.573 | **A1 + A2 → A (8 pts)** |
| 9–11 | 2.010 | 2.088, 2.010 | 2.088 | 0.479 | pair in B |
| 11–10 | 2.010 | 2.010, 2.236 | 2.236 | 0.447 | B grows |
| 11–12 | 2.059 | 2.010, 2.236 | 2.236 | 0.447 | B grows (4 pts) |
| 8–9 | 2.088 | 2.408, 2.088 | 2.408 | 0.415 | B complete (5 pts) |
| 5–8 | 2.828 | 0.632, 2.408 | 2.828 | 0.354 | **A + B (13 pts)** |
| 6–13 | 3.162 | 0.632, 3.162 | 3.162 | 0.316 | **stray point joins** |

**Condense, score, select**

1. **Root (C0), from $\lambda=0$.** The top split at $\lambda=0.316$ separates point 13 (1 point $<m$) from 13 others: point 13 **falls out**; the root carries on.
2. **$\lambda=0.354$ (edge 5–8):** pieces of 8 and 5 points, both $\ge 3$ — a true split. **C1** = A (points 0–7) and **C4** = B (points 8–12) are born at $\lambda=0.354$.
3. **C1 at $\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(\text{C1})=8\times(0.5726-0.3536)=1.752$.
4. **C2 (A1):** the next merges inside it (0.707) cut it into pieces smaller than 3, so all four points leave at $\lambda=1.414$: $S(\text{C2})=4\times(1.4142-0.5726)=3.366$. Likewise **C3 (A2)** ends at 1.581: $S(\text{C3})=4\times(1.5811-0.5726)=4.034$.
5. **C4 (B):** point 8 falls out at $\lambda=0.415$ (edge 8–9); at 0.447 the rest breaks into pieces under 3 and the cluster dies. $S(\text{C4})=(0.4152-0.3536)+4\times(0.4472-0.3536)=0.062+0.374=0.436$.
6. **Excess of mass, bottom-up.** Leaves C2, C3, C4 are provisionally kept. At C1: $S(\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.**

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.

| Cluster | Points | Born at λ | Points leave at λ | Stability S | Selected |
| --- | --- | --- | --- | --- | --- |
| C0 (root) | 0–13 | 0 | 13 at 0.316; rest at 0.354 | — | never |
| C1 = A | 0–7 | 0.354 | all at 0.573 (split) | 1.752 | no (1.752 < 7.40) |
| C2 = A1 | 0–3 | 0.573 | all at 1.414 | 3.366 | **yes** |
| C3 = A2 | 4–7 | 0.573 | all at 1.581 | 4.034 | **yes** |
| C4 = B | 8–12 | 0.354 | 8 at 0.415; rest at 0.447 | 0.436 | **yes** |

**Membership strength** is $\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.928$; point 13 is noise with 0.

**Placing a new point q = (5.5, 1.5)**

1. Distances 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: $\text{core}_3(q)=1.581$.
2. Mutual reachability to point 7: $\max(1.581,\,0.608,\,1.404)=1.581$; to point 8 it is $\max(1.581,\,2.408,\,1.581)=2.408$. The nearest in $d_\text{mr}$ is **point 7** at 1.581, so q attaches at $\lambda_q=1/1.581=0.632$.
3. Point 7 is in C3 (A2), which is alive from $\lambda=0.573$ to 1.581. Since $0.573\le 0.632$, q lands **inside A2**, with strength $0.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 $\lambda_q<0.573$ it would land in C1, which is not selected, and be noise.)

> Figure: 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.

> **Try the knobs in the figure:** With min_cluster_size = 5 the 4-point squares can no longer be clusters, so C1 = A is a leaf and wins: two clusters (A, B). With min_samples = 4, B's core distances grow and its points 8 and 12 fall out early: A1, A2 and a 3-point B with 8 and 12 as noise when min_cluster_size = 2 or 3; at min_cluster_size = 4, all of B is noise.

## The algorithm, step by step

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

1. **Core distances.** For each point, the distance to its $k$-th nearest neighbour (itself included). A kd-tree or ball tree makes this $O(n\log n)$ in low dimensions; brute force is $O(n^2)$.
2. **Mutual-reachability MST.** Build the minimum spanning tree of $d_\text{mr}$. Prim on the dense matrix is $O(n^2)$ time and memory; dual-tree Borůvka avoids materializing the matrix and runs in roughly $O(n\log n)$ for low-dimensional Euclidean data.
3. **Single-linkage tree.** Sort the $n-1$ edges and merge with union–find: $O(n\log n)$.
4. **Condense.** Walk the tree top-down in $\lambda=1/\varepsilon$; splits with a side smaller than `min_cluster_size` become fall-outs. Record each point's leaving $\lambda$: $O(n)$.
5. **Stability.** $S(C)=\sum_{x\in C}(\lambda_x-\lambda_\text{birth}(C))$ for every condensed cluster: $O(n)$.
6. **Select.** Bottom-up: keep $C$ if $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. **Label.** Every point in a kept cluster's subtree gets that label and strength $\lambda_x/\lambda_\text{max}$; all others are noise ($-1$).

The expensive part is the MST; everything after it is linear in $n$. Memory is the practical limit of the naive $O(n^2)$ version (about 8 GB of float64 distances at $n=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(n^2)$.

## Variants and practical tuning

Effect of the two main knobs on the worked example (all results from scikit-learn's HDBSCAN, identical to the from-scratch code).

| min_cluster_size | min_samples | Clusters found | Noise |
| --- | --- | --- | --- |
| 2 or 3 | 2 or 3 | A1, A2, B | 13 |
| 2 or 3 | 4 | A1, A2, B without 8 and 12 | 8, 12, 13 |
| 4 | 4 | A1, A2 | all of B, 13 |
| 5 | 2 or 3 | A (= A1 ∪ A2), B | 13 |
| 5 | 4 | none | everything |
| 6 | 3 | none | everything |

**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.

> **Two libraries, two meanings of min_samples:** scikit-learn's `HDBSCAN` counts the point itself in `min_samples` (as in DBSCAN); the standalone `hdbscan` package does not. On the worked example `hdbscan.HDBSCAN(min_samples=2)` reproduces `sklearn.cluster.HDBSCAN(min_samples=3)` exactly. Translate before comparing results or copying settings between them.

## In code

```python
import numpy as np

def hdbscan(X, min_cluster_size=3, min_samples=3):
    n = len(X)
    D = np.sqrt(((X[:, None] - X[None]) ** 2).sum(-1))
    core = np.sort(D, axis=1)[:, min_samples - 1]            # k-th nearest, the point itself included
    M = np.maximum(D, np.maximum(core[:, None], core[None]))   # mutual reachability distance

    # 1. minimum spanning tree of M (Prim, O(n^2))
    seen, best, src, edges = np.zeros(n, bool), M[0].copy(), np.zeros(n, int), []
    seen[0] = True
    for _ in range(n - 1):
        j = np.where(seen, np.inf, best).argmin()
        edges.append((best[j], src[j], j)); seen[j] = True
        upd = ~seen & (M[j] < best); best[upd], src[upd] = M[j][upd], j
    edges.sort()

    # 2. single-linkage tree: node = (left, right, height, points)
    nodes, owner = [(None, None, 0.0, [i]) for i in range(n)], list(range(n))
    for w, a, b in edges:
        A, B = owner[a], owner[b]
        nodes.append((A, B, w, nodes[A][3] + nodes[B][3]))
        for p in nodes[-1][3]: owner[p] = len(nodes) - 1

    # 3. condensed tree: walk down in lambda = 1/distance
    clusters = []                                   # dicts: birth, leave {point: lambda}, children
    def new(birth):
        clusters.append(dict(birth=birth, leave={}, children=[])); return len(clusters) - 1
    def walk(node, c):
        left, right, h, pts = nodes[node]
        if left is None: return
        lam, kids = 1 / h, (left, right)
        big = [k for k in kids if len(nodes[k][3]) >= min_cluster_size]
        if len(big) == 2:                           # a true split: two clusters are born
            for p in pts: clusters[c]["leave"][p] = lam
            for k in kids:
                child = new(lam); clusters[c]["children"].append(child); walk(k, child)
            return
        for k in kids:                              # small pieces fall out of c
            if len(nodes[k][3]) < min_cluster_size:
                for p in nodes[k][3]: clusters[c]["leave"][p] = lam
        if big: walk(big[0], c)                     # c lives on as the big piece
    walk(len(nodes) - 1, new(0.0))

    # 4. stability and excess-of-mass selection (bottom-up; the root never counts)
    S = [sum(l - c["birth"] for l in c["leave"].values()) for c in clusters]
    best_S, keep = S[:], [False] * len(clusters)
    for k in reversed(range(len(clusters))):
        kids = clusters[k]["children"]
        below = sum(best_S[ch] for ch in kids)
        if k > 0 and (not kids or S[k] >= below):
            keep[k] = True
        else:
            best_S[k] = below
    def drop(k):
        for ch in clusters[k]["children"]: keep[ch] = False; drop(ch)
    for k in range(len(clusters)):
        if keep[k]: drop(k)

    labels = -np.ones(n, int)
    def points(k):
        return set(clusters[k]["leave"]) | set().union(*[points(ch) for ch in clusters[k]["children"]])
    for lab, k in enumerate(k for k in range(len(clusters)) if keep[k]):
        labels[list(points(k))] = lab
    return labels, core, edges, clusters, S, keep

X = np.array([[1.0, 1.0], [1.6, 1.1], [1.1, 1.7], [1.7, 1.6],        # A1: tight square
              [3.4, 1.2], [4.0, 1.0], [3.6, 1.8], [4.1, 1.6],        # A2: tight square
              [6.8, 0.6], [8.8, 1.2], [7.0, 3.0], [9.0, 3.2], [8.0, 5.0],  # B: loose
              [4.6, 4.8]])                                            # a stray point
labels, core, edges, clusters, S, keep = hdbscan(X)
print("core     ", core.round(3))
print("MST      ", [(int(a), int(b), round(float(w), 3)) for w, a, b in edges])
for k, c in enumerate(clusters):
    print(f"C{k}: birth lam={c['birth']:.3f}  size={len(c['leave'])}  S={S[k]:.3f}  keep={keep[k]}")
print("labels   ", labels)

# 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
#  2.236 3.162]
# 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),
#            (3, 4, 1.746), (9, 11, 2.088), (11, 10, 2.236), (11, 12, 2.236), (8, 9, 2.408),
#            (5, 8, 2.828), (6, 13, 3.162)]
# C0: birth lam=0.000  size=14  S=4.912  keep=False
# C1: birth lam=0.354  size=8  S=1.752  keep=False
# C2: birth lam=0.573  size=4  S=3.366  keep=True
# C3: birth lam=0.573  size=4  S=4.034  keep=True
# C4: birth lam=0.354  size=5  S=0.436  keep=True
# 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
import numpy as np
from sklearn.cluster import HDBSCAN, DBSCAN

X = np.array([[1.0, 1.0], [1.6, 1.1], [1.1, 1.7], [1.7, 1.6],
              [3.4, 1.2], [4.0, 1.0], [3.6, 1.8], [4.1, 1.6],
              [6.8, 0.6], [8.8, 1.2], [7.0, 3.0], [9.0, 3.2], [8.0, 5.0],
              [4.6, 4.8]])

hdb = HDBSCAN(min_cluster_size=3, min_samples=3).fit(X)
print("labels       ", hdb.labels_)
print("probabilities", hdb.probabilities_.round(3))

# No single DBSCAN eps recovers all three groups:
for eps in [1.0, 1.7, 2.05, 2.5]:
    print(f"DBSCAN eps={eps}:", DBSCAN(eps=eps, min_samples=3).fit(X).labels_)

# Variants
print("leaf     ", HDBSCAN(min_cluster_size=3, min_samples=3, cluster_selection_method="leaf").fit(X).labels_)
print("eps=2.0  ", HDBSCAN(min_cluster_size=3, min_samples=3, cluster_selection_epsilon=2.0).fit(X).labels_)
print("mcs=5    ", HDBSCAN(min_cluster_size=5, min_samples=3).fit(X).labels_)

# labels        [ 1  1  1  1  2  2  2  2  0  0  0  0  0 -1]
# probabilities [1.    1.    1.    1.    1.    1.    1.    1.    0.928 1.    1.    1.
#  1.    0.   ]
# DBSCAN eps=1.0: [ 0  0  0  0  1  1  1  1 -1 -1 -1 -1 -1 -1]
# DBSCAN eps=1.7: [ 0  0  0  0  1  1  1  1 -1 -1 -1 -1 -1 -1]
# DBSCAN eps=2.05: [ 0  0  0  0  0  0  0  0 -1  1  1  1 -1 -1]
# DBSCAN eps=2.5: [ 0  0  0  0  0  0  0  0  1  1  1  1  1 -1]
# leaf      [ 1  1  1  1  2  2  2  2  0  0  0  0  0 -1]
# eps=2.0   [ 0  0  0  0  0  0  0  0  1  1  1  1  1 -1]
# 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.

> **Predicting new points:** scikit-learn's `HDBSCAN` has `fit_predict` but no `predict`. The `hdbscan` package offers `approximate_predict(clusterer, points)` after fitting with `prediction_data=True`; for q = (5.5, 1.5) it returns cluster A2 with strength 0.40, matching the hand calculation. For batch scoring of many new points, refitting on the combined data is the exact answer.

**Strengths**

- 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.

**Limitations**

- 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.

- **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.

> **Stability is measured in λ, which favours dense clusters:** λ is $1/\varepsilon$, so dense clusters live at large λ and score large stabilities: here B scores 0.436 against 3.4–4.0 for the squares, although all three are equally "real". B survives only because it is a leaf that is never compared with them. When a sparse cluster sits *inside* a dense parent's branch, EOM can swallow it — try "leaf" selection or `cluster_selection_epsilon` if obvious sparse clusters disappear.

> **Noise is not an error to be eliminated:** Lowering `min_samples` to 1 to get rid of noise turns HDBSCAN into plain single linkage, which chains clusters together through bridges of sparse points. Treat a large noise fraction as information (the data may have less structure than hoped); if you need every point labelled, assign noise points afterwards by their membership vectors or nearest cluster.

> **HDBSCAN = robust single linkage + a smart cut:** Without mutual reachability ($k=1$) the tree is the ordinary single-linkage dendrogram, famous for chaining. The core-distance max lifts every sparse point's edges up to its core distance, so a thin bridge of noise points connects clusters only at a low density level — and the stability-based selection then cuts each branch at the level where it is most persistent.

**Question:** 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)?

- A. 0.5
- B. 1.2
- C. 2.0
- D. 3.7

**Answer:** C. 2.0 — $d_\text{mr}=\max(0.5,\,2.0,\,1.2)=2.0$. Point b is sparse, so it is only reachable from anything once $\varepsilon$ reaches its own core distance.

**Question:** 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…

- A. 0.4
- B. 2.0
- C. 2.4
- D. 6.0

**Answer:** C. 2.4 — $S=2\times(0.7-0.5)+4\times(1.0-0.5)=0.4+2.0=2.4$ — the area of the bar.

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

- A. Because min_cluster_size = 3 forbids clusters of 8 points
- B. Because S(A) = 1.752 is smaller than S(A1) + S(A2) = 7.40
- C. Because A1 and A2 have different core distances
- D. Because DBSCAN with ε = 1.0 separates them

**Answer:** B. Because S(A) = 1.752 is smaller than S(A1) + S(A2) = 7.40 — Excess of mass keeps a parent only if it is at least as stable as its children combined. A lives only from λ = 0.354 to 0.573, while the squares survive until 1.414 and 1.581.

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

- A. Nothing changes
- B. B becomes noise
- C. A1 and A2 are reported as one cluster A, and B stays
- D. Every point becomes noise

**Answer:** C. A1 and A2 are reported as one cluster A, and B stays — With m = 5 the split of A into 4 + 4 is no longer a true split (both pieces are too small), so A is a leaf of the condensed tree and is kept; B has exactly 5 points and survives. Result: A, B and the stray point as noise.

**Key points**

- Core distance = distance to the $k$-th nearest point (a density estimate); mutual reachability $d_\text{mr}=\max(\text{core}(a),\text{core}(b),d(a,b))$ pushes sparse points apart.
- The MST of $d_\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)=\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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
