Learn AI Create the Future — with Pranay
Main site

Clustering in Depth

HDBSCAN

HDBSCAN finds clusters of any shape by following density, decides the cluster count itself, and is honest enough to label leftover points as noise.

Read these first

On this page 5
  1. Why this matters
  2. How it works
  3. A real example you have seen
  4. Remember this
  5. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

HDBSCAN groups points by following where the data is dense.

It finds clusters of any shape, picks the number of clusters itself, and files points that fit nowhere as noise.

Look at a satellite photo of India at night. Cities glow as bright patches — some round, some sprawling along a coastline or a river. Villages form smaller specks. And a few lone lights sit alone in the dark, belonging to no patch at all.

Your eye needs no one to announce "there are 47 cities". Bright-and-connected is a city; a lone light is noise. HDBSCAN is that instinct, written as an algorithm.

Why this matters

K-means has three quiet assumptions: you know the group count, groups are roughly round, and every point belongs somewhere. Real data breaks all three. A crescent-shaped cluster gets sliced. A count you guessed wrong shreds real structure. And a fraud case gets stuffed into a "customer segment" as if it were normal.

Density-based clustering drops all three assumptions at once. A cluster is a region where points crowd together, whatever its shape. Sparse points between crowds are labelled noise — a refusal to force membership.

The H stands for hierarchical. An older method, DBSCAN, needed you to pick one fixed density cut-off. One cut-off cannot suit a dense city and a sparse town at the same time. HDBSCAN examines all density levels and keeps the groupings that persist across them.

How it works

          . .. .....::::..... .        <- dense crescent = cluster
        .   ...:::::::::... .
   x                                   <- lone point = noise
              ....:::....
             ..:::::::::..             <- second cluster, different density
              ....:::....

Three ideas, in order. First, measure how crowded each point's neighbourhood is. Second, connect points that sit in each other's crowded regions — clusters grow along chains of density, which is why shape does not matter. Third, watch clusters appear and dissolve as the density bar rises, and keep the ones that survive longest. Points never caught in a surviving cluster are noise.

You state one preference: the smallest group size you would call a real cluster. That is a question about your problem, not about geometry — far easier to answer than "how many clusters exist?"

A real example you have seen

Map apps mark "busy areas" for restaurants and traffic. Those regions are irregular blobs following roads and markets — never neat circles — and isolated pins must not invent a hotspot. Density clustering handles exactly this.

Remember this

  • Clusters are dense regions, so any shape works and the count is discovered, not guessed.
  • Points that fit nowhere are labelled noise — that honesty is a feature.
  • You choose only the minimum cluster size worth caring about.

What to learn next

Developer — Code and libraries.

Setup

bash
pip install scikit-learn

HDBSCAN has lived in scikit-learn itself since version 1.3 — no separate hdbscan package needed. Outputs verified with scikit-learn 1.7.2 on CPU.

Two moons and some litter

Two crescent shapes — K-means' classic failure case — plus 20 random noise points:

hdbscan_moons.py
import numpy as np
from sklearn.cluster import HDBSCAN
from sklearn.datasets import make_moons

X, _ = make_moons(n_samples=200, noise=0.07, random_state=3)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform(-1.5, 2.5, size=(20, 2))])   # sprinkle random noise

hdb = HDBSCAN(min_cluster_size=10).fit(X)
labels = hdb.labels_

print("clusters found:", sorted(set(labels) - {-1}))
for c in sorted(set(labels) - {-1}):
    print(f"  cluster {c}: {int((labels == c).sum())} points")
print("flagged as noise:", int((labels == -1).sum()), "points")
Output
clusters found: [0, 1]
  cluster 0: 103 points
  cluster 1: 99 points
flagged as noise: 18 points

The walkthrough

Nobody told it "2". It recovered both crescents — 103 and 99 points against the 100-each truth — from density alone. K-means with n_clusters=2 splits these moons down the middle instead, gluing each half-moon to the wrong partner.

labels_ == -1 means noise. Not "cluster minus one" — it is the deliberate no-cluster verdict. 18 of our 20 planted noise points were caught; a couple landed close enough to a crescent to be absorbed. Count your -1 points before doing anything downstream.

min_cluster_size=10 is the one decision that matters: groups smaller than 10 are never promoted to clusters. Raise it and small clusters dissolve into noise; lower it and noise starts crystallising into micro-clusters.

min_samples (defaults to min_cluster_size) sets how conservative the density estimate is. Higher values declare more points noise. Tune it second, and gently.

Probabilities exist too. hdb.probabilities_ gives each point's strength of membership — 1.0 deep inside a cluster, falling toward 0 at the fringe.

Common mistakes

Feeding unscaled features. Density is measured with distances, so a big-ranged column dictates the density landscape. Scale features first, exactly as with K-means.

Treating noise as an error to eliminate. Tempted to shrink min_cluster_size until every point gets a label? You are then inventing clusters out of scatter. Noise is the algorithm telling the truth about your data.

Expecting stable labels across reruns with edited data. Add or drop points and cluster ids may renumber and borders shift. Compare groupings with proper metrics, not by id.

Using HDBSCAN in high dimensions and trusting the result blindly. Past a few dozen dimensions, distances concentrate and "density" loses meaning. Reduce dimensions first — this pairs naturally with embedding-based workflows like text embeddings.

Try it yourself

Set min_cluster_size=50 and rerun — watch both moons survive but the noise count grow. Then set it to 5 and count the phantom micro-clusters. Find the range where the answer is stable; stability across settings is the real sign of structure.

What to learn next

Researcher — Mathematics and papers.

From DBSCAN to a hierarchy

DBSCAN (Ester, Kriegel, Sander, Xu, 1996) fixes a radius $\varepsilon$ and a count minPts, defines core points as those with $\ge$ minPts neighbours within $\varepsilon$, and forms clusters as connected components of core points. Its weakness is the single global $\varepsilon$: no one value handles clusters of differing densities.

HDBSCAN (Campello, Moulavi, Sander, 2013; expanded with Zimek in 2015) removes $\varepsilon$ by building the entire density hierarchy. Define the core distance $\mathrm{core}_k(x)$ as the distance from $x$ to its $k$-th nearest neighbour, and the mutual reachability distance:

$$ d_{\mathrm{mreach}}(a, b) = \max{\mathrm{core}_k(a),\, \mathrm{core}_k(b),\, d(a, b)} $$

Where:

  • $d(a,b)$ — the base metric (Euclidean unless chosen otherwise).
  • $\mathrm{core}_k(\cdot)$ — a point's local density scale; sparse points get inflated distances.
  • $k$ — the min_samples parameter.

This inflation pushes sparse points away from everything, so chance bridges through low-density regions break.

The algorithm

  1. Build the minimum spanning tree of the complete graph under $d_{\mathrm{mreach}}$.
  2. Remove edges in decreasing weight order — this sweeps a density threshold and yields a dendrogram of connected components.
  3. Condense the tree: a component that falls below min_cluster_size when it splits is treated as the parent shedding points, not as a genuine split.
  4. Score each candidate cluster by stability — the integral of its membership over the density parameter $\lambda = 1/\varepsilon$ — and select a non-overlapping set of clusters maximising total stability. Points outside every selected cluster are noise.

Complexity: the MST via dual-tree Borůvka runs near $O(n \log n)$ for low-dimensional Euclidean data; worst case $O(n^2)$. Memory is $O(n)$ beyond the neighbour queries.

Relations and extensions

  • Single-linkage connection: the mutual-reachability MST is exactly robust single linkage in the sense of Chaudhuri and Dasgupta (2010), giving HDBSCAN consistency arguments for recovering the density cluster tree of the underlying distribution.
  • OPTICS (Ankerst et al., 1999) is the earlier all-$\varepsilon$ ordering approach; HDBSCAN supersedes it with a principled flat extraction.
  • Soft clustering and prediction: the reference implementation (McInnes, Healy, Astels, JOSS 2017) adds membership vectors and approximate_predict for new points; scikit-learn's port covers the core estimator.
  • GLOSH outlier scores fall out of the same hierarchy, connecting this lesson directly to outlier detection.
  • Standard pairing in modern NLP pipelines: UMAP to ~5 dimensions, then HDBSCAN — the topic-modelling recipe popularised by BERTopic (Grootendorst, 2022).

What to learn next