Clustering with shallow trees

TitleClustering with shallow trees
Publication TypeJournal Article
Year of Publication2009
AuthorsBailly-Bechet M, Bradde S, Braunstein A, Flaxman A, Foini L, Zecchina R
Refereed DesignationRefereed
JournalJournal of Statistical Mechanics: Theory and Experiment
Start PageP12010
Date Published12/2009

We propose a new method for obtaining hierarchical clustering based on the optimization of a cost function over trees of limited depth, and we derive a message-passing method that allows one to use it efficiently. The method and the associated algorithm can be interpreted as a natural interpolation between two well-known approaches, namely that of single linkage and the recently presented affinity propagation. We analyse using this general scheme three biological/medical structured data sets (human population based on genetic information, proteins based on sequences and verbal autopsies) and show that the interpolation technique provides new insight.

Alternate JournalJSTAT