EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Clustering with Minimum Spanning Trees: How Good Can It Be?

Marek Gagolewski, Anna Cena, Maciej Bartoszuk, Łukasz Brzozowski

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →