Clustering with minimum spanning trees: How good can it be?

Abstract

Minimum spanning trees (MSTs) provide a convenient representation of datasets in numerous pattern recognition activities. Moreover, they are relatively fast to compute. In this paper, we quantify the extent to which they are meaningful in low-dimensional partitional data clustering tasks. By identifying the upper bounds for the agreement between the best (oracle) algorithm and the expert labels from a large battery of benchmark data, we discover that MST methods can be very competitive. Next, we review, study, extend, and generalise a few existing, state-of-the-art MST-based partitioning schemes. This leads to some new noteworthy approaches. Overall, the Genie and the information-theoretic methods often outperform the non-MST algorithms such as K-means, Gaussian mixtures, spectral clustering, Birch, density-based, and classical hierarchical agglomerative procedures. Nevertheless, we identify that there is still some room for improvement, and thus the development of novel algorithms is encouraged.

References in corpus (9)

• Estimation of Rényi Entropy and Mutual Information Based on Generalized Nearest-Neighbor Graphs
• Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm
• Are Cluster Validity Measures (In)valid?
• The Area Under the ROC Curve as a Measure of Clustering Quality
• Theory of minimum spanning trees I: Mean-field theory and strongly disordered spin-glass model
• A framework for benchmarking clustering algorithms
• Theory of minimum spanning trees II: exact graphical methods and perturbation expansion at the percolation threshold
• Benchmarking in cluster analysis: A white paper
• Quantifying dependencies for sensitivity analysis with multivariate input sample data