Merging more than one cluster in hierarchical clustering

Question

I have this simple example consisting of

• 5 data points X = {A,B,C,D,E}
• the following proximity matrix (higher value = higher similarity)

| A | B | C | D | E
A | - | 9 | 0 | 9 | 3
B | 9 | - | 8 | 4 | 0
C | 0 | 8 | - | 5 | 0
D | 9 | 4 | 5 | - | 7
E | 3 | 0 | 0 | 7 | -


Given the first row of the matrix, what would happen in the first iteration, if I would apply an agglomerative hierarchical clustering algorithm. Which clusters are merged? Just (A,B) or (A,B,D)? Every example that I could find only merged two clusters per iteration. But in my example Clusters A, B and D have the same proximity/similarity, hence my intuition is to merge all three.

Any advice?

Answer 1

In real continuous data, one assumes that this doesn't occur often. Unfortunately for binary and categorical data it is fairly common...

To avoid the additional complexity of 'multi merges', pretty much every implementation I have seen will just pick one of the 'equally good' best solutions. Usually the first or last one found.

With single-link it does not matter, but with others it may make a difference, which is why different permutations may yield different results.

But I'd go as far as saying: if the merge order makes a difference to your resulting clusters, then they probably are not significant.