DBSCAN Clustering
Introduction
DBSCAN — Density-Based Spatial Clustering of Applications with Noise — groups points that are packed closely together and labels points sitting alone in low-density regions as noise. Instead of asking “which of k centers is each point nearest to?”, DBSCAN asks “is this point in a crowded neighborhood, and who else is in that same crowd?”
That single shift in perspective gives DBSCAN two abilities that centroid methods like k-means lack: it can discover clusters of arbitrary shape (rings, spirals, crescents — not just round blobs), and it can flag outliers rather than forcing every point into a cluster. It also does not need you to choose the number of clusters in advance.
Core intuition: a cluster is a region where points are densely packed, separated from other clusters by regions of low density. Density is measured by counting how many neighbors a point has within a radius ε.
The two parameters
DBSCAN has exactly two knobs, and everything else follows from them:
ε (eps) — the radius
The radius of the neighborhood around each point. The ε-neighborhood of a point p is the set of all points within distance ε of p:
Nε(p) = { q : dist(p, q) ≤ ε }
Distance is usually Euclidean. ε controls how close points must be to count as “neighbors.”
minPts — the density threshold
The minimum number of points that must lie within ε (including the point itself) for a region to count as dense. A point whose ε-neighborhood has at least minPts members is a core point.
A common rule of thumb is minPts ≥ dimensions + 1, and often 2×dimensions. For 2D data, values around 4 are typical.
The point taxonomy
Given ε and minPts, DBSCAN sorts every point into one of three roles. Understanding these three categories is the heart of the algorithm.
Core point
Has at least minPts points within its ε-neighborhood (counting itself). Core points sit in the dense interior of a cluster and are what allow clusters to grow.
Border point
Has fewer than minPts neighbors (so it is not core), but lies within ε of at least one core point. Border points sit on the fringe of a cluster — close enough to belong, but not dense enough to extend it.
Noise point (outlier)
Neither a core point nor within ε of any core point. Noise points are not assigned to any cluster — this is how DBSCAN performs built-in outlier detection.
Subtle point: a point that is unreachable from any core point at one setting of (ε, minPts) is noise, but the same point may become a border point if you raise ε or lower minPts. Border points are also a known source of ambiguity: a border point within ε of cores from two different clusters is assigned to whichever cluster reaches it first.
Density-reachability: how clusters grow
DBSCAN builds clusters by chaining together core points and the points they can reach. Three related definitions make this precise:
- Directly density-reachable: a point q is directly density-reachable from p if p is a core point and q is within ε of p (q ∈ Nε(p)).
- Density-reachable: q is density-reachable from p if there is a chain of points p = p₁, p₂, …, pₙ = q where each pᵢ₊₁ is directly density-reachable from pᵢ. (Every link except possibly the last must be a core point.)
- Density-connected: two points are density-connected if there exists some core point o from which both are density-reachable. A cluster is a maximal set of density-connected points.
Density-reachability is not symmetric: a border point is density-reachable from a core point, but not the reverse (the border point is not core, so nothing is directly reachable from it). Density-connectivity restores symmetry and is what actually defines a cluster.
The algorithm, step by step
- Mark all points as unvisited. Pick an arbitrary unvisited point p.
- Retrieve its ε-neighborhood. If it contains fewer than minPts points, provisionally label p as noise (it may be reclaimed later as a border point) and move on.
- Otherwise p is a core point: start a new cluster and add p to it.
- Expand the cluster. For every point q in p's neighborhood: if q was labeled noise, reclaim it as a border point of this cluster. If q is unvisited, add it to the cluster, then retrieve q's ε-neighborhood; if q is itself a core point, append all of its neighbors to the set of points still to process (this is how the cluster grows along chains of density-reachability).
- When no more reachable points remain, the cluster is complete. Return to step 1 with the next unvisited point until every point is processed.
Complexity: the naive version computes a neighborhood for each point by scanning all others — O(n²) time. With a spatial index (k-d tree, ball tree, R*-tree) for fast neighbor queries, the average case drops to about O(n log n). Memory is O(n) (no full distance matrix is required when neighborhoods are computed on demand).
Interactive DBSCAN visualizer
Below is a dataset of two interleaving crescents (“moons”) plus a scatter of noise — a shape no centroid method can cluster correctly. Adjust ε and minPts and watch DBSCAN run for real: neighborhoods are recomputed, points are reclassified as core / border / noise, and clusters merge or split live. Hover a point to see its ε-neighborhood.
Hover any point to see its ε-neighborhood (dashed circle). Points inside it get a yellow ring.
Solid dot = core point. Hollow ring = border point. Gray ✕ = noise.
Parameters
Bigger ε → larger neighborhoods → clusters merge.
Higher minPts → denser regions required → more noise.
Result
Try this:
- Set ε small — the two moons shatter into noise.
- Raise ε — each moon becomes one cluster.
- Raise ε too far — both moons merge into one.
- Raise minPts — sparse edges turn to noise.
Legend
- Core point (solid)
- Border point (hollow)
- ✕Noise / outlier
Advantages vs. limitations
✓ Advantages
- • Finds clusters of arbitrary, non-convex shape
- • Detects and isolates noise / outliers automatically
- • No need to specify the number of clusters k in advance
- • Robust to outliers (they do not distort a centroid)
- • Only two parameters to tune (ε and minPts)
- • Deterministic given the data and parameters*
*Up to the assignment of ambiguous border points, which can depend on point processing order.
✗ Limitations
- • Struggles with clusters of varying density — a single ε cannot fit both dense and sparse clusters
- • Sensitive to the choice of ε; small changes can merge or shatter clusters
- • The curse of dimensionality: distances become nearly uniform in high dimensions, so density loses meaning
- • Needs a meaningful distance metric and feature scaling
- • Border-point assignment can be order-dependent
Picking ε: a standard heuristic is the k-distance plot. Fix k = minPts, compute each point's distance to its k-th nearest neighbor, sort these distances ascending, and plot them. The “elbow” (sharp upward bend) marks a good value of ε — below it points are inside clusters, above it they are noise. The variable-density problem motivated HDBSCAN, which removes the single fixed ε.
DBSCAN vs. k-means
| Aspect | DBSCAN | k-means |
|---|---|---|
| Cluster model | Dense regions of any shape | Spherical blobs around centroids |
| Need to pick k? | No — k emerges from the data | Yes — k is required up front |
| Handles outliers | Yes — labels them as noise | No — every point is forced into a cluster |
| Arbitrary shapes | Yes (moons, rings, spirals) | No — assumes convex, roughly round clusters |
| Varying density | Struggles (single ε) | Not density-based; partitions by nearest centroid |
| Determinism | Deterministic (modulo border ties) | Depends on random centroid initialization |
| Parameters | ε, minPts | k |
The interactive demo above makes the contrast vivid: the two moons are not linearly separable and their centroids would sit in empty space, so k-means with k = 2 slices each moon in half. DBSCAN follows the density along each crescent and recovers the true structure — while discarding the scattered points as noise.
Key Takeaways
- DBSCAN defines clusters as dense, density-connected regions separated by sparse regions, not by distance to a centroid.
- It has two parameters: ε (neighborhood radius) and minPts (the density threshold for a core point).
- Every point is a core (≥ minPts neighbors within ε), a border (within ε of a core but not core itself), or noise (neither).
- Clusters grow by following chains of density-reachability from core point to core point.
- Strengths: arbitrary-shaped clusters, automatic outlier detection, no need to pick k. Weaknesses: varying density, sensitivity to ε, and the curse of dimensionality.
- Unlike k-means, DBSCAN does not assume spherical clusters, does not require k, and can leave points unassigned as noise.