Complete Linkage: Farthest-Pair Cluster Distance

Why Complete Linkage Uses the Farthest Pair

In agglomerative hierarchical clustering, objects begin as individual clusters. At each step, the algorithm merges the two current clusters judged closest under a specified rule. Complete linkage defines that closeness using the most dissimilar pair across the two clusters. A merge is therefore judged by its farthest cross-cluster pair, not by a representative point or by the nearest pair.

This rule puts a limit on how far apart the objects in a proposed merged cluster can be. It tends to favor compact groups: a cluster cannot be joined to another just because one pair of their members is close if some other cross-cluster pair is much farther apart. The rule is especially important when several objects have already been grouped, because every cross-cluster pair then matters.

Definition: Let $d(i,j)$ be the dissimilarity between objects $i$ and $j$. For two nonempty, disjoint clusters $G$ and $H$, their complete-linkage distance is $$ D_{\mathrm{complete}}(G,H)=\max_{i\in G,\;j\in H} d(i,j). $$ In agglomerative complete-linkage clustering, calculate this distance for every pair of current clusters and merge a pair with the smallest value.

The starting dissimilarities are usually supplied in a symmetric matrix with zero diagonal. The method can be applied to nonnegative dissimilarities; they need not come from Euclidean coordinates. The dissimilarities must, however, be on a scale that makes comparisons meaningful. If features have very different scales, their measurement units can dominate the dissimilarities, so suitable scaling must be considered before clustering.

For two singleton clusters, complete-linkage distance is simply their original dissimilarity. Once a cluster contains multiple objects, its distance to another cluster is the largest value among all cross-cluster dissimilarities. If two candidate cluster pairs have the same smallest distance, either is a valid next merge under the rule; the resulting sequence can depend on how such a tie is resolved.

Updating a Distance After a Merge

Suppose the current clusters $G$ and $H$ are merged, and $C$ is another current cluster. The distance from the new cluster $G\cup H$ to $C$ is the larger of the two previous complete-linkage distances to $C$:

D_{\mathrm{complete}}(G\cup H,C) =\max\left\{D_{\mathrm{complete}}(G,C),D_{\mathrm{complete}}(H,C)\right\}.

This update is useful because it avoids listing all the object pairs again, provided the two distances on the right have already been calculated correctly.

Why the Maximum Update Formula Holds

The definition itself gives a short justification. The pairs crossing from $G\cup H$ to $C$ are exactly the pairs crossing from $G$ to $C$, together with the pairs crossing from $H$ to $C$. The largest dissimilarity in that combined set must be the larger of the two separate largest dissimilarities.

\begin{aligned} D_{\mathrm{complete}}(G\cup H,C) &=\max_{\substack{i\in G\cup H\\j\in C}} d(i,j)\\ &=\max\left\{ \max_{\substack{i\in G\\j\in C}}d(i,j), \max_{\substack{i\in H\\j\in C}}d(i,j) \right\}\\ &=\max\left\{D_{\mathrm{complete}}(G,C),D_{\mathrm{complete}}(H,C)\right\}. \end{aligned}

This argument depends on the definition of complete linkage as a maximum over every cross-cluster pair. Replacing the maximum with a minimum would describe a different rule and would not calculate complete-linkage distance.

Worked Example: Completing a Merge Schedule from a Dissimilarity Matrix

A hypothetical insurer summarizes four portfolios, $A,B,C,D$, using a supplied pairwise dissimilarity matrix. Find the complete-linkage merge sequence and its merge distances. Assume the entries are comparable dissimilarities; no interest rate, mortality assumption, or probability distribution is involved.

Pair	Dissimilarity
A, B	2
A, C	7
A, D	9
B, C	5
B, D	8
C, D	4

Step 1: Find the first merge. Initially all clusters are singletons, so their complete-linkage distances equal the listed dissimilarities. The smallest is $d(A,B)=2$. Merge $\{A\}$ and $\{B\}$, forming $\{A,B\}$ at distance 2.

Step 2: Calculate distances from the new cluster. For $C$, the cross-cluster values are $d(A,C)=7$ and $d(B,C)=5$. Thus $D_{\mathrm{complete}}(\{A,B\},\{C\})=\max(7,5)=7$. For $D$, the values are 9 and 8, so $D_{\mathrm{complete}}(\{A,B\},\{D\})=\max(9,8)=9$. The remaining distance $D_{\mathrm{complete}}(\{C\},\{D\})$ is 4.

Step 3: Find the next merge. The current distances are 7, 9, and 4. The smallest is 4, so merge $\{C\}$ and $\{D\}$ at distance 4.

Step 4: Calculate the final distance. Between $\{A,B\}$ and $\{C,D\}$, the four cross-cluster values are 7, 9, 5, and 8. Their maximum is 9, so the final merge is at distance 9.

Check. The sequence is $A$ with $B$ at 2, $C$ with $D$ at 4, and $\{A,B\}$ with $\{C,D\}$ at 9. The final distance is the largest of all six original pairwise dissimilarities, which is 9. The method avoids the mistake of treating the cluster distance as the smallest cross-cluster value.

Complete Linkage with Ordered Profile Scores

When objects have one quantitative feature, a common dissimilarity is absolute difference. The following hypothetical example uses a scaled profile score. The score units are treated as comparable, and $d(i,j)$ is the absolute difference between scores. This is a dissimilarity calculation, not a claim that the scores represent actual insurance-company data.

Worked Example: Merging Five Hypothetical Risk Profiles

Five hypothetical risk profiles $A,B,C,D,E$ have scores 0, 1, 3, 8, and 10, respectively. Use absolute difference and complete linkage to find every merge. State each intermediate cluster distance.

Step 1: List the initial pairwise dissimilarities. The values are $d(A,B)=1$, $d(A,C)=3$, $d(A,D)=8$, $d(A,E)=10$, $d(B,C)=2$, $d(B,D)=7$, $d(B,E)=9$, $d(C,D)=5$, $d(C,E)=7$, and $d(D,E)=2$. The smallest value is 1, so merge $A$ and $B$.

Step 2: Update distances after merging $A$ and $B$. The distance from $\{A,B\}$ to $C$ is $\max(3,2)=3$. Its distance to $D$ is $\max(8,7)=8$, and its distance to $E$ is $\max(10,9)=10$. The distances among the remaining singleton clusters are $d(C,D)=5$, $d(C,E)=7$, and $d(D,E)=2$.

Step 3: Make the next merge. The smallest current distance is 2, between $D$ and $E$. Merge them to form $\{D,E\}$ at distance 2.

Step 4: Compare the remaining cluster distances. The distance from $\{A,B\}$ to $C$ is 3. The distance from $C$ to $\{D,E\}$ is $\max(d(C,D),d(C,E))=\max(5,7)=7$. The distance from $\{A,B\}$ to $\{D,E\}$ is $\max(8,10,7,9)=10$. Therefore, merge $\{A,B\}$ with $C$ at distance 3.

Step 5: Find the final merge distance. The distance from $\{A,B,C\}$ to $\{D,E\}$ is the maximum of the six cross-cluster values $8,10,7,9,5,7$. Their maximum is 10. The final merge is at distance 10.

Check. The merge distances are 1, 2, 3, and 10, in that order. The final distance of 10 agrees with the largest original pairwise difference, $d(A,E)=|0-10|=10$. This verifies both the update calculations and the final cross-cluster maximum.

Reading a Merge from Already-Formed Clusters

At an intermediate stage, each cluster can contain several objects. It is not enough to inspect a single convenient pair: the complete-linkage distance is the maximum over all pairs crossing between the two clusters. The maximum-update formula can then simplify the calculations.

Worked Example: Choosing Between Three Existing Clusters

At an intermediate stage of a hypothetical clustering analysis, the current clusters are $G=\{A,B\}$, $H=\{C\}$, and $J=\{D,E\}$. Their relevant cross-cluster dissimilarities are listed below. Decide which pair merges next and calculate the distance from the resulting cluster to the remaining cluster. No additional distributional assumption is used: the table supplies the dissimilarities.

Cross-cluster pair	Dissimilarity
A, C	4
B, C	7
A, D	2
A, E	9
B, D	5
B, E	6
C, D	3
C, E	8

Step 1: Calculate each current cluster distance. For $G$ and $H$, the cross-cluster values are 4 and 7, so $D_{\mathrm{complete}}(G,H)=\max(4,7)=7$. For $G$ and $J$, the values are 2, 9, 5, and 6, so $D_{\mathrm{complete}}(G,J)=9$. For $H$ and $J$, the values are 3 and 8, so $D_{\mathrm{complete}}(H,J)=8$.

Step 2: Choose the merge. The three current distances are 7, 9, and 8. The smallest is 7, so merge $G$ and $H$.

Step 3: Update the distance to $J$. By the maximum-update formula, $D_{\mathrm{complete}}(G\cup H,J)=\max(D_{\mathrm{complete}}(G,J),D_{\mathrm{complete}}(H,J))=\max(9,8)=9$. Directly, the cross-cluster values from $\{A,B,C\}$ to $\{D,E\}$ are 2, 9, 5, 6, 3, and 8; their maximum is also 9.

Check. The selected merge has distance 7, less than the other current distances, 8 and 9. The updated distance is 9 because the pair $(A,E)$ has dissimilarity 9. Using the nearest cross-cluster value instead would fail to account for that farthest pair.

What Complete Linkage Favors—and a Common Trap

For any cluster formed by merging two clusters at complete-linkage distance $h$, every cross-cluster dissimilarity is at most $h$, and at least one equals $h$. Thus, at that merge, $h$ is the largest dissimilarity introduced between the two sides of the merge. This explains why complete linkage tends to avoid joining groups when even one pair across them is very far apart. It can consequently favor compact groups rather than long, loosely connected groups.

This is a tendency, not a guarantee that the final clusters will have equal sizes or any particular shape. The result also depends on the input dissimilarities and any feature scaling used to construct them. A single unusually large cross-cluster dissimilarity can control the merge decision, because the maximum—not a typical value—is being used.

Common exam trap: using the minimum cross-cluster value. Suppose the cross-cluster dissimilarities from $G=\{A,B\}$ to $H=\{C,D\}$ are 2, 9, 5, and 6. The incorrect calculation is $\min(2,9,5,6)=2$, which uses the nearest pair. The complete-linkage calculation is $\max(2,9,5,6)=9$. The correction is to list or otherwise account for every cross-cluster pair and take the largest value before comparing cluster pairs for the next merge.

Key takeaway: Complete linkage has two distinct operations: calculate each cluster-pair distance as a maximum over cross-cluster dissimilarities, then choose the cluster pair with the smallest of those maximum distances. Confusing these two operations reverses the rule.

Check Your Understanding

For each problem, apply the complete-linkage definition before selecting a merge.

Clusters $R=\{r_1,r_2\}$ and $T=\{t\}$ have cross-dissimilarities $d(r_1,t)=4$ and $d(r_2,t)=6$. What is their complete-linkage distance? (Answer: 6)
Three singleton objects have dissimilarities $d(P,Q)=3$, $d(P,R)=8$, and $d(Q,R)=5$. Which pair merges first, and what is the distance from the new cluster $\{P,Q\}$ to $R$? (Answer: Merge $P,Q$ at 3; the updated distance is 8.)
Clusters $G=\{A,B\}$ and $H=\{C,D\}$ have cross-dissimilarities $d(A,C)=4$, $d(A,D)=7$, $d(B,C)=6$, and $d(B,D)=2$. Find $D_{\mathrm{complete}}(G,H)$. (Answer: 7)
Four singleton objects have $d(A,B)=1$, $d(A,C)=5$, $d(A,D)=8$, $d(B,C)=4$, $d(B,D)=7$, and $d(C,D)=3$. Find the full merge sequence and merge distances. (Answer: Merge $A,B$ at 1; merge $C,D$ at 3; merge $\{A,B\}$ and $\{C,D\}$ at 8.)
At an intermediate stage, $X=\{a,b\}$, $Y=\{c,d\}$, and $Z=\{e\}$. The cross-dissimilarities from $X$ to $Y$ are 2, 9, 4, and 5; from $X$ to $Z$ they are 6 and 7; and from $Y$ to $Z$ they are 8 and 3. Which clusters merge next, and at what distance? (Answer: $X$ and $Z$ merge at distance 7.)

What You'll Learn