Chapter 20 · Hierarchical Clustering
K-Means demanded k before it would start. Hierarchical clustering refuses the question: merge the two closest points, then the two closest clusters, and keep going until everything is one — producing a dendrogram that contains every k simultaneously. This chapter builds the distance matrix and all four linkage rules by hand, reads the real dendrogram's merge-height cliff, watches single linkage fail catastrophically on real data — and finds the same five mall segments K-Means found, the strongest structural evidence yet.
🎯 Learning Objectives
- Compute a pairwise distance matrix by hand and trace agglomerative merging step by step
- Define all four linkage rules — single, complete, average, ward — and see them disagree on real data
- Read a dendrogram fluently: leaves, merge heights, and the cut line that selects k
- Use the real merge-height cliff as k evidence, alongside Chapter 19's elbow and silhouette
- Compare K-Means and hierarchical clustering honestly — cost, determinism, scale, k
- Recognise when two clustering algorithms agreeing is itself a finding
1. Every k at Once
Chapter 19's awkward opening question — "how many clusters?" — had to be answered before the algorithm ran, and every instrument for answering it (elbow, silhouette) required fitting the model many times. Hierarchical clustering inverts the deal: run once, and receive a complete map of every possible grouping.
The practical family is agglomerative (bottom-up): every customer starts as their own cluster; repeatedly find the two closest clusters and merge them; stop when everything is one cluster. The theoretical twin — divisive (top-down: start with one cluster, split recursively) — is rarely implemented, because deciding the best split is far harder than deciding the best merge. Same mall data as Chapter 19: 200 customers, Income × Spending, and the same question — how many segments, and who is in each?
2. The Distance Matrix & Linkage, by Hand
Two ingredients replace K-Means' centroids. First, the pairwise distance matrix — the distance between every two customers. Second, a linkage rule — how to measure the distance between clusters once they contain more than one point. Five customers on a line, spending scores 1, 2, 6, 8, 9; the full matrix, every entry by hand (|a − b|):
| 1 | 2 | 6 | 8 | 9 | |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 5 | 7 | 8 |
| 2 | 1 | 0 | 4 | 6 | 7 |
| 6 | 5 | 4 | 0 | 2 | 3 |
| 8 | 7 | 6 | 2 | 0 | 1 |
| 9 | 8 | 7 | 3 | 1 | 0 |
Now merge, step by step — and here is where linkage enters:
- Merge 1 (distance 1): {1, 2} — and (checking the matrix) {8, 9} likewise. Singleton distances need no rule.
- Merge 2: {6} joins {8, 9}. Under single linkage the clusters' distance is their closest pair — d(6,8) = 2, so the merge happens at height 2. Under complete linkage it is the furthest pair — max(2, 3) = 3, so height 3.
- Merge 3 (final): {1, 2} absorbs {6, 8, 9}. Single: the closest cross pair is d(2,6) = 4 → height 4. Complete: the furthest is d(1,9) = 8 → height 8.
Same data, same final clusters — but the merge heights differ by linkage, and heights are the dendrogram's entire shape. The four rules, in full:
| Linkage | Cluster distance = | Personality | Watch out |
|---|---|---|---|
| single | min pairwise distance | Friendly — merges on one close pair | Chaining: snakes across gaps (Section 4's real failure) |
| complete | max pairwise distance | Strict — whole clusters must be close | Outliers stretch every distance |
| average | mean pairwise distance | The compromise | Can produce awkward in-between shapes |
| ward | the merge that least increases total WCSS | Compact, balanced clusters | Assumes (roughly) spherical clusters, like K-Means |
3. The Dendrogram
Every merge is drawn as a upside-down U: two branches joining at the merge height. The result — the dendrogram — is the algorithm's complete autobiography. On our real data (ward linkage), the final eight merge heights, top-down:
Notice what the dendrogram adds over elbow and silhouette: it shows which clusters merge at which height — structure at every scale, visible before any k is chosen. Move the cut line down to 100 and you get 6+ clusters; up to 300 and the segments begin fusing into super-groups. No refitting — the tree already contains every answer.
4. Linkage in Practice: a Real Failure
Section 2's little line of points was too polite to expose the linkages' differences. The real mall data is not polite. All four rules, k = 5, same distance metric (real results):
| Linkage | Silhouette | Cluster sizes | Verdict |
|---|---|---|---|
| ward | 0.5530 | 32, 85, 39, 21, 23 | Five balanced segments |
| complete | 0.5530 | 39, 85, 32, 21, 23 | The same partition as ward |
| average | 0.4792 | 38, 102, 36, 21, 3 | Degrading — a 3-customer fragment peels off |
| single | 0.2695 | 3, 193, 1, 1, 2 | Catastrophe — chaining |
Single linkage's 193-customer blob plus four orphans is chaining in its purest form: the rule only needs one close pair to merge, so the cluster snakes from customer to customer across the whole scatter — every intermediate point dragging in its neighbour. Average linkage starts down the same road (that orphan cluster of 3 is the beginning of fragmentation). Ward and complete, both demanding that clusters be coherent as wholes, land on the same balanced five.
linkage='ward' is the right default for blobby data, but
the table above is why you check: swap in single linkage on elongated
data and it may be the right tool (it traces snakes well) while
ward carves them wrongly. Linkage choice encodes a belief about cluster
shape — state it, test it.
5. Implementation in Python
import numpy as np
import pandas as pd
dataset = pd.read_csv('Mall_Customers.csv')
X = dataset.iloc[:, [3, 4]].values # Income, Spending
# 1. The dendrogram (scipy) — the map of every k
import scipy.cluster.hierarchy as sch
dendrogram = sch.dendrogram(sch.linkage(X, method='ward'))
plt.title('Dendrogram'); plt.xlabel('Customers')
plt.ylabel('Euclidean distances'); plt.show()
# read the tallest unbroken spans -> cut -> count clusters
# 2. The cut, as a fitted model (sklearn)
from sklearn.cluster import AgglomerativeClustering
hc = AgglomerativeClustering(n_clusters=5, metric='euclidean',
linkage='ward')
y_hc = hc.fit_predict(X)
print(np.bincount(y_hc)) # [32 85 39 21 23]
# 3. The linkage A/B test of Section 4
from sklearn.metrics import silhouette_score
for link in ['ward', 'complete', 'average', 'single']:
m = AgglomerativeClustering(n_clusters=5, metric='euclidean',
linkage=link).fit(X)
print(link, silhouette_score(X, m.labels_).round(4),
np.bincount(m.labels_))Listing 20.1 — Dendrogram, cut, and the linkage comparison (source: hierarchical_clustering.py, modernised).
affinity='euclidean' was renamed
metric='euclidean' in sklearn ≥ 1.2 (affinity is
deprecated). Old notebooks will show the old spelling — both mean the
distance used between points.
6. The Segments vs K-Means
The climax the chapter has been building toward. Ward hierarchical, k = 5, centres and sizes — side by side with Chapter 19's K-Means segments (all real):
| Segment | K-Means (Ch 19) | Hierarchical ward (Ch 20) | Reading |
|---|---|---|---|
| Target | (87, 82) · 39 | (87, 82) · 39 | Identical |
| Standard | (55, 50) · 81 | (56, 49) · 85 | 4 boundary customers reassigned |
| Careful | (88, 17) · 35 | (89, 16) · 32 | 3 customers differ |
| Careless | (26, 79) · 22 | (25, 80) · 21 | 1 customer differs |
| Sensible | (26, 21) · 23 | (26, 21) · 23 | Identical |
Two algorithms with different machinery — centroid refinement versus merge trees — converge on the same five segments, centres within a point and sizes within a handful of boundary customers. And the ward silhouette sweep peaks at k = 5 (0.5530) exactly where Chapter 19's elbow and silhouette did. Three instruments, two algorithms, one structure. When independent methods agree this closely, the segmentation stops being an algorithmic output and starts being a fact about the customers — the strongest evidence clustering can offer, because in Part IV there is no ground truth to check against.
7. K-Means vs Hierarchical — Settled
| K-Means (Ch 19) | Hierarchical (Ch 20) | |
|---|---|---|
| k | Must be fixed before running | Chosen after, by cutting the dendrogram — every k from one run |
| Output | Centroids + assignments (a deployable model) | Assignments only — no centroid object for new points |
| New points | Assign instantly to nearest centroid | No native answer — refit or improvise (nearest cluster member) |
| Determinism | Init lottery (needs k-means++ and restarts) | Deterministic — same data, same tree |
| Cost | Fast: roughly O(n·k·iterations) | O(n²) distance matrix — memory and time explode on big n |
| Shape bias | Spherical (ward-like) | Depends on linkage — single even traces snakes |
| Best habitat | Production, large data, repeated assignment | Exploration, small-to-medium n, unknown structure at many scales |
8. Strengths, Limits & the Road Ahead
| Strengths | Limitations |
|---|---|
| No k in advance — the dendrogram holds every answer | O(n²) — thousands of rows, not millions |
| Deterministic; rich visual story for stakeholders | No model object — new points don't assign natively |
| Linkage choice adapts to believed cluster shape | Linkage choice is a belief — single linkage fails badly (real: 0.27) |
| Agreement with K-Means = structural evidence | Early merges are greedy and unfixable — no lookahead |
Part IV is complete: two structure-finders, judged without labels and cross-validated by each other's agreement. Part V changes the question one more time — from who groups together to what occurs together. Association rule learning abandons distance entirely: baskets, not points, and patterns like "people who buy X usually buy Y" — starting with the Apriori algorithm and the three numbers that govern it: support, confidence and lift.
🛠 Hands-On: Cut the TreeIntermediate
The segmentation team wants dendrogram-based evidence for k = 5 — not because K-Means said so, but because the tree does. Work the hand example, read the real merge heights, run the linkage gauntlet, and deliver the cross-algorithm verdict.
Steps
- By hand: build the 5×5 distance matrix for {1, 2, 6, 8, 9}; trace merges under single and complete; confirm the final heights 4 vs 8.
- Fit the ward dendrogram on the mall data; extract the last 8 merge heights; locate the gap that argues for k = 5.
- Cut into 5 clusters; extract centres and sizes; match them to Chapter 19's segments.
- Run all four linkages at k = 5; tabulate silhouettes and sizes; name single linkage's failure mode from the numbers.
- Run ward's silhouette sweep k = 2..10; confirm the peak.
- Write the cross-algorithm verdict paragraph: why agreement strengthens the segmentation, and which method ships for exploration vs production.
View Solution / Walkthrough
import numpy as np, pandas as pd
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import silhouette_score
from scipy.cluster.hierarchy import linkage
X = pd.read_csv('Mall_Customers.csv').iloc[:, [3, 4]].values
Z = linkage(X, method='ward')
h = np.sort(Z[:, 2])[::-1]
print('top merge heights:', h[:8].round(0)) # the cliff
for link in ['ward', 'complete', 'average', 'single']:
m = AgglomerativeClustering(n_clusters=5, metric='euclidean',
linkage=link).fit(X)
print('%-9s sil=%.4f sizes=%s' % (link, silhouette_score(X, m.labels_),
np.bincount(m.labels_)))
for k in range(2, 11):
m = AgglomerativeClustering(n_clusters=k, metric='euclidean',
linkage='ward').fit(X)
print('k=%2d sil=%.4f' % (k, silhouette_score(X, m.labels_)))
hc5 = AgglomerativeClustering(n_clusters=5, metric='euclidean',
linkage='ward').fit(X)
for c in range(5):
m = X[hc5.labels_ == c]
print(c, '(%.0f, %.0f)' % (m[:,0].mean(), m[:,1].mean()), len(m))Expected results (real):
- Step 1: matrix as in Section 2; merges {1,2} & {8,9} at 1; {6}+{8,9} at 2 (single) / 3 (complete); final merge at 4 (single) vs 8 (complete).
- Step 2: heights 406, 395, 263, 246 then 114, 113, 107, 81 — the 114–246 gap; cut at ~200 → 5.
- Step 3: (87,82)·39 Target, (56,49)·85 Standard, (89,16)·32 Careful, (25,80)·21 Careless, (26,21)·23 Sensible — matching Ch 19 within boundary customers.
- Step 4: 0.5530 / 0.5530 / 0.4792 / 0.2695; single's [3, 193, 1, 1, 2] = chaining into one giant blob.
- Step 5: ward sweep peaks at k = 5 (0.5530) — elbow, K-Means silhouette and the tree all agree.
- Step 6: two algorithms, one structure — evidence the five segments are real; hierarchical for exploration, K-Means for production assignment.
🎯 Key Takeaways
Hierarchical clustering builds every k at once: merge nearest clusters repeatedly, cut the dendrogram where the data says cut.
Linkage defines cluster distance — single (min) chains, complete (max) is strict, average compromises, ward minimises WCSS growth like K-Means' cousin.
The real merge-height cliff (114 → 246) IS the k evidence: cutting inside the gap leaves exactly the five segments.
Single linkage failed for real: silhouette 0.27 with a 193-customer blob — chaining. Ward and complete (0.5530) produced the balanced five.
Ward's five segments match K-Means' five within boundary customers — two independent algorithms agreeing is the strongest label-free evidence.
The professional sequence: hierarchical to explore and choose k, K-Means to deploy — dendrogram for insight, centroids for the next million customers.
Test Your Understanding
30 questions across the chapter — the algorithm, linkage by hand, the dendrogram, the real linkage failure, and the K-Means comparison. Choose one answer per question, then check your answers.
Q1.Agglomerative clustering works:
Q2.Hierarchical clustering's headline advantage over K-Means:
Q3.(Hand) In the distance matrix for points {1, 2, 6, 8, 9}, the closest pair is:
Q4.Single linkage measures the distance between two clusters as:
Q5.Complete linkage measures it as:
Q6.Ward linkage chooses each merge by:
Q7.(Hand) Merging {1,2} with {6,8,9}: single linkage's height vs complete linkage's:
Q8.The y-axis of a dendrogram records:
Q9.(Real) On the mall data, cutting the ward dendrogram at height ≈ 200 yields:
Q10.(Real) The last eight merge heights read 406, 395, 263, 246, then 114, 113, 107, 81. The k-evidence is:
Q11.(Real) Single linkage, k = 5, produced silhouette 0.2695 with sizes [3, 193, 1, 1, 2]. The diagnosis:
Q12."Chaining" is the classic failure of:
Q13.(Real) Ward and complete linkage both scored 0.5530 with the same partition. Average scored 0.4792. The ranking's lesson:
Q14.(Real) Ward hierarchical's five segments versus Chapter 19's K-Means five:
Q15.Two clustering algorithms with different machinery agreeing on the same structure is:
Q16.(Real) Ward's silhouette sweep peaked at k = 5 (0.5530) — the same k as Chapter 19's elbow and K-Means silhouette. The tally:
Q17.Unlike K-Means, hierarchical clustering is:
Q18.Hierarchical clustering's scaling wall:
Q19.Divisive clustering — the top-down twin:
Q20.The source code's affinity='euclidean' argument:
Q21.The dendrogram's unique product:
Q22.Average linkage defines cluster distance as:
Q23.Unlike K-Means, a fitted hierarchical clustering offers:
Q24.The natural habitat of hierarchical clustering:
Q25.The production role where K-Means wins:
Q26.Calling ward "K-Means' cousin" refers to their shared:
Q27.Hierarchical clustering and feature scaling:
Q28.(Real) Average linkage's sizes [38, 102, 36, 21, 3] versus ward's [32, 85, 39, 21, 23] show:
Q29.Part V's subject abandons distance for co-occurrence:
Q30.The professional two-step this chapter endorses: