CECM: constrained evidential \(C\)-means algorithm. (English) Zbl 1243.62086
Summary: In clustering applications, prior knowledge about cluster membership is sometimes available. To integrate such auxiliary information, constraint-based (or semi-supervised) methods have been proposed in the hard or fuzzy clustering frameworks. This approach is extended to evidential clustering, in which the membership of objects to clusters is described by belief functions. A variant of the Evidential \(C\)-means (ECM) algorithm taking into account pairwise constraints is proposed. These constraints are translated into the belief function framework and integrated in the cost function. Experiments with synthetic and real data sets demonstrate the interest of the method. In particular, an application to medical image segmentation is presented.
MSC:
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 68T37 | Reasoning under uncertainty in the context of artificial intelligence |
| 65C60 | Computational problems in statistics (MSC2010) |
| 92C55 | Biomedical imaging and signal processing |
Keywords:
clustering; semi-supervised learning; pairwise constraints; adaptive metric; active learning; belief functions; Dempster-Shafer theory; evidence theorySoftware:
CECMReferences:
| [1] | Basu, S., Banerjee, A., Mooney, R.J., 2004. Active semi-supervision for pairwise constrained clustering. In: Proceedings of the SIAM International Conference on Data Mining. Lake Buena Vista, FL, USA, pp. 333-344.; Basu, S., Banerjee, A., Mooney, R.J., 2004. Active semi-supervision for pairwise constrained clustering. In: Proceedings of the SIAM International Conference on Data Mining. Lake Buena Vista, FL, USA, pp. 333-344. |
| [2] | Basu, S.; Bilenko, M.; Banerjee, A.; Mooney, R. J., Probabilistic semi-supervised clustering with constraints, (Chapelle, O.; Schölkopf, B.; Zien, A., Semi-Supervised Learning (2006), MIT Press), 71-98 |
| [3] | Baudrit, C.; Dubois, D., Practical representations of incomplete probabilistic knowledge, Computational Statistics & Data Analysis, 51, 1, 86-108 (2006), The Fuzzy Approach to Statistical Analysis · Zbl 1157.62564 |
| [4] | Berget, I.; Mevik, B.; Næs, T., New modifications and applications of fuzzy \(c\)-means methodology, Computational Statistics & Data Analysis, 52, 5, 2403-2418 (2008) · Zbl 1452.62432 |
| [5] | Bezdek, J. C., Pattern Recognition with Fuzzy Objective Function Algorithms (1981), Plenum Press: Plenum Press New York · Zbl 0503.68069 |
| [6] | Bloch, I., Defining belief functions using mathematical morphology: application to image fusion under imprecision, International Journal of Approximate Reasoning, 48, 437-465 (2008) · Zbl 1184.68581 |
| [7] | Cohn, D. A.; Ghahramani, Z.; Jordan, M. I., Active learning with statistical models, Journal of Artificial Intelligence Research, 4, 129-145 (1996) · Zbl 0900.68366 |
| [8] | Davé, R. N., Clustering relational data containing noise and outliers, Pattern Recognition Letters, 12, 657-664 (1991) |
| [9] | Davidson, I.; Ravi, S. S., Clustering with constraints: feasibility issues and the \(k\)-means algorithm, (Proceedings of the Fifth SIAM International Conference on Data Mining (2005), Society for Industrial Mathematics: Society for Industrial Mathematics Newport Beach, CA, USA), 138 |
| [10] | Davidson, I., Wagstaff, K.L., Basu, S., 2006. Measuring constraints-set utility for partitional clustering algorithms. In: Proceedings of the 10th European Conference on Principle and Practice of Knowledge Discovery in Databases. Berlin, Germany, pp. 115-126.; Davidson, I., Wagstaff, K.L., Basu, S., 2006. Measuring constraints-set utility for partitional clustering algorithms. In: Proceedings of the 10th European Conference on Principle and Practice of Knowledge Discovery in Databases. Berlin, Germany, pp. 115-126. |
| [11] | Denœux, T.; Masson, M.-H., EVCLUS: evidential clustering of proximity data, IEEE Transactions on Systems, Man, and Cybernetics, Part B, 34, 95-109 (2004) |
| [12] | Dring, C.; Lesot, M.-J.; Kruse, R., Data analysis with fuzzy clustering methods, Computational Statistics & Data Analysis, 51, 1, 192-214 (2006), The Fuzzy Approach to Statistical Analysis · Zbl 1157.62434 |
| [13] | Gondek, D.; Hofmann, T., Non-redundant data clustering, Knowledge and Information Systems, 12, 1, 1-24 (2007) |
| [14] | Gordon, A. D., A survey of constrained classification, Computational Statistics & Data Analysis, 21, 1, 17-29 (1996) · Zbl 0900.62313 |
| [15] | Grira, N.; Crucianu, M.; Boujemaa, N., Active semi-supervised fuzzy clustering, Pattern Recognition, 41, 5, 1851-1861 (2008) · Zbl 1140.68461 |
| [16] | Gustafson, D.E., Kessel, W.C., 1978. Fuzzy clustering with a fuzzy covariance matrix. In: IEEE Conference on Decision and Control Including the 17th Symposium on Adaptive Processes. San Diego, CA, USA, vol. 17, pp. 761-765.; Gustafson, D.E., Kessel, W.C., 1978. Fuzzy clustering with a fuzzy covariance matrix. In: IEEE Conference on Decision and Control Including the 17th Symposium on Adaptive Processes. San Diego, CA, USA, vol. 17, pp. 761-765. · Zbl 0448.62045 |
| [17] | Höppner, F.; Klawonn, F.; Kruse, R.; Runkler, T., Fuzzy Cluster Analysis: Methods for Classification, Data Analysis and Image Recognition (1999), John Wiley and Sons: John Wiley and Sons New York · Zbl 0944.65009 |
| [18] | Kohonen, T., Self-Organizing Maps (1997), Springer: Springer Berlin · Zbl 0866.68085 |
| [19] | Krishnapuram, R.; Keller, J. M., A possibilistic approach to clustering, IEEE Transactions on Fuzzy Systems, 1, 2, 98-110 (1993) |
| [20] | Law, M. H.C.; Topchy, A.; Jain, A. K., Clustering with soft and group constraints, Lecture Notes in Computer Science, 31, 662-670 (2004) · Zbl 1104.68639 |
| [21] | Masson, M.-H.; Denœux, T., Clustering interval-valued data using belief functions, Pattern Recognition Letters, 25, 2, 163-171 (2004) |
| [22] | Masson, M.-H.; Denœux, T., ECM: an evidential version of the fuzzy \(c\)-means algorithm, Pattern Recognition, 41, 1384-1397 (2008) · Zbl 1131.68081 |
| [23] | Masson, M.-H.; Denœux, T., RECM: relational evidential \(c\)-means algorithm, Pattern Recognition Letters, 30, 1015-1026 (2009) |
| [24] | Shafer, G., A Mathematical Theory of Evidence (1976), Princeton University Press: Princeton University Press Princeton, NJ, USA · Zbl 0359.62002 |
| [25] | Smets, P., The transferable belief model for quantified belief representation, (Handbook of Defeasible Reasoning and Uncertainty Management Systems, vol. 1 (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA, USA), 267-301 · Zbl 0939.68112 |
| [26] | Smets, P.; Kennes, R., The transferable belief model, Artificial Intelligence, 66, 191-234 (1994) · Zbl 0807.68087 |
| [27] | Wagstaff, K., Value, cost, and sharing: open issues in constrained clustering, Lecture Notes in Computer Science, 4747, 1 (2007) |
| [28] | Wagstaff, K., Cardie, C., Rogers, S., Schroedl, S., 2001. Constrained \(k\); Wagstaff, K., Cardie, C., Rogers, S., Schroedl, S., 2001. Constrained \(k\) |
| [29] | Xing, E. P.; Ng, A. Y.; Jordan, M. I.; Russell, S., Distance metric learning, with application to clustering with side-information, (Advances in Neural Information Processing Systems, vol. 15 (2002), MIT Press: MIT Press Cambridge, MA), 505-512 |
| [30] | Yager, R. R., On the normalization of fuzzy belief structures, International Journal of Approximate Reasoning, 14, 2-3, 127-153 (1996) · Zbl 0935.03036 |
| [31] | Ye, Y.; Tse, E., An extension of Karmarkar’s projective algorithm for convex quadratic programming, Mathematical Programming, 44, 1, 157-179 (1989) · Zbl 0674.90077 |
| [32] | Zhong, S., Ghosh, J., 2003. Scalable, balanced model-based clustering. In: Proc. 3rd SIAM Int. Conf. Data Mining. San Francisco, CA, USA, pp. 71-82.; Zhong, S., Ghosh, J., 2003. Scalable, balanced model-based clustering. In: Proc. 3rd SIAM Int. Conf. Data Mining. San Francisco, CA, USA, pp. 71-82. |
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.
