Why Compare Linkage Rules?
Agglomerative hierarchical clustering starts with each observation in its own cluster and repeatedly joins the pair of clusters judged closest under a chosen linkage rule. The distance between individual observations is fixed, but the distance between clusters depends on that rule. Consequently, the same observations can produce different partitions after the first merge.
This comparison uses four hypothetical risk profiles, labelled A, B, C, and D. Their features have already been put on a common scale, and their dissimilarities are Euclidean distances. The coordinates are given as well as the distance matrix because centroid linkage and Ward linkage require information about the locations of the observations, not just a rule for combining arbitrary dissimilarities.
The first three definitions use the original pairwise distances directly. Centroid linkage instead computes a distance between means, which need not equal the average of the pairwise distances. Ward linkage uses a change in a squared-error criterion; below, its reported merge value is that increase, denoted by \(\Delta\), rather than an ordinary distance.
Worked Comparison on One Distance Matrix
Suppose the four profiles have coordinates \(A=(0,0)\), \(B=(1,0)\), \(C=(4,0)\), and \(D=(5,3)\). Their pairwise distances are as follows. Values involving square roots are shown to four decimal places where needed.
| Pair | Distance | Calculation |
|---|---|---|
| A, B | 1.0000 | \(\sqrt{(1-0)^2+(0-0)^2}=1\) |
| A, C | 4.0000 | \(\sqrt{(4-0)^2}=4\) |
| A, D | 5.8310 | \(\sqrt{5^2+3^2}=\sqrt{34}\) |
| B, C | 3.0000 | \(\sqrt{(4-1)^2}=3\) |
| B, D | 5.0000 | \(\sqrt{4^2+3^2}=5\) |
| C, D | 3.1623 | \(\sqrt{1^2+3^2}=\sqrt{10}\) |
Worked Example: Follow All Five Linkage Rules
Method. At each stage, calculate the candidate distances between the current clusters and merge the pair with the smallest value. The unique smallest initial pair is A and B. For single, complete, and average linkage, calculate distances from \(\{A,B\}\) to C and D from the original matrix entries.
Single linkage. After merging A and B, the distance from \(\{A,B\}\) to C is \(\min(4,3)=3\). Its distance to D is \(\min(\sqrt{34},5)=5\), while \(d(C,D)=\sqrt{10}\approx3.1623\). The next merge is \(\{A,B\}\) with C, at 3. The distance from \(\{A,B,C\}\) to D is \(\min(\sqrt{34},5,\sqrt{10})=\sqrt{10}\approx3.1623\), so D joins last.
Complete linkage. After A and B merge, the distances to C and D are \(\max(4,3)=4\) and \(\max(\sqrt{34},5)=\sqrt{34}\approx5.8310\). Since \(d(C,D)=\sqrt{10}\approx3.1623\), C and D merge next. The final distance between \(\{A,B\}\) and \(\{C,D\}\) is the largest cross-cluster distance: \(\max(4,\sqrt{34},3,5)=\sqrt{34}\approx5.8310\).
Average linkage. The distance from \(\{A,B\}\) to C is \((4+3)/2=3.5\). Its distance to D is \((\sqrt{34}+5)/2\approx5.4155\). Thus C and D, at \(\sqrt{10}\approx3.1623\), merge next. The final average across the four cross-cluster pairs is \((4+\sqrt{34}+3+5)/4=(12+\sqrt{34})/4\approx4.4577\).
Centroid linkage. The centroid of \(\{A,B\}\) is \(((0+1)/2,0)=(0.5,0)\). Its distances to C and D are \(\sqrt{(4-0.5)^2}=3.5\) and \(\sqrt{(5-0.5)^2+3^2}=\sqrt{29.25}\approx5.4083\). Because the C–D distance is \(\sqrt{10}\approx3.1623\), C and D merge second. Their centroid is \((4.5,1.5)\). The final centroid distance is \(\sqrt{(4.5-0.5)^2+(1.5-0)^2}=\sqrt{18.25}\approx4.2720\).
Ward linkage. The initial increase from merging two singletons at distance \(d\) is \(d^2/2\). Thus the A–B merge has cost \(1^2/2=0.5\). After that merge, the cost for joining \(\{A,B\}\) to C is \((2/3)(3.5)^2=8.1667\), and the cost for joining \(\{A,B\}\) to D is \((2/3)(29.25)=19.5\). The C–D cost is \(3.1623^2/2=5\). Ward therefore merges C and D next. The final cost is \(1(18.25)=18.25\), using the two cluster sizes, both 2, and the squared distance \(18.25\) between their centroids.
Check. Each method first merges A and B because that is the uniquely closest pair of individual observations. Afterward, single linkage merges \(\{A,B\}\) with C, whereas complete, average, centroid, and Ward linkage merge C with D. The choices and the final merge values follow from the calculations above.
Why Ward’s Formula Measures the Merge Cost
For Euclidean coordinates, let \(W\) be the total within-cluster sum of squares: the sum, over clusters, of the squared distances from each observation to its own cluster mean. If clusters \(G\) and \(H\) have sizes \(n_G\) and \(n_H\), and means \(\bar{x}_G\) and \(\bar{x}_H\), then the increase in \(W\) from merging them is
To see why, write the mean of the merged cluster as \(\bar{x}=(n_G\bar{x}_G+n_H\bar{x}_H)/(n_G+n_H)\). The change in the sum of squared deviations can be split into the deviations within each original cluster plus the shifts of their means to \(\bar{x}\). The within-cluster deviations are unchanged; the added amount is \(n_G\|\bar{x}_G-\bar{x}\|^2+n_H\|\bar{x}_H-\bar{x}\|^2\). Substituting \(\bar{x}_G-\bar{x}=\{n_H/(n_G+n_H)\}(\bar{x}_G-\bar{x}_H)\) and \(\bar{x}_H-\bar{x}=-\{n_G/(n_G+n_H)\}(\bar{x}_G-\bar{x}_H)\) gives the stated formula after collecting terms. For two singletons, \(n_G=n_H=1\) and their means are the observations themselves, so \(\Delta=d^2/2\).
The formula assumes Euclidean feature vectors and the squared-error objective just defined. It should not be applied to a general dissimilarity matrix unless the problem establishes that the distances correspond to suitable Euclidean coordinates. Ward’s merge cost is also not the same quantity as the Euclidean distance between cluster means.
Worked Example: Calculate Ward Costs from Coordinates
A separate three-profile data set has one-dimensional coordinates \(P=0\), \(Q=3\), and \(R=8\). Use Ward’s criterion to determine the first merge and the cost of the final merge, then check the final within-cluster sum of squares.
Method. For singleton pairs, calculate \(d^2/2\). The pair distances are \(d(P,Q)=3\), \(d(Q,R)=5\), and \(d(P,R)=8\). Their Ward costs are \(9/2=4.5\), \(25/2=12.5\), and \(64/2=32\), respectively. Therefore P and Q merge first, at cost 4.5.
The mean of \(\{P,Q\}\) is \((0+3)/2=1.5\). Its distance to R is \(8-1.5=6.5\). The final merge cost is \((2\cdot1)/(2+1)\times6.5^2=(2/3)(42.25)=28.1667\). The total within-cluster sum of squares after all three observations are together is \(4.5+28.1667=32.6667\), rounded to four decimals.
Check. The overall mean is \((0+3+8)/3=11/3\). The sum of squared deviations is \((0-11/3)^2+(3-11/3)^2+(8-11/3)^2=(121+4+169)/9=294/9=32.6667\), matching the accumulated merge cost. The common mistake this calculation avoids is treating Ward’s criterion as the smallest raw pairwise distance at every step.
Average Linkage Is Not Centroid Linkage
The two methods can produce close numerical values while measuring different things. Average linkage takes the mean of every original cross-cluster pair distance. Centroid linkage first averages the coordinates within each cluster and then computes the distance between those two means. In general, the mean of distances is not the distance between means.
Worked Example: Distinguish Average and Centroid Distances
For the main four-profile example, calculate the distance from \(\{A,B\}\) to D under average and centroid linkage. Explain why the answers differ and state whether either value changes the second merge.
Average linkage. The two cross-cluster distances are \(d(A,D)=\sqrt{34}\approx5.8310\) and \(d(B,D)=5\). Their mean is \((\sqrt{34}+5)/2\approx(5.8310+5)/2=5.4155\).
Centroid linkage. The mean of A and B is \((0.5,0)\), so its distance to D at \((5,3)\) is \(\sqrt{(5-0.5)^2+(3-0)^2}=\sqrt{29.25}\approx5.4083\). The values differ because average linkage averages two lengths, while centroid linkage measures one length between two points. Neither changes the second merge in this data set: both exceed \(d(C,D)=\sqrt{10}\approx3.1623\). Do not assume that their agreement on a merge choice makes the definitions interchangeable.
Common Exam Trap: Compare the Right Quantities
A frequent error is to use a cluster-centroid distance when the question asks for average linkage. Another is to compare Ward’s \(\Delta\) with an ordinary distance as though they were the same scale. In the main example, A–B has raw distance 1 but Ward cost \(1^2/2=0.5\). For C–D, the raw distance is \(\sqrt{10}\approx3.1623\), while its Ward cost is \(10/2=5\). The formulas give different quantities, even though both identify the same first merge here.
To avoid these mistakes, identify the linkage rule before calculating. For single, complete, and average linkage, list the original cross-cluster distances and apply the minimum, maximum, or arithmetic mean, respectively. For centroid linkage, calculate both cluster means before taking a Euclidean distance. For Ward linkage, use cluster sizes and squared centroid distance to calculate the increase in within-cluster sum of squares.
Check Your Understanding
For each problem, calculate the requested linkage value before choosing a merge.
- Four observations have distances \(d(A,B)=2\), \(d(A,C)=4\), \(d(B,C)=3\), \(d(A,D)=7\), \(d(B,D)=6\), and \(d(C,D)=3.5\). After A and B merge, which pair merges next under single linkage? (Answer: \(\{A,B\}\) with C, at distance 3.)
- Using the distances in question 1, which pair merges next under complete linkage? (Answer: C and D, at distance 3.5; the complete distance from \(\{A,B\}\) to C is 4.)
- Clusters \(G\) and \(H\) have sizes 2 and 3 and centroids \((1,2)\) and \((4,6)\). Calculate Ward’s merge cost. (Answer: \((2\cdot3/5)(3^2+4^2)=30\).)
- Two clusters have cross-distances 2, 5, 4, and 7. Their centroids are 3 units apart. Find average linkage and centroid linkage, and say whether they are equal. (Answer: Average linkage is \((2+5+4+7)/4=4.5\); centroid linkage is 3; they are not equal.)
- Three one-dimensional observations are at 1, 5, and 11. Under Ward linkage, identify the first merge and calculate its cost. (Answer: The observations at 1 and 5 merge first; their distance is 4 and the cost is \(4^2/2=8\).)