# Get k most diverse objects from dendrogram (hierarchical clustering)

I have a dendrogram which groups similar object in a hierarchical order. The problem I try to solve is based on a dendrogram how to get k most diverse objects. E.g. We start with some random (?) object, the next object we choose is the one with farthest distance value from it, the third is the object that is farthest from the group of two previously chosen (we could use the same criteria as in complete linkage, single, group average etc), and so on until we get k objects.

I am wondering if this can be done based on already constructed dendrogram? One thing I am thinking of is to use similarity measure instead of distance measure. Then when constructing a dendrogram, we first link points that are most diverse. So it can be understand as a "inversed" dendrogram.

Any clues? Or maybe this problem has some alias I could lookup on web?

There are two cases of this problem:

1. We know k. I think it is equal if we just cut the dendrogram on kth level and select one object (might be random) from each cluster.

2. We do not know k up front. This option could work as an enumerator with getNext() method and the stop criteria define where we stop. ofcourse 1 <= k <= n, where n is the number of all leaves (objects) in dendrogram.

• I use cubic-clustering-criterion (ccc) to determine appropriate cluster count - it is for optimal count of clusters. If you want to assert a number, then just assert it, and pop one element per cluster out. Ward dendrograms are built to minimize within-cluster variance so within-group variation is much smaller than group-to-group variation. It might not be maximum difference, but it will be characteristically different. – EngrStudent Mar 20 '15 at 19:33
• One general solution, for case 1 (known k) at least, is to consider the dendrogram as a general-type graph (= create matrix of dissimilarity for it) and perform Edmonds blossom algorithm on it. Your task is not a clustering task, it is a matching optimization task. – ttnphns Mar 21 '15 at 8:53