DBSCAN
A clustering algorithm that grows clusters from dense regions of points, finds clusters of any shape and labels isolated points as noise.
Also density-based clustering · HDBSCAN · core points · noise points
Ester, Kriegel, Sander and Xu, 1996
Look at a city from a plane at night. Bright, crowded patches are towns, however oddly shaped. A few lonely lights in the countryside don't belong to any town.
Where it fits
+All relationships as a list
Is a kind of / part of
Applies to
How it works
k-means assumes round clusters and needs you to say how many there are. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) makes neither assumption.
It works with two settings: a radius and a minimum count, minPts.
- A point with at least minPts neighbors within is a core point: it sits in a dense region.
- Core points that are within of each other are linked into the same cluster, which spreads like a chain reaction.
- Points near a core point but not dense themselves are border points and join that cluster.
- Everything else is noise.
Because clusters grow by following density, they can be long, curved or ring-shaped. And noise points come for free, which makes DBSCAN a handy tool for anomaly detection.
The weak spot is : a single radius cannot suit both a dense city center and sparse suburbs. HDBSCAN, a later extension, builds a hierarchy over many radii (similar in spirit to hierarchical clustering) and handles varying densities better.
Everyday use cases
- Case 01
Finding hotspots on a map
Grouping GPS points of taxi pickups into popular locations of any shape, ignoring scattered one-off trips.
- Case 02
Cleaning sensor data
Points labeled as noise are natural outlier candidates.
Strengths, weaknesses and when to use it
Strengths
- Finds arbitrarily shaped clusters and does not need the number of clusters.
- Built-in notion of noise and outliers.
Weaknesses
- Sensitive to ε; one radius cannot fit clusters of very different density.
- Distances become less meaningful in high dimensions.
When to use itLow-dimensional data with irregular cluster shapes and noise, such as geographic points.
Compare with
Check yourself
- Q01
Which shape can DBSCAN find that k-means cannot?
Show answer
A: Two interlocking crescent moons
- Q02
What happens to a point with too few neighbors that is not near any core point?
Show answer
B: It is labeled as noise