Why Distance Updates Matter
In agglomerative hierarchical clustering, each step merges two clusters. The algorithm must then calculate the new cluster’s distance to every cluster that remains. Recomputing that distance directly from all observations can be inconvenient; the Lance–Williams formula expresses it using distances already available and the sizes of the clusters.
The formula is a framework, not one universal choice of coefficients. Single, complete, average, and Ward linkage use different coefficients because they define cluster distance differently. In particular, Ward linkage requires care about whether the stored quantity is a Ward dissimilarity or its square.
Here, \(d_{A,B}\) is the distance between the two clusters about to merge, while \(d_{A,C}\) and \(d_{B,C}\) are their current distances to a third cluster. The recurrence updates one distance at a time; after a merge, it is applied separately to each remaining cluster \(C\).
Single and Complete Linkage
Single linkage defines the distance between two clusters as the smallest distance between a point in one and a point in the other. Complete linkage uses the largest such point-to-point distance. These definitions lead to minimum and maximum updates, respectively.
To see why, let \(x=d_{A,C}\) and \(y=d_{B,C}\). The identities $$ \min(x,y)=\frac{x+y-\lvert x-y\rvert}{2}, \qquad \max(x,y)=\frac{x+y+\lvert x-y\rvert}{2} $$ give exactly the single- and complete-linkage coefficients. The distance \(d_{A,B}\) does not enter either update. This derivation relies on the definitions of those linkages; it does not establish the same minimum or maximum rule for other linkage methods.
Worked Example: Updating Single and Complete Linkage
A clustering step merges clusters \(A\) and \(B\). The available linkage distances to a third cluster \(C\) are \(d_{A,C}=6\), \(d_{B,C}=10\), and \(d_{A,B}=4\). Find the new distance from \(A\cup B\) to \(C\) under both single and complete linkage.
Single linkage. Its coefficients are \(\alpha_A=\alpha_B=\tfrac12\), \(\beta=0\), and \(\gamma=-\tfrac12\). First, \(\lvert 6-10\rvert=4\). Substitution gives $$ d_{A\cup B,C} =\tfrac12(6)+\tfrac12(10)+0(4)-\tfrac12(4) =3+5-2=6. $$ This agrees with \(\min(6,10)=6\).
Complete linkage. The coefficients are \(\alpha_A=\alpha_B=\tfrac12\), \(\beta=0\), and \(\gamma=\tfrac12\). Thus $$ d_{A\cup B,C} =\tfrac12(6)+\tfrac12(10)+0(4)+\tfrac12(4) =3+5+2=10. $$ This agrees with \(\max(6,10)=10\).
Check. Both answers match the defining point-to-cluster rules. A common mistake is to use the single-linkage minus sign for complete linkage; that would incorrectly give 6 instead of 10 for the complete-linkage update.
Average Linkage and Cluster Sizes
Average linkage defines cluster distance as the mean of all point-to-point distances across the two clusters. After merging \(A\) and \(B\), the cross-cluster pairs between \(A\cup B\) and \(C\) consist of the pairs from \(A\) to \(C\) together with those from \(B\) to \(C\). Their counts are \(n_A n_C\) and \(n_B n_C\). This is why the two existing average distances must be weighted by cluster size.
For a justification, let \(S_{A,C}\) be the sum of all point-to-point distances between \(A\) and \(C\), and define \(S_{B,C}\) similarly. By the average-linkage definition, \(S_{A,C}=n_A n_C d_{A,C}\) and \(S_{B,C}=n_B n_C d_{B,C}\). There are \((n_A+n_B)n_C\) pairs between \(A\cup B\) and \(C\), so $$ d_{A\cup B,C} =\frac{S_{A,C}+S_{B,C}}{(n_A+n_B)n_C} =\frac{n_A d_{A,C}+n_B d_{B,C}}{n_A+n_B}. $$ The common factor \(n_C\) cancels. The merge distance \(d_{A,B}\) is not needed for this update.
Worked Example: A Size-Weighted Average-Linkage Update
A hypothetical risk-profile analysis merges a cluster \(A\) of 2 profiles with a cluster \(B\) of 3 profiles. Their average-linkage distances to a cluster \(C\) of 4 profiles are \(d_{A,C}=6\) and \(d_{B,C}=10\). Find the updated average-linkage distance.
The cluster sizes are \(n_A=2\) and \(n_B=3\). The average-linkage update is $$ d_{A\cup B,C} =\frac{2(6)+3(10)}{2+3} =\frac{12+30}{5} =\frac{42}{5} =8.4. $$
To check by pair counts, there are \(2(4)=8\) pairs from \(A\) to \(C\), whose total distance is \(8(6)=48\). There are \(3(4)=12\) pairs from \(B\) to \(C\), whose total distance is \(12(10)=120\). The combined mean is \((48+120)/(8+12)=168/20=8.4\).
Check. The result lies between 6 and 10, as a weighted average should. Using \((6+10)/2=8\) would incorrectly give equal weight to clusters of different sizes.
Ward Linkage: Use Squared Ward Dissimilarities
Ward linkage merges the pair of clusters that produces the smallest increase in within-cluster sum of squares. For a cluster \(A\) of \(n_A\) observations with mean vector \(\bar{x}_A\), that increase when 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. $$ This definition uses squared Euclidean geometry. A common convention stores the Ward dissimilarity \(h_{A,B}=\sqrt{2\Delta(A,B)}\); the recurrence is linear in the squares of these dissimilarities, not in \(h\) itself.
The identity behind this update can be justified from the Ward increase formula. Write \(p=n_A\), \(q=n_B\), \(r=n_C\), and let the three cluster means be \(a,b,c\). Since \(h^2=2\Delta\), expanding squared norms gives $$ \frac{(p+r)h_{A,C}^{\,2}+(q+r)h_{B,C}^{\,2}-r h_{A,B}^{\,2}}{p+q+r} = \frac{2(p+q)r}{p+q+r} \left\lVert\frac{pa+qb}{p+q}-c\right\rVert^2. $$ The right side is \(2\Delta(A\cup B,C)\), because the merged mean is \((pa+qb)/(p+q)\). The left side is the stated recurrence. This derivation depends on squared Euclidean distances and the stated Ward convention; a different software convention for reported heights may rescale the values.
Worked Example: A Ward Update from Cluster Means
Consider one-dimensional observations with \(A=\{0,2\}\), \(B=\{4\}\), and \(C=\{7\}\). Suppose \(A\) and \(B\) merge. Compute the Ward dissimilarity from \(A\cup B\) to \(C\), using \(h=\sqrt{2\Delta}\).
The sizes are \(n_A=2\), \(n_B=1\), and \(n_C=1\). The means are \(\bar{x}_A=1\), \(\bar{x}_B=4\), and \(\bar{x}_C=7\). First compute the existing Ward increases: $$ \Delta(A,C)=\frac{2(1)}{2+1}(1-7)^2 =\frac{2}{3}(36)=24, \qquad h_{A,C}^{\,2}=2(24)=48. $$ $$ \Delta(B,C)=\frac{1(1)}{1+1}(4-7)^2 =\frac12(9)=4.5, \qquad h_{B,C}^{\,2}=2(4.5)=9. $$ $$ \Delta(A,B)=\frac{2(1)}{2+1}(1-4)^2 =\frac{2}{3}(9)=6, \qquad h_{A,B}^{\,2}=2(6)=12. $$
The denominator in the recurrence is \(T=2+1+1=4\). The coefficients are \(\alpha_A=(2+1)/4=3/4\), \(\alpha_B=(1+1)/4=1/2\), and \(\beta=-1/4\). Therefore, $$ h_{A\cup B,C}^{\,2} =\frac34(48)+\frac12(9)-\frac14(12) =36+4.5-3 =37.5. $$ Taking the square root gives \(h_{A\cup B,C}=\sqrt{37.5}\approx 6.1237\), rounded to four decimal places.
Check. The merged cluster has size 3 and mean \((0+2+4)/3=2\). Directly, \(\Delta(A\cup B,C)=\frac{3(1)}{4}(2-7)^2=\frac34(25)=18.75\), so \(2\Delta=37.5\), matching the recurrence.
Coefficient Summary and Exam Trap
| Linkage | \(\alpha_A\) | \(\alpha_B\) | \(\beta\) | \(\gamma\) | Distance convention |
|---|---|---|---|---|---|
| Single | \(\tfrac12\) | \(\tfrac12\) | 0 | \(-\tfrac12\) | Ordinary cluster distances |
| Complete | \(\tfrac12\) | \(\tfrac12\) | 0 | \(\tfrac12\) | Ordinary cluster distances |
| Average | \(\dfrac{n_A}{n_A+n_B}\) | \(\dfrac{n_B}{n_A+n_B}\) | 0 | 0 | Mean cross-cluster distances |
| Ward | \(\dfrac{n_A+n_C}{T}\) | \(\dfrac{n_B+n_C}{T}\) | \(-\dfrac{n_C}{T}\) | 0 | Squared Ward dissimilarities \(h^2=2\Delta\) |
A frequent exam trap is to use the Ward coefficients on unsquared distances. For the preceding example, that incorrect calculation would be $$ \tfrac34\sqrt{48}+\tfrac12\sqrt{9}-\tfrac14\sqrt{12} \approx 5.1962+1.5000-0.8660=5.8302. $$ It does not equal the correct \(h_{A\cup B,C}\approx6.1237\). The recurrence first produces \(h^2=37.5\); only then is the square root taken. Another trap is to use average linkage’s size weights for single or complete linkage: those rules update by a minimum or maximum, regardless of cluster sizes.
The Lance–Williams framework is useful because it makes the update rule explicit and exposes which information matters. Single and complete linkage depend on the smaller or larger of two distances; average linkage depends on the sizes of the two merged clusters; Ward linkage also uses the size of the third cluster and a negative term involving the squared merge dissimilarity. Always identify the linkage definition and stored distance convention before substituting coefficients.
Check Your Understanding
For each problem, identify the linkage rule and apply its appropriate update.
- Clusters \(A\) and \(B\) merge, and their distances to \(C\) are 5 and 12. What is the updated distance to \(C\) under single linkage? (Answer: 5)
- For the same distances, what is the updated distance under complete linkage? (Answer: 12)
- Under average linkage, \(n_A=4\), \(n_B=1\), \(d_{A,C}=3\), and \(d_{B,C}=8\). Find \(d_{A\cup B,C}\). (Answer: 4)
- Under average linkage, \(n_A=2\), \(n_B=5\), \(d_{A,C}=6\), and \(d_{B,C}=2\). Find the updated distance, giving the exact value. (Answer: \(22/7\))
- Under Ward linkage, \(n_A=1\), \(n_B=2\), \(n_C=3\), \(h_{A,C}^2=16\), \(h_{B,C}^2=25\), and \(h_{A,B}^2=9\). Using \(h^2=2\Delta\), find \(h_{A\cup B,C}^2\) and \(h_{A\cup B,C}\) to four decimal places. (Answer: \(27\) and \(5.1962\))