6 · Hierarchical + DBSCAN: clusters of any shape
When K-Means' spherical-cluster assumption fails, reach for hierarchical clustering or DBSCAN — density-based, outlier-native, no K required.
When K-Means' spherical-cluster assumption fails, reach for hierarchical clustering (no K needed) or DBSCAN (handles arbitrary shapes + outliers natively).
Without this:
Without alternatives, K-Means on a crescent-shaped dataset gives garbage and you wouldn't know why.
K-Means works beautifully when clusters are roughly spherical and similarly sized. But many real datasets have structure K-Means cannot represent — crescents, rings, chains, or datasets with outliers. Two algorithms address these failure modes:
Hierarchical (agglomerative) clustering starts with each point as its own cluster, then repeatedly merges the two closest clusters until all points belong to a single cluster. This builds a dendrogram — a tree of merges. You can cut the dendrogram at any height to get any number of clusters from 1 to N. The key choice is the linkage criterion, which defines "closest" between two clusters:
| Linkage | Distance between clusters A and B | |---|---| | Single | min distance between any point in A and any point in B | | Complete | max distance between any point in A and any point in B | | Average | mean distance across all pairs (A, B) | | Ward | minimise within-cluster variance increase at merge (similar to K-Means objective) |
Ward linkage is usually the best default — it produces compact, similarly-sized clusters.
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) works completely differently. It defines structure through density:
- A point is a core point if it has ≥
min_samplesneighbours within distanceeps. - A point is a border point if it is within
epsof a core point but has fewer thanmin_samplesneighbours itself. - A point is noise (label = −1) if it is neither core nor reachable from any core point.
- A cluster = one core point + all points reachable from it (directly or transitively).
DBSCAN's superpower: it can discover clusters of any shape — crescents, rings, chains — without specifying K. Its noise label natively identifies outliers. Weakness: the eps and min_samples hyperparameters are hard to choose without domain knowledge.
Python (in browser)
Ward hierarchical clustering dendrogram — large jumps in merge height mark natural cluster boundaries. Cutting at K=4 produces the four blob clusters.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
K-Means vs DBSCAN on the crescent (make_moons) dataset — K-Means cuts each crescent in half; DBSCAN perfectly recovers the two arms.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
DBSCAN with 10 injected outliers — the noise label (−1) natively identifies them without a separate anomaly detection step.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
DBSCAN's 3×3 hyperparameter grid on make_moons — eps too small fragments clusters; eps too large merges everything; min_samples controls noise tolerance.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Algorithm selection guide — when to choose K-Means vs hierarchical vs DBSCAN.
On the make_moons dataset, why does K-Means fail to recover the two crescents?
- Hierarchical (Ward) clustering builds a dendrogram from the bottom up — cut it at any height to get any K without refitting.
- DBSCAN defines clusters via density connectivity — a point is core if it has ≥ min_samples neighbours within eps; noise points (label=−1) are natural outliers.
- DBSCAN finds arbitrarily shaped clusters (crescents, rings) because it uses density connectivity, not Voronoi boundaries — K-Means' assumption of spherical clusters is not required.
- Choosing eps and min_samples for DBSCAN is the hard part — use the k-distance plot heuristic as a starting point, then tune visually.
- Algorithm selection: K-Means for spherical clusters + known K; Hierarchical for hierarchy exploration; DBSCAN for arbitrary shapes + outliers + unknown K.
Anomaly detection (DBSCAN's noise label = anomaly); customer-journey clustering with hierarchical methods; spatial / GIS clustering of incidents using DBSCAN; gene expression heatmaps use hierarchical clustering's dendrograms.
If you remove it: You'd be stuck with K-Means and produce wrong clusterings on every non-blob-shaped dataset.