Why Tied Distances Need Careful Interpretation
Agglomerative hierarchical clustering repeatedly joins the two current clusters with the smallest dissimilarity. Usually this instruction identifies one pair. If several pairs share the minimum, however, the algorithm has a choice. The choice may change only the order of two independent merges, or it may produce different cluster memberships at a specified stage. Those are different consequences, and an analysis should not treat every tie as harmless or every different sequence as a different final partition.
The important distinction is between a merge history—the sequence of pairwise joins—and a partition—the collection of clusters at a particular stage. Two histories can differ while giving the same partition after the tied merges are completed. Conversely, a tie can leave different partitions at an intermediate stage or even at the same later stage.
The dissimilarities are computed using the selected linkage rule, such as single, complete, average, centroid, or Ward linkage. Once a merge is made, distances are updated and the minimum is found again. Thus a tie at one step does not, by itself, tell us what the next minimum will be. It must be recalculated for each alternative merge.
Independent Ties Can Change the Order but Not the Resulting Partition
Worked Example: Two Disjoint Pairs Tied Under Average Linkage
Four hypothetical risk profiles, \(A,B,C,D\), have the following dissimilarities. Use average linkage. Find the tied first merges and compare the partitions after one and two merges.
| Pair | Dissimilarity |
|---|---|
| \(A,B\) | 1 |
| \(A,C\) | 4 |
| \(A,D\) | 5 |
| \(B,C\) | 5 |
| \(B,D\) | 4 |
| \(C,D\) | 1 |
Step 1: Find every minimum pair. The smallest value is \(1\), attained by \(\{A,B\}\) and \(\{C,D\}\). Thus \(\mathcal{M}=\{\{A,B\},\{C,D\}\}\), so there are two eligible first merges.
Step 2: Compare the first-stage partitions. If \(A\) and \(B\) merge first, the partition is \(\{\{A,B\},\{C\},\{D\}\}\). If \(C\) and \(D\) merge first, it is \(\{\{A\},\{B\},\{C,D\}\}\). These are distinct partitions at three clusters.
Step 3: Recalculate after either choice. Following the first choice, \(D(C,D)=1\) remains the minimum, so \(C\) and \(D\) merge next. Following the second choice, \(D(A,B)=1\) remains the minimum, so \(A\) and \(B\) merge next. Either way, after two merges the partition is \(\{\{A,B\},\{C,D\}\}\).
Method and check. The two tied pairs are disjoint, so merging one does not remove the other candidate pair. The histories differ in order, but the partition after both merges is the same. The common mistake is to call the clustering result nonunique without specifying the stage: the three-cluster partition differs, whereas the two-cluster partition here does not.
Overlapping Ties Can Produce Different Partitions
A tie is more consequential when the eligible pairs share an object. The first merge then changes which clusters exist and can change the distances used at the following step. The next example uses single linkage, for which the distance between two clusters is the smallest dissimilarity between any member of one cluster and any member of the other.
Worked Example: Overlapping Ties and a Unique Height-Based Cut
Four hypothetical portfolios \(A,B,C,D\) have these dissimilarities. Use single linkage. Compare the alternatives at the first tie, then examine the partition after two merges and the partition obtained by including all merges of height at most \(1\).
| Pair | Dissimilarity |
|---|---|
| \(A,B\) | 1 |
| \(A,C\) | 1 |
| \(B,C\) | 3 |
| \(A,D\) | 7 |
| \(B,D\) | 6 |
| \(C,D\) | 5 |
Step 1: Identify the tie. The minimum is \(1\), attained by \(\{A,B\}\) and \(\{A,C\}\). These alternatives overlap at \(A\).
Step 2: Follow the \(A,B\) choice. The distance from \(\{A,B\}\) to \(C\) is \(\min(1,3)=1\). The other current distances are \(D(\{A,B\},D)=\min(7,6)=6\) and \(D(C,D)=5\). Thus the next merge joins \(\{A,B\}\) to \(C\), at height \(1\).
Step 3: Follow the \(A,C\) choice instead. The distance from \(\{A,C\}\) to \(B\) is \(\min(1,3)=1\). Also, \(D(\{A,C\},D)=\min(7,5)=5\) and \(D(B,D)=6\). The next merge joins \(\{A,C\}\) to \(B\), again at height \(1\).
After one merge, the three-cluster partitions differ: one contains \(\{A,B\}\), and the other contains \(\{A,C\}\). After two merges, both paths give \(\{\{A,B,C\},\{D\}\}\). In this example, a height-based cut that includes all merges at height at most \(1\) therefore gives the same partition under either tie-breaking choice. The histories are nonunique, but that cut is unique.
Method and check. Each second merge was recalculated using the single-linkage minimum, not the original pairwise distance alone. The common mistake is to stop at the first arbitrary tie-break and conclude that every cut must differ. Here the intermediate three-cluster partitions differ, while the partition after all height-\(1\) merges is the same.
Why a Tie Can Change the Subsequent Clustering
With other linkage rules, an alternative first merge can produce different updated distances and a different next pair. For average linkage, the distance between clusters is the mean of all pairwise dissimilarities across them. If \(A\) and \(B\) are merged and \(C\) is another cluster, the update is a size-weighted average of the two former cluster distances.
Worked Example: Alternative Ties Change the Next Average-Linkage Merge
Four hypothetical claim portfolios \(A,B,C,D\) have the following pairwise dissimilarities. Use average linkage. For each eligible first merge, calculate the next minimum and the partition after two merges.
| Pair | Dissimilarity |
|---|---|
| \(A,B\) | 1.0 |
| \(A,C\) | 1.0 |
| \(B,C\) | 1.5 |
| \(A,D\) | 1.1 |
| \(B,D\) | 1.8 |
| \(C,D\) | 1.1 |
Step 1: Find the first tied minimum. The minimum is \(1.0\), attained by \(\{A,B\}\) and \(\{A,C\}\). All other listed dissimilarities exceed \(1.0\).
Step 2: Merge \(A,B\). Each cluster has size 1. The updated distances are \(D(\{A,B\},C)=(1.0+1.5)/2=1.25\) and \(D(\{A,B\},D)=(1.1+1.8)/2=1.45\). The remaining singleton distance is \(D(C,D)=1.1\). Therefore \(C,D\) merge next, at \(1.1\). The two-cluster partition is \(\{\{A,B\},\{C,D\}\}\).
Step 3: Merge \(A,C\) instead. The updated distances are \(D(\{A,C\},B)=(1.0+1.5)/2=1.25\) and \(D(\{A,C\},D)=(1.1+1.1)/2=1.1\). The remaining singleton distance is \(D(B,D)=1.8\). Therefore \(\{A,C\}\) merges with \(D\) next, at \(1.1\). The two-cluster partition is \(\{\{A,C,D\},\{B\}\}\).
Method and check. Both alternatives have the same first merge height and the same second merge height, but they give different two-cluster partitions. The update formula applies because average linkage averages all cross-cluster pairs; the clusters being merged in each calculation have equal size. The common mistake is to assume that equal merge heights force equal cluster memberships. They do not.
Reporting Ties and Avoiding Exam Traps
A complete answer to a tied-distance problem should state the minimum value, list every eligible unordered pair, and explain what the requested conclusion means. If the question asks for the next merge, a tie means there is no single answer unless a tie-breaking convention is specified. If it asks for a partition after several merges or at a stated height, follow each relevant path far enough to compare memberships.
- Do not count reversed pairs twice. The pair \(\{A,B\}\) is one eligible merge, not two ordered choices \((A,B)\) and \((B,A)\).
- Do not assume the tie persists. After one tied pair is merged, recalculate the distances and the minimum.
- Do not confuse history with partition. Different chronological orders can lead to the same cluster memberships at a later stage.
- Do not assume a unique partition at every stage. Overlapping tied pairs can give different memberships at the same number of clusters.
- Distinguish exact and rounded ties. Values displayed to a fixed number of decimals may look equal even when their unrounded values differ. Use exact values or the stated numerical tolerance before declaring a tie.
A tie-breaking rule—such as choosing the lexicographically first pair—can make software output reproducible, but it does not make the underlying minimum unique. Report the rule when a single sequence is required. For a cut or requested stage, report whether the cluster memberships are invariant across the eligible choices, rather than inferring uniqueness from one sequence alone. This distinction is useful when interpreting clustering results and is aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.
Check Your Understanding
For each problem, distinguish the tied merge choices from any conclusion about the resulting partition.
- Four objects have dissimilarities \(D(A,B)=2\), \(D(C,D)=2\), \(D(A,C)=5\), \(D(A,D)=6\), \(D(B,C)=6\), and \(D(B,D)=5\). How many unordered first-merge choices are there, and what partition results after two merges if the two tied pairs are merged? (Answer: Two first-merge choices; after both merges the partition is \(\{\{A,B\},\{C,D\}\}\).)
- Under single linkage, \(D(A,B)=1\), \(D(A,C)=1\), \(D(B,C)=2\), and each of \(D(A,D),D(B,D),D(C,D)\) is \(4\). Compare the partition after one merge with the partition after both height-\(1\) merges. (Answer: The one-merge partition is either \(\{\{A,B\},\{C\},\{D\}\}\) or \(\{\{A,C\},\{B\},\{D\}\}\); after both merges it is \(\{\{A,B,C\},\{D\}\}\).)
- For average linkage, singleton dissimilarities are \(D(A,B)=1\), \(D(A,C)=1\), \(D(B,C)=1.4\), \(D(A,D)=1.2\), \(D(B,D)=2\), and \(D(C,D)=1.2\). If \(A,B\) merge first, calculate the next minimum. (Answer: \(D(\{A,B\},C)=(1+1.4)/2=1.2\), tied with \(D(C,D)=1.2\); there are two eligible next merges.)
- Use the dissimilarities in question 3. If \(A,C\) merge first instead, calculate the updated distances from \(\{A,C\}\) to \(B\) and \(D\), and identify the next merge. (Answer: \(D(\{A,C\},B)=(1+1.4)/2=1.2\), \(D(\{A,C\},D)=(1.2+1.2)/2=1.2\); both are tied for the next merge.)
- A clustering program reports the sequence \(\{A,B\}\) then \(\{C,D\}\), although both pairs had equal minimum dissimilarity initially. What additional information is needed to establish that the first merge was mathematically unique? (Answer: The unrounded current dissimilarities and the full set of unordered minimum pairs; the reported sequence alone does not establish uniqueness.)