Why Ward Linkage Uses an Increase in Variation
Hierarchical clustering repeatedly joins two existing clusters. A linkage rule specifies how to assess the possible joins. Ward linkage assesses each join by asking: how much will the total within-cluster sum of squares increase if these clusters are combined? It selects the pair with the smallest increase.
This rule uses the cluster sizes as well as the distance between their centroids. Consequently, choosing the pair with the closest centroids is not, in general, the same as choosing the pair with the smallest Ward cost. The distinction matters especially when candidate clusters have substantially different sizes.
Here, \(\|\cdot\|\) is the Euclidean norm, so its square is the sum of squared coordinate differences. Ward’s criterion is based on squared Euclidean distance. It is not the ordinary Euclidean distance between centroids, nor is it one of the pairwise-distance averages or extremes used by other linkage rules.
Deriving the Ward Merge Criterion
Suppose two disjoint clusters \(A\) and \(B\) have sizes \(n_A\) and \(n_B\), and centroids \(\bar{x}_A\) and \(\bar{x}_B\). Their combined cluster has size \(n_A+n_B\) and centroid $$ \bar{x}_{A\cup B}=\frac{n_A\bar{x}_A+n_B\bar{x}_B}{n_A+n_B}. $$ The other clusters in the current partition do not change during this proposed merge. Therefore, the change in total WCSS is the new WCSS of \(A\cup B\) minus the former WCSS values of \(A\) and \(B\).
For a point \(x\in A\), write \(x-\bar{x}_{A\cup B}=(x-\bar{x}_A)+(\bar{x}_A-\bar{x}_{A\cup B})\). When squared deviations are summed over \(A\), the cross-product term is zero because \(\sum_{x\in A}(x-\bar{x}_A)=0\). Thus the contribution from \(A\) is \(W(A)+n_A\|\bar{x}_A-\bar{x}_{A\cup B}\|^2\). The same argument applies to \(B\).
The new WCSS equals \(W(A)+W(B)+n_A\|\bar{x}_A-\bar{x}_{A\cup B}\|^2+n_B\|\bar{x}_B-\bar{x}_{A\cup B}\|^2\). Subtracting \(W(A)+W(B)\) leaves only the two centroid-displacement terms.
From the formula for \(\bar{x}_{A\cup B}\), \(\bar{x}_A-\bar{x}_{A\cup B}=\frac{n_B}{n_A+n_B}(\bar{x}_A-\bar{x}_B)\), and \(\bar{x}_B-\bar{x}_{A\cup B}=-\frac{n_A}{n_A+n_B}(\bar{x}_A-\bar{x}_B)\). Substitution gives the size factor \(\frac{n_A n_B}{n_A+n_B}\) multiplying the squared centroid separation.
The derivation also explains why the criterion depends on cluster size. A centroid’s displacement affects every observation in its cluster, so the cost is not determined by centroid separation alone. The factor \(n_A n_B/(n_A+n_B)\) is small when one cluster is very small relative to the other, and is large when both clusters are large.
Worked Example: Verifying a One-Dimensional Merge
Two clusters contain \(A=\{0,2\}\) and \(B=\{2,4,4,6\}\). Calculate the WCSS increase if they merge, and verify it by calculating the WCSS before and after the merge. The method is Ward’s criterion; the main trap is omitting its size factor.
Step 1: Find the sizes and centroids. Cluster \(A\) has \(n_A=2\) and mean \(\bar{x}_A=(0+2)/2=1\). Cluster \(B\) has \(n_B=4\) and mean \(\bar{x}_B=(2+4+4+6)/4=16/4=4\).
Step 2: Apply the criterion. The squared centroid separation is \((4-1)^2=9\), and the size factor is \((2\cdot4)/(2+4)=8/6=4/3\). Therefore, $$ \Delta(A,B)=\frac{4}{3}\cdot9=12. $$
Step 3: Check by direct WCSS calculations. Before merging, \(W(A)=(0-1)^2+(2-1)^2=1+1=2\). For \(B\), \(W(B)=(2-4)^2+(4-4)^2+(4-4)^2+(6-4)^2=4+0+0+4=8\). Total WCSS before the merge is \(2+8=10\).
The merged observations have mean \((0+2+2+4+4+6)/6=18/6=3\). Their WCSS is \((0-3)^2+(2-3)^2+(2-3)^2+(4-3)^2+(4-3)^2+(6-3)^2=9+1+1+1+1+9=22\). The increase is \(22-10=12\), which agrees with the formula. The calculation also shows why using only the squared centroid separation, 9, would be incorrect.
Comparing Candidate Merges
In more than one dimension, square the Euclidean distance by summing the squared differences in every coordinate. For example, if centroids are \((a_1,a_2)\) and \((b_1,b_2)\), the squared separation is \((a_1-b_1)^2+(a_2-b_2)^2\). Calculate this quantity for each candidate pair, multiply by that pair’s size factor, and compare the resulting increases.
Worked Example: Choosing Among Three Two-Dimensional Merges
Three current clusters have summaries \(A: n_A=2,\ \bar{x}_A=(0,0)\), \(B: n_B=3,\ \bar{x}_B=(2,0)\), and \(C: n_C=1,\ \bar{x}_C=(0,3)\). Calculate all three Ward costs and identify the merge Ward linkage selects. Do not compare centroid distances without their size factors.
Merge \(A\) with \(B\). Their squared centroid separation is \((2-0)^2+(0-0)^2=4\). Their size factor is \(2\cdot3/(2+3)=6/5\), so \(\Delta(A,B)=(6/5)\cdot4=24/5=4.8\).
Merge \(A\) with \(C\). The squared separation is \((0-0)^2+(3-0)^2=9\). The size factor is \(2\cdot1/(2+1)=2/3\), so \(\Delta(A,C)=(2/3)\cdot9=6\).
Merge \(B\) with \(C\). The squared separation is \((2-0)^2+(0-3)^2=4+9=13\). The size factor is \(3\cdot1/(3+1)=3/4\), so \(\Delta(B,C)=(3/4)\cdot13=39/4=9.75\).
Comparing the increases gives \(4.8<6<9.75\), so Ward linkage merges \(A\) and \(B\). The result is checked by comparing the calculated WCSS increases, not by comparing the three unsquared distances alone.
Worked Example: A Close Pair of Centroids Need Not Be the Ward Merge
Suppose three one-dimensional clusters have sizes and means \(A:(100,0)\), \(B:(100,1)\), and \(C:(1,-2)\). Determine the Ward merge and compare it with the pair having the closest centroids. This example tests whether cluster sizes have been included.
The centroid separations are \(|0-1|=1\) for \(A,B\), \(|0-(-2)|=2\) for \(A,C\), and \(|1-(-2)|=3\) for \(B,C\). Thus \(A,B\) have the closest centroids.
For \(A,B\), the size factor is \(100\cdot100/(100+100)=50\), and the squared separation is \(1\). Hence \(\Delta(A,B)=50\cdot1=50\).
For \(A,C\), the size factor is \(100\cdot1/(100+1)=100/101\), and the squared separation is \(2^2=4\). Hence \(\Delta(A,C)=400/101\), approximately \(3.9604\).
For \(B,C\), the size factor is also \(100/101\), and the squared separation is \(3^2=9\). Hence \(\Delta(B,C)=900/101\), approximately \(8.9109\). Since \(400/101<900/101<50\), Ward linkage merges \(A,C\), even though \(A,B\) have the closest centroids. The small size of \(C\) makes its merge with \(A\) less costly in WCSS.
The method is to calculate all size-adjusted squared separations. The common mistake this avoids is choosing \(A,B\) just because their centroids are nearest.
What the Criterion Measures—and What It Does Not
Ward’s rule is a greedy merging rule: at each stage it selects the current pair with the least increase in total WCSS. It does not search all possible sequences of future merges to find a globally optimal final partition. Nor does a small merge cost mean that the two clusters are identical; it means that combining them produces a relatively small increase under this particular measure.
The calculation uses the current cluster sizes and centroids, so those summaries are sufficient to calculate a candidate merge cost. The clusters can contain many observations, but the formula does not require listing all point-to-point distances once those summaries are known. After a merge, the new size and centroid must be used when evaluating later candidate merges.
| Quantity | Role in Ward linkage | Common misinterpretation |
|---|---|---|
| \(n_A,n_B\) | Determine the size factor \(n_A n_B/(n_A+n_B)\) | Assuming cluster sizes do not affect the merge |
| \(\|\bar{x}_A-\bar{x}_B\|^2\) | Squared Euclidean separation of the centroids | Using the unsquared distance alone |
| \(\Delta(A,B)\) | Increase in total WCSS from the candidate merge | Calling it the distance between the clusters without specifying a convention |
Feature scale is important because squared coordinate differences contribute directly to the cost. If one feature is measured in much larger numerical units than another, it can dominate the squared distances. Any scaling or weighting decision should therefore be made deliberately and consistently with the analysis. The Ward formula is not a general-purpose criterion for arbitrary dissimilarities: if observations have no meaningful Euclidean coordinates, or a non-Euclidean dissimilarity is substituted, this WCSS derivation does not justify the same merge costs.
Common Exam Traps
- Dropping the size factor. The cost is not merely the squared distance between centroids. For sizes 2 and 4 with means 1 and 4, the correct increase is \((2\cdot4/6)(4-1)^2=(4/3)\cdot9=12\), not 9.
- Doubling the size factor calculation. For those same sizes, \(2\cdot4/(2+4)=8/6=4/3\), not \(8/3\). The denominator is the sum of the two sizes.
- Using an ordinary distance where a squared distance is required. If centroid separation is 3, the term in the criterion is \(3^2=9\), not 3.
- Choosing the closest centroids automatically. A pair with greater separation can have a lower merge cost if its size factor is sufficiently smaller.
- Forgetting that other clusters are unchanged. In a proposed merge, their WCSS contributions cancel when calculating the increase in total WCSS.
Check Your Understanding
For each problem, calculate the requested Ward merge cost using the stated cluster sizes and centroids. Keep the size factor and squared Euclidean separation distinct.
- Two one-dimensional clusters have sizes 3 and 5 and means 2 and 5. What is the WCSS increase if they merge? (Answer: \(45/8=5.625\))
- Two clusters have sizes 2 and 6 and centroids \((1,1)\) and \((4,5)\). Calculate the merge increase using squared Euclidean distance. (Answer: \(60\))
- Three one-dimensional clusters have summaries \(A:(4,0)\), \(B:(4,2)\), and \(C:(1,5)\), where each pair lists size and mean. Calculate all three merge costs and name the selected pair. (Answer: \(\Delta(A,B)=8\), \(\Delta(A,C)=100/5=20\), \(\Delta(B,C)=9/5\cdot9=81/5=16.2\); merge \(A,B\))
- Clusters \(P\) and \(Q\) have sizes 8 and 2, and centroids \((0,0)\) and \((3,4)\). A third cluster \(R\) has size 1 and centroid \((0,2)\). Calculate the three candidate costs and select the Ward merge. (Answer: \(\Delta(P,Q)=80\), \(\Delta(P,R)=32/9\), \(\Delta(Q,R)=20/3\); merge \(P,R\))
- Two clusters have sizes 10 and 10 and centroid separation 1. A third cluster has size 1 and is at centroid distance 2 from the first cluster. Compare the cost of merging the two size-10 clusters with the cost of merging the first cluster and the singleton. (Answer: first pair cost \(5\); first cluster with singleton cost \(40/11\); Ward prefers the first cluster and singleton.)