Linkage Choices, Connectivity, and Tree Cuts

These are not defects in isolation. They are consequences of the structure each method rewards. For single linkage the consequence has a proof attached.

The elongated shapes single linkage recovers and the chaining it suffers are one fact, not two. Gower and Ross established that in 1969: “Minimum spanning trees (MST) and single linkage cluster analysis (SLCA) are explained and it is shown that all the information required for the SLCA of a set of points is contained in their MST.” If the analysis is the minimum spanning tree, one accidental short edge is enough. The bridge joins two otherwise separate basins because there is nothing else in the tree to weigh against it. Daniel Müllner restates the observation and builds an MST-based single-linkage algorithm on it.

Cost is the other reason single linkage survives its worst property. Sibson's SLINK, published in 1973, reports that “The algorithm achieves the theoretical order-of-magnitude bounds for both compactness of storage and speed of operation”. That made single-link analysis feasible for numbers of operational taxonomic units well into the 10^3-10^4 range. Müllner records that SLINK needs “no working copy of the Θ(N2) input array and only Θ(N) working memory”. Murtagh and Contreras note that the O(n^2) implementations for single link and a non-unique complete link — Sibson (1973), Rohlf (1973), Defays (1977) — “have been widely cited”. The memory advantage is real. A time advantage is not: SciPy v1.18.0 documents O(n^2) for 'single' via the minimum spanning tree, and equally O(n^2) for 'complete', 'average', 'weighted' and 'ward' via the nearest-neighbour chain algorithm. O(n^3) is reserved for the remaining methods.

And a widely cited implementation is not automatically the method its name claims. Müllner warns that Defays (1977), “mostly cited as a fast algorithm for complete linkage clustering”, “definitely is not an algorithm for complete linkage clustering, as the complete linkage method is commonly defined”. That is the second linkage in this lesson whose label in software outruns its arithmetic. The first is Ward.

In R the entire choice is one string argument. The stats::hclust manual page lists eight values for method: "ward.D", "ward.D2", "single", "complete", "average" (= UPGMA), "mcquitty" (= WPGMA), "median" (= WPGMC) and "centroid" (= UPGMC). SciPy's scipy.cluster.hierarchy.linkage documents its own formal definitions of the same rules — single as Nearest Point, complete as Farthest Point, average as UPGMA, and the Ward update.

Nothing in either interface touches the data. The argument changes what "closest" means, and the hierarchy changes with it. Single linkage produces one winding chain. Complete linkage breaks the same points into compact pieces. Ward returns balanced groups. No implementation bug is required. Each rule asks a different question about distance between groups, and therefore builds a different tree from one distance matrix.

The algorithm repeatedly selects the pair of clusters with the smallest linkage value. The rules that supply that value are not separate algorithms. Lance and Williams settled the point in 1967: “The conventional strategies are shown to be simple variants of a single linear system defined by four parameters.”

The system gives the distance from a newly merged cluster i∪j to any remaining cluster k:

d(i∪j,k) = α_i d(i,k) + α_j d(j,k) + β d(i,j) + γ |d(i,k) − d(j,k)|

Single linkage is α_i = α_j = 0.5, β = 0, γ = −0.5. Complete linkage is identical except γ = +0.5 — one sign, and the nearest cross-cluster pair becomes the farthest. Group average (UPGMA) is α_i = |i|/(|i|+|j|), β = 0, γ = 0.

Ward is not one of the strategies Lance and Williams parameterised; their 1967 paper does not consider it. Wishart brought Ward's criterion into the same framework in 1969, with α_i = (|i|+|k|)/(|i|+|j|+|k|), β = −|k|/(|i|+|j|+|k|), γ = 0, applied to squared Euclidean distances. It is the only one of the four whose coefficients depend on the size of the third cluster k. Murtagh and Contreras print the same table, “Specifications of seven hierarchical clustering methods”, covering single link, complete link, group average (UPGMA), McQuitty, median, centroid and Ward's method.

The final partition depends both on how the tree was built and on the level chosen. Step 3 is where the hidden trade-off sits.

A connectivity constraint does not merely narrow the search. It changes which linkage rules remain usable. scikit-learn ran its own example on 1500-sample Swiss-roll and 2D-spiral data, with kneighbors_graph at n_neighbors=10 and 30, and records the cost: “Second, when using a connectivity matrix, single, average and complete linkage are unstable and tend to create a few clusters that grow very quickly.” The same page names the mechanism — “having a very small number of neighbors in the graph, imposes a geometry that is close to that of single linkage”. The graph deletes the long-distance comparisons by which average and complete linkage normally resist chaining. The smaller the k, the more they percolate.

For Ward the complementary result runs the other way. A 2021 review of hierarchical agglomerative clustering with and without contiguity constraints reports: “Finally, a simulation study shows that the constrained version of HAC can sometimes provide more relevant results than its unconstrained version despite the fact that the constraint leads to optimize the objective criterion on a reduced set of solutions at each step.”

So a constraint is neither free nor merely restrictive. It buys speed, it can beat the unconstrained fit, and it degrades three of the four linkages toward single-linkage percolation at the same time. That is a design decision to be argued for at step 3, not a default.

Examples make the merge criterion easier to connect with actual data. Each one below is the coefficient behaviour showing through a domain.

Analysts often tune the dendrogram height while leaving the merge criterion unquestioned. The tree has already encoded which shapes and bridges are acceptable.

Nor is judging the gap by eye the only alternative to a rule. The rules disagree with each other, and that disagreement has been measured. Milligan and Cooper reported it in 1985: “A Monte Carlo evaluation of 30 procedures for determining the number of clusters was conducted on artificial data sets which contained either 2, 3, 4, or 5 distinct nonoverlapping clusters.” Four hierarchical clustering methods analysed the data. The outcome was not a winner but a spread: “The simulation results for the stopping rules revealed a wide range in their ability to determine the correct number of clusters in the data.” Several worked fairly well. Others performed rather poorly. Nearly thirty years later the NbClust R package was built around the same set — “Indeed, Milligan and Cooper (1985) examined thirty indices, with simulated data, where the number of clusters is known beforehand” — and provided 30 indices. Only thirteen were then available in R, and some of the indices from that study still could not be reimplemented.

Treat linkage, metric, connectivity, and cut as a joint design. Ward published the criterion in 1963, where the procedure “is suggested for use in large-scale (n > 100) studies when a precise optimal solution for a specified number of groups is not practical”, reducing n sets to n − 1 “by considering the union of all possible n(n − 1)/2 pairs and selecting a union having a maximal value for the functional relation, or objective function”. It was proposed as an approximation from the start. A defensible hierarchy explains why the four choices match the intended structure. It does not ask the cut to repair the first three.