How do single, complete, average and Ward linkage decide which clusters merge next?

## The shared frame A linkage rule answers one question: given two clusters `A` and `B`, and the distances between every point of `A` and every point of `B`, how far apart are the clusters? Every agglomerative run then merges whichever current pair scores lowest. The rules differ only in how they summarise the same set of cross-cluster distances, and that single choice determines what shape of cluster the method can find. ## Single linkage — the minimum `d(A, B) = min` over all cross pairs. Two clusters are close if *any* member of one is close to *any* member of the other. This makes single linkage a shape-agnostic method: it will happily recover a crescent, a ring or a snake, because it only ever needs a chain of near neighbours to hold a cluster together. The same property is its notorious failure, called **chaining**. Imagine soil samples from two clearly distinct field zones, with a thin trail of transitional samples collected along the track between them. Each consecutive trail sample is near its neighbour, so single linkage walks the trail step by step and merges the two dense zones into one sprawling cluster at a very low height. The dendrogram gives it away: instead of two deep branches you see a lopsided comb, with singletons peeling onto a growing blob one at a time. Single linkage is also the linkage most damaged by a handful of noise points, because one bridging point is enough. A useful piece of structure: single linkage is exactly a minimum spanning tree computation. Cutting the tree at height `h` gives the connected components you would get by deleting every MST edge longer than `h`. ## Complete linkage — the maximum `d(A, B) = max` over all cross pairs. Two clusters merge only if their *most distant* members are still tolerably close. The effect is the opposite of chaining: complete linkage produces tight, roughly equal-diameter clusters and refuses to build elongated ones, because extending a cluster raises its diameter and so raises the cost of every further merge. Its weakness follows from the same definition — the score depends on one extreme pair, so a single outlier attached to a cluster inflates that cluster's distance to everything and can push the tree into a poor arrangement. It also tends to split a genuinely elongated group into several pieces. ## Average linkage — the mean `d(A, B) = mean` of all cross pairs (the classical UPGMA rule). Because it averages over every pair rather than trusting an extreme, it is far more robust than either min or max, and its behaviour lies between them: less chaining than single, less fragmentation of elongated shapes than complete. Note precisely what is averaged — the *pairwise distances*, not the two centroids. Averaging centroids is a different rule (centroid linkage), and centroid linkage can produce inversions, where a merge is drawn below an earlier one, which single, complete, average and Ward never do. ## Ward linkage — the variance criterion Ward does not summarise cross-cluster distances at all. Define the within-cluster sum of squares of a cluster as the summed squared distance from its members to its own mean. Ward merges the pair whose union raises the *total* within-cluster sum of squares by the least: `cost(A, B) = SSE(A union B) - SSE(A) - SSE(B)` which has a closed form: `cost(A, B) = (n_A * n_B / (n_A + n_B)) * squared distance between the centroids of A and B` Read that formula and Ward's character falls out. The centroid distance is scaled by a size factor, so merging two large clusters is expensive even when their centres are close. Ward therefore produces compact, roughly equal-sized clusters and resists both chaining and the lopsided one-point-at-a-time tree. That is why a Ward dendrogram drawn beside a heatmap of, say, 60 tumour gene-expression profiles reads so cleanly: balanced branches, visually blocky groups. It is also why Ward can be misleading — if the real structure is one large group and one tiny group, Ward is biased against reporting it, and it will impose equal-sized blocks on data that has none. Two practical consequences. First, the derivation is in terms of squared Euclidean distance, so Ward is not defined for an arbitrary distance function; feeding it precomputed non-Euclidean distances produces numbers, not a valid criterion. Second, because it works on squared Euclidean geometry, unscaled features dominate: a variable measured in thousands will drive every merge unless the features are standardised first. Complete linkage inherits the same scaling sensitivity; single linkage is affected too, but its min-based rule cares about local neighbourhoods rather than global spread. ## Choosing Ward first when you expect roughly convex, comparable-sized groups and have scaled the features. Average linkage when you want a robust general-purpose tree without Ward's equal-size bias. Complete linkage when tight diameter matters and outliers have been handled. Single linkage when the clusters are genuinely elongated or connected-by-density, and only after asking whether a bridge of transitional points could exist in the data.