complete linkage聚类平局问题：distance matrix示例及成因咨询

Hey there! Great call diving into building complete linkage clustering from scratch—grasping edge cases like tie distances is key to making your implementation solid. Let’s break this down with a concrete example and walk through why these ties hit complete linkage way harder than single linkage.

Example Distance Matrix with Ties #

Here’s a simple 4-point distance matrix where ties are present:

A     B     C     D
A        0.0   1.0   3.0   4.0
B        1.0   0.0   3.0   4.0
C        3.0   3.0   0.0   2.0
D        4.0   4.0   2.0   0.0

Notice the ties here:

• Distance between (A,C) and (B,C) are both 3.0
• Distance between (A,D) and (B,D) are both 4.0

Why Ties Impact Complete Linkage More #

Let’s contrast how single vs complete linkage handle this scenario to see the difference:

Single Linkage’s Reaction #

Single linkage uses the minimum distance between any two points across clusters. Let’s walk through the steps:

1. First, we merge C and D (distance 2.0, the smallest in the matrix)
2. Next, calculate distances between the new cluster {C,D} and A: min(3.0, 4.0) = 3.0; between {C,D} and B: min(3.0, 4.0) = 3.0
3. The smallest remaining distance is between A and B (1.0), so we merge those next
4. Finally, merge {A,B} with {C,D} (min distance is 3.0)

Even with ties in the matrix, single linkage’s focus on the closest connections leads to a consistent, intuitive cluster structure—no ambiguity here.

Complete Linkage’s Reaction #

Complete linkage uses the maximum distance between any two points across clusters. Let’s adjust our example to create a tie at a critical merging step (changing A-B distance to 4.0):

A     B     C     D
A        0.0   4.0   3.0   4.0
B        4.0   0.0   3.0   4.0
C        3.0   3.0   0.0   2.0
D        4.0   4.0   2.0   0.0

Now, let’s walk through possible paths:

1. Start by merging C and D (still the smallest distance, 2.0)
2. Now, all pairwise cluster distances are:
   • {C,D} ↔ A: max(3.0, 4.0) = 4.0
   • {C,D} ↔ B: max(3.0, 4.0) = 4.0
   • A ↔ B: 4.0
     All three are ties—here’s where ambiguity kicks in.
3. Path 1: Merge A and B first. Then merge {A,B} with {C,D} (max distance between clusters is 4.0). Final clusters: {A,B} and {C,D}.
4. Path 2: Merge {C,D} with A first. Now calculate the distance between {A,C,D} and B: max(d(A,B)=4.0, d(C,B)=3.0, d(D,B)=4.0) = 4.0. Merging these gives a single cluster {A,B,C,D}—and if you stopped at 2 clusters, you’d have {A,C,D} and {B} instead of the first path’s result.

The Core Reason for Sensitivity #

Complete linkage’s reliance on the maximum cluster distance makes it far more sensitive to ties. This metric focuses on the farthest points between clusters, so ties in these maximum values can lead to drastically different merging orders (and thus different final cluster structures). Single linkage, by contrast, prioritizes the closest connections—ties in non-minimum distances don’t throw off the merging logic as much, since it’s always picking the smallest available distance first.

内容的提问来源于stack exchange，提问作者heresthebuzz