DBSCAN & Hierarchical Clustering
How does DBSCAN work?
DBSCAN groups points that are densely packed together and labels sparse points as noise. It needs two parameters: eps (a neighborhood radius) and minPts (how many neighbors make a region “dense”).
Has enough points within eps — the seed of a cluster.
Within eps of a core point but not dense itself.
Not reachable from any core point — left unclustered as an outlier.
- “Do you specify the number of clusters?” — No — DBSCAN discovers it from the data, unlike K-Means.
DBSCAN vs K-Means — when to use which?
They make different assumptions about cluster shape and outliers.
- Finds arbitrary shapes (crescents, rings).
- Detects outliers as noise automatically.
- No need to pick k; struggles with varying densities and high dimensions.
- Assumes round, similarly-sized clusters.
- Every point is forced into a cluster — outliers distort centroids.
- Fast and scalable; needs k up front.
How do you choose eps and minPts?
minPts is often set to roughly 2 × dimensions. For eps, use a k-distance plot: sort each point's distance to its k-th neighbor and look for the “elbow” — the knee marks a good radius.
DBSCAN is sensitive to eps: too small and everything is noise; too large and clusters merge. It also assumes a single global density, so clusters of very different densities are hard — that's what HDBSCAN improves on.
How does hierarchical (agglomerative) clustering work?
Agglomerative clustering starts with every point as its own cluster and repeatedly merges the two closest clusters until one remains, building a tree. The definition of “closest” is the linkage.
Can chain into long, straggly clusters.
Compact, roughly equal-diameter clusters.
Merges to minimize within-cluster variance — a common default.
What is a dendrogram and how do you cut it?
A dendrogram is the tree of merges, with the merge distance on the vertical axis. Cutting it at a chosen height gives a clustering — a higher cut yields fewer, larger clusters.
- “How do you pick where to cut?” — Cut where there's a large vertical gap between merges, or to get a target number of clusters.
- “What's the cost?” — Naive agglomerative clustering needs ~O(n²) memory and ~O(n³) time (reducible to O(n² log n) with a priority queue), so it doesn't scale to huge datasets like K-Means does.