DBSCAN (Density-Based Spatial Clustering of Applications with Noise) groups points that are densely packed together, and explicitly labels sparse, isolated points as noise — a fundamentally different approach from K-Means, which forces every point into some cluster.
The Three Point Types
| Type | Definition |
|---|---|
| Core point | Has at least min_samples other points within distance eps of it |
| Border point | Not a core point itself, but falls within eps of a core point |
| Noise point | Neither core nor border — isolated, not part of any dense region |
Graphical Intuition
Dense neighborhoods form the cluster core; points on the fringe of that density join as borders; anything too far from any dense region is labeled noise, not forced into a cluster.
The Algorithm, As Explicit Steps
| Step | What Happens |
|---|---|
| 1 | For each unvisited point, count how many other points fall within eps |
| 2 | If that count ≥ min_samples, mark it a core point and start a new cluster |
| 3 | Recursively add every point reachable through a chain of core points within eps to that same cluster |
| 4 | Points not reachable from any core point are labeled noise (\(-1\)) |
Python Implementation
from sklearn.cluster import DBSCAN
import numpy as np
# A dense cluster, plus one far-away isolated point
X = np.array([
[1,1],[1.2,1],[1,1.2],[1.1,1.1],[1.3,0.9], # dense group
[10,10], # isolated -> likely noise
])
model = DBSCAN(eps=0.5, min_samples=3)
labels = model.fit_predict(X)
print(labels) # e.g. [0 0 0 0 0 -1] -- the isolated point gets label -1 (noise)Why DBSCAN Handles Irregular Shapes K-Means Can't
K-Means always produces roughly round, convex clusters, because it assigns points by distance to a single centroid. DBSCAN has no such constraint — it can trace out arbitrarily curved, elongated, or crescent-shaped dense regions, since it only cares about local density, not distance to any single center point.
Choosing eps and min_samples
# A common heuristic for eps: plot the distance to each point's k-th nearest
# neighbor, sorted -- look for a "knee" in the curve, similar to the elbow method
from sklearn.neighbors import NearestNeighbors
import matplotlib.pyplot as plt
k = 4 # often set close to min_samples
neighbors = NearestNeighbors(n_neighbors=k).fit(X)
distances, _ = neighbors.kneighbors(X)
sorted_distances = np.sort(distances[:, k-1])
plt.plot(sorted_distances)
plt.ylabel(f"Distance to {k}-th nearest neighbor")
plt.show() # eps is often chosen around the "knee" of this curvePractical Use Cases
- Anomaly/fraud detection — noise points are directly, explicitly flagged as outliers by the algorithm itself
- Geographic/spatial clustering, where clusters naturally have irregular shapes
- Any dataset with a genuinely unknown number of clusters and some expected noise/outliers
Advantages
- Doesn't require specifying the number of clusters upfront
- Naturally identifies outliers as noise, rather than forcing them into the nearest cluster
- Handles non-round, irregularly shaped clusters
Limitations
- Sensitive to the choice of
epsandmin_samples— poor choices can merge distinct clusters or split one cluster into many - Struggles with clusters of very different densities, since a single global
epsis used everywhere
Common Mistakes
- Using DBSCAN's default parameters without any tuning —
epsin particular is highly dataset-dependent and rarely works well left at an arbitrary default. - Expecting DBSCAN to assign every point to a cluster — some points being labeled noise (\(-1\)) is expected, correct behavior, not a bug.
Interview Relevance
Q: "Why might DBSCAN be a better choice than K-Means for fraud detection?" DBSCAN explicitly labels sparse, isolated points as noise rather than forcing every point into some cluster — this maps naturally onto fraud detection, where fraudulent transactions are often exactly the sparse, non-conforming points that don't fit any dense "normal behavior" region.
Practice Question
A DBSCAN run with a small eps produces dozens of tiny clusters and a huge amount of noise. What adjustment would you try first, and why?
