Why measure the cost of a merge?
A hierarchical clustering begins with each observation in its own group and successively merges two groups. Single linkage looks for the closest pair of observations across two groups; Ward's method instead asks how much the best within-group squared reconstruction error increases. The question connects hierarchical clustering to the same squared-error objective used by k-means, but the algorithms do not search the same sets of partitions. Once Ward merges two groups, it never separates them again.
Definition 23.1.1
(Within-group error and Ward merge cost)
Let be a fixed, nonempty finite sample, with Euclidean distance and equal observation weights. For a nonempty index set , write , , and let be its within-group squared error. For disjoint nonempty groups , the Ward merge cost is
Ward's method repeatedly merges a pair of current groups with the smallest merge cost.
Ties need a specified rule. Record the actual increase if plotting merge heights: software conventions sometimes display a rescaled quantity instead.
Theorem 23.1.2
(The Ward merge identity)
For disjoint nonempty ,
In particular, the merge cost is nonnegative, and group sizes matter as well as the distance between means.
Proof
(Decompose deviations about each group mean)
Put . Expanding and summing over , the cross term vanishes because . Hence , with the analogous identity for . Adding the two identities gives , so
Since , the two offsets are respectively and . Substituting,
The formula remains valid for repeated observations; two distinct groups can have zero cost when their means agree.
Proof X-ray
What the merge identity proof depends on
Two facts do all the work. The cross term disappears only because each group is centered at its own mean, where ; around any other center the decomposition would carry an extra linear term. The offsets are then forced by the weighted mean , which divides the segment between the two means in the ratio from . The product-over-sum weight appears when is divided by . Equal observation weights are used here; with unequal weights each would be replaced by a total weight. The dimension plays no role, and nonnegativity and the equality case (equal means) are read off at the end.
The identity also lets us avoid recomputing means after a merge.
Proposition 23.1.3
(Updating merge costs after a merge)
For pairwise disjoint nonempty groups with sizes ,
Proof
(Split the merged group about its own mean)
Write for the means of and for the mean of . Expanding and , the cross terms combine to , because is the weighted mean. Therefore
where the last term is the expression found in the previous proof. Multiply by . By the merge identity applied to and , ; likewise and . Substituting and dividing by gives the claim.
So after each merge the costs to every remaining group can be computed from three stored numbers, without returning to the data.
A complete small hierarchy
Worked example 23.1.4
(Four one-dimensional observations)
Take . The initial singleton merge costs are half the squared distances. The smallest is . The new group has size two and mean . Its cost to merge with is , while its cost to merge with is . The remaining singleton pair costs 50. Thus the second merge forms and increases total within-group error to . Its mean is ; merging with costs . The final error is , also obtained directly from the overall mean . The merge costs are therefore under this convention.
The update formula reproduces the second step without any new means. With , , , the singleton costs are , , , so . With the costs are and , giving .
Concept lensStructural
Ward's cost as lost between-group scatter
The total scatter does not depend on the partition. For a partition into groups , , a within-group part plus a between-group part. A merge raises the within-group part by , so it lowers the between-group part by exactly . Ward therefore loses the least between-group scatter at each step. In the four-point example the singletons have between-group part , and the three costs sum to it.
Worked example 23.1.5
(Two dimensions and a tie)
Take the corners of a rectangle, , , , . Singleton costs are half the squared distances: for each vertical pair, for each horizontal pair and for each diagonal pair. The two vertical pairs tie at . Suppose the tie rule merges the left pair first; its mean is . Its costs to the remaining singletons are each, while the right vertical pair still costs , so the second merge forms the right pair, with mean . The third merge costs . The merge costs are and the final error is . The overall mean is and each corner has squared deviation , so the direct total is also . Resolving the first tie the other way produces the same hierarchy here, because the other vertical pair is then the unique cheapest merge.
Worked example 23.1.6
(Repeated observations merge for free)
Take the sample . The two copies of have mean difference zero, so , while merging with costs . The first merge therefore creates at no cost. Merging it with costs , which is the final error. Directly, the overall mean is and the squared deviations are , with sum . A zero merge cost is the edge case of the identity: it records equal means, not an absence of earlier error.
Counterexample mode
Nearest points and nearest merge costs need not agree
For current groups , and , the smallest single-link distance is one between and . Ward's corresponding increase is , whereas merging costs . It chooses . These are legitimate current groups for illustrating the rules; no claim is made that this partition arose from Ward's earlier merges. The distances between the nearest observations alone do not determine Ward's criterion.
Common mistakes
Common mistake
(A small merge cost is not a population guarantee)
A hierarchy depends on the sample, feature scales and distance. Squared distances give a large numerical influence to outliers and to coordinates with large units. Standardization may be sensible when units are arbitrary, but it changes the objective and should be fitted on training data when the procedure is part of a predictive workflow. Selecting a cut from the same data is a modeling decision, not evidence that a unique true number of groups exists.
Common mistake
(Cutting the hierarchy does not give the best partition of that size)
At each stage the identity picks the cheapest next merge among the current groups. It does not compare all partitions with one fewer group, because most of them cannot be obtained by merging two current groups, so the total error rising monotonically proves nothing about optimality. For the observations the singleton costs are for the pairs , so Ward first merges . Merging with costs , merging it with costs , and merging with costs , so it forms with error . The partition has error and can never appear in this hierarchy, because and were already joined.
Practice and solutions
Quick check
(For and , calculate each within-group error and the merge increase. What is the total error after merging?)
Find the two group means first.
Solution · Answer
The means are 2 and 7, and each group has error . The merge increase is , so the combined error is . Directly, the combined mean is and the four squared deviations also sum to 41.
Quick check
(Two groups have equal means. Does Ward necessarily say that every observation in the groups is identical? Explain.)
Look for two groups with the same mean but spread-out observations.
Solution · Answer
No. The groups and both have mean zero, so their merge cost is zero, but each has positive internal error. Ward measures the additional cost of replacing two means by one; it does not say that the pre-existing error is zero.
Quick check
(Multiplying every coordinate by 3 changes a merge cost by what factor? Does the merge order necessarily change?)
Track what happens to the distance between means.
Solution · Answer
Every mean difference is multiplied by three, so every cost is multiplied by nine. Exact arithmetic preserves strict ordering and ties, so the same deterministic tie rule preserves the merge sequence. Scaling different coordinates by different factors can change the order.
Quick check
(Use the update formula to find the cost of merging with from the three singleton costs, and check it directly.)
Take , , .
Solution · Answer
The singleton costs are , and . The formula gives . Directly, has mean and size , so the cost is .