Agglomerative Clustering: Linkages, Ward’s Criterion and Dendrograms

The output is a hierarchy

If observations might have meaningful groupings at several resolutions, one flat partition can hide the structure. Agglomerative clustering builds a sequence of nested partitions: n singleton clusters, then n−1 groups, down to one. A dendrogram records which groups merge and the dissimilarity or criterion value associated with that merge.

Every merge is greedy and irreversible. A dendrogram therefore represents the history of a chosen algorithm, metric and linkage. It does not prove that the observations belong to a unique underlying taxonomy. Ties, noisy distances and scaling can change early merges and their descendants.

Four linkage rules, four questions

For clusters A and B, common definitions are:

Average linkage here means averaging all observation pairs across A and B, often called UPGMA. Equal weighting of cluster-level distances gives a different method when cluster sizes differ. Specify the variant rather than assuming “average” has only one implementation.

Single linkage can recover elongated connected sets, but a chain of intermediate observations may join two otherwise separate regions. Complete linkage resists that chaining but is sensitive to a single faraway member. These are consequences of the minimum and maximum operators, not accidental implementation defects.

One merge decision, computed three ways

Suppose a current partition contains \(A=\{0,2\}\), \(B=\{3\}\) and \(C=\{6\}\) on the number line. The distances between A and B are 3 and 1; between B and C the distance is 3.

Single linkage scores A–B as 1 and B–C as 3, so it favours A–B. Complete linkage gives both 3, producing a tie that needs an explicit rule. Average linkage gives A–B a score of 2 and B–C a score of 3.

The same observations therefore present different evidence under different cluster definitions. A plotting library that draws the resulting trees attractively does not resolve that modelling choice.

Derive Ward’s increase in error

Let \(n_A,n_B\) and \(\mu_A,\mu_B\) be sizes and means. Decomposing squared deviations around the merged mean gives

For the example, A has size 2 and mean 1, while B has size 1 and mean 3. Their merge costs \(\tfrac23(1-3)^2=8/3\). Merging B and C costs \(\tfrac12(3-6)^2=4.5\), so Ward favours A–B.

Ward’s derivation uses squared Euclidean geometry. Substituting an arbitrary cosine or edit-distance matrix into software labelled “Ward” does not preserve this interpretation. Also check dendrogram height conventions: some libraries plot a square-root rescaling of the SSE increment rather than the increment itself.

Cutting and interpreting the tree

A horizontal cut at a chosen height gives the groups whose merges occur below that threshold. Requesting a fixed number of clusters instead selects a point in the merge sequence. These procedures need not correspond to a single unambiguous height when many merges tie.

Large vertical gaps can suggest a useful scale, but they depend on the metric and linkage. Show several cuts, compare stability under resampling, and examine representative observations. A leaf’s horizontal position is usually arbitrary within allowed subtree rotations; distance along the x-axis does not measure similarity.

Complexity and implementation

Naively recomputing all cluster distances at every step can take cubic time. Specialised algorithms improve this substantially: several standard linkages admit quadratic-time implementations, and single linkage can exploit a minimum spanning tree. Dense pairwise storage is often still quadratic.

Connectivity-constrained agglomeration permits merges only along a supplied neighbourhood graph. That can reduce work and encode meaningful adjacency, such as nearby image regions. It also changes which partitions are reachable. Report the graph construction and isolated-component handling, not just the linkage name.

There is no universal prediction rule for unseen observations. Assigning a new point to the nearest existing cluster representative is an added rule, not a rerun of the original hierarchy. If deployment requires assignments for new data, specify and validate that extension.

When a hierarchy helps

Use agglomeration for moderate datasets, exploratory multi-resolution structure and applications where a nested grouping is meaningful. Compare density methods when noise should remain unassigned, and k-means when a large flat Euclidean partition is enough.

Keep the original metric, linkage, tie handling, tree and cut rule together. A flat label vector alone discards the main product of the algorithm and makes it difficult to investigate why two groups were joined.

References

1. Müllner. Modern hierarchical, agglomerative clustering algorithms. 2011.
2. scikit-learn. Clustering user guide.