DBSCAN and density-based clustering

Two lessons of centroid thinking have hit the same wall twice: moons, rings, and every cluster whose shape is not a blob. The obstruction is the definition — “close to a shared center” is intrinsically convex. Density clustering replaces it: a cluster is a connected region where points are dense, and clusters are separated by regions where they are sparse. No centers, no convexity, no $k$. The canonical algorithm is DBSCAN — and its definition is precise enough to be run in your head, which is exactly what this lesson teaches you to do.

Three kinds of point

Fix a radius $\varepsilon$ and a count minPts. Then:

• A core point has at least minPts neighbors within distance $\varepsilon$ (itself included) — it sits in the interior of a dense region.
• A border point is within $\varepsilon$ of a core point but is not core itself — the edge of a cluster.
• Everything else is noise — a first-class output, not a failure. No centroid method can say “this point belongs to nothing”; DBSCAN says it natively, which is why it doubles as an anomaly detector.

Clusters are then built by connectivity: a cluster is a maximal set of core points reachable from one another through chains of $\varepsilon$-neighbor core points, plus their borders. Because chains can snake, clusters can be any shape that density can trace — moons, rings, spirals.

Choosing the dials

minPts first: a common default is $2d$ (twice the dimensionality), higher for noisier data — it sets how many samples constitute evidence of density. Then $\varepsilon$ via the k-distance plot: for every point compute the distance to its minPts-th nearest neighbor, sort descending, and look for the knee — points left of the knee are in dense regions (small k-distance), points right of it are the would-be noise. The knee’s height is a principled $\varepsilon$. It is the elbow heuristic’s cousin, with the same honest status: guidance, not oracle.

HDBSCAN: all the ε at once

A single global $\varepsilon$ is one horizontal cut through a density hierarchy. HDBSCAN builds the whole hierarchy — conceptually, running DBSCAN for every $\varepsilon$ simultaneously via a minimum spanning tree on “mutual reachability” distances — then selects, per branch, the clusters that are most stable (persist over the widest range of density). The result: clusters of different densities extracted together, a per-point membership strength, and one fewer hyperparameter (only min_cluster_size really remains). In practice HDBSCAN is the modern default for exploratory clustering, with plain DBSCAN kept for when you truly know your scale.

When density fails

Symmetry demands the same honesty centroid methods got:

• The curse of dimensionality. In high dimensions pairwise distances concentrate — everything is nearly equidistant from everything (the fraction of volume within a fixed radius collapses exponentially in $d$). Density estimates need $n$ exponential in $d$; above a few dozen dimensions raw DBSCAN degrades badly. Standard remedy: reduce dimension first (PCA/UMAP), then cluster — with next lesson’s caveats about what those maps distort.
• Varying density breaks single-ε DBSCAN (use HDBSCAN).
• Border ambiguity: border points reachable from two clusters are assigned to whichever was processed first — a small nondeterminism worth knowing exists.
• Cost: naive neighborhood queries are $O(n^2)$ (fine at the widget’s n = 325; painful at 10⁷) — spatial indexes bring it near $O(n \log n)$ in low dimensions but degrade in high ones, the same curse again.

The through-line of three lessons: k-means assumes convex-and-round, GMM assumes Gaussian-shaped, DBSCAN assumes density-separated. None is “the best clusterer” — each is the MLE-or-geometry of a different structural bet, and choosing one is asserting which structure your domain plausibly has.

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
from sklearn.neighbors import NearestNeighbors

X, _ = make_moons(n_samples=300, noise=0.06, random_state=0)

# k-distance plot for eps selection
d, _ = NearestNeighbors(n_neighbors=6).fit(X).kneighbors(X)
print(np.sort(d[:, -1])[::-1][:15])          # look for the knee

db = DBSCAN(eps=0.18, min_samples=6).fit(X)
labels = db.labels_                           # -1 = noise, a first-class answer
print("clusters:", labels.max() + 1, " noise:", (labels == -1).sum())

Exercises