Get k most diverse objects from dendrogram (hierarchical clustering)

Question

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.

Answer 1

I would say that if you're looking for the truly optimal solution then no, a dendogram won't help. However, it may give you some decent heuristics.

There's a mismatch between what you dendogram represents and what you're trying to achieve. A dendogram is based on distances between clusters, whereas you're trying to optimize (some function of) distances between points.

Also, what you're trying to optimize is not clear.

If you're trying to optimize the sum of all distances, you've got something that looks like a "reverse" travelling salesman problem. So my hunch is that if you can maximize the distances, then you can probably minimize them, i.e. the problem is NP-complete and to get an optimal solution you basically need to enumerate every solution (in the worst case). Since a dendogram doesn't give you all the point-to-point distances, I can't see how you would do it with a dendogram.

Also, for the case where k is not known, you suggest that we start with a point then incrementally add points while maintaining the criterion that they are "most diverse". Following what I said above, if you're trying to maximize the sum of distances, then this can't work (i.e. the definition of what you want doesn't match the optimization criterion), because the optimal solution for a given k is not, in general, the optimal solution for k-1 plus one more point. Take points, for example, on a circle, for example the unity circle. In that (admittedly artificial example) the points that maximize the sum of distances form a regular polygon in that circle. For k=2 you want two points diametrically opposed, but for k=3, you would want points that form an equilateral triangle, and that can't include two diametrically opposed points.

Another optimization criterion would be to maximize the minimum distance of two points within your set of diverse points. Again, the case of k unknown would be a problem.