Hierarchical Clustering and Linkage

Take 500 points arranged as two interlocking crescents and ask for two clusters. Single linkage recovers them perfectly, an adjusted Rand index of 1.0 against the true labels. Add 30 points of uniform background noise and run it again: single linkage now returns one cluster of 529 points and one cluster containing a single stray point, and agreement with the crescents falls to zero. Ward linkage on the clean crescents scores 0.56, complete and average linkage about 0.45. (These figures come from a small scikit-learn simulation, not a published benchmark.) Across these runs only one rule changed, how to measure the distance between two groups, and that rule is the whole method.

The algorithm is fixed; the linkage is the model

Agglomerative clustering starts with \(n\) singleton clusters and performs \(n-1\) merges, each time joining the pair of clusters with the smallest inter-cluster dissimilarity. The output is not a partition but a dendrogram: a binary tree whose internal nodes record which clusters merged and at what height. A flat clustering is obtained afterwards by cutting the tree.

The linkage defines dissimilarity between clusters \(A\) and \(B\) from point-level distances \(d(a,b)\):

Ward's method does something different in kind. It merges the pair whose union least increases the total within-cluster sum of squares (Ward, 1963, Hierarchical Grouping to Optimize an Objective Function, JASA 58(301)). For clusters with centroids \(\mu_A, \mu_B\) and sizes \(n_A, n_B\), that increase is

which is the k-means objective pursued greedily, one merge at a time. That is why Ward trees tend to produce compact, similar-sized, roughly spherical groups, and why Ward inherits the assumptions spelled out in the k-means concept on this track. It also means Ward is only meaningful on squared Euclidean geometry; feeding it cosine or Manhattan distances runs without error and optimises nothing in particular.

All four rules can be updated incrementally with the Lance-Williams recurrence, which expresses the distance from a newly merged cluster to every other cluster as a weighted combination of existing distances, so the full pairwise matrix never needs recomputing from raw points (Müllner, 2011, Modern hierarchical, agglomerative clustering algorithms, arXiv:1109.2378).

What each linkage sees

Single linkage is the minimum spanning tree in disguise: cutting the \(k-1\) longest MST edges gives the single-linkage \(k\)-clustering. It follows arbitrary shapes because a cluster only needs a chain of close neighbours, and it fails for the same reason. One bridge of noise points between two groups is a chain, so the groups fuse. This is the chaining effect, and the crescents-plus-noise experiment above is it in miniature.

Complete linkage judges a merge by the two farthest members, so it refuses to create clusters with a large diameter. It resists chaining and tends to break large natural groups into pieces of similar diameter.

Average linkage (UPGMA) sits between the two and is the common default in phylogenetics and gene-expression heatmaps.

Centroid and median linkage can produce inversions, where a later merge occurs at a lower height than an earlier one, which makes the dendrogram impossible to cut consistently. Single, complete, average and Ward are monotone and do not.

Monotone linkages turn the dendrogram into an ultrametric: the cophenetic distance between two points, the height at which they first share a cluster, satisfies \(c(x,z) \le \max\{c(x,y), c(y,z)\}\). The cophenetic correlation between \(c\) and the original distances is a quick check of how much the tree distorts the data.

Cutting the tree

A horizontal cut at height \(h\) yields every cluster that exists at \(h\). This assumes one height is right for every region of the data, which fails whenever clusters differ in density or scale. Practitioners genuinely disagree about what to do. One camp treats the dendrogram as an exploratory visualisation, where the tree is the output and any flat cut is a convenience. Another cuts at a variable height per branch, for example with dynamic tree cutting in genomics, or by choosing the most persistent branches, which is exactly what HDBSCAN does on a density-based hierarchy (see the density-based clustering concept on this track). A third simply picks \(k\) with an internal index, inheriting every weakness discussed in the clustering-validation concept.

When it breaks

Quadratic memory is the hard wall. The standard algorithms take the condensed pairwise distance matrix as input, \(n(n-1)/2\) entries. At \(n = 100{,}000\) that is about five billion doubles, roughly 40 GB, before any work begins. Time is \(O(n^2)\) for single linkage via SLINK or the MST, and \(O(n^2)\) for Ward, complete and average via the nearest-neighbour-chain algorithm, with worse worst cases for the generic implementations Müllner analyses. Beyond a few tens of thousands of points, the usual move is to cluster a sample or to pre-aggregate with mini-batch k-means and build the tree on the centroids, which changes what the tree describes.

Merges are never undone. A greedy early mistake, often from near-ties in the distance matrix, propagates to every level above it, and with exact ties the input order can change the tree.

Heights are not comparable across linkages. A Ward dendrogram's heights are increases in squared error; a single-linkage dendrogram's heights are raw distances. Reading "long branches mean strong clusters" off one and comparing it to the other is a category error.

The tree always looks hierarchical. Uniformly scattered points still produce a tidy binary dendrogram with confident-looking branches. The procedure imposes hierarchy; it does not detect it, and the absence of structure has to be tested separately.