DBSCAN & Density Clustering
Finding arbitrary-shaped clusters and identifying noise outliers without specifying cluster count k.
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$:
- 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$:
- 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
epsat 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?