From Pairwise Dissimilarities to a Sequence of Merges
Agglomerative clustering builds a hierarchy by starting with the observations separated and joining them step by step. Its defining decision is local: at each stage, it merges the pair of current clusters with the smallest dissimilarity. After the merge, the clusters and their dissimilarities must be updated before the next choice is made.
This procedure is useful when the desired number of groups is not known in advance. Rather than choosing a fixed number of clusters at the outset, it produces a sequence of nested partitions: a partition is a collection of disjoint groups whose union is the full set of observations. A practitioner can later inspect the sequence and decide where to stop. The distance measure and scaling of the input features matter because they affect the dissimilarities that drive each decision.
The distance between two individual observations is not, by itself, enough to determine how to compare two clusters once either contains multiple observations. A linkage rule specifies how the dissimilarity between clusters is obtained and how it changes after a merge. The algorithm described here applies with a selected linkage rule; the choice of rule is separate from the agglomerative procedure.
For clarity, write \(D(G,H)\) for the current dissimilarity between distinct clusters \(G\) and \(H\). At a given step, the candidate pairs are all unordered pairs of current clusters. The next merge is a pair attaining the minimum of \(D(G,H)\) across those candidates. Once \(G\) and \(H\) become \(G\cup H\), that union is one current cluster, not two. The next comparison must use the updated set of clusters and dissimilarities.
The Procedure and Its Partition Invariant
Put each of the \(n\) observations in its own cluster. There are \(n\) singleton clusters.
For every pair of distinct current clusters, obtain its dissimilarity using the chosen linkage rule. Do not restrict the search to pairs of original observations.
Select a pair with the smallest current cluster dissimilarity. If several pairs tie, the rule for resolving ties must be specified, but the minimum value is still the relevant criterion.
Replace the selected two clusters by their union. Recalculate or update the dissimilarities involving that new cluster, as required by the chosen linkage rule.
Repeat until one cluster remains, or stop when the required number of clusters has been reached.
The partition property is preserved at every merge. Initially, every observation appears in exactly one singleton cluster. If the current clusters are disjoint and cover all observations, replacing two of them, \(G\) and \(H\), with \(G\cup H\) still covers the same observations: \(G\) and \(H\) are both represented by their union, while every other cluster is unchanged. Because \(G\) and \(H\) were disjoint from each other and from the other clusters, the new collection is still disjoint. Thus every step produces another partition of the full data set.
The number of clusters also follows directly. A merge replaces two clusters with one, reducing the count by exactly one. Starting with \(n\) clusters, reaching one cluster therefore requires \(n-1\) merges. To stop with \(k\) clusters, where \(1\leq k\leq n\), perform exactly \(n-k\) merges.
Worked Merge Schedules
In the examples below, the cluster dissimilarities after a merge are supplied as outputs of the problem’s pre-specified linkage update rule. This isolates the agglomerative algorithm: the task is to compare all current pairs, choose the minimum, merge, and continue. The numerical values are hypothetical and are dissimilarities, not probabilities.
Worked Example: Four Observations and a Full Merge Schedule
A portfolio analyst has four hypothetical risk profiles, \(A,B,C,D\). The initial pairwise dissimilarities are \(D(A,B)=2\), \(D(A,C)=7\), \(D(A,D)=9\), \(D(B,C)=6\), \(D(B,D)=8\), and \(D(C,D)=3\). Under the specified linkage update rule, after the first merge the cluster dissimilarities are as stated below. Find the full agglomerative sequence.
Initial comparison. The six candidate dissimilarities are \(2,7,9,6,8,3\). The minimum is \(D(A,B)=2\), so merge \(A\) and \(B\). The partition becomes \(\{\{A,B\},\{C\},\{D\}\}\), with three clusters.
Second comparison. The update rule gives \(D(\{A,B\},C)=5\), \(D(\{A,B\},D)=8\), and \(D(C,D)=3\). The minimum is \(3\), so merge \(C\) and \(D\). The partition is now \(\{\{A,B\},\{C,D\}\}\), with two clusters.
Final comparison. The specified update rule gives \(D(\{A,B\},\{C,D\})=4\). These are the only two current clusters, so they merge. The final partition is \(\{\{A,B,C,D\}\}\).
Check. There were four observations and three merges: \(4-1=3\). The cluster count went \(4\to3\to2\to1\), decreasing by exactly one at each step. A common mistake would be to select the original pair \(C,D\) first because its distance is 3; the correct first choice is \(A,B\), whose distance is 2.
Worked Example: Stop at Three Clusters
A hypothetical claims-screening exercise begins with five observations \(P,Q,R,S,T\). The initial dissimilarities are \(D(P,Q)=1.5\), \(D(P,R)=6\), \(D(P,S)=7\), \(D(P,T)=8\), \(D(Q,R)=5\), \(D(Q,S)=6.5\), \(D(Q,T)=7.5\), \(D(R,S)=2.5\), \(D(R,T)=4\), and \(D(S,T)=3\). The update rule gives the cluster distances indicated at each later step. Find the partition after stopping at three clusters.
First merge. Of the ten initial pairs, the minimum is \(D(P,Q)=1.5\). Merge \(P\) and \(Q\). The partition is \(\{\{P,Q\},\{R\},\{S\},\{T\}\}\), with four clusters.
Update and second merge. The updated distances are \(D(\{P,Q\},R)=5.5\), \(D(\{P,Q\},S)=6.8\), \(D(\{P,Q\},T)=7.7\), \(D(R,S)=2.5\), \(D(R,T)=4\), and \(D(S,T)=3\). The minimum is \(2.5\), so merge \(R,S\). The partition is \(\{\{P,Q\},\{R,S\},\{T\}\}\), with three clusters.
Stopping decision. The requested count is three, so stop now. The answer is \(\{P,Q\}\), \(\{R,S\}\), and \(\{T\}\). No comparison for a third merge is needed. If the algorithm continued, it would make another merge, but that would not answer the stated question.
Check. The initial count was five, and the final count is three; exactly \(5-3=2\) merges were made. The common trap is to continue until one cluster remains simply because that is the full algorithm’s eventual endpoint. A requested cluster count is a valid stopping condition.
Worked Example: Recompare Every Current Pair
Four hypothetical customer profiles \(U,V,W,Z\) start with \(D(U,V)=2\), \(D(U,W)=4\), \(D(U,Z)=9\), \(D(V,W)=5\), \(D(V,Z)=8\), and \(D(W,Z)=6\). The linkage update rule gives \(D(\{U,V\},W)=3\) and \(D(\{U,V\},Z)=7\) after the first merge; after the second merge it gives \(D(\{U,V,W\},Z)=5\). Determine the sequence and explain why the original distances cannot simply be used at every step.
First step. Compare all six initial pairs. Their minimum is \(D(U,V)=2\), so merge \(U,V\). The current clusters are \(\{U,V\},W,Z\).
Second step. Compare the three current pairs, not the six original pairs: \(D(\{U,V\},W)=3\), \(D(\{U,V\},Z)=7\), and \(D(W,Z)=6\). The minimum is \(3\), so merge \(\{U,V\}\) with \(W\). The new partition is \(\{\{U,V,W\},\{Z\}\}\).
Final step. There is just one current pair, with dissimilarity \(D(\{U,V,W\},Z)=5\), so the clusters merge. The sequence is \(U,V\) first, then \(\{U,V\}\) with \(W\), then \(\{U,V,W\}\) with \(Z\).
Check. The cluster count decreases \(4\to3\to2\to1\), giving \(4-1=3\) merges. The original value \(D(U,W)=4\) does not describe the current pair \(\{U,V\}\) and \(W\); the updated value for that pair is 3. Reusing 4 would compare the wrong objects and could change the merge sequence.
Why the Procedure Is Greedy
The procedure is called greedy because it makes the best-looking choice according to the current criterion: merge the pair with the smallest dissimilarity available now. It does not enumerate every possible sequence of merges and prove that the chosen sequence optimizes some overall score across all possible clusterings. The selected merge changes the candidate clusters and hence the choices available later.
This distinction matters when interpreting results. The first merge is optimal among the pairs currently eligible under the chosen dissimilarity rule, but that statement is local. It does not establish that every later partition is globally best under a separate objective. Nor does a small current dissimilarity alone establish that the resulting grouping is substantively useful. The linkage rule, feature scaling, and the purpose of the analysis remain important.
Common Errors to Avoid
- Choosing a pair that is not the current minimum. List or scan all current candidate pairs before merging. The minimum is determined at the present stage, not by an earlier stage.
- Ignoring cluster updates. Once a cluster contains multiple observations, its dissimilarity to another cluster must follow the chosen linkage rule. An original distance between two individual observations may no longer be the relevant quantity.
- Failing to update the partition. A merge removes two separate clusters and inserts their union. It does not leave the original clusters in the partition alongside the union.
- Making too many merges. To stop at \(k\) clusters from \(n\) singleton clusters, make \(n-k\) merges, not \(n-1\).
- Calling a local choice a global optimum. “Closest pair now” describes the algorithm’s step. It is not a proof that the resulting full clustering is best under every possible criterion.
For exam-style problems, a compact agglomeration schedule is often the safest working method. At each row, record the current clusters, the smallest eligible dissimilarity, the pair merged, and the new partition. This makes the order of operations explicit and helps reveal an omitted update or an incorrect cluster count.
Check Your Understanding
For each problem, apply the stated current dissimilarities and update information. In each case, the values are hypothetical and the update rule is assumed to be specified by the problem.
- Four observations \(A,B,C,D\) have initial dissimilarities \(D(A,B)=4\), \(D(A,C)=2\), \(D(A,D)=7\), \(D(B,C)=5\), \(D(B,D)=6\), and \(D(C,D)=3\). Which pair merges first? (Answer: \(A\) and \(C\), at dissimilarity 2.)
- Starting from eight singleton clusters, how many merges are required to stop with five clusters? (Answer: 3 merges.)
- Current clusters are \(\{M,N\},R,S\), with dissimilarities \(D(\{M,N\},R)=4\), \(D(\{M,N\},S)=6\), and \(D(R,S)=3\). Which merge occurs next, and what is the new partition? (Answer: Merge \(R,S\); the partition is \(\{\{M,N\},\{R,S\}\}\).)
- A clustering starts with six observations and is intended to stop with two clusters. An analyst performs five merges. Is the stopping count correct? (Answer: No; four merges are required, since \(6-2=4\).)
- At one step, the smallest current cluster dissimilarity is 2.1. An analyst instead merges a pair with dissimilarity 2.4 because its original observation-level distance was among the smallest. What is the procedural error? (Answer: The analyst did not select the minimum among current cluster pairs using the updated dissimilarities; the pair at 2.1 must be selected.)