Hierarchical Clustering

k-Means commits you to k before it shows you anything. Agglomerative hierarchical clustering inverts that: it builds the full nesting of groups bottom-up, and you choose the cut afterwards. The mechanism is one loop.

1. Start with every point in its own cluster (n clusters).
2. Find the pair of clusters with the smallest distance between them and merge them.
3. Recompute distances from the new cluster to every remaining cluster.
4. Repeat until one cluster remains.

Step 3 is the whole design space. The distance between points is fixed (usually Euclidean), but the distance between two clusters — each containing many points — is a choice, and that choice is the linkage criterion. Given clusters A and B, the common linkages are:

Ward deserves special attention because it is the sklearn default and the one to reach for first. Its merge cost has a closed form — merging A and B inflates the within-cluster sum of squares by exactly:

d_ward(A, B) = (|A| * |B|) / (|A| + |B|) * ||mean(A) - mean(B)||^2

The factor (|A|·|B|)/(|A|+|B|) means ward resists merging two big clusters just because their means are moderately close, while single and average linkage ignore cluster size entirely.

Trace a merge. Three clusters so far: A = {p1, p2} with mean (1.0, 2.0), B = {p3, p4} with mean (5.0, 8.0), C = {p5} at (9.5, 9.0). Which pair merges first?

• single: d(A,B) = 4.72 (closest cross pair), d(B,C) = 4.52 → B–C merges
• complete: d(A,B) = 8.49 (farthest cross pair), d(B,C) = 5.52 → B–C merges
• ward: cost(A,B) = (2·2/4)·52 = 26.0; cost(B,C) = (2·1/3)·21.25 ≈ 14.2 → B–C merges

Same answer, but change C's position to (6.0, 9.0) and single linkage merges A–B while complete merges B–C — the linkage, not the data, decided. That is the experiment to run when someone claims the clusters are "obvious".

The cost profile explains the practical ceiling. Naive agglomeration is O(n^3) time (n merges, each scanning O(n^2) pairs), reducible to O(n^2 log n) with a priority queue, and the initial distance matrix is O(n^2) memory regardless — 10,000 points is 100M floats, ~800 MB in float64. This is why hierarchical clustering is a tool for up to roughly 10,000 rows, and why larger problems go to k-Means or BIRCH. sklearn's implementation gives you the matrix directly:

from scipy.cluster.hierarchy import linkage
Z = linkage(X_scaled, method='ward', metric='euclidean')
Z.shape   # (n-1, 4): each row is one merge — [id_a, id_b, height, cluster_size]

Linkage choice is not a cosmetic setting. Single linkage can connect two dense groups through a sparse chain because it only asks for the closest cross-cluster pair. Complete linkage resists long chains by looking at the farthest pair, but a single outlier can keep otherwise coherent groups apart. Average linkage smooths those extremes by averaging pairwise distances. Ward tends to produce compact groups, but it is defined around increases in within-cluster squared error and is ordinarily paired with Euclidean distance. Before comparing dendrograms, hold preprocessing and distance fixed, then inspect representative points from clusters near the cut.

The output of hierarchical clustering is not a labeling — it is the entire merge history, drawn as a dendrogram. Learning to read it is the skill, because it lets you see every k at once instead of committing to one — the problem Choosing the Cluster Count attacked with elbow and silhouette curves.

The picture is a binary tree read bottom-up. Each horizontal join is a merge, and the height of the join is the distance between the two clusters at the moment they merged. Low joins mean near-identical groups; tall joins mean the algorithm was forced to glue together things that did not want to be glued. The vertical length of a join's two legs is the practical diagnostic: a tall empty stretch on both legs with no joins inside it marks a natural cut height.

import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, fcluster, cophenet
from scipy.spatial.distance import pdist

fig, ax = plt.subplots(figsize=(12, 4))
dendrogram(Z, truncate_mode='level', p=4, ax=ax)   # collapse below 4 levels
ax.axhline(12.5, ls='--', c='k')                   # your chosen cut
plt.ylabel('merge height (euclidean)')

labels = fcluster(Z, t=12.5, criterion='distance')  # cut at height 12.5
# or: fcluster(Z, t=4, criterion='maxclust')        # ask for exactly 4 clusters

truncate_mode='level' matters in practice: drawing all n leaves is unreadable past a few hundred points, and truncation keeps the top structure visible. Cutting is fcluster, either by a height threshold (criterion='distance') or by a target count (criterion='maxclust'), and the two can disagree when merges happen at nearly equal heights — cut by height when the tree shows a real gap, by count when the business gave you a number.

How do you know the tree is faithful? The cophenetic correlation coefficient correlates the merge heights in the tree with the original pairwise distances between points. Each point pair's cophenetic distance is the height at which its two points first joined the same cluster; correlate that vector with the condensed distance matrix:

corr, _ = cophenet(Z, pdist(X_scaled))
print(round(corr, 3))   # e.g. 0.71 — decent preservation

A standard interview exercise is comparing linkages on the same data: run linkage with method='single', 'complete', 'average', and 'ward', compute cophenetic correlation for each, and see that average or ward usually wins. The correlation measures fidelity to the distances — it does not tell you the clusters are meaningful. That distinction is exactly why the last topic of this phase, Cluster Evaluation and Profiling, exists: a perfectly faithful tree of garbage structure is still garbage.

A horizontal cut at height h merges every branch whose linkage distance is at most h; moving the line lower creates more groups. A large vertical gap between merge heights can suggest a stable cut because several clusters remain separate until a relatively costly merge. That gap is evidence to investigate, not a universal rule. Compare cuts using domain constraints, cluster sizes, and downstream usefulness. If you need exactly k groups, the cut may be chosen to produce k, but report that k was imposed. When clusters are uneven, a single global cut can produce tiny groups alongside large ones; check whether those small groups represent meaningful rare cases or noise.

The same linkage choice that gives hierarchical clustering its flexibility gives it three well-known failure modes. Knowing which one you are looking at is the difference between debugging and re-running blindly.

Single linkage chains. Because single linkage merges on the closest pair of points, a thin trail of intermediate points can bridge two genuinely separate groups into one. Add five noise points spaced 1.5 apart between two blobs whose centers are 12 apart, and single linkage merges the blobs at height 1.5 — long before anything meaningful happens. The dendrogram shows it plainly: a series of low merges forming a path, then one enormous jump. Ward and complete linkage ignore the bridge entirely because their cluster distances depend on the bulk, not the closest pair. If your single-linkage dendrogram has one very tall join, you chained.

Complete linkage over-corrects. Taking the farthest pair as cluster distance makes it hypersensitive to one outlier: a single stray point inflates d_complete(A, B) and can force a premature merge elsewhere. Complete linkage also shrinks the largest cluster's apparent distance as it grows, biasing the tree toward similar-sized groups that may not exist.

Ward bakes in k-Means' assumptions. Ward's cost is built on squared Euclidean variance, so it needs Euclidean features, prefers roughly spherical equal-variance groups, and demands the same scaling discipline as k-Means — apply StandardScaler first or the largest-magnitude column decides the tree. scipy will not stop you from passing metric='manhattan' with method='ward'; the result is meaningless.

Then there are the structural limits, which no parameter tuning fixes:

The interview question this equips you for is comparative: "When would you pick hierarchical over k-Means?" A strong answer names three situations — the cluster count is genuinely unknown and you want to see the nesting before deciding; the dataset is small enough for the O(n^2) matrix (typically under ~10k rows) and interpretability of the tree matters to stakeholders; or you suspect multi-level structure (sub-clusters within clusters) that a flat partition hides. And the honest counter-answer: when n is large, features are many, or you only need one flat partition at a known k, k-Means with k-means++ is faster and often just as good — while genuinely non-spherical or noise-heavy data should push you one topic forward to DBSCAN Density Clustering.

The quadratic cost matters before you launch the job: a dense pairwise distance matrix for n records has n squared entries, so doubling n can roughly quadruple memory and distance work. At 50,000 records, even float64 storage for one full matrix is about 20 GB before library overhead. Sampling can help explore linkage and cut behavior, but the resulting hierarchy is not an exact tree for the full population. For larger data, consider a domain-informed sample, a scalable clustering method, or a nearest-neighbor graph approach, and state how that changes the interpretation. Avoid silently dropping records just to make the algorithm fit.