Clustering with Minimum Spanning Trees: How Good Can It Be?
Journal of Classification · 2025-03 · 42 (1) · 90-112
DOI: 10.1007/s00357-024-09483-1 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Classification, online erschienen am 06.07.2024. Verfasst von Marek Gagolewski und 3 weiteren Autor:innen. Die Arbeit wurde bisher 22-mal zitiert (Crossref) und nennt 101 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Australian Research Council.
Abstract (Originalsprache)
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.
Förderung
- Australian Research Council
Zitieren
APA
Gagolewski, M., Cena, A., Bartoszuk, M., & Brzozowski, Ł. (2025). Clustering with Minimum Spanning Trees: How Good Can It Be?. Journal of Classification, 42(1), 90-112. https://doi.org/10.1007/s00357-024-09483-1
Vancouver
Gagolewski M, Cena A, Bartoszuk M, Brzozowski Ł. Clustering with Minimum Spanning Trees: How Good Can It Be?. Journal of Classification. 2025;42(1):90-112. doi:10.1007/s00357-024-09483-1
BibTeX
@article{Gagolewski2025,
author = {Gagolewski, Marek and Cena, Anna and Bartoszuk, Maciej and Brzozowski, Łukasz},
title = {Clustering with Minimum Spanning Trees: How Good Can It Be?},
journal = {Journal of Classification},
year = {2025},
volume = {42},
number = {1},
pages = {90--112},
doi = {10.1007/s00357-024-09483-1}
}
EUVIMED