DBSCAN & Density Clustering

Finding arbitrary-shaped clusters and identifying noise outliers without specifying cluster count k.

🟡 intermediate4 min readunsupervised

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) groups points based on spatial density rather than centroids. Given neighborhood radius ε (eps) and minimum points minPts, points are categorized as Core Points, Border Points, or Noise Outliers. DBSCAN discovers clusters of arbitrary shapes (concentric rings, spirals), handles noise natively, and does not require specifying k upfront.

The Three Point Types in DBSCAN

DBSCAN requires two hyperparameters:

eps ( $\epsilon$ ): Neighborhood search radius.
minPts: Minimum number of points required within $\epsilon$ -radius to form a dense region.

       Core Point (>= minPts)          Border Point (< minPts, near Core)     Noise Outlier
           o  o  o                            o                                   x
         o   (C)   o                             (B) ──► Near (C)
           o  o  o

Core Point: Has $\ge \text{minPts}$ points within distance $\epsilon$ .
Border Point: Has $< \text{minPts}$ points within distance $\epsilon$ , but falls within $\epsilon$ -neighborhood of a Core Point.
Noise Outlier: Neither a Core Point nor a Border Point. Labeled $-1$ .

Algorithm Mechanics

For each unvisited point $p$ $p$ :
- Find all points in $\epsilon$ -neighborhood $N_\epsilon(p)$ .
- If $|N_\epsilon(p)| < \text{minPts}$ , mark $p$ as Noise (provisionally).
- If $|N_\epsilon(p)| \ge \text{minPts}$ , mark $p$ as Core Point and start a new Cluster $C$ .
Expand Cluster $C$ $C$ :
- Add all points in $N_\epsilon(p)$ to $C$ .
- For any neighbor $q \in N_\epsilon(p)$ that is also a Core Point, add its neighbors $N_\epsilon(q)$ to cluster expansion queue.
Repeat until all points are visited.

Algorithm Comparison

Feature	k-Means	Hierarchical (Agglomerative)	DBSCAN
Cluster Shapes	Spherical / Convex	Depends on Linkage	Arbitrary non-convex shapes
Specify $k$ Upfront?	Yes	No (Cut dendrogram)	No (Discovered automatically)
Noise & Outliers	Sensitive (Pulls centroids)	Sensitive	Robust (Labels noise as -1)
Time Complexity	$O(N \cdot k \cdot d)$	$O(N^3)$	$O(N \log N)$ with KD-Trees
Vulnerability	Initial seeds	High compute	Variable density clusters

Say this out loud

"DBSCAN clusters data based on spatial density using radius eps and minPts. Points with at least minPts neighbors within eps are Core Points; points near Core Points are Border Points; remaining unassigned points are Noise Outliers. DBSCAN discovers arbitrary non-spherical shapes, ignores noise, and doesn't require pre-specifying k, but struggles when clusters have varying densities."

Follow-ups to expect

What is HDBSCAN? Hierarchical DBSCAN. It runs DBSCAN across varying $\epsilon$ values, building a density hierarchy that automatically extracts optimal clusters across varying density regions.
How do you choose eps and minPts? Set $\text{minPts} = 2 \cdot d$ (twice feature dimension). Plot a $k$ -NN distance graph (sorting points by distance to $k$ -th nearest neighbor) and select eps at the inflection "elbow" point.

Check yourself

Question 1 of 3

How does DBSCAN classify a data point p if its ε-neighborhood contains at least minPts points?

More in Classical ML

See all →

Bias–Variance Tradeoff4 min Overfitting vs Underfitting3 min Linear Regression4 min