Stratégies de rejet en classification supervisée: une synthèse par opérateurs de De Morgan

Stratégies de rejet en classification supervisée: une synthèse par opérateurs de De Morgan

Reject strategies for supervised classification with De Morgan operators : a review

C. Frélicot L. Mascarilla 

Laboratoire Informatique Image Interaction (L3i), UPRES EA 2218, Université de La Rochelle, Avenue Michel Crépeau, 17042 La Rochelle,France cedex 1.

Corresponding Author Email:
15 November 2002
29 February 2004
| Citation



In this article we review strategies used in the design of two-folded rejection-based classifiers. Beside the so-called classical “accept-first” strategy we have recently proposed very general families built on two different approaches, namely the “reject-first”[Fré98a, MF01b] and “mixture-first”[SFM02] reject schemes. These three approaches differ by the kind, as well as the order, of the tests leading to the classifier final output. While the first one starts by testing for distance rejection and, if necessary, finishes by testing for exclusive classification or ambiguity rejection respectively, the two others start respectively by testing for exclusive classification and ambiguity rejection, and then finish by the remaining alternatives. We unify the three schemes by defining fuzzy operators built on De Morgan operators (t-norms, t-conorms, complement). Behaviours of such different classifiers are illustrated on artificially generated examples.


Dans cet article, nous proposons une synthèse des stratégies mises en œuvre pour la conception de discriminateurs avec options de rejet opérant en deux étapes séquentielles. Outre l'approche classique dite «accepte d'abord», nous avons récemment défini des classes générales qui suivent deux approches différentes dites «rejette d'abord» [Fré98a, MF01b] et «mélange d'abord» [SFM02]. Ces trois approches diffèrent par la nature, et l'ordre, des tests effectués pour produire la sortie du discriminateur. La première consiste à tester en premier lieu le rejet de distance, puis seulement si nécessaire à tester l'affectation exclusive contre le rejet d'ambiguïté, la deuxième et la troisième, quant à elles, débutent, respectivement, par un test pour le classement exclusif et un test pour le rejet d'ambiguïté à opposer aux alternatives correspondantes. Nous unifions ici ces trois familles de discriminateurs par l'utilisation d'opérateurs flous fondés sur des opérateurs de De Morgan (t-norme, t-conorme, complément). Les comportements des différentes approches sont illustrées sur des exemples synthétiques.


Classification, reject options, De Morgan operators

Mots clés

Classification supervisée, rejet, opérateurs de De Morgan

1. Introduction
2. Classement Et Options De Rejet
3. Stratégies De Rejet Par Opérateurs De De Morgan
4. Conclusion

[Bez87] J.C. Bezdek, Pattern Recognition with Fuzzy Objective Functions, Plenum Press, New-York, NY, second edition,1987.

[Bis95] C. Bishop, Neural Networks for Pattern Recognition, Oxford University Press, 1995.

[BM98] C.L. Blake and C.J. Merz, UCI repository of machine learning databases, 1998, Dept. of Information and Computer Science, University of California, Irvine, CA,

[BRLA96] J.C. Bezdek, T.R. Reichherzer, G. Lim and Y. Attikiouzel, Classification with multiple prototypes, In: 5th IEEE Int. Conf. on Fuzzy Systems (FUZZ-IEEE), volume 1, pages 626-632, New-Orleans, Lousiana, August, 1996.

[Cho57] C.K. Chow, An optimum character recognition system using decision functions, IRE Trans. on Electronic Computers, EC-6, pp. 247-253, December, 1957.

[Cho70] C.K. Chow, On optimum recognition error and reject tradeoff, IEEE Trans. on Information Theory, IT-16, pp.41-46, 1970.

[Dav91] R. Davé, Characterization and detection of noise in clustering, Pattern Recognition, 12(11), pp. 657-664, 1991.

[Det00] M. Detyniecki, Mathematical aggregation operators and their application to video querying, PhD thesis, Université de Paris 6, November, 2000.

[DH73] R. Duda and P. Hart, Pattern Recognition and Scene Analysis, John Wiley and Sons, 1973.

[DM93] B. Dubuisson and M-H. Masson, A statistical decision rule with incomplete knowledge about classes, Pattern Recognition, 26(1), pp. 155-165, 1993.

[DP85] D. Dubois and H. Prade, A review of fuzzy sets aggregation connectives, Information Sciences, 36, pp. 85-121, 1985.

[DP88] D. Dubois and H. Prade, Théorie des possibilités – Application à la représentation des connaissances en informatique, Masson, Paris, 1988.

[Dub01] B. Dubuisson, Diagnostic, intelligence artificielle et reconnaissance des formes, Traité IC2 – Information, Commande, Communication, Hermès, Paris, ISBN 2-7462-0249-2, 2001.

[FD92] C. Frélicot and B. Dubuisson, A multi-step predictor of membership function as an ambiguity reject solver in pattern recognition, In: 4th Int. Conf. on Information Processing and Management of Uncertainty in Knowledge-based Systems (IPMU), pp. 709-715, Palma de Mallorca, Spain, July, 1992.

[FM02] C. Frélicot and L. Mascarilla, A third way to design pattern classifiers with reject options, In: 21th Int. Conf. of the North American Fuzzy Information Processing Society (NAFIPS), pp. -, New-Orleans, Louisiana, June 25-27, 2002.

[FMD95] C. Frélicot, M-H. Masson and B. Dubuisson, Reject options in fuzzy pattern classification rules, In: 3rd European Congress on Intelligent Techniques and Soft Computing (EUFIT), volume 3, pp. 1459-1464, Aachen, Germany, June, 1995.

[FR99] G. Fumera and F. Roli, Multiple reject thresholds for improving classification reliability, Technical report, University of Cagliari, pp. 1-13, 1999.

[Fré97] C. Frélicot, Learning rejection thresholds for a class of fuzzy classifiers from possibilistic clustered noisy data, In: 7th Int. Fuzzy Systems Association World Congress (IFSA), volume 3, pp. 111-116, Prague, Czech Republic, June, 1997.

[Fré98a] C. Frélicot, On unifying probabilistic/fuzzy and possibilistic rejection-based classifiers, pp. 736-745, In: Lecture Notes in Computer Science 1451: Advances in Pattern Recognition (Amin A., Dori D., Pudil P., Freeman H., Eds), SpringerVerlag, Berlin, 1998.

[Fré98b] C. Frélicot, A rejection-based possibilistic classifier and its para-meters learning, In : 7th IEEE Int. Conf. on Fuzzy Systems (FUZZ-IEEE), pp. 1423-1428, Anchorage, Alaska, May, 1998.

[FRG00] G. Fumera, F. Roli and G. Giacinto, , Reject options with multiple thresholds, Pattern Recognition, 33(12), pp. 2099-2101, 2000.

[Fuk90] K. Fukunaga, Introduction to Statistical Pattern Recognition, Academic Press, Boston, MA, second edition, 1990.

[Ha96] T-M. Ha, An optimum class-selective rejection rule for pattern recognition, In : 13th Int. Conf. on Pattern Recognition (ICPR), volume 2, pp. 75-80, Vienna, Austria, August 25-30, 1996.

[Ha96] T-M. Ha, The optimum class-selective rejection rule, IEEE Trans. on Pattern Analysis and Machine Intelligence, PAMI-19(6), pp. 608-615, June, 1997.

[JDM00] A.K. Jain, R.P.W. Duin and J. Mao, Statistical pattern recognition: a review, IEEE Trans. on Pattern Analysis and Machine Intelligence, PAMI-22(1), pp. 4-37, January, 2000.

[KK93] R. Krishnapuram and J.M. Keller, A possibilistic approach to clustering, IEEE Trans. on Fuzzy Systems, TFS-1, pp. 98-110, 1993.

[KY95] G.J. Klir and B. Yuan, Fuzzy Sets and Fuzzy Logic: Theory and Applications, Prentice Hall, NJ, USA, 1995.

[MDF96] M-H. Masson, B. Dubuisson and C. Frélicot, Conception de systèmes de diagnostic par reconnaissance des formes floues, Journal Européen des Systèmes Automatisés, 30, pp. 319-341, 1996.

[MF01a] L. Mascarilla and C. Frélicot, A class of reject-first possibilistic classifiers based on dual triples, In: joint 9th Int. Fuzzy Systems Association World Congress (IFSA) and 20th Int. Conf. of the North American Fuzzy Information Processing Society (NAFIPS), pp. 743-747, Vancouver, Canada, July, 2001.

[MF01b] L. Mascarilla and C. Frélicot, Une famille de discriminateurs possibilistes avec rejets fondée sur des triplets de De Morgan, In: 11èmes Rencontres Francophones sur la Logique Floue et ses Applications (LFA), pp. 31-38, Mons, Belgium, Novembre, 2001.

[MYP98] R. Muzzolini, Y-H. Yang and R. Pierson, Classifier design with incomplete knowledge, Pattern Recognition, 31(4), pp. 345-369, 1998.

[Pal91] S.K. Pal, Fuzzy tools in the management of uncertainty in pattern recognition, image analysis, vision and expert systems, International Journal Of Systems Sciences, 22(3), pp. 511-549, 1991.

[PM77] S.K. Pal and D. Majumber, Fuzzy sets and decision making approaches in vowel and speaker recognition, IEEE Trans. on Systems, Man and Cybernetics, SMC-7, pp.625-629, 1977.

[Rus69] E. Ruspini, A New approach to clustering, Information and Control, 8, pp. 338-353, 1969.

[SFM02] D. Semani, C. Frélicot and L. Mascarilla, Discrimination possibiliste avec options de rejet: une nouvelle approche, In: 12èmes Rencontres Francophones sur la Logique Floue et ses Applications (LFA), pp. 27-34, Montpellier, France, Octobre, 2002.

[Smy94] P. Smyth, Markov monitoring with unknown states, IEEE Journal on Selected Areas in Communications, 12(9), pp. 1600-1612, 1994.