Why the Nearest Pair Matters
In hierarchical clustering, a cluster can contain several observations, so a distance between two clusters cannot be read directly from the distance between two individual observations. A linkage rule specifies how to turn the collection of pairwise dissimilarities into one cluster-to-cluster dissimilarity. Single linkage uses the closest pair: it asks how near the most similar member of one cluster is to any member of the other cluster.
This rule can make a cluster grow by joining observations or groups that are connected through short pairwise distances, even when other members of the resulting cluster are much farther apart. The key calculation is not an average and does not compare cluster centers. At every step, identify all relevant cross-cluster pairs, take their minimum dissimilarity, and then apply the agglomerative rule: merge a pair of current clusters with the smallest single-linkage distance.
The starting data may be coordinates from which distances are calculated, or a pairwise dissimilarity matrix supplied directly. For a symmetric dissimilarity matrix, the dissimilarity between a pair does not depend on the order of its observations. The values are usually nonnegative, with zero dissimilarity from an observation to itself. A dissimilarity need not satisfy the triangle inequality for the minimum rule to be defined; if the task specifies a particular metric, use that metric to obtain the observation-level values.
In agglomerative clustering, each observation starts as its own cluster. At each step, calculate single-linkage distances between the current clusters and merge a pair whose distance is smallest. After a merge, the new cluster contains all observations in both clusters. Its distance to another cluster is again found by taking the minimum over all cross-cluster observation pairs. It is not enough to retain only the pair that triggered the previous merge: a different pair of members may be the closest pair to the next cluster.
Calculating a Merge Sequence
A reliable calculation separates two tasks. First, find the distance between clusters using the minimum cross-pair dissimilarity. Second, compare those cluster distances to choose the next merge. Keeping these tasks distinct helps prevent a common error: selecting a close individual pair correctly, but then using an unrelated rule when calculating the distance between the enlarged cluster and another cluster.
Each observation is initially in its own cluster, so the initial cluster distances are the supplied pairwise dissimilarities.
Merge the two clusters whose single-linkage distance is smallest. Record the observations or clusters merged and the dissimilarity at which they merge.
For each other current cluster, examine all pairs crossing between it and the new cluster and take the minimum.
At every stage, compare only distances between the clusters that currently exist.
Worked Example: A Complete Sequence from One-Dimensional Observations
A hypothetical insurer groups five portfolios using a single numerical profile coordinate. Treat the listed coordinates as observations on one scale and use ordinary Euclidean distance, which in one dimension is the absolute difference. Find the successive single-linkage merges and their distances.
The coordinates are \(A=0\), \(B=1.2\), \(C=4\), \(D=6.5\), and \(E=11\). Initially, the clusters are \(\{A\}\), \(\{B\}\), \(\{C\}\), \(\{D\}\), and \(\{E\}\). The pairwise distances are:
First merge. The smallest listed distance is \(d(A,B)=1.2\), so merge \(\{A\}\) and \(\{B\}\) to form \(\{A,B\}\) at distance \(1.2\).
Second merge. The remaining singleton pair distances include \(d(C,D)=2.5\), \(d(B,C)=2.8\), and \(d(D,E)=4.5\); the smallest available distance is \(2.5\). Merge \(\{C\}\) and \(\{D\}\) to form \(\{C,D\}\).
Third merge. The distance between \(\{A,B\}\) and \(\{C,D\}\) is the minimum of their four cross-cluster distances:
The other current cluster distances are \(D_{\text{single}}(\{A,B\},\{E\})=\min\{11,9.8\}=9.8\) and \(D_{\text{single}}(\{C,D\},\{E\})=\min\{7,4.5\}=4.5\). Therefore, merge \(\{A,B\}\) with \(\{C,D\}\) at \(2.8\).
Final merge. The distance from \(\{A,B,C,D\}\) to \(\{E\}\) is the minimum of \(11,9.8,7,\) and \(4.5\), which is \(4.5\). Thus, \(E\) joins the other four observations at \(4.5\).
The sequence is \(\{A\}\) with \(\{B\}\) at \(1.2\), \(\{C\}\) with \(\{D\}\) at \(2.5\), \(\{A,B\}\) with \(\{C,D\}\) at \(2.8\), and \(\{A,B,C,D\}\) with \(\{E\}\) at \(4.5\). A check of the final steps confirms that the reported distances are the smallest cross-pair values for the clusters being merged.
Why the Minimum Formula Holds
The definition follows directly from what “nearest pair” means. The cross-cluster pairs are all possible pairs \((i,j)\) for which \(i\) belongs to \(A\) and \(j\) belongs to \(B\). Each such pair has a dissimilarity \(d(i,j)\). The nearest cross-cluster pair is the pair with the smallest value in this finite collection. The minimum of that collection is therefore exactly the single-linkage distance.
For example, if \(A\) has two observations and \(B\) has three, there are \(2\times3=6\) cross-cluster pairs. The rule requires checking those six dissimilarities and selecting the smallest; within-cluster pairs such as two observations both in \(A\) are irrelevant to \(D_{\text{single}}(A,B)\). This also explains why the distance after a merge must be based on the membership of the whole new cluster, rather than only on the particular observations that were joined most recently.
Worked Example: Updating Distances from a Dissimilarity Matrix
A hypothetical study has five risk profiles, \(P,Q,R,S,T\). Their symmetric pairwise dissimilarities are given below. Use single linkage to determine the complete merge sequence.
| Pair | Dissimilarity | Pair | Dissimilarity |
|---|---|---|---|
| \(P,Q\) | 3 | \(P,R\) | 8 |
| \(P,S\) | 10 | \(P,T\) | 11 |
| \(Q,R\) | 6 | \(Q,S\) | 9 |
| \(Q,T\) | 12 | \(R,S\) | 2 |
| \(R,T\) | 7 | \(S,T\) | 5 |
First merge. The smallest initial dissimilarity is \(d(R,S)=2\), so the first merge is \(\{R\}\) with \(\{S\}\) at \(2\).
Update distances from \(\{R,S\}\). To \(P\), the cross-pair values are \(d(R,P)=8\) and \(d(S,P)=10\), so the cluster distance is \(\min\{8,10\}=8\). To \(Q\), it is \(\min\{6,9\}=6\). To \(T\), it is \(\min\{7,5\}=5\). The other current singleton distances include \(d(P,Q)=3\), \(d(P,T)=11\), and \(d(Q,T)=12\).
Second merge. The smallest current distance is \(d(P,Q)=3\), so merge \(\{P\}\) and \(\{Q\}\) at \(3\).
Third merge. The candidate distances are \(D_{\text{single}}(\{R,S\},\{T\})=5\), \(D_{\text{single}}(\{R,S\},\{P,Q\})=\min\{8,10,6,9\}=6\), and \(D_{\text{single}}(\{P,Q\},\{T\})=\min\{11,12\}=11\). The smallest is \(5\), so merge \(\{R,S\}\) with \(\{T\}\).
Final merge. The distance between \(\{R,S,T\}\) and \(\{P,Q\}\) is the minimum of the six cross-cluster values \(8,10,11,6,9,12\). That minimum is \(6\), so the two clusters merge at \(6\).
The checked merge sequence is \(R,S\) at \(2\); \(P,Q\) at \(3\); \(\{R,S\},T\) at \(5\); and \(\{R,S,T\},\{P,Q\}\) at \(6\). The calculation uses only the supplied dissimilarities and the minimum rule; no coordinates or probability distribution are required.
Applying the Rule to Coordinates
When observations are described by several numerical features, first compute observation-level dissimilarities using the specified metric. If Euclidean distance is specified for two-dimensional coordinates \((x_i,y_i)\) and \((x_j,y_j)\), then \(d(i,j)=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\). The single-linkage step occurs after those pairwise distances have been obtained. If the coordinates are on different scales, the metric and any scaling must be settled before clustering; the minimum rule does not itself correct for scale differences.
Worked Example: Successive Merges from Two-Dimensional Profiles
For a hypothetical set of normalized risk profiles, suppose the coordinates are \(A=(0,0)\), \(B=(2,0)\), \(C=(6,0)\), \(D=(6,3)\), \(E=(11,3)\), and \(F=(11,9)\). Use Euclidean distance and single linkage. The coordinates are already supplied on the intended common scale; no additional transformation is requested.
The shortest relevant initial distances are \(d(A,B)=2\), \(d(C,D)=3\), \(d(B,C)=4\), \(d(D,E)=5\), and \(d(E,F)=6\). Other pairs do not have a smaller distance: for instance, \(d(B,D)=\sqrt{(6-2)^2+(3-0)^2}=5\), and \(d(C,E)=\sqrt{(11-6)^2+(3-0)^2}=\sqrt{34}>5\). Thus, the smallest pair is \(A,B\), and they merge at \(2\).
Second merge. Among the remaining singleton pairs, \(d(C,D)=3\) is smaller than \(d(B,C)=4\), \(d(D,E)=5\), and \(d(E,F)=6\). Merge \(C,D\) at \(3\).
Third merge. The distance from \(\{A,B\}\) to \(\{C,D\}\) is the minimum of four distances. They are \(d(A,C)=6\), \(d(A,D)=\sqrt{45}\), \(d(B,C)=4\), and \(d(B,D)=5\). Their minimum is \(4\), so merge \(\{A,B\}\) and \(\{C,D\}\) at \(4\).
Fourth merge. The distance from \(\{A,B,C,D\}\) to \(E\) is the minimum of the distances from \(E\) to \(A,B,C,D\). The smallest is \(d(D,E)=5\); hence \(E\) joins at \(5\). The distance from the enlarged cluster to \(F\) is the minimum of its distances to \(F\), which is \(d(E,F)=6\). Therefore, the final merge adds \(F\) at \(6\).
The completed schedule is \(A,B\) at \(2\); \(C,D\) at \(3\); the two pairs at \(4\); \(E\) at \(5\); and \(F\) at \(6\). Checking each reported height against its nearest cross-cluster pair confirms the sequence.
Common Mistake: Averaging Instead of Minimizing
A frequent error is to calculate the average of all cross-cluster distances after a merge. That produces a different cluster distance and is not single linkage. For the clusters \(\{A,B\}\) and \(\{C,D\}\) in the first worked example, the four cross distances are \(4, 6.5, 2.8,\) and \(5.3\). Their average is:
Wrong calculation: reporting \(4.65\) as the distance between \(\{A,B\}\) and \(\{C,D\}\). This is an average of cross-pair dissimilarities, not their minimum.
Correction: apply the definition and select the smallest of the four values: \(\min\{4,6.5,2.8,5.3\}=2.8\). Thus, the single-linkage distance is \(2.8\), and the pair \(B,C\) is the nearest cross-cluster pair. The average calculation may look reasonable as a summary, but it answers a different question.
A second practical check is to ensure that every pair considered crosses between the two clusters. Including distances between two members of the same cluster can change the minimum incorrectly. Also, the minimum must be found again for each new cluster pairing; the closest pair in one merge does not automatically determine every later distance.
Check Your Understanding
For each problem, use the single-linkage rule and show the cross-cluster comparisons needed to support your answer.
- Three observations have pairwise dissimilarities \(d(U,V)=2\), \(d(U,W)=7\), and \(d(V,W)=4\). State the first merge and the distance from the resulting cluster to the remaining observation. (Answer: Merge \(U,V\) at \(2\); the distance from \(\{U,V\}\) to \(W\) is \(4\).)
- Four observations have one-dimensional coordinates \(A=0\), \(B=1\), \(C=4\), and \(D=9\), with ordinary Euclidean distance. Give the full sequence of merges and distances. (Answer: Merge \(A,B\) at \(1\); merge \(\{A,B\}\) with \(C\) at \(3\); merge \(\{A,B,C\}\) with \(D\) at \(5\).)
- A dissimilarity matrix gives \(d(A,B)=4\), \(d(A,C)=9\), \(d(A,D)=8\), \(d(B,C)=3\), \(d(B,D)=7\), and \(d(C,D)=6\). Give the full single-linkage merge sequence. (Answer: Merge \(B,C\) at \(3\); merge \(\{B,C\}\) with \(A\) at \(4\); merge \(\{A,B,C\}\) with \(D\) at \(6\).)
- Clusters \(G=\{g_1,g_2\}\) and \(H=\{h_1,h_2,h_3\}\) have cross-cluster dissimilarities \(d(g_1,h_1)=5\), \(d(g_1,h_2)=8\), \(d(g_1,h_3)=4\), \(d(g_2,h_1)=7\), \(d(g_2,h_2)=2\), and \(d(g_2,h_3)=6\). What is their single-linkage distance, and which pair realizes it? (Answer: The distance is \(2\), realized by \(g_2,h_2\).)
- Four singleton clusters \(J,K,L,M\) have dissimilarities \(d(J,K)=6\), \(d(J,L)=10\), \(d(J,M)=9\), \(d(K,L)=3\), \(d(K,M)=8\), and \(d(L,M)=4\). Determine the first two merges and then the single-linkage distance between the two resulting clusters. (Answer: First merge \(K,L\) at \(3\); second merge \(\{K,L\}\) with \(M\) at \(4\); the distance from \(\{K,L,M\}\) to \(J\) is \(\min\{6,10,9\}=6\).)