Exam PA · Clustering and Similarity Structure · Tutorial 598 of 966
Ward Linkage And Its Increase In Within-Cluster Variation
Learn to derive Ward’s merge cost and use it to compare candidate merges while avoiding common mistakes about squared distance and cluster size.
Intermediate
12 min read
What You'll Learn
Define within-cluster sum of squares for a cluster of numeric observations
Derive Ward’s merge cost from the weighted cluster centroids
Calculate a merge cost from cluster sizes, centroids, and within-cluster sums of squares
Compare candidate merges using Ward’s criterion
Explain why the criterion tends to favor compact groups under squared Euclidean distance
Recognize common calculation and interpretation traps
What Ward Linkage Measures
Hierarchical clustering repeatedly joins two clusters. The linkage rule determines which pair is joined next. Ward linkage chooses a pair by asking: which merge produces the smallest increase in within-cluster variation? This makes the rule different from comparing only the closest pair of observations or only the distance between two cluster representatives.
Ward linkage is defined for numeric observations represented as vectors, with squared Euclidean distance as the measure of variation. The variables should be on scales that make the resulting distances meaningful; if their units differ substantially, scaling choices can affect the merge sequence. This tutorial derives the merge criterion and explains its interpretation. The method is aligned with the SOA Exam PA (Predictive Analytics) syllabus.
Definition: Let \(C\) be a cluster of \(n_C\) observations \(x_i\), each represented by a vector of \(p\) numeric features. Its centroid is \(\bar{x}_C=(1/n_C)\sum_{i\in C}x_i\). Its within-cluster sum of squares is
$$
W(C)=\sum_{i\in C}\lVert x_i-\bar{x}_C\rVert^2.
$$
For two disjoint clusters \(A\) and \(B\), Ward’s merge cost is the increase in within-cluster sum of squares, \( \Delta(A,B)=W(A\cup B)-W(A)-W(B) \).
The norm in this definition is Euclidean: for a vector with \(p\) coordinates, its squared norm is the sum of the squared coordinate differences. Thus the criterion depends on squared Euclidean distances, not on raw distances. For a collection of clusters, the total within-cluster sum of squares is the sum of their individual \(W\) values. Merging \(A\) and \(B\) changes that total by exactly \(\Delta(A,B)\); all other clusters are unchanged.
Deriving the Merge Cost
The key result expresses the increase using only the two cluster sizes and their centroids. It applies to nonempty, disjoint clusters of numeric vectors in the same feature space, with finite within-cluster sums of squares. Write \(n_A\) and \(n_B\) for their sizes and \(\bar{x}_A\) and \(\bar{x}_B\) for their centroids. The merged centroid is the size-weighted average
$$
\bar{x}_{A\cup B}=\frac{n_A\bar{x}_A+n_B\bar{x}_B}{n_A+n_B}.
$$
To see why the merge formula holds, consider any cluster \(C\) with centroid \(\bar{x}_C\) and a proposed reference point \(m\). Expanding each squared distance gives
$$
\sum_{i\in C}\lVert x_i-m\rVert^2
=
W(C)+n_C\lVert\bar{x}_C-m\rVert^2.
$$
The cross term vanishes because \(\sum_{i\in C}(x_i-\bar{x}_C)=0\). Apply this identity to clusters \(A\) and \(B\), using their merged centroid \(m=\bar{x}_{A\cup B}\). The merged sum of squares equals the two original sums plus the squared displacement of each centroid from the merged centroid, weighted by its cluster size.
For the second equality, substitute the weighted-centroid expression. The two displacements are
$$
\bar{x}_A-\bar{x}_{A\cup B}
=\frac{n_B}{n_A+n_B}(\bar{x}_A-\bar{x}_B),
\qquad
\bar{x}_B-\bar{x}_{A\cup B}
=-\frac{n_A}{n_A+n_B}(\bar{x}_A-\bar{x}_B).
$$
Their weighted squared lengths therefore sum to
$$
n_A\frac{n_B^2}{(n_A+n_B)^2}\lVert\bar{x}_A-\bar{x}_B\rVert^2
+n_B\frac{n_A^2}{(n_A+n_B)^2}\lVert\bar{x}_A-\bar{x}_B\rVert^2
=
\frac{n_A n_B}{n_A+n_B}\lVert\bar{x}_A-\bar{x}_B\rVert^2.
$$
This proves the criterion. Ward linkage selects the pair with the smallest \(\Delta(A,B)\) at each merge. The formula does not apply unchanged to arbitrary dissimilarities, such as a non-Euclidean distance matrix: it relies on the within-cluster sum of squared Euclidean deviations from centroids.
Theorem: For squared Euclidean features, the increase in total within-cluster sum of squares from merging \(A\) and \(B\) is
$$
\Delta(A,B)=\frac{n_A n_B}{n_A+n_B}\lVert\bar{x}_A-\bar{x}_B\rVert^2.
$$
At each step, Ward linkage merges the pair with the smallest increase. The criterion includes both centroid separation and cluster size.
Using the Criterion
A useful calculation sequence is to identify the sizes and centroids, calculate the squared distance between centroids, multiply by the size factor, and compare the resulting costs. If the original within-cluster sums of squares are supplied, add the cost to their sum to obtain the merged cluster’s within-cluster sum of squares.
Worked Example: Correcting a Merged Sum of Squares
Two one-dimensional clusters have sizes \(n_A=3\) and \(n_B=2\), centroids \(\bar{x}_A=2\) and \(\bar{x}_B=8\), and within-cluster sums of squares \(W(A)=4\) and \(W(B)=2\). Find the merged centroid and merged within-cluster sum of squares. The cluster summaries are taken as given.
Method. Use the weighted centroid for the merged cluster, then add Ward’s merge cost to the two original sums of squares. This avoids confusing the increase with the final merged sum.
Step 1: Find the merged centroid.
$$
\bar{x}_{A\cup B}=\frac{3(2)+2(8)}{3+2}=\frac{6+16}{5}=\frac{22}{5}=4.4.
$$
Step 2: Find the squared distance between centroids. In one dimension, the squared distance is
$$
(8-2)^2=6^2=36.
$$
Step 3: Calculate the increase.
$$
\Delta(A,B)=\frac{3(2)}{3+2}(36)=\frac{6}{5}(36)=43.2.
$$
Step 4: Calculate the merged sum of squares.
$$
W(A\cup B)=W(A)+W(B)+\Delta(A,B)=4+2+43.2=49.2.
$$
Check. The centroid displacements contribute \(3(2-4.4)^2=3(5.76)=17.28\) and \(2(8-4.4)^2=2(12.96)=25.92\). Their sum is \(17.28+25.92=43.2\), so adding the original \(4+2=6\) gives \(49.2\). The merge increases within-cluster variation by \(43.2\); that increase is not itself the merged sum of squares.
Worked Example: Comparing Three Candidate Merges
Suppose three clusters have the following summaries in a two-dimensional feature space: \(A\) has size 2, centroid \((0,0)\), and \(W(A)=1.5\); \(B\) has size 3, centroid \((2,0)\), and \(W(B)=2\); \(C\) has size 2, centroid \((0,5)\), and \(W(C)=1.2\). Determine which pair Ward linkage merges first and the within-cluster sum of squares after that merge.
Method. Calculate the merge cost for each candidate pair. The original sums of squares are not needed to rank the costs, but they are needed for the merged sum.
Candidate \(A,B\). Their squared centroid distance is \((2-0)^2+(0-0)^2=4\). Their size factor is \(2(3)/(2+3)=6/5\). Therefore
$$
\Delta(A,B)=\frac{6}{5}(4)=4.8.
$$
Candidate \(A,C\). Their squared centroid distance is \((0-0)^2+(5-0)^2=25\), and their size factor is \(2(2)/(2+2)=1\). Thus \(\Delta(A,C)=1(25)=25\).
Candidate \(B,C\). Their squared centroid distance is \((2-0)^2+(0-5)^2=4+25=29\), and their size factor is \(3(2)/(3+2)=6/5\). Thus \(\Delta(B,C)=(6/5)(29)=34.8\).
The costs are \(4.8\), \(25\), and \(34.8\), so Ward linkage merges \(A\) and \(B\). The merged sum of squares is
$$
W(A\cup B)=1.5+2+4.8=8.3.
$$
Check. This is an increase of \(4.8\) over the previous total for those clusters, \(1.5+2=3.5\). The cost ranking is based on the increase, not on the post-merge total including each pair’s original sums.
Worked Example: A Two-Dimensional Merge and Direct Check
Cluster \(A\) contains points \((0,0)\) and \((2,0)\). Cluster \(B\) contains the single point \((4,3)\). Calculate Ward’s merge cost and verify the resulting within-cluster sum of squares directly from the merged centroid.
Step 1: Find the summaries. Cluster \(A\) has size 2 and centroid \((1,0)\). Its within-cluster sum is
$$
W(A)=[(0-1)^2+(0-0)^2]+[(2-1)^2+(0-0)^2]=1+1=2.
$$
Cluster \(B\) has size 1, centroid \((4,3)\), and \(W(B)=0\).
Step 2: Calculate the merge cost. The squared centroid distance is \((4-1)^2+(3-0)^2=9+9=18\). The size factor is \(2(1)/(2+1)=2/3\). Hence
$$
\Delta(A,B)=\frac{2}{3}(18)=12.
$$
Step 3: Find the merged sum. The merged centroid is
$$
\bar{x}_{A\cup B}=\left(\frac{0+2+4}{3},\frac{0+0+3}{3}\right)=(2,1).
$$
Thus the merged sum is \(W(A)+W(B)+\Delta(A,B)=2+0+12=14\).
Direct check. Squared distances from \((2,1)\) are \(5\) for \((0,0)\), \(1\) for \((2,0)\), and \(8\) for \((4,3)\). Their sum is \(5+1+8=14\), matching the criterion.
Why the Criterion Tends to Form Compact Groups
A merge cost grows when the centroids are farther apart because the squared centroid distance is multiplied by the size factor. It also reflects cluster sizes: a merge between a large cluster and a small one is not assessed by centroid distance alone. Consequently, a pair with a somewhat larger centroid distance can have a lower cost than another pair if its size factor is smaller.
The criterion tends to form compact groups because every merge is judged by how much it increases squared deviation from the new centroid. A large increase means that joining the groups would leave observations, collectively, farther from their assigned centroid. This tendency is not a guarantee that all resulting clusters are spherical, equal in size, or substantively meaningful. The result depends on the feature representation and scaling, and squared distances give greater influence to large deviations than ordinary distances do.
A dendrogram may display merge heights rather than the raw increases \(\Delta\). The exact height convention depends on the implementation. Interpret a reported height using that implementation’s definition; do not assume it is numerically identical to the increase in within-cluster sum of squares. The criterion itself is the increase \(\Delta\), and minimizing it determines the chosen pair.
Common Mistakes and Exam Traps
Reporting the increase as the new total. If \(W(A)=4\), \(W(B)=2\), and \(\Delta=43.2\), the merged sum is \(4+2+43.2=49.2\), not \(43.2\).
Using the centroid distance without squaring it. The formula uses \(\lVert\bar{x}_A-\bar{x}_B\rVert^2\). For centroids separated by 6 units in one dimension, the squared distance is \(36\), not \(6\).
Ignoring cluster sizes. The factor \(n_A n_B/(n_A+n_B)\) must be included. Centroid distances alone do not generally rank candidate merges the same way.
Using the wrong distance summary. Ward’s criterion uses the squared Euclidean distance between cluster centroids in the merge-cost formula. It is not the average of all pairwise distances between observations in the clusters.
Applying the formula to an arbitrary distance matrix. The derivation uses Euclidean vectors and centroids. Without that structure, the sum-of-squares interpretation and formula need not hold.
Key takeaway: Ward linkage chooses the merge with the smallest increase in total within-cluster sum of squares. Calculate that increase as the size factor \(n_A n_B/(n_A+n_B)\) times the squared Euclidean distance between centroids, then add the original sums of squares only if the merged total is requested.
Check Your Understanding
For each problem, calculate the requested Ward quantity using the cluster sizes and centroids provided.
Two one-dimensional clusters have sizes 4 and 1, with centroids 3 and \(-2\). Find the increase in within-cluster sum of squares if they are merged. (Answer: \(20\))
Two clusters have sizes 2 and 4, with centroids \((1,1)\) and \((4,5)\). Find the merge cost. (Answer: \(100/3\), or approximately \(33.3333\))
Clusters \(A\) and \(B\) have sizes 3 and 2, centroids 0 and 4, and within-cluster sums of squares 6 and 3. Find the merge cost and merged sum of squares. (Answer: merge cost \(19.2\); merged sum of squares \(28.2\))
Cluster \(A\) contains \((0,0)\) and \((2,0)\); cluster \(B\) contains \((3,4)\). Find the Ward merge cost and verify the merged sum of squares. (Answer: merge cost \(40/3\); merged sum of squares \(46/3\))
Three one-dimensional clusters have summaries \(A:(n=2,\bar{x}=0)\), \(B:(n=3,\bar{x}=2)\), and \(C:(n=1,\bar{x}=5)\). Calculate all three candidate merge costs and identify the first merge. (Answer: \(\Delta(A,B)=4.8\), \(\Delta(A,C)=50/3\), \(\Delta(B,C)=6.75\); merge \(A\) and \(B\))