Benchmarking Minimax Linkage in Hierarchical Clustering

Minimax linkage was first introduced by Ao et al. (2004) in 2004, as an alternative to standard linkage methods used in hierarchical clustering. Minimax linkage relies on distances to a prototype for each cluster; this prototype can be thought of as a representative object in the cluster, hence improving the interpretability of clustering results. Bien and Tibshirani analyzed properties of this method in 2011 (Bien and Tibshirani 2011), popularizing the method within the statistics community. Additionally, they performed some comparisons of minimax linkage to standard linkage methods. In an effort to expand upon their work and evaluate minimax linkage more comprehensively, we follow the guidelines for neutral benchmark studies outlined in Van Mechelen et al. (2018), focusing on thorough method evaluation via multiple performance metrics on several well-described data sets. We also make all code and data publicly available through an R package, for full reproducibility. Similarly to Bien and Tibshirani (2011), we find that minimax linkage often produces the smallest distances to prototypes, meaning that objects in a cluster are tightly clustered around their prototype. This is true across a range of values for the total number of clusters (k). However, this is not universally true, and special attention should be paid to the case when k is the true known value. For true k, minimax linkage does not always perform the best in terms of all the evaluation metrics studied, including distance to prototype.