Hierarchical Clustering
Press Next → or use ← → arrow keys
The Intuition — The Librarian's Bookshelf
Every merge is recorded, so the whole history forms a branching tree. Want four groups? Cut the tree where four branches exist. Want two? Cut higher. That tree is a dendrogram, and building it is hierarchical clustering.
Unlike K-Means, you don't commit to the number of clusters before running. One fit produces a full tree of every possible grouping — you decide K afterward by choosing where to cut.
Bottom-Up vs Top-Down
Agglomerative (AGNES) starts from singletons and merges upward —
it's what people almost always mean by "hierarchical clustering."
Divisive (DIANA) starts from one cluster and splits downward;
it's elegant but O(2ⁿ) and rarely used in production.
Agglomerative Clustering — Five Steps
Step 4 is where the personality of the algorithm lives. "Distance between two clusters" isn't one thing — it depends on the linkage rule (single, complete, average, Ward…), and that choice can completely change the shape of the clusters you get.
Building The Dendrogram — Five Cities
A and B merge first (distance 10), then C and D (20), then E joins them (30), and finally the two groups fuse at the top (55). The height of each bar is how different the merged clusters were. Slide a cut line to d≈40 and it crosses two branches → two clusters: {A,B} and {C,D,E}.
How To Measure Distance Between Clusters
Single uses the closest pair (can chain into long straggly clusters). Complete uses the farthest pair (tight, compact). Average takes the mean of all pairs (a balanced compromise). Ward merges whichever pair adds the least within-cluster variance — the go-to default for tabular data.
Linkage Methods — Behaviour & Best Fit
| Linkage | Distance rule | Behaviour | Best for |
|---|---|---|---|
| Single | Min pairwise | Chaining → elongated | Manifolds, irregular shapes |
| Complete | Max pairwise | Tight; outlier-sensitive | Equal-size, compact clusters |
| Average (UPGMA) | Mean pairwise | Balanced compromise | General purpose, bioinformatics |
| Ward ⭐ | Min variance increase | Compact, balanced | Most tabular tasks (default) |
| Centroid / Median | Centroid distance | Can invert dendrogram | Rarely used today |
Ward's method is built on minimizing squared-error variance, so it's only mathematically meaningful with Euclidean distance. If you need cosine or Manhattan distance (text, sparse, or profile data), use average or complete linkage instead.
Choosing The Distance Metric
Ask what "similar" means for your data. Similar values → Euclidean. Similar direction regardless of scale → cosine. Similar shape over time → correlation distance. Similar categories → Hamming. The metric encodes your definition of similarity.
Reading The Tree — The Biggest-Gap Rule
Find the longest vertical stretch that no horizontal merge crosses — the biggest jump in dissimilarity — and cut just below where it ends. The number of vertical lines your cut crosses is the natural K. Here the tall gap before the final merge gives a clean 3 clusters.
Back Up The Cut With Numbers
s = (b−a)/max(a,b). Sweep K=2–10 and keep the peak; > 0.5 signals solid structure.The dendrogram gives you a visual candidate K; the metrics confirm it objectively. In a typical 150-sample run, K=3 topped the silhouette at 0.72 — matching the biggest visual gap. When the two disagree, trust the metric and re-examine the tree.
Scale Before You Cluster
Hierarchical clustering is built entirely on distances, and distance is dominated by whichever feature
has the largest range. If income spans 0–100,000 and age spans 0–100, the tree
forms on income alone. StandardScaler (or MinMaxScaler) first puts every feature on an
equal footing.
scipy To Explore · sklearn To Ship
# ── scipy: build + visualize the tree ── from scipy.cluster.hierarchy import linkage, dendrogram, fcluster from sklearn.preprocessing import StandardScaler X_scaled = StandardScaler().fit_transform(X) # always scale first Z = linkage(X_scaled, method='ward', metric='euclidean') dendrogram(Z, color_threshold=5.0) # inspect the gaps labels = fcluster(Z, t=3, criterion='maxclust') # ── sklearn: production clustering ── from sklearn.cluster import AgglomerativeClustering hac = AgglomerativeClustering(n_clusters=3, linkage='ward') labels = hac.fit_predict(X_scaled)
Use scipy's linkage + dendrogram to explore the tree and pick
K, then switch to sklearn's AgglomerativeClustering for the production fit.
Prefer distance_threshold over n_clusters when you'd rather cut by a
dissimilarity height than a fixed count.
The Cost — And When To Stop
| Method | Time | Space | Practical limit |
|---|---|---|---|
| Naive agglomerative | O(n³) | O(n²) | ~1,000 rows |
| Optimized (NN-chain) | O(n²) | O(n²) | ~10,000 rows |
| sklearn | O(n² log n) | O(n²) | ~50,000 rows |
| K-Means (for contrast) | O(nKt) | O(nK) | Millions |
Storing all pairwise distances for 10,000 points is 100 million values (~800 MB); it grows with the square of your data. Past ~50,000 rows, cluster a random 5,000–10,000 sample to find K and the structure, then run K-Means (or DBSCAN) on the full dataset.
Hierarchical vs K-Means
| Property | Hierarchical | K-Means |
|---|---|---|
| Pre-specify K? | No — cut after | Yes — up front |
| Cluster shapes | Arbitrary (linkage-dependent) | Spherical only |
| Scalability | ≤ ~50K rows | Millions |
| Deterministic? | Yes | No (random init) |
| Interpretability | Very high (dendrogram) | Moderate |
| Best use case | Exploration, unknown K, small data | Large data, known K, speed |
Choose hierarchical when the dataset is under ~50K rows, K is unknown, and you want the interpretable story a dendrogram tells. Choose K-Means when data is large, K is known, clusters are roughly round, and speed matters most.
Where The Dendrogram Earns Its Keep
In genomics, taxonomy, and phylogenetics, the nesting itself is the insight — which groups are sub-groups of which. That's a story K-Means can't tell, and it's why hierarchical clustering remains the default in these fields.
Seven Rules For Hierarchical Clustering
You Now Own Hierarchical Clustering
Hierarchical clustering merges the closest clusters over and over, recording a dendrogram that encodes every possible K at once. Pick a linkage (usually Ward), scale your features, read the tree by its biggest gap, and confirm K with a silhouette — no cluster count needed up front.
Build dendrograms on Iris and a customer dataset with scipy, try Ward vs average vs complete on the same data to feel the difference, then compare against K-Means and DBSCAN to know when each is the right tool.
🌳 End of tutorial · Press ← to review, or click Restart