Combinaison Crédibiliste de Classifieurs Binaires

Combinaison Crédibiliste de Classifieurs Binaires

Benjamin Quost Thierry Denœux  Marie-Hélène Masson 

UMR CNRS 6599 Heudiasyc, Université de Technologie de Compiègne BP 20529 - F-60205 Compiègne cedex - France

Université de Picardie Jules Verne, Chemin du Thil 80025 Amiens

9 May 2006
30 April 2007
| Citation



The problem of binary classifier combination is adressed in this article.This approach consists in solving a multi-class classification problem by combining the solutions of binary sub-problems.We consider two strategies in which each class is opposed to each other,or to all others.The combination is considered from the point of view of the theory of evidence.The classifier outputs are interpreted either as conditional belief functions,or as belief functions expressed in a coarser frame.They are combined by computing a belief function that is consistent with the available information.The performances of the methods are compared with those of other techniques and illustrated on various datasets.


Nous étudions dans cet article le problème de la combinaison de classifieurs binaires. Cette approche consiste à résoudre un problème de discrimination multi-classes,en combinant les solutions de sous-problèmes binaires; nous nous intéressons aux stratégies opposant chaque classe à chaque autre, et chaque classe à toutes les autres. La combinaison est considérée ici du point de vue de la théorie de Dempster-Shafer:les sorties des classifieurs sont ainsi interprétées comme des fonctions de croyance, conditionnelles ou exprimées dans un cadre plus grossier que le cadre initial. Elles sont combinées en calculant une fonction de croyance consistante avec les informations disponibles. Les performances des deux approches sont comparées à celles d’autres méthodes et illustrées sur divers jeux de données.


Polychotomous classification,Dempster-Shafer theory,Belief Functions Theory,Classification,Classifier Fusion.

Mots clés 

Classification multi-classes,théorie de Dempster-Shafer,théorie des fonctions de croyance,classification supervisée,fusion de classifieurs.

1. Introduction
2. Combinaison de Classifieurs Binaires
3. Le Modèle des Croyances Transférables (MCT)
4. Combinaison de Classifieurs 1-1 dans le Cadre du MCT
5. Combinaison de Classifieurs 1-T dans le Cadre du MCT
6. Réduction de la Complexité
7. Expériences
8. Conclusion

[1] E. L. ALLWEIN, R. E. SCHAPIRE, and Y. SINGER, Reducing multiclass to binary : a unifying approach for margin classifiers. In Proc. 17th International Conf. on Machine Learning, pages 9-16. Morgan Kaufmann, San Francisco, CA, 2000. 

[2] A. APPRIOU, Approche générique de la gestion de l’incertain dans les processus de fusion multisenseur, Revue Traitement du Signal, 22(4): 307-319, 2005. 

[3] L. BREIMAN, J. H. FRIEDMAN, R. A. OLSHEN, and C. J. STONE, Classification and Regression Trees. Wadsworth International Group, Belmont, CA, 1984. 

[4] T. DENŒUX,A neural network classifier based on Dempster-Shafer theory, IEEE Transactions on Systems, Man and Cybernetics A, 30(2): 131-150, 2000. 

[5] T. DENŒUX and A. B. YAGHLANE, Approximating the combination of belief functions using the fast möbius transform in a coarsened frame, International Journal of Approximate Reasoning, 31(1), 2002. 

[6] T. G. DIETTERICH, Approximate statistical tests for comparing supervised classification learning algorithms, Neural Computation, 10(7): 1895-1923, 1998. 

[7] T. G. DIETTERICHand G. BAKIRI,Solving multiclass learning problems via errorcorrecting output codes. Journal of Artificial Intelligence Research, 2: 263-286, 1995. 

[8] J. FRIEDMAN, Another approach to polychotomous classification. Technical report, Department of Statistics and Stanford Linear Accelerator Center, Stanford University, 1996. 

[9] J. FÜRNKRANZ, Round robin rule learning, In C. E. Brodley and A. P. Danyluk, editors, Proceedings of the 18th International Conference on Machine Learning (ICML-01), pages 146-153, Williamstown, MA, Morgan Kaufmann Publishers, 2001.

[10] T. HASTIE and R. TIBSHIRANI, Classification by pairwise coupling. In M. I. Jordan,M. J. Kearns,and S. A. Solla,editors,Advances in Neural Information Processing Systems, volume 10, The MIT Press, 1998. 

[11] T. HASTIE, R. TIBSHIRANI and J. FRIEDMAN, The Elements of Statistical Learning : Data Mining, Inference and Prediction, Springer Verlag, New York, 2001. 

[12] T.-K. HUANG, R. C. WENG and C.-J. LIN, Generalized BradleyTerry models and multi-class probability estimates. Journal of Machine Learning Research, 7 :85–115, 2006. 

[13] F. JANEZ and A. APPRIOU, Theory of evidence and non-exhaustive frames of discernment : Plausibilities correction methods, International Journal of Approximate Reasoning, 18(1-2): 1-19, 1998.

[14] S. KNERR, L. PERSONNAZ and G. DREYFUS, Single-layer learning revisited : a stepwise procedure for building and training a neural network. In F. Fogelman-Soulie and J. Herault, editors, Neurocomputing: Algorithms, Architectures and Applications – NATO ASI Series, volume F68, Springer Verlag, Berlin, Germany, 1990. 

[15] W. KOONTZ and K. FUKUNAGA. Asymptotic analysis of a nonparametric clustering technique. IEEE Transactions on Computers, C-21(9): 967-974, 1972. 

[16] M. MOREIRA and E. MAYORAZ, Improved pairwise coupling classification with correcting classifiers, In European Conference on Machine Learning, pages 160-171, 1998. 

[17] A. PASSERINI, M. PONTIL, and P. FRASCONI. New results on error correcting output codes of kernel machines. IEEE Transactions on Neural Networks, 15(1): 45-54, 2004. 

[18] J. PLATT, N. CRISTIANINI, and J. SHAWE-TAYLOR, Large margin dags for multiclass classification. In S. Solla, T. Leen, and K.-R. Mueller, editors, Advances in Neural Information Processing Systems 12, pages 547–553, 2000. 

[19] B. QUOST,T. DENŒUX and M. MASSON, Pairwise classifier combination in the framework of belief functions. In Proceedings of FUSION’2005, Philadelphia, PA, July 2005. 

[20] B. QUOST, T. DENŒUX and M. MASSON, One-against-all classifier combination in the framework of belief functions. In Proceedings of IPMU’2006, volume 1, pages 356-363, Paris, 28, July 2006. 

[21] B. SCHÖLKOPF, J. PLATT, J. SHAWE-TAYLOR, A. SMOLA and R. WILLIAMSON, Estimating the support of a high-dimensional distribution, Technical report, Microsoft Research, 1999. 

[22] G. SHAFER, A Mathematical Theory of Evidence, Princeton Univ. Press. Princeton, NJ, 1976. 

[23] P. SMETS and R. KENNES, The transferable belief model, Artificial Intelligence, 66: 191- 234, 1994. 

[24] T.-F. WU, C.-J. LIN and R. C. WENG, Probability estimates for multi-class classi- fication by pairwise coupling, Journal of Machine Learning Research, 5: 975-1005, 2004. 

[25] B. ZADROZNY, Reducing multiclass to binary by coupling probability estimates. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems, volume 14, Cambridge, MA, 2002. MIT Press.