Hierarchial clustering cannonnical representation?

Question

I have to handle large binary dataset. That is one of the reasons I have to build my own Hierarchical Clustering. As I digged into the algorithms I was surprised and not ;) to find that it is possible to have multiple (not just two) vectors that have the same distance (hamming,overlap,...), so you can pair them differently in a 'correct' way.

F.e. using overlap as similarity mesaure ... the following 3 vectors have overlap of 2 and there are 2 different correct pairing.

 sequence : 110,101,111

what this means is that there is multiple ways to cluster those :

 ((110,111),101)  vs (110,(111,101))

 sequence : 110,101,111,011

 (110,((111,011),101))  vs ((110,(111,011)),101)

Let me illustrate it with integers :

 2,6,8,4
 (2,((4,6),8))  vs ((2,(4,6)),8) vs ....

What this means is that there are no canonical way of clustering/dendogram .

How do you handle that ? Is there a different type of clustering that can have canonical/single representation ?

Answer 1

You can always adjust your algorithm to use a deterministic tie-breaking rule, e.g., sort the data points before applying the clustering algorithm, and always break ties in favor of the earliest/leftmost item. This yields a deterministic algorithm, so if you give it exactly the same input both times, it will produce the same clustering both times. I can't tell whether this is what you are looking for or not.