Interactive guide
Clustering by crowding, not by distance-to-center
K-means asks "which centroid is closest?" DBSCAN asks a completely different question: "how crowded is it around here?" No K, no centroids, just two numbers, eps and minPts, that decide how dense is dense enough.
Three kinds of point, decided locally
For every point, DBSCAN counts how many other points sit within eps of it. Reach at least minPts neighbors (including itself) and it's a core point: the anchor of a dense region. Fall short, but still land within eps of some core point, and it's a border point, pulled into that region without qualifying on its own. Everyone else is noise.
Clusters grow by chaining core points together: start at any core point, absorb everything in its eps-neighborhood, and for every neighbor that's also core, absorb its neighborhood too. The chain only stops where the density does, which is exactly why DBSCAN doesn't care what shape a cluster is, only whether it stays dense all the way through.
40 points below sit in two clusters of different density plus scattered noise. Drag the sliders and watch the same points relabel themselves in real time.
Region-growing, from every core point
-
1
Pick an unvisited point
Count its neighbors within eps. Fewer than minPts and it's marked noise, for now.
-
2
Enough neighbors → it's core
Start a new cluster and add every one of its neighbors to a queue.
-
3
Expand the queue
Each queued point joins the cluster. If it's core too, its neighbors get queued as well: noise gets upgraded to border the moment this happens.
-
4
Repeat until nothing's left
Move to the next unvisited point and start over: new cluster, or noise for good this time.
Click any point to see why it's labeled that way
core border noise dashed circle = eps around the clicked point.
Try this: start from Reset to untuned: eps too small slices the sparser cluster into scraps and calls half of it noise. Then press Snap to tuned. Same points, same true groups; just two numbers changed, and DBSCAN suddenly agrees with what your eye already saw. Push eps far enough and watch both clusters melt into one: density has no built-in sense of "too far."
The shape k-means can't see
K-means assigns every point to its nearest centroid, which only ever carves space into convex regions; it has no way to represent a cluster that curves around another one. DBSCAN never computes a centroid at all; it only asks whether density stays connected, so shape is irrelevant. Two interleaving moons make the difference impossible to miss.
DBSCAN
- Purity
- —
- Noise
- —
K-Means (K=2)
- This attempt
- —
- Best so far
- —
However many random starting points k-means gets, its centroids can only draw a straight dividing line through this data: some of one moon's tips always end up closer to the other moon's centroid. Even the best of 20 restarts stays well short of DBSCAN's single well-tuned attempt.
The jargons
Two numbers, eps and minPts, decide everything: together they define what “dense” means, and every other term here — core, border, noise, density-reachable — just describes where a point lands once that definition is fixed.
The neighborhood radius: how close two points must be to count as neighbors at all. Too small and everything looks like noise; too large and separate clusters merge.
The minimum neighborhood size (including the point itself) needed to call a point core. Higher minPts demands denser evidence before starting a cluster.
Has at least minPts points within eps of it, dense enough on its own to anchor a cluster.
Not dense enough to be core itself, but within eps of a core point, pulled into that cluster from the edge.
Neither core nor within reach of any core point. Not forced into any cluster: DBSCAN is one of the few clustering methods that gets to say "this doesn't belong anywhere."
Point B is density-reachable from core point A if there's a chain of core points, each within eps of the next, linking A to B. This chaining is what lets clusters take any shape.