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,((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 ?


1 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.

  • $\begingroup$ good advice .. btw I'm doing online/incremental clustering, so it is by default deterministic, but I was hoping there will be some other "arrangement" that would fix the multiplicity problem ... multidimensional clustering or something ? $\endgroup$
    – sten
    May 12, 2021 at 23:34
  • $\begingroup$ @sten, I don't know, I can't understand what exactly the problem is or what the precise requirements are, so I'm not sure what to suggest. $\endgroup$
    – D.W.
    May 13, 2021 at 2:15
  • $\begingroup$ h-clustering that i know of pairs only 2 values .. i'm looking for clustering which can accommodate multi-pairing and is still hierarchical .. i imagine it is as multidimensional or some sort of fuzzy clustering ... $\endgroup$
    – sten
    May 13, 2021 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.