DBSCAN: Density-Based Clustering

Density instead of distance to a centroid

DBSCAN - Density-Based Spatial Clustering of Applications with Noise, published by Ester, Kriegel, Sander and Xu in 1996 - takes a completely different view of a cluster than k-means. Instead of measuring distance to a centroid, it asks whether a point sits in a dense neighbourhood, and grows clusters by chaining together points that are mutually reachable through dense regions. Two parameters define density: eps, a radius, and minPts, the number of points (including the point itself) that must fall within that radius for the neighbourhood to count as dense.

Core points, border points, noise

Every point falls into one of three categories. A core point has at least minPts points, itself included, within eps - it is unambiguously inside a dense region. A border point is not itself dense enough to be a core point, but lies within eps of one that is, so it gets pulled into that cluster from the edge. Anything that is neither is noise and is never forced into a cluster - it is simply labelled an outlier, which is a genuine output of the algorithm rather than a failure of it.

for (const p of points) {
  if (p.visited) continue;
  p.visited = true;
  const nbrs = regionQuery(p, eps);
  if (nbrs.length < minPts) { p.label = 'noise'; continue; }   // not dense enough
  const cluster = newCluster();
  expandCluster(p, nbrs, cluster, eps, minPts);                 // chain-grow through core points
}

Why clusters can be any shape

expandCluster works by density-reachability: if point A is a core point and point B is within eps of A, B joins A's cluster, and if B is also a core point the search continues outward from B too. Because the chain follows wherever density leads rather than measuring distance to one fixed centre, a cluster can trace a crescent, a spiral, or two concentric rings - shapes that would confuse a centroid-based method entirely. The trade-off is that a single narrow bridge of dense points can accidentally connect two clusters a human would consider separate, which is why eps needs to be tuned rather than guessed.

Setting eps and minPts

minPts is usually set to roughly twice the number of dimensions, with a practical floor of 3 or 4 in two dimensions. For eps, the standard heuristic computes, for every point, the distance to its minPts-th nearest neighbour, sorts those distances, and plots them - the k-distance plot. Dense regions produce small, flat distances; the curve bends sharply upward where points start to thin out, and that elbow is a reasonable eps. Set eps too small and everything becomes noise; set it too large and the whole dataset collapses into one cluster.

Frequently asked questions

Try it live

Everything above runs in your browser - open DBSCAN and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.