Why Ward Linkage Requires Careful Distance Interpretation
Hierarchical clustering merges clusters one pair at a time. Ward’s method chooses the merge that causes the smallest increase in within-cluster variation. This gives it a precise objective, but it also means that Ward linkage is not simply a generic linkage rule applied to ordinary Euclidean distances. The distinction matters whenever a dissimilarity matrix or software output is interpreted.
The key quantity is the increase in within-cluster sum of squares. For observations represented by numerical feature vectors, Ward’s merge cost depends on both the squared distance between cluster centroids and the sizes of the clusters. Squared Euclidean distances enter the derivation naturally; ordinary Euclidean distances do not replace the criterion.
This definition assumes ordinary, unweighted observations in a Euclidean feature space and a specified set of features and scales. All observations contribute equally to the sums. If features have been transformed or scaled, the criterion applies to those transformed coordinates. The merge cost is nonnegative; it is zero when the two cluster centroids coincide.
Deriving the Ward Merge Cost
Let \(n_A\) and \(n_B\) be the sizes of two clusters, and let \(\bar{x}_A\) and \(\bar{x}_B\) be their centroids. The centroid of their union is the size-weighted average \(\bar{x}_{A\cup B}=(n_A\bar{x}_A+n_B\bar{x}_B)/(n_A+n_B)\). The weight is essential: an unweighted average of the two centroids is correct only when the cluster sizes are equal.
To find the extra sum of squares, write each observation in \(A\) as its deviation from \(\bar{x}_A\), plus the displacement of \(\bar{x}_A\) from the new centroid. When squared deviations are summed, the cross-product terms vanish because the deviations from a cluster centroid sum to zero. The same argument applies to \(B\).
Subtracting \(W(A)+W(B)\) leaves the two centroid-displacement terms. From the weighted-centroid formula, \(\bar{x}_A-\bar{x}_{A\cup B}=\frac{n_B}{n_A+n_B}(\bar{x}_A-\bar{x}_B)\), while \(\bar{x}_B-\bar{x}_{A\cup B}=-\frac{n_A}{n_A+n_B}(\bar{x}_A-\bar{x}_B)\). Substitution gives the standard formula:
The multiplier \(\frac{n_A n_B}{n_A+n_B}\) makes the cost depend on cluster sizes as well as centroid separation. A small centroid gap can still have a substantial cost when both clusters are large. Conversely, a pair of singleton clusters at separation \(d\) has cost \(d^2/2\). That initial-stage relationship explains why squared Euclidean distances are closely associated with Ward’s method, but it does not make Ward identical to every linkage calculation using squared distances.
Worked Example: Calculating a Merge Cost from Two-Dimensional Clusters
A clustering step considers \(A=\{(0,0),(2,0)\}\) and \(B=\{(1,2),(1,4)\}\). Calculate the Ward cost directly from the centroids, then verify it by calculating the within-cluster sums of squares before and after merging. The method is the increase-in-sum-of-squares criterion; the check guards against confusing centroid distance with merge cost.
Centroids and sizes. Both clusters have size \(2\). Their centroids are \(\bar{x}_A=(1,0)\) and \(\bar{x}_B=(1,3)\). Their squared centroid separation is \((1-1)^2+(0-3)^2=9\).
Ward cost. The size multiplier is \(2(2)/(2+2)=1\). Therefore, \(\Delta(A,B)=1(9)=9\).
Check using within-cluster sums of squares. In \(A\), each point is one unit from its centroid, so \(W(A)=1^2+1^2=2\). In \(B\), each point is also one unit from its centroid, so \(W(B)=2\). The union centroid is \((1,1.5)\). The two points in \(A\) each have squared distance \(1^2+1.5^2=3.25\) from it; the points in \(B\) have squared distances \(0.5^2=0.25\) and \(2.5^2=6.25\). Thus \(W(A\cup B)=3.25+3.25+0.25+6.25=13\).
The increase is \(13-2-2=9\), matching the formula. The direct calculation checks that the merge cost is not merely the squared centroid distance in every case: here the multiplier happens to equal \(1\).
How Squared Euclidean Distances Enter
The connection to squared Euclidean distances can also be seen from the observation pairs crossing between two clusters. Summing squared distances over every pair with one point in \(A\) and one in \(B\) gives the identity below. Here the sum is over unordered cross-cluster pairs, so each such pair is included once.
To justify it, write \(x_i-x_j=(x_i-\bar{x}_A)+(\bar{x}_A-\bar{x}_B)+(\bar{x}_B-x_j)\), square the norm, and sum over \(i\) and \(j\). Terms involving a single centered deviation sum to zero, since \(\sum_{i\in A}(x_i-\bar{x}_A)=0\) and \(\sum_{j\in B}(x_j-\bar{x}_B)=0\). The remaining within-cluster terms are \(n_BW(A)\) and \(n_AW(B)\); the constant centroid-separation term appears \(n_An_B\) times.
The formula for \(\Delta(A,B)\) then shows that the final term in this cross-pair identity is \((n_A+n_B)\Delta(A,B)\). Thus Ward’s objective is linked to squared Euclidean geometry. It is not, however, the sum or average of the ordinary Euclidean distances between all cross-cluster pairs. Nor is it simply the average of their squared distances: the Ward cost is specifically the increase in total within-cluster sum of squares.
Worked Example: Ward Versus Average Linkage
At a particular stage, let \(A=\{0,2,10\}\) lie on the real line, with two candidate clusters \(B=\{4.2\}\) and \(C=\{3\}\). Compare the Ward costs with average linkage based first on ordinary Euclidean distances and then on squared Euclidean distances. The method is to calculate each rule as defined; the trap is to treat the three calculations as interchangeable because they use the same observations.
Ward costs. The size of \(A\) is \(3\), and its centroid is \((0+2+10)/3=4\). Each candidate has size \(1\). For \(B\), the squared centroid gap is \((4.2-4)^2=0.04\), and the size multiplier is \(3(1)/4=0.75\). Thus \(\Delta(A,B)=0.75(0.04)=0.03\). For \(C\), the squared gap is \((3-4)^2=1\), so \(\Delta(A,C)=0.75(1)=0.75\). Ward chooses \(B\).
Average ordinary Euclidean distances. The distances from \(B\) to the three points in \(A\) are \(4.2\), \(2.2\), and \(5.8\), whose average is \(12.2/3=4.0667\) to four decimal places. The distances from \(C\) are \(3\), \(1\), and \(7\), whose average is \(11/3=3.6667\) to four decimal places. Average linkage on ordinary distances chooses \(C\), not \(B\).
Average squared Euclidean distances. For \(B\), the squared distances are \(17.64\), \(4.84\), and \(33.64\). Their average is \(56.12/3=18.7067\) to four decimal places. For \(C\), they are \(9\), \(1\), and \(49\); their average is \(59/3=19.6667\) to four decimal places. This generic average-linkage calculation on squared distances chooses \(B\). It agrees with Ward’s choice here, but its values, \(18.7067\) and \(19.6667\), are not Ward costs, \(0.03\) and \(0.75\). The three rules answer different questions.
Interpreting the Distance Convention
A distance convention must be identified before comparing merge costs or interpreting heights. The following table summarizes the distinction. “Generic average linkage” means the mean of all pairwise dissimilarities between observations in the two clusters.
| Calculation | Quantity compared | What it represents |
|---|---|---|
| Ward | \(\frac{n_A n_B}{n_A+n_B}\|\bar{x}_A-\bar{x}_B\|^2\) | Increase in within-cluster sum of squares |
| Average linkage on ordinary distances | Mean of cross-cluster Euclidean distances | Average pairwise separation on the original distance scale |
| Average linkage on squared distances | Mean of cross-cluster squared Euclidean distances | Average pairwise squared separation, not the Ward increase |
For singleton clusters, Ward’s cost is one-half the squared Euclidean distance between their observations. Since squaring preserves the ordering of nonnegative distances, the first Ward merge has the same ordering as the closest singleton pair under ordinary Euclidean distance. At later steps, cluster sizes and centroids matter, so this simple equivalence does not justify using a generic linkage calculation.
A reported dendrogram height also needs its convention stated. An implementation may report the increase in sum of squares itself or a transformed height, such as a square-root or rescaled version. Those choices affect the numerical height, not the definition of the Ward merge cost or the merge chosen when the transformation preserves the ordering. Interpret a height using the implementation’s stated convention rather than assuming it is an ordinary Euclidean distance.
Worked Example: Two Singleton Merges and the Next Ward Decision
Four observations are \(P=(0,0)\), \(Q=(2,0)\), \(R=(2,2)\), and \(S=(6,2)\). Calculate the singleton Ward costs, take \(P,Q\) as the first merge under a stated tie rule, and find the next merge. The method is to use half the squared distance for singleton pairs, then recalculate cluster sizes and centroids. This avoids continuing to use singleton distances after a cluster has formed.
Initial singleton costs. The squared distances for \(PQ\), \(QR\), \(PR\), \(RS\), \(QS\), and \(PS\) are respectively \(4,4,8,16,20,40\). Since each pair consists of singletons, its Ward cost is half its squared distance: \(2,2,4,8,10,20\), respectively. The minimum cost is \(2\), tied between \(PQ\) and \(QR\). Suppose the tie rule selects \(PQ\).
Recalculate the candidates. The new cluster \(A=\{P,Q\}\) has size \(2\) and centroid \((1,0)\). Cluster \(R\) has centroid \((2,2)\) and size \(1\), so \(\Delta(A,R)=\frac{2(1)}{3}[(2-1)^2+(2-0)^2]=\frac{2}{3}(5)=10/3\). Cluster \(S\) has centroid \((6,2)\) and size \(1\), so \(\Delta(A,S)=\frac{2}{3}[(6-1)^2+(2-0)^2]=\frac{2}{3}(29)=58/3\). The remaining singleton pair \(R,S\) has squared distance \(16\), so its cost is \(8\).
The three available costs are \(10/3\), \(58/3\), and \(8\). Since \(10/3<8<58/3\), Ward next merges \(A\) with \(R\). The check is the direct comparison of all current candidate costs; the initial singleton distance ranking alone would not determine this next step.
Common Mistakes and Practical Checks
- Using the centroid distance alone. The Ward cost includes the multiplier \(n_An_B/(n_A+n_B)\). Omitting it can change the chosen pair, especially when cluster sizes differ.
- Using ordinary distances in the Ward formula. The centroid separation is squared. Using \(\|\bar{x}_A-\bar{x}_B\|\) rather than its square does not calculate the increase in sum of squares.
- Calling average squared distance Ward linkage. A generic average of squared pairwise distances is a different quantity. The Ward cost follows from the change in within-cluster sum of squares.
- Ignoring feature scaling. Squared differences give larger-scale features greater influence. The chosen coordinate scale is part of the clustering specification.
- Assuming every reported height is an ordinary distance. Check whether the implementation reports a sum-of-squares increase or a transformed height.
Check Your Understanding
For each problem, state the distance convention used and calculate the requested quantity before checking the answer.
- Two singleton observations in a two-dimensional feature space are separated by Euclidean distance \(6\). What is their Ward merge cost? (Answer: \(18\).)
- Clusters \(A\) and \(B\) have sizes \(3\) and \(2\), and their centroids are \(4\) units apart in Euclidean distance. Calculate their Ward merge cost. (Answer: \(19.2\).)
- On the real line, \(A=\{0,2,8\}\) and \(B=\{5\}\). Calculate the Ward cost using cluster sizes and centroids. (Answer: \(25/12\), approximately \(2.0833\).)
- Let \(A=\{0,2,10\}\), \(B=\{4.2\}\), and \(C=\{3\}\), all on the real line. Which candidate is chosen by Ward, and which by average linkage on ordinary Euclidean distances? (Answer: Ward chooses \(B\); average linkage on ordinary distances chooses \(C\).)
- For the three one-dimensional observations \(0,2,4\), calculate their within-cluster sum of squares about their common centroid, and verify it using the sum of unordered pairwise squared distances divided by the number of observations. (Answer: \(8\); the pairwise squared distances sum to \(24\), and \(24/3=8\).)