Clustering Accuracy Evaluation Based on the Correspondence Probabilities
DOI:
https://doi.org/10.24160/1993-6982-2026-2-164-173Keywords:
clustering, contingency matrix, clustering accuracy, clustering qualityAbstract
A method for assessing the clustering accuracy based on predicted and true clustering is proposed. The latter is obtained as a result of manually labeling the original data to be clustered. The essence of the method is to make sure that each label of the predicted clustering can be replaced with a true clustering label and then calculate the clustering accuracy as a quotient of dividing the number of accurate predictions by the total number of predictions. The replacement label is taken as a result of random selection from the total number of labels equal to the number of clusters, using the probabilities of matches between predicted and true labels. In the general case, a predicted cluster contains instances of data from different true clusters; therefore, one predicted label corresponds to several true ones. The probability of matching the predicted and true labels is defined as the quotient of dividing the number of true-label data instances contained in the predicted cluster by the total number of data instances in that cluster. Algorithms for calculating the clustering accuracy based on the correspondence probabilities and experimental clustering accuracy estimates of the MNIST and Iris data sets are given. The KMeans method is used as the clustering algorithm.
References
1. Davies–Bouldin Index [Электрон. ресурс] https://en.wikipedia.org/wiki/Davies%E2%80%93Bouldin_index (дата обращения 01.06.2025).
2. MNIST Database [Электрон. ресурс] https://en.wikipedia.org/wiki/MNIST_database (дата обращения 01.06.2025).
3. Iris Species [Электрон. ресурс] https://www.kaggle.com/datasets/uciml/iris (дата обращения 01.06.2025).
4. Sklearn Metrics [Электрон. ресурс] https://scikit-learn.org/stable/api/sklearn.metrics.html (дата обращения 01.06.2025).
5. Rand Index [Электрон. ресурс] https://en.wikipedia.org/wiki/Rand_index (дата обращения 01.06.2025).
6. Vinh N. X., Epps J., Bailey J. Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance // J. Machine Learning Research. 2010. V. 11. Pp. 2837—2854.
7. Hubert L., Arabie P. Comparing Partitions // J. Classification. 1985. V. 2. Pp. 193—218.
8. Chacón J.E., Rastrojo A.I. Minimum Adjusted Rand Index for Two Clusterings of a Given Size // Advances in Data Analysis and Classification. 2023. V. 17. Pp. 125—133.
9. Mutual Info Score [Электрон. ресурс] https://scikit-learn.org/stable/modules/generated/sklearn.metrics.mutual_info_score.html (дата обращения 01.06.2025).
10. Кластеризация [Электрон. ресурс] https://scikit-learn.ru/stable/modules/clustering.html (дата обращения 01.06.2025).
11. Gates A.J., Ahn Y. The Impact of Random Models on Clustering Similarity // J. Machine Learning Research. 2017. V. 18. Pp. 1—28.
12. Fränti P., Sieranoja S. Clustering Accuracy // Appl. Computing and Intelligence. 2024. V. 4(1). Pp. 24—44.
13. SciPy Documentation [Электрон. ресурс] https://docs.scipy.org/doc/scipy/index.html (дата обращения 01.06.2025).
14. Yang B. e. a. Towards K-means-friendly Spaces: Simultaneous Deep Learning and Clustering // Proc. 34th Intern. Conf. Machine Learning. 2017. V. 70. Pp. 3861—3870.
15. Affeldt S., Labiod L., Nadif M. Spectral Clustering via Ensemble Deep Autoencoder Learning [Электрон. ресурс] https://arxiv.org/pdf/1901.02291 (дата обращения 01.06.2025).
16. Yang X. e. a. Adversarial Learning for Robust Deep Clustering // NeurIPS Proc. 2020. V. 33. Pp. 9098—9108.
17. McConville R. N2D: (Not Too) Deep Clustering via Clustering the Local Manifold of an Autoencoded Embedding // Proc. XXV Intern. Conf. Pattern Recognition. 2021. Pp. 5145—5152.
18. Wang J., Jiang J. Unsupervised Deep Clustering via Adaptive GMM Modeling and Optimization // Neurocomputing. 2021. V. 433. Pp. 199—211.
19. Lim K. Deep clustering Using Adversarial Net-based Clustering Loss [Электрон. ресурс] https://arxiv.org/html/2412.08933v1 (дата обращения 01.06.2025).
20. Gagolewski M. Normalized Clustering Accuracy: an Asymmetric External Cluster Validity Measure [Электрон. ресурс] https://arxiv.org/pdf/2209.02935 (дата обращения 01.06.2025).
21. Jerdee M., Kirkley A., Newman M.E.J. Normalized Mutual Information is a Biased Measure for Classification and Community Detection. [Электрон. ресурс] https://arxiv.org/pdf/2307.01282 (дата обращения 01.06.2025)
---
Для цитирования: Бартеньев О.В. Оценка качества кластеризации на основе вероятностей соответствий // Вестник МЭИ. 2026. № 2. С. 164—173. DOI: 10.24160/1993-6982-2026-2-164-173.
#
1. Davies–Bouldin Index [Elektron. Resurs] https://en.wikipedia.org/wiki/Davies%E2%80%93Bouldin_index (Data Obrashcheniya 01.06.2025).
2. MNIST Database [Elektron. Resurs] https://en.wikipedia.org/wiki/MNIST_database (Data Obrashcheniya 01.06.2025).
3. Iris Species [Elektron. Resurs] https://www.kaggle.com/datasets/uciml/iris (Data Obrashcheniya 01.06.2025).
4. Sklearn Metrics [Elektron. Resurs] https://scikit-learn.org/stable/api/sklearn.metrics.html (Data Obrashcheniya 01.06.2025).
5. Rand Index [Elektron. Resurs] https://en.wikipedia.org/wiki/Rand_index (Data Obrashcheniya 01.06.2025).
6. Vinh N. X., Epps J., Bailey J. Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance. J. Machine Learning Research. 2010;11:2837—2854.
7. Hubert L., Arabie P. Comparing Partitions. J. Classification. 1985;2:193—218.
8. Chacón J.E., Rastrojo A.I. Minimum Adjusted Rand Index for Two Clusterings of a Given Size. Advances in Data Analysis and Classification. 2023;17:125—133.
9. Mutual Info Score [Elektron. Resurs] https://scikit-learn.org/stable/modules/generated/sklearn.metrics.mutual_info_score.html (Data Obrashcheniya 01.06.2025).
10. Klasterizatsiya [Elektron. Resurs] https://scikit-learn.ru/stable/modules/clustering.html (Data Obrashcheniya 01.06.2025). (in Russian).
11. Gates A.J., Ahn Y. The Impact of Random Models on Clustering Similarity. J. Machine Learning Research. 2017;18:1—28.
12. Fränti P., Sieranoja S. Clustering Accuracy. Appl. Computing and Intelligence. 2024;4(1):24—44.
13. SciPy Documentation [Elektron. Resurs] https://docs.scipy.org/doc/scipy/index.html (Data Obrashcheniya 01.06.2025).
14. Yang B. e. a. Towards K-means-friendly Spaces: Simultaneous Deep Learning and Clustering. Proc. 34th Intern. Conf. Machine Learning. 2017;70:3861—3870.
15. Affeldt S., Labiod L., Nadif M. Spectral Clustering via Ensemble Deep Autoencoder Learning [Elektron. Resurs] https://arxiv.org/pdf/1901.02291 (Data Obrashcheniya 01.06.2025).
16. Yang X. e. a. Adversarial Learning for Robust Deep Clustering. NeurIPS Proc. 2020;33:9098—9108.
17. McConville R. N2D: (Not Too) Deep Clustering via Clustering the Local Manifold of an Autoencoded Embedding. Proc. XXV Intern. Conf. Pattern Recognition. 2021:5145—5152.
18. Wang J., Jiang J. Unsupervised Deep Clustering via Adaptive GMM Modeling and Optimization. Neurocomputing. 2021;433:199—211.
19. Lim K. Deep clustering Using Adversarial Net-based Clustering Loss [Elektron. Resurs] https://arxiv.org/html/2412.08933v1 (Data Obrashcheniya 01.06.2025).
20. Gagolewski M. Normalized Clustering Accuracy: an Asymmetric External Cluster Validity Measure [Elektron. Resurs] https://arxiv.org/pdf/2209.02935 (Data Obrashcheniya 01.06.2025).
21. Jerdee M., Kirkley A., Newman M.E.J. Normalized Mutual Information is a Biased Measure for Classification and Community Detection. [Elektron. Resurs] https://arxiv.org/pdf/2307.01282 (Data Obrashcheniya 01.06.2025)
---
For citation: Bartenyev O.V. Clustering Accuracy Evaluation Based on the Correspondence Probabilities. Bulletin of MPEI. 2026;2:164—173. (in Russian). DOI: 10.24160/1993-6982-2026-2-164-173
