Finding a representative of a branch in hierarchical clustering - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T23:39:40Z http://mathoverflow.net/feeds/question/23451 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/23451/finding-a-representative-of-a-branch-in-hierarchical-clustering Finding a representative of a branch in hierarchical clustering bgbg 2010-05-04T16:17:54Z 2010-06-02T05:29:23Z <p>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...</p> <p>Can anyone point me to a simple method of averaging such branches?</p> http://mathoverflow.net/questions/23451/finding-a-representative-of-a-branch-in-hierarchical-clustering/23467#23467 Answer by Mikael Vejdemo-Johansson for Finding a representative of a branch in hierarchical clustering Mikael Vejdemo-Johansson 2010-05-04T18:51:13Z 2010-05-04T18:51:13Z <p>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.</p> <p>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 ( <a href="http://comptop.stanford.edu/programs/jplex/index.html" rel="nofollow">http://comptop.stanford.edu/programs/jplex/index.html</a> ) or javaPlex ( <a href="http://code.google.com/p/javaplex" rel="nofollow">http://code.google.com/p/javaplex</a> ) should both be able to do just that if I remember correctly.</p> http://mathoverflow.net/questions/23451/finding-a-representative-of-a-branch-in-hierarchical-clustering/26791#26791 Answer by Suresh Venkat for Finding a representative of a branch in hierarchical clustering Suresh Venkat 2010-06-02T05:25:07Z 2010-06-02T05:25:07Z <p>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. </p> <p>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: </p> <p><a href="http://en.wikipedia.org/wiki/BIRCH_%28data_clustering%29" rel="nofollow">http://en.wikipedia.org/wiki/BIRCH_%28data_clustering%29</a></p>