diffeo / kodama

Fast hierarchical agglomerative clustering in Rust.
MIT License
91 stars 11 forks source link

Add Mini-Max-Linkage #10

Open kno10 opened 6 months ago

kno10 commented 6 months ago

Minimax linkage is popular in bioinformatics, because it provides prototypes for each cluster.

The objective is the "minimum maximum distance", i.e., choose the merge $C=A\cup B$ with the smallest $$\min{c\in C} \max{o\in C} d(c,o)$$ where this object $c$ can be seen as a cluster center, and the linkage score as a radius.

S. I. Ao, K. Yip, M. Ng, D. Cheung, P.-Y. Fong, I. Melhado, P. C. Sham
CLUSTAG: hierarchical clustering and graph methods for selecting tag SNPs
Bioinformatics, 21 (8)

J. Bien and R. Tibshirani
Hierarchical Clustering with Prototypes via Minimax Linkage
Journal of the American Statistical Association 106(495)