Fast semi-supervised evidential clustering. (English) Zbl 1522.68547
Summary: Semi-supervised clustering is a constrained clustering technique that organizes a collection of unlabeled data into homogeneous subgroups with the help of domain knowledge expressed as constraints. These methods are, most of the time, variants of the popular \(k\)-means clustering algorithm. As such, they are based on a criterion to minimize. Amongst existing semi-supervised clusterings, Semi-supervised Evidential Clustering (SECM) deals with the problem of uncertain/imprecise labels and creates a credal partition. In this work, a new heuristic algorithm, called SECM-h, is presented. The proposed algorithm relaxes the constraints of SECM in such a way that the optimization problem is solved using the Lagrangian method. Experimental results show that the proposed algorithm largely improves execution time while accuracy is maintained.
MSC:
| 68T37 | Reasoning under uncertainty in the context of artificial intelligence |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 90C90 | Applications of mathematical programming |
Keywords:
evidential clustering; label constraints; constrained clustering; theory of belief functions; optimizationReferences:
| [1] | Tsai, C.-W., Seira: an effective algorithm for iot resource allocation problem, Comput. Commun., 119, 156-166 (2018) |
| [2] | Sun, S.; Wang, S.; Zhang, G.; Zheng, J., A decomposition-clustering-ensemble learning approach for solar radiation forecasting, Sol. Energy, 163, 189-199 (2018) |
| [3] | Bilge, A.; Polat, H., A scalable privacy-preserving recommendation scheme via bisecting k-means clustering, Inf. Process. Manag., 49, 4, 912-927 (2013) |
| [4] | Zahra, S.; Ghazanfar, M. A.; Khalid, A.; Azam, M. A.; Naeem, U.; Prugel-Bennett, A., Novel centroid selection approaches for kmeans-clustering based recommender systems, Inf. Sci., 320, 1, 156-189 (2015) |
| [5] | Li, Y.; Sun, J., 3d magnetization inversion using fuzzy c-means clustering with application to geology differentiation, Geophysics, 81, 5, J61-J78 (2016) |
| [6] | Xue, M.; Zhou, L.; Kojima, N.; dos Muchangos, L. S.; Machimura, T.; Tokai, A., Application of fuzzy c-means clustering to prtr chemicals uncovering their release and toxicity characteristics, Sci. Total Environ., 622-623, 1, 861-868 (2018) |
| [7] | Dongdong, J.; Arunkumar, N.; Wenyu, Z.; Beibei, L.; Xinlei, Z.; Guangjian, Z., Semantic clustering fuzzy c means spectral model based comparative analysis of cardiac color ultrasound and electrocardiogram in patients with left ventricular heart failure and cardiomyopathy, Future Gener. Comput. Syst., 92, 324-328 (2019) |
| [8] | Anter, A. M.; Hassenian, A. E.; Oliva, D., An improved fast fuzzy c-means using crow search optimization algorithm for crop identification in agricultural, Expert Syst. Appl., 118, 340-354 (2019) |
| [9] | Masson, M.-H.; Denœux, T., ECM: an evidential version of the fuzzy c-means algorithm, Pattern Recognit., 41, 4, 1384-1397 (2008) · Zbl 1131.68081 |
| [10] | Denœux, T.; Li, S.; Sriboonchitta, S., Evaluating and comparing soft partitions: an approach based on Dempster-Shafer theory, IEEE Trans. Fuzzy Syst., 26, 3, 1231-1244 (2017) |
| [11] | Lian, C.; Ruan, S.; Denœux, T.; Li, H.; Vera, P., Spatial evidential clustering with adaptive distance metric for tumor segmentation in fdg-pet images, IEEE Trans. Biomed. Eng., 65, 1, 21-30 (2017) |
| [12] | Ayed, S. B.; Elouedi, Z.; Lefevre, E., ECTD: evidential clustering and case types detection for case base maintenance, (IEEE/ACS 14th International Conference on Computer Systems and Applications (AICCSA) (2017), IEEE: IEEE Hammamet, Tunisia), 1462-1469 |
| [13] | Abdelkhalek, R.; Boukhris, I.; Elouedi, Z., An evidential clustering for collaborative filtering based on users’ preferences, (International Conference on Modeling Decisions for Artificial Intelligence (2019), Springer: Springer Milan, Italy), 224-235 |
| [14] | Masson, M.-H.; Denœux, T., RECM: relational evidential c-means algorithm, Pattern Recognit. Lett., 30, 11, 1015-1026 (2009) |
| [15] | Zhou, K.; Martin, A.; Pan, Q.; Liu, Z.-G., ECMdd: evidential c-medoids clustering with multiple prototypes, Pattern Recognit., 60, 239-257 (2016) |
| [16] | Lui, Z.; Pan, Q.; Dezert, J.; Mercier, G., Credal c-means clustering method based on belief functions, Knowl.-Based Syst., 74, 119-132 (2015) |
| [17] | Zhang, Z.; Liu, Z.; Martin, A.; Liu, Z.; Zhou, K., Dynamic evidential clustering algorithm, Knowl.-Based Syst., 213, Article 106643 pp. (2021) |
| [18] | Denœux, T.; Masson, M.-H., EVCLUS: evidential clustering of proximity data, IEEE Trans. Syst. Man Cybern., Part B, Cybern., 34, 1, 95-109 (2004) |
| [19] | Denœux, T.; Sriboonchitta, S.; Kanjanatarakul, O., Evidential clustering of large dissimilarity data, Knowl.-Based Syst., 106, 179-195 (2016) |
| [20] | Pedrickz, W.; Waletzky, J., Fuzzy clustering with partial supervision, IEEE Trans. Syst. Man Cybern., 27, 5, 787-795 (1997) |
| [21] | Grira, N.; Crucianu, M.; Boujemaa, N., Semi-supervised fuzzy clustering with pairwise-constrained competitive agglomeration, (IEEE International Conference on Fuzzy Systems (FUZZ 2005) (2005), IEEE: IEEE Reno, U.S.A.), 867-872 |
| [22] | Basu, S.; Bilenko, M.; Banerjee, A.; Mooney, R., Probabilistic semi-supervised clustering with constraints, (Chapelle, O.; Scholkopf, B.; Zien, A., Semi-Supervised Learning (2006), MIT Press: MIT Press Cambridge, MA), 71-98, Ch. 5 |
| [23] | Antoine, V.; Labroche, N., Semi-supervised fuzzy c-means variants: a study on noisy label supervision, (International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (2018), Springer: Springer Cádiz, Spain), 51-62 |
| [24] | Antoine, V.; Quost, B.; Masson, M.-H.; Denœux, T., CECM: constrained evidential c-means algorithm, Comput. Stat. Data Anal., 56, 4, 894-914 (2012) · Zbl 1243.62086 |
| [25] | Antoine, V.; Quost, B.; Masson, M.-H.; Denœux, T., CEVCLUS: evidential clustering with instance-level constraints for relational data, Soft Comput., 18, 1321-1335 (2014) |
| [26] | Li, F.; Li, S.; Denoeux, T., k-CEVCLUS: constrained evidential clustering of large dissimilarity data, Knowl.-Based Syst., 142, 29-44 (2018) |
| [27] | Xie, J.; Antoine, V., On a new evidential c-means algorithm with instance-level constraints, (Ben Amor, N.; Quost, B.; Theobald, M., International Conference on Scalable Uncertainty Management. International Conference on Scalable Uncertainty Management, Lecture Notes in Computer Science, vol. 11940 (2019), Springer), 66-78 · Zbl 1440.68303 |
| [28] | Denoeux, T., NN-EVCLUS: neural network-based evidential clustering, CoRR · Zbl 1528.68372 |
| [29] | Antoine, V.; Labroche, N.; Vu, V. V., Evidential seed-based semi-supervised clustering, (International Symposium on Soft Computing & Intelligent Systems. International Symposium on Soft Computing & Intelligent Systems, Kitakyushu, Japan (2014)), 706-711 |
| [30] | Antoine, V.; Gravouil, K.; Labroche, N., On evidential clustering with partial supervision, (International Conference on Belief Functions (2018), Springer: Springer Compiègne, France), 14-21 |
| [31] | Basu, S.; Banerjee, A.; Mooney, R., Semi-supervised clustering by seeding, (Proceedings of 19th International Conference on Machine Learning (ICML). Proceedings of 19th International Conference on Machine Learning (ICML), Sydney, Australia (2002)), 19-26 |
| [32] | Shafer, G., A Mathematical Theory of Evidence (1976), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ · Zbl 0359.62002 |
| [33] | Smets, P.; Kennes, R., The transferable belief model, Artif. Intell., 66, 191-234 (1994) · Zbl 0807.68087 |
| [34] | Smets, P., The combination of evidence in the transferable belief model, IEEE Trans. Pattern Anal. Mach. Intell., 12, 5, 447-458 (1990) |
| [35] | Bezdek, J., Pattern Recognition with Fuzzy Objective Function Algorithms, Advanced Applications in Pattern Recognition (1981), Springer: Springer Boston, MA · Zbl 0503.68069 |
| [36] | Ye, Y., An Extension of Karmarkar’s Algorithm and the Trust Region Method for Quadratic Programming, 49-63 (1989), Springer: Springer New York, NY · Zbl 0678.90064 |
| [37] | Ye, Y., On affine scaling algorithms for nonconvex quadratic programming, Math. Program., 56, 1-3, 285-300 (1992) · Zbl 0767.90065 |
| [38] | Dua, D.; Graff, C., UCI machine learning repository (2020) |
| [39] | Hubert, L.; Arabie, P., Comparing partitions, J. Classif., 2, 1, 193-218 (1985) |
| [40] | Goutte, C.; Gaussier, E., A probabilistic interpretation of precision, recall and f-score, with implication for evaluation, (European Conference on Advances in Information Retrieval Research (2005), Springer: Springer Granada, Spain), 345-359 |
| [41] | Smets, P., Imperfect information: imprecision and uncertainty, (Motro, A.; Smets, P., Uncertainty Management in Information Systems (1997), Springer), 225-254 |
| [42] | Wagstaff, K.; Basu, S.; Davidson, I., When is constrained clustering beneficial, and why?, (21st National Conference on Artificial Intelligence and 18th Innovative Applications of Artificial Intelligence Conference (2006), AAAI Press: AAAI Press Boston, U.S.A.), 62-63 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
