Why Average Linkage Is a Cluster Distance
In agglomerative hierarchical clustering, each step joins two of the current clusters. The decision rule needs a distance between clusters, even though the original dissimilarity matrix records distances between individual observations. Average linkage supplies that rule by averaging every dissimilarity that crosses from one cluster to the other. Unlike single linkage, it does not use only the nearest cross-cluster pair; unlike complete linkage, it does not use only the farthest.
The calculation is straightforward once the pairs are counted. The main exam risk is not the arithmetic: it is averaging the wrong set of distances, or treating a large cluster as if it contributed the same number of pairs as a small one. Average linkage is determined by the original pairwise dissimilarities across the two clusters being compared.
This definition applies directly to a symmetric pairwise dissimilarity matrix, such as one computed using Euclidean or Manhattan distance. The distances must be on a common, meaningful scale for their arithmetic mean to be interpretable. Average linkage does not require the dissimilarities to be Euclidean distances, but it does use the supplied values as they are; it does not rescale features or correct a poorly chosen dissimilarity measure.
How the Agglomerative Merge Is Chosen
At the start of agglomerative clustering, every observation is its own cluster. At each step, calculate or identify the average-linkage distance for every pair of current clusters, and merge the pair with the smallest value. After a merge, the resulting cluster replaces its two component clusters. Distances to other clusters must then reflect all cross-cluster observation pairs under the definition.
At the first step they are single observations. At later steps, some clusters contain multiple observations.
For each pair of clusters, count the cross-cluster pairs, add their dissimilarities, and divide by the number of pairs.
Choose the two current clusters with the smallest average-linkage distance. If several pairs tie, more than one next merge is possible.
Use all original dissimilarities between its members and the members of the other cluster. Repeat until the desired number of clusters remains.
A useful justification for the denominator is a simple count: a cluster with \(n_C\) members forms one pair with each of the \(n_D\) members of \(D\), so there are \(n_Cn_D\) cross-cluster pairs. The definition is therefore the ordinary arithmetic mean over exactly that many values. If a cluster formed by joining \(C\) and \(D\) is compared with another cluster \(E\), the pairs between the new cluster and \(E\) split into the pairs from \(C\) to \(E\) and the pairs from \(D\) to \(E\). The pooled mean must consequently weight those two means by their numbers of pairs:
The numerator adds the sums of the two disjoint sets of cross-cluster dissimilarities; the denominator counts all \((n_C+n_D)n_E\) pairs. This is a consequence of the definition, not a reason to average the two existing cluster distances equally. If the cluster sizes differ, their numbers of pairs usually differ too.
Worked Merge Sequences
Worked Example: Updating Distances After the First Merge
A hypothetical insurer groups four policy portfolios, labelled \(A,B,C,D\), using a supplied symmetric dissimilarity matrix. The off-diagonal entries are \(d(A,B)=2\), \(d(A,C)=6\), \(d(A,D)=10\), \(d(B,C)=4\), \(d(B,D)=8\), and \(d(C,D)=7\). Use average linkage to find the first two merges and the distance between the final two clusters.
Method. Begin with four singleton clusters. At this stage, each cluster-to-cluster distance is just the corresponding individual dissimilarity. The smallest value is \(d(A,B)=2\), so the first merge is \(\{A,B\}\).
The current clusters are now \(\{A,B\}\), \(\{C\}\), and \(\{D\}\). The distance from \(\{A,B\}\) to \(\{C\}\) has two cross-cluster pairs:
The distance from \(\{A,B\}\) to \(\{D\}\) is:
The remaining distance is \(d(\{C\},\{D\})=7\). Comparing \(5,9,\) and \(7\), the second merge is \(\{A,B\}\) with \(\{C\}\), at distance \(5\). The clusters are then \(\{A,B,C\}\) and \(\{D\}\). Their distance averages three pairs:
Check. The final denominator is \(3\times1=3\), because there are three members in \(\{A,B,C\}\) and one in \(\{D\}\). The computed distance is between the remaining two clusters, not an average of their earlier merge heights. This avoids the common mistake of carrying forward the previous value \(9\) for \(\{A,B\}\) versus \(D\) after \(C\) has joined the cluster.
Worked Example: Comparing All Current Cluster Pairs
A hypothetical risk team has five risk profiles, \(A,B,C,D,E\), with these pairwise dissimilarities: \(d(A,B)=3\), \(d(A,C)=8\), \(d(A,D)=9\), \(d(A,E)=12\), \(d(B,C)=7\), \(d(B,D)=10\), \(d(B,E)=11\), \(d(C,D)=4\), \(d(C,E)=6\), and \(d(D,E)=5\). Find the agglomerative merge sequence until two clusters remain.
First merge. The smallest individual dissimilarity is \(d(A,B)=3\). Merge \(\{A\}\) and \(\{B\}\) to form \(\{A,B\}\).
The clusters are now \(\{A,B\},\{C\},\{D\},\{E\}\). The distances involving \(\{A,B\}\) are:
Among the remaining singleton pairs, \(d(C,D)=4\), \(d(C,E)=6\), and \(d(D,E)=5\). The smallest current distance is \(4\), so the second merge is \(\{C,D\}\).
The current clusters are \(\{A,B\},\{C,D\},\{E\}\). Calculate each of the three candidate distances. First, between the two size-two clusters, there are four pairs:
The other two distances are:
Thus the third merge is \(\{C,D\}\) with \(\{E\}\), at distance \(5.5\), forming \(\{C,D,E\}\). The two clusters left are \(\{A,B\}\) and \(\{C,D,E\}\). Their six cross-cluster dissimilarities sum to \(8+9+12+7+10+11=57\), so:
Check. The merge sequence is \(\{A,B\}\) at \(3\), \(\{C,D\}\) at \(4\), then \(\{C,D\}\) joins \(\{E\}\) at \(5.5\); the final two-cluster distance is \(9.5\). Each selection was made by comparing distances between clusters that existed at that step, rather than by sorting the original ten entries alone.
Worked Example: Unequal Cluster Sizes and a Weighted Mean
A hypothetical portfolio segmentation currently has clusters \(\{A,B\}\), \(\{C\}\), \(\{D,E\}\), with dissimilarities \(d(A,B)=1\), \(d(D,E)=2\), \(d(A,C)=4\), \(d(B,C)=6\), \(d(A,D)=8\), \(d(A,E)=10\), \(d(B,D)=10\), \(d(B,E)=12\), \(d(C,D)=6\), and \(d(C,E)=8\). Confirm which clusters merge next, then find the distance from the resulting cluster to the other remaining cluster.
The current cluster-pair distances are calculated as follows:
The smallest value is \(5\), so \(\{A,B\}\) merges with \(\{C\}\), forming \(\{A,B,C\}\). The remaining clusters are \(\{A,B,C\}\) and \(\{D,E\}\). There are \(3\times2=6\) cross-cluster pairs, with total dissimilarity \(8+10+10+12+6+8=54\). Therefore:
Why an unweighted average fails. The earlier distance from \(\{A,B\}\) to \(\{D,E\}\) was \(10\), and the distance from \(\{C\}\) to \(\{D,E\}\) was \(7\). Simply averaging these values gives \((10+7)/2=8.5\), which is incorrect: the first value represents four pairs, while the second represents only two. The correct pooled mean is \((4(10)+2(7))/(4+2)=54/6=9\). The result agrees with the direct calculation over all six pairs.
Common Traps and Interpretation
Average linkage is a rule for defining distances between clusters; it is not a claim that the members of a cluster are all close to one another, nor does it summarize the clusters by their centers. When checking a calculation, make the membership of both clusters explicit and list the cross-pairs before adding values. The pair count provides a quick denominator check.
| Candidate clusters | Cross-pair count | What to average |
|---|---|---|
| \(\{A,B\}\) and \(\{C\}\) | 2 | \(d(A,C)\) and \(d(B,C)\) |
| \(\{A,B\}\) and \(\{C,D\}\) | 4 | All four distances from a member of the first cluster to a member of the second |
| \(\{A,B,C\}\) and \(\{D,E\}\) | 6 | All six distances from \(\{A,B,C\}\) to \(\{D,E\}\) |
The procedure is greedy: at each stage it joins the pair with the smallest current average-linkage distance. It does not reconsider an earlier merge when a later cluster forms. Consequently, a mistake in an early pair selection changes the clusters and all subsequent candidates. Ties in the smallest value allow multiple valid next merges; if a problem specifies a tie-breaking convention, use it, and otherwise report the tied alternatives.
- Wrong pair set: averaging within-cluster distances or including a previously merged pair gives a different quantity. Include only pairs with one observation in each candidate cluster.
- Wrong denominator: the denominator is \(n_Cn_D\), not \(n_C+n_D\). Count the cross-pairs directly if uncertain.
- Unweighted pooling: when a cluster has grown, do not give its previous distance and a smaller cluster's distance equal weight unless they represent equal numbers of cross-pairs.
- Wrong merge decision: compare all distances between the current clusters. The smallest original entry is not necessarily the smallest current cluster distance after the first merge.
Check Your Understanding
For each problem, compute the stated average-linkage distance or next merge using only the listed cross-cluster dissimilarities.
- Clusters \(\{P,Q\}\) and \(\{R\}\) have \(d(P,R)=3\) and \(d(Q,R)=9\). Find their average-linkage distance. (Answer: 6)
- Clusters \(\{A,B\}\) and \(\{C,D\}\) have cross-distances \(d(A,C)=2\), \(d(A,D)=6\), \(d(B,C)=4\), and \(d(B,D)=8\). Find the average-linkage distance. (Answer: 5)
- Four singleton clusters have distances \(d(A,B)=2\), \(d(A,C)=7\), \(d(A,D)=9\), \(d(B,C)=5\), \(d(B,D)=11\), and \(d(C,D)=8\). Find the first merge, the second merge, and the distance between the two clusters remaining after the second merge. (Answer: Merge \(\{A,B\}\) at 2, then merge \(\{A,B\}\) with \(\{C\}\) at 6; the remaining distance to \(\{D\}\) is \(28/3\), or about 9.333.)
- Clusters of sizes three and two have six cross-cluster dissimilarities \(2,4,6,8,10,12\). Find the average-linkage distance. (Answer: \(42/6=7\))
- The current clusters are \(\{A,B\},\{C\},\{D,E\}\). Their relevant individual distances are \(d(A,C)=4\), \(d(B,C)=10\), \(d(A,D)=3\), \(d(A,E)=5\), \(d(B,D)=7\), \(d(B,E)=9\), \(d(C,D)=8\), and \(d(C,E)=10\). Identify the next merge and the distance from the resulting cluster to the remaining cluster. (Answer: Merge \(\{A,B\}\) with \(\{D,E\}\) at 6; its distance to \(\{C\}\) is \((4+10+8+10)/4=8.)