Density-based clustering: DBSCAN & HDBSCAN

Two short chains of points, plus one point sitting far off on its own. Drag eps — the neighborhood radius — and watch clusters appear, merge, and disappear. Too small, and even points one unit apart look unrelated; too large, and two genuinely separate chains fuse into one.

DBSCAN — short for Density-Based Spatial Clustering of Applications with Noise — never asks how many clusters to expect. Instead, a point is a core point if it has enough neighbors within a radius eps:

• $\text{core}(i)$ — whether point $i$ qualifies as a core point, based on how many neighbors it has.
• $x_i, x_j$ — two points in the dataset being compared.
• eps — the neighborhood radius: how close two points must be to count as neighbors.
• minPts — the minimum number of neighbors within eps needed for a point to be a core point.

1. Clusters grow by hopping between core points

   A cluster is everything reachable by hopping from core point to core point, radius by radius — like a chain of falling dominoes, each one only needing to be close enough to knock over the next.

2. Unreached points are noise

   Anything never reached this way, from any core point, is noise — not assigned to any cluster at all.

At eps=0.5, even points exactly $1$ unit apart aren't neighbors — every point is isolated, and the whole dataset is noise. At eps=1.5, both chains connect internally without merging with each other. At eps=5.0, the two chains fuse into a single cluster — genuinely different structures, collapsed together by too generous a radius.

Two chains at $y=0$ and $y=5$, points spaced $1$ unit apart within each chain, plus one point at $(10,10)$:

1. Checking a core point

   Point $(1,0)$ has neighbors $(0,0)$ and $(2,0)$, both at distance exactly $1$ — with eps=1.5 and minPts=1, that's enough: it's a core point.

2. The gap between chains

   The closest pair across the two chains is $(0,0)$ and $(0,5)$, at distance exactly $5$. At eps=1.5, that's nowhere close enough to connect — the chains stay two separate clusters.

3. The point with no neighbors at all

   $(10,10)$'s nearest other point is $(2,5)$: $\sqrt{(10-2)^2+(10-5)^2}=\sqrt{64+25}=\sqrt{89}\approx9.4$ units away — far beyond any reasonable eps. It's never a core point and never reachable from one, so DBSCAN correctly leaves it as noise, folded into neither cluster.