Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have constructed a hierarchical clustering of data using some proximity function. Now I would like to calculate a representative value of any given node of this clustering, such that it reflects the different contributions of the branch components. I know that this is a very tricky and risky task, but still...

Can anyone point me to a simple method of averaging such branches?

share|improve this question
    
en.wikipedia.org/wiki/Hierarchical_clustering Wikipedia referred to this free downloadable book. www-stat.stanford.edu/~tibs/ElemStatLearn –  Will Jagy May 4 '10 at 18:23
add comment

2 Answers 2

up vote 1 down vote accepted

If you do some sort of centroid linkage algorithm to construct your hierarchal clustering, you should be able to pick out the centroid values just before merging clusters as representatives at those levels. It'd require tweaking the algorithm to get the points to tag the corresponding tree, but shouldn't be too hard to write up.

Alternatively, reinterpret the hierarchal clustering as persistent homology and pick out representative cycles for the homology classes associated to each bar in the barcode. jPlex ( http://comptop.stanford.edu/programs/jplex/index.html ) or javaPlex ( http://code.google.com/p/javaplex ) should both be able to do just that if I remember correctly.

share|improve this answer
add comment

it really depends on how you're doing the hierarchical clustering, but if (for example) you're using a sum-of-squares measure, then the centroidal merging that Mikael recommends is in fact the exact representative.

There are entire families of clustering algorithms that rely on the ability to store representatives of lower parts of the clustering and merge them. While these are not hierarchical per se, they use a hierarchical approach, and so the concept is the same. For reference, check out the BIRCH algorithm:

http://en.wikipedia.org/wiki/BIRCH_%28data_clustering%29

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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