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