Abstract
Measures for quantifying the distance between two partitions are involved in many current applications, including machine vision, image processing and understanding, image and video segmentation, biology and genetics, among others. This article investigates three fundamental aspects of the comparison of partitions: the characterization of metrics for comparing partitions; their role in average-based consensus of partitions; and how the different metrics distort the spatial organization of the partitions of a finite data set. In particular, we significantly reduce number of properties in the existing characterizations of metrics for comparing partitions such as Variation of Information and Mirkin metric. Moreover, we compile the main results describing the impact of these metrics on the construction of average-based consensus functions, as well as we compute the exact reduction of the search space that the different pruning criteria (quota rules) provide. Finally, we compute the distortion value for different \(\beta \)-entropy metrics.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Rand, W.M.: Objetive criteria for the evaluation of clustering methods. J. Am. Stat. Assoc. 66, 846–850 (1971)
Mirkin, B.G., Chernyi, L.B.: Measurement of the distance between distinct partitions of a finite set of objects. Autom. Remote. Control. 31, 786–792 (1970)
Arabie, P., Boorman, S.A.: Multidimensional scaling of mesures of distance between partitions. J. Math. Psychol. 10, 148–203 (1973)
Hubert, L.J.: Nominal scale response agreement as a generalized correlation. Br. J. Math. Stat. Psychol. 30, 98–103 (1977)
Hubert, L.J.: Matching models in the analysis of cross-classification. Psychometrika 44, 21–41 (1979)
Fowlkes, E.B., Mallows, C.L.: A method for comparing two hierarchical clusterings. J. Am. Stat. Assoc. 78(383), 553–569 (1983)
Hubert, L., Arabie, P.: Comparing partitions. J. Classif. 2(1), 193–218 (1985)
Amigó, E., Gonzalo, J., Artiles, J., Verdejo, F.: A comparison of extrinsic clustering evaluation metrics based on formal constraints. Inf. Retrieval 12(4), 461–486 (2009)
Barthélemy, J.P., Monjardet, B.: The median procedure in cluster analysis and social choice theory. Math. Soc. Sci. 1(3), 235–267 (1981)
Xiao, W., Yang, Y., Wang, H., Li, T., Xing, H.: Semi-supervised hierarchical clustering ensemble and its application. Neurocomputing 173(3), 1362–1376 (2016)
Sun, N., Yu, H.: A method to determine the number of clusters based on multi-validity index. In: Nguyen, H.S., Ha, Q.-T., Li, T., Przybyła-Kasperek, M. (eds.) IJCRS 2018. LNCS (LNAI), vol. 11103, pp. 427–439. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99368-3_33
Zaleshina, M., Zaleshin, A.: Multiscale integration for pattern recognition in neuroimaging. In: Pardalos, P.M., Conca, P., Giuffrida, G., Nicosia, G. (eds.) MOD 2016. LNCS, vol. 10122, pp. 411–418. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-51469-7_35
Vega-Pons, S., Jiang, X., Ruiz-Shulcloper, J.: Segmentation ensemble via kernels. In: ACPR 2011, pp. 686–690 (2011)
Huang, D., Lai, J.-H., Wang, C.-D., Yuen, P.C.: Ensembling over-segmentations: from weak evidence to strong segmentation. Neurocomputing 207, 416–427 (2016)
Zhang, Y., Wang, H., Zhou, H., Deng, P.: A mixture model for image boundary detection fusion. IEICE Trans. Inf. Syst. E101-D(4), 1159–1166 (2018)
Meilǎ, M.: Comparing clusterings: an axiomatic view. In: Proceedings of the 22nd International Conference on Machine Learning, pp. 577–584 (2005)
Meilǎ, M.: Comparing clusterings-an information based distance. J. Multivar. Anal. 98(5), 873–895 (2002)
Meilǎ, M., Heckerman, D.: An experimental comparison of model-based clustering methods. Mach. Learn. 42(1–2), 9–29 (2001)
Correa-Morris, J.: Comparing partitions: shortest path length metrics and submodularity. Int. J. Math. Models Methods Appl. Sci. 13, 45–51 (2019)
Barthélemy, J.-P., Leclerc, B.: The median procedure for partitions. Partitioning Data Sets 19, 3–34 (1993)
Vega-Pons, S., Correa-Morris, J., Ruiz-Shulcloper, J.: Weighted partition consensus via kernels. Pattern Recogn. 43(8), 2712–2724 (2010)
Vega-Pons, S., Avesani, P.: Clustering ensemble on reduced search spaces. In: COPEM Workshop (2013)
Franek, L., Jiang, X.: Ensemble clustering by means of clustering embedding in vector spaces. Pattern Recognit. 47(2), 833–842 (2014)
Ilc, N.: Weighted cluster ensemble based on partition relevance analysis with reduction step. IEEE Access 8, 113720–113736 (2020)
Simovici, D.: On generalized entropy and entropic metrics. J. Multiple Valued Logic Soft Comput. 13(4/6), 295 (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Correa-Morris, J., Urra-Yglesias, A., Reyes, E., Martínez, J., Gonzalez, B. (2022). Comparing Partitions: Metric Characterizations, Mean Partition, and Distortion. In: Arai, K. (eds) Intelligent Computing. Lecture Notes in Networks and Systems, vol 283. Springer, Cham. https://doi.org/10.1007/978-3-030-80119-9_56
Download citation
DOI: https://doi.org/10.1007/978-3-030-80119-9_56
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-80118-2
Online ISBN: 978-3-030-80119-9
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)