Agglomerative Clustering and the Lance-Williams Recurrence

Agglomerative clustering starts with n singleton groups and repeatedly merges the two that are closest, producing a nesting of partitions rather than a single one. After n - 1 merges everything is in one group, and the sequence of merges with the distance at which each occurred is enough to recover any intermediate partition. The method needs no value of k up front, which is its main appeal; the price is that it needs the entire pairwise distance matrix, and that the notion of closeness between groups has to be chosen by the user.

The greedy merge and what the dendrogram stores

The merge is greedy. At every step the globally closest pair of current groups is joined, and no later step revisits that decision. Nothing about the procedure is optimal for a global criterion: the hierarchy produced by greedy merging is a heuristic solution to a nested partitioning problem, and it can disagree with the best hierarchy available for the same data.

The output is a dendrogram: a binary tree whose leaves are the original points and whose internal nodes carry the merge height. Cutting the tree horizontally at a threshold gives a flat partition, one per threshold, and the sequence of partitions is nested, so a point that shares a group at a low threshold still shares it at a high one. That nesting is what makes hierarchy useful and also what limits it, since the true groups in a dataset need not be nested at all.

Greedy merging is also order dependent in the presence of ties. When several pairs are equidistant, the implementation picks one, and the remaining structure can differ between runs. For single linkage the resulting clusters at a fixed threshold are still determined, because they equal the connected components of a graph, but the intermediate dendrogram may not be unique.

Four definitions of the distance between groups

Four answers dominate practice, and each implies a different cluster shape.

Single linkage, or nearest neighbour, defines the distance between two groups as the minimum distance over all cross pairs. A chain of points each close to the next merges into one group regardless of how far its endpoints are apart, so the method happily returns elongated and non-convex clusters, and a single bridging observation can join two well separated groups. Its compensating property is exactness: the clusters obtained by cutting the tree at a threshold are the connected components of the graph whose edges are the pairs at or below that distance.

Complete linkage, or farthest neighbour, uses the maximum cross-pair distance. Groups therefore stay compact, with a bounded diameter, and two groups merge only when every pair across them is close. The cost is sensitivity to outliers: one distant point inflates the distance from its own group to every other group and delays merges indefinitely.

Average linkage uses the mean of all cross-pair distances. It smooths the two extremes, and it has a weighting subtlety: the unweighted form averages over pairs, which lets a group with many members dominate a merge with a small group, while the weighted form averages group distances recursively so that cluster sizes no longer matter. The two produce different hierarchies on the same data.

Ward linkage is defined by an objective instead of a geometry. Merging groups i and j increases the within-cluster sum of squares by

$$\Delta = \frac{n_i n_j}{n_i + n_j} \lVert c_i - c_j \rVert^2$$

where c denotes a group centroid and n a group size. Ward always takes the merge with the smallest increase, so it is the agglomerative analogue of the objective in Lloyd’s Algorithm and the Local Minima of k-Means, and it inherits the isotropic, equal-volume preference of squared Euclidean distance. Because the formula is written in terms of squared Euclidean norms, feeding Ward a dissimilarity that is not squared Euclidean, such as the cosine-based distances discussed in What a Distance Function Decides About Cluster Shape, optimizes a quantity that no longer matches the criterion.

The recurrence that makes merging affordable

After the merge of i and j into a group u, the distances from u to every other group k can be computed from three numbers that are already known: d(i, k), d(j, k), and d(i, j). The Lance-Williams form of that update is

$$d(u, k) = \alpha_i d(i, k) + \alpha_j d(j, k) + \beta d(i, j) + \gamma \lvert d(i, k) - d(j, k) \rvert$$

with coefficients fixed by the linkage method:

Linkage	alpha_i	alpha_j	beta	gamma
Single	1/2	1/2	0	-1/2
Complete	1/2	1/2	0	1/2
Average	n_i/(n_i+n_j)	n_j/(n_i+n_j)	0	0
Ward	(n_i+n_k)/T	(n_j+n_k)/T	-n_k/T	0

In the Ward row, T = n_i + n_j + n_k. The recurrence is what turns a conceptually cubic procedure into a quadratic one. Scanning the whole matrix for the closest pair at each of the n - 1 merges costs O(n^3); maintaining the matrix rows and updating only the row and column of the merged group costs O(n) per merge and therefore O(n^2) in total. Memory remains O(n^2) because the distances not yet consumed have to be retained. A dataset of 50,000 points implies about 1.25 billion off-diagonal distances, which at eight bytes each is roughly 10 GB, and this is the boundary that usually forces a different approach.

More careful implementations avoid the full matrix for some linkages. Single and complete linkage both admit reciprocal nearest neighbour chains, so the entire merge sequence can be extracted in O(n^2) time with O(n) memory, which is how the classical single-link and complete-link algorithms work. Ward and average linkage are also reducible, so the nearest neighbour chain technique applies to them as well. For larger inputs the usual pattern is to compress first: run a centroid method to obtain a few thousand representatives by weight, then agglomerate the representatives with weights.

import numpy as np
from scipy.cluster.hierarchy import linkage, fcluster, cophenet
from scipy.spatial.distance import pdist

X = np.loadtxt('points.csv')          # n by d
D = pdist(X, metric='euclidean')      # condensed upper triangle, n*(n-1)/2 values

Z = linkage(D, method='average')      # rows: [left, right, distance, size]
labels = fcluster(Z, t=2.5, criterion='distance')   # cut at a height

# how faithfully the hierarchy reproduces the original distances
c, _ = cophenet(Z, D)
print(c)

Monotone heights and the linkages that break them

A dendrogram is only readable as a hierarchy if merge heights never decrease along any branch. A linkage is reducible when the closest pair of groups is always mutual, and reducibility implies monotone merges. Single, complete, average, and Ward linkage are reducible, so their merge distances are non-decreasing and cutting by height is well defined.

Centroid linkage, which simply uses the distance between group means, and median linkage, which uses a recursively updated midpoint, are not reducible. They can produce inversions, points in the tree where a merge sits below the height of one of its children. An inversion makes a horizontal cut ambiguous: a group can appear and disappear as the threshold sweeps upward. These linkages also lose the correspondence between merge height and within-group scatter that Ward provides.

Reading a hierarchy and where it fails

The natural summary of fit is the cophenetic correlation, the correlation between the original dissimilarities and the merge heights at which each pair first shares a group. A value near one means the tree reproduces the distance matrix; a low value means many pairs of similar points were separated by early merges elsewhere in the tree. The statistic evaluates the hierarchy, not a particular flat partition, and it says nothing about whether the groups at a cut correspond to anything meaningful.

Cutting is the part that requires judgement. Cutting by a fixed height answers the question of which groups are separated by more than that distance; cutting by a fixed cluster count requires a value of k chosen elsewhere, which returns the problem to the model-selection discussion in Cluster Validity, Stability, and Choosing the Number of Clusters.

The characteristic failure of single linkage is chaining, where a sparse bridge of points connects two dense groups. The characteristic failure of complete linkage and Ward is the opposite: a wide, diffuse group is split into fragments because its diameter exceeds the gaps inside a neighbouring group. When clusters genuinely vary in density, neither extreme is right, and the density-based definition in DBSCAN, Density Reachability, and the Parameter Cliff replaces the merge rule with a local density test, at the cost of giving up the nesting.