How to build the tree with the "most different" solutions of a clustering?

Question

Illustrate the question with an example : we have a similarity matrix for 1000 people, and the similarity represents how much their hobbies are the same (it does not really matter how it's built).

Let's say that among these people :

• 50% are 15 years old and 50% are 60 years old ;
• At the same time, 33% are American, 33% are European, and 34% are Asian.

Now if we run a clustering algorithm on this dataset.

• with k = 2, groups are divided based on their age (younger / older);
• with k = 3, groups are divided based on their place of origin (US, Europe, Asia), and the cluster allocation is very different from k = 2 : many couples together in k = 2 are separate with k = 3 and vice versa.
• and with k = 6, groups are divided on both age and region (young US, young EU, ...)

I find it interesting to realize that :

• clusters with k = 2 and k = 3 are the most different
• cluster with k = 6 merge both

My question is the following :

On a more complex dataset, how to detect automatically this "tree-like shape" of the "most different clustering paths" ? In the current example it would be to detect that k = 2 and k = 3 are the two most different yet interesting clusterings; and that k = 6 is a parent of both.

I am having trouble doing bibliography on this, I tried keywords like "trees", "consensus", "most different" clustering, but I didn't find an answer.

Honestly I can't believe I am the first one to ask this question, I guess I just don't know how to formulate it correctly.

Edit : Maybe "alternative clustering" is the keyword I am looking for

Answer 1

Have you taken a look at hierarchical clustering algorithms? You can choose among several distance metrics and use a dendrogram to visualize the various splits. Standard packages like scikit-learn & Scipy have a number of common hierarchical clustering algorithms/visualization tools.