The Fuzzy C+2 Means: Solving the Extended Ambiguity Reject in Clustering
Le Rejet D'Ambiguïté dans les Fc+2M: Extension à Toutes les Classes Composées
OPEN ACCESS
We address in this paper a clustering problem whose goal consists of computing a partition of a family of patterns into disjoint classes. The method that we propose is formulated as a constrained minimization problem, whose solution depends on a cost function in which rejection options are introduced . Two types of rejection have been included : the ambiguity rejection which concerns patterns lying near the class boundaries and the distance rejection dealing with patterns that are far away from all the classes. To compute these rejections, we propose an extension of the fuzzy c-means (FcM) algorithm of Bezdec ([2]). This algorithm is called the fuzzy c+2-means (Fc+2M). These measures allow to manage uncertainty due both to imprecise and incomplete definition of the classes. The advantages of our method are (1) the degree of membership to the rejection classes for a pattern xk are learned in the iterative clustering problem; (2) the partial ambiguity rejections introduce a discounting process between the classical FcM membership functions in order to avoid the memberships to be spread across the classes ; (3) the membership functions are more immune to noise and correspond more closely to the notion of compatibility .
Résumé
Cet article concerne le problème de la classification dont l'objectif consiste à calculer une partition d'un ensemble de formes en classes disjointes. La méthode que nous proposons s'écrit sous la forme d'un problème de minimisation d'un critère de classification dont la solution dépend d'une fonction de contrainte dans laquelle la notion de rejet est introduite . Deux types de rejet ont été inclus : le rejet d'ambiguité qui concerne les individus situés sur la frontière de deux ou plusieurs classes et le rejet de distance gérant ceux qui sont loin de toutes les classes. La notion de rejet permet de gérer l'incertitude due à l'imprécision et à la définition incomplète des classes. Pour. calculer ces rejets, nous proposons une extension de l'algorithme des c -moyennes floues (FcM) de Bezdec [2]. Cet algorithme est appeléc+2-moyennes floues (Fc+2 M). Ces avantages sont :(1) le degré d'appartenance aux classes de rejet d'un individu est déterminé par un calcul itératif durant la phase de coalescence; (2) l'algorithme inclut une modélisation de l'hésitation ou de l'ambigu ité, et des fonctions d'appartenance sont affectées à tous les sous-ensembles de classes de 211 plutôt qu'aux éléments de c2 seulement (S2 étant l'ensemble des classes). De plus, le degré d'appartenance à la classe de rejet d'ambiguité totale d'un individu est calculé explicitement; (3) en introduisant les rejets d'ambigui'té partielle, nous créons une discontinuité entre les fonctions d'appartenance affectées aux classes de 52, ce qui permet de rendre ces fonctions d'appartenance indépendantes .
Pattern recognition, fuzzy sets, clustering, fuzzy c-means, distance rejection, ambiguity rejection .
Mots clés
Reconnaissance des formes, théorie des ensembles flous, coalescence flou, c-moyennes floues, rejet d'ambiguité et rejet de distance.
[1] M.R. Andenberg. Cluster Analysis for Applications, Academic Press, New ork,1973.
[2] J.C. Bezdek. Pattern Recognition with Fuzzy Objective Function Algorithms, PlenumPress, New- ork 1981.
[3] J.C. Bezdek, and J.C. Dunn. Optimal fuzzy partition : a heuristic for estimating the parameters in a mixture of normal distributions, IEEETrans. on Computers, c-24, 835-838, 1975.
[4] J.C.Bezdek, R.J. Hathaway, M.J. Sabin and .T. Tucker. Convergence Theory for Fuzzy c-Means : Counter examples and Repairs, 17(5) : 873-877, September/October 1987.
[5] A. Black and A. isserman. isual reconstruction,In Cambridge, MA : MIT Press, 1987.
[6] I. Bloch. Fuzzy spatial relationships : a few tools for model-based pattern recognition in aerial images. In Image and Signal Processing for remote sensing III, SPIE, ol2955, page 141-150, Taormina, Italie, 1996.
[7] I.Bloch.Fusion dedonnées, ensemblesflousetmorphologiemathématiqueen traitement d'images.Rapportd'habilitation. 95D 007. Telecom Paris, 1995.
[8] I. Bloch and H. Maitre. Fuzzy mathematical morphologies : A comparativem? 1 study,Pattern Recognition, 28(9) : 1341-1387, 1995.
[9] C. Pedrycz and P. aletzky. Fuzzy clsuttring with partial supervision, IEEE Transactions on systems, Man, and Cybernetics, 27(5) : 788-795, 1997.
[10] C.K.Chow. On optimum Recognition Error and Reject Tradeoff. InIEEE Trans.Information Theory. ol 16, pages 41-46, January 1990.
[11] C.K.Chow. RecognitionError and Reject Trade-off.InProc. ThirdAnn.Symp. Document Analysis and Information Retrieval. Vol. 13., page 1-8, Univ of Nevada, Las egas, April 1994.
[12] R. Dave. Characterization and detection of noise in clustering, 1991. In vol.12, pp. 657-664, Pattern recognition letters, 1991.
[13] R. Dave. Robust fuzzyclustering algorithms,IEEE International Conference on Fuzzy Systems. San Francisco, 2: 1281-1286, 1993.
[14] R.N. Dave. Boundary detection through fuzzy clustering. Proc. 1st IEEE International Conferenceon Fuzzy Systems, San Diego, CA, 1992. 1992
[15] C. Demko, P. Looms and M. Ménard.Les c+1 moyennes floues: introduction dur ejeten on classification. SGC'98, Montpellier, septembre 1998.
[16] E. Diday. Optimisation en classificationautomatique, INRIA Ed., 1-2, 179.
[17] B. Dubuisson. Decision with reject option. In European Signal Processing Conference, SPAIN, 1990.
[18] B. Dubuisson and M.H. Mason. A statistical decision rule with incomplete knowledge about classes, Pattern Recognition, 26 : 155-165, 1993.
[19] R.A. Fisher. The statistical utilisation of multiple measurements, (Ann. Eugen., 8, 1938.
[20] C. Fréficot, B. Dubuissonand M.H. Mason. Reject options in fuzzy pattern classifications rules, proc. Eufit'95, Aachen, Germany, 1995.
[21] Donald E. Gustafson and illiam C.Kessel.Fuzzy clustering with a fuzzy covariance matrix, In Proc. IEEE CDC, pages 761-766, San Diago, CA, January 10-12 1979.
[22] T.M. Ha. The Optimum Class-Selective Rejection Rule. InIEEE Transactions on Pattern Analysis and Machine Intelligence. ol.19, N°.6, 1997, pages 608614, okohama, Japan, march 1997.
[23] R.J. Hathaway and J.C. Bezdec. Switching Regression Models and Fuzzy Clustering. InIEEE Transactions on fuzzy systems, ol. 1, N°.3, pages 195203,1993.
[24] A.K. Jain and R.C. Dubes. Algorithms for clustering data, Prentice Hall, 1988.
[25] J.C.Bezdek. Pattern recognition with fuzzy objective function algorithms . In PlenumPress, New- ork, 1987.
[26] R. Krishnapuram and J.M. Keller. The Possibilistic C-Means Algorithm Insights and Recommendations. IEEE Transactions onFuzzySystems,4(3) : 148-158, August 1996.
[27] Raghu Krishnapuram. A possibilistic approach to clustering.IEEE Transactions onFuzzySystems, 1(2) : 98-110, 1993.
[28] S. . Li. Markov Random Field Modelin in Computer ision, Computer Science orkbench. Springer, 16 : 260 pp, 1995.
[29] J. MacQueen. Some methods of classification and analysis of multivariate observations. InProc. 5th Berkeley Symposium on Math., Stat., andProb., . California Press, Berkeley, CA, 1967.
[30] Nikhil R. Pal, Kuhu Pal and James C. Bezdek. A Mixed c-Means Clustering Model. In Proceedingsofthe sixth IEEE International Conference on Fuzzy Systems,apges 11-21, Barcelona, July 1997.
[31] T. Pavlidis. A critical survey of image analysis methods . pages 502-511, ICPR, 1986.
[32] Pawlack. Rough Sets. Theorical Aspects of Reasoning about Data.,Kluwer Academic Publishers. Dordrecht, Boston, London, 1991.
[33] A. Ribert, A. Ennaji, E.Stocker,and .Lecourtier.Structuration dedonnées application à la construction d'un classifieur neuronal distribué, RFIA'98, 1998, 2 : 145-151,janvier 1998.
[34] E. Ruspini. A new approach to clustering, Information and Control, 15 22-32, 1969.
[35] S. K. Pal. Fuzzy tools in the management of uncertainty in pattern recognition, image analysis, vision and expert systems.International Journal ofSystems Sciences. ol. 22, pages 511-549, 1991.
[36] S.K.Pal and D Dutta Majumber. Fuzzy sets and decision making approaches in vowel and speaker recognition, I.E.E.E. Transactions on Systems, Man and Cybernetics. ol.7,pages 625-629, 1977.
[37] N. Tarel,J-Ph. etN. Boujemaa. ne approche flouedu recalage 3D, généricité etrobustesse. 10ème Congrès de Reconnaissance des Formeset Intelligence artificielle(RFIA'96), 1 : 267-276, 1996.
[38] J. . Tukey. Explortary Data Analysis.Reading, MA: Addison- esley, 1977.
[39] M.H. ektae, E.L. ahzah and M. Menard. Automatic segmentation of printed Persian,SCIA'97, 10th Scandinavian Conference on Image Analysis. Finland,pages 767-772, june 1997.
[40] E. ahzah. Contribution à la représentation des connaissances et à leur utilisation pourl'interprétation automatique des images satellites.PhDThesis niversitéPaul Sabatier, Toulouse, 1992.
[41] H.J. immerman, and P. ysno. Quantifying vagueness in decision models. European J. Operational Res.,22 : 148-158, 1985.