×

The combination of multiple classifiers using an evidential reasoning approach. (English) Zbl 1184.68385

Summary: In many domains when we have several competing classifiers available we want to synthesize them or some of them to get a more accurate classifier by a combination function. In this paper we propose a ‘class-indifferent’ method for combining classifier decisions represented by evidential structures called triplet and quartet, using Dempster’s rule of combination. This method is unique in that it distinguishes important elements from the trivial ones in representing classifier decisions, makes use of more information than others in calculating the support for class labels and provides a practical way to apply the theoretically appealing Dempster-Shafer theory of evidence to the problem of ensemble learning. We present a formalism for modelling classifier decisions as triplet mass functions and we establish a range of formulae for combining these mass functions in order to arrive at a consensus decision. In addition we carry out a comparative study with the alternatives of simplet and dichotomous structure and also compare two combination methods, Dempster’s rule and majority voting, over the UCI benchmark data, to demonstrate the advantage our approach offers.

MSC:

68T05 Learning and adaptive systems in artificial intelligence

Software:

UCI-ml
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Al-Ani, A.; Deriche, M., A new technique for combining multiple classifiers using the Dempster-Shafer theory of evidence, J. Artif. Intell. Res., 17, 333-361 (2002) · Zbl 1045.68114
[2] J.A. Barnett, Computational methods for a mathematical theory of evidence, in: Proc. of 17th Joint Conference of Artificial Intelligence, 1981, pp. 868-875; J.A. Barnett, Computational methods for a mathematical theory of evidence, in: Proc. of 17th Joint Conference of Artificial Intelligence, 1981, pp. 868-875
[3] C.L. Blake, C.J.E. Keogh, UCI repository of machine learning databases, http://www.ics.uci.edu/mlearn/MLRepository.html; C.L. Blake, C.J.E. Keogh, UCI repository of machine learning databases, http://www.ics.uci.edu/mlearn/MLRepository.html
[4] Y. Bi, D. Bell, J.W. Guan, Combining evidence from classifiers in text categorization, in: Proc. of KES04, 2004, pp. 521-528; Y. Bi, D. Bell, J.W. Guan, Combining evidence from classifiers in text categorization, in: Proc. of KES04, 2004, pp. 521-528
[5] Y. Bi, Combining multiple classifiers for text categorization using the Dempster-Shafer theory of evidence, PhD thesis, University of Ulster, UK, 2004; Y. Bi, Combining multiple classifiers for text categorization using the Dempster-Shafer theory of evidence, PhD thesis, University of Ulster, UK, 2004
[6] Bell, D.; Guan, J. W.; Bi, Y., On combining classifiers mass functions for text categorization, IEEE Trans. Knowledge Data Engrg., 17, 10, 1307-1319 (2005)
[7] Y. Bi, J.W. Guan, An efficient triplet-based algorithm for evidential reasoning, in: Proc. of the 22nd Conference on Uncertainty in Artificial Intelligence, 2006, pp. 31-38; Y. Bi, J.W. Guan, An efficient triplet-based algorithm for evidential reasoning, in: Proc. of the 22nd Conference on Uncertainty in Artificial Intelligence, 2006, pp. 31-38
[8] Y. Bi, S.I. McClean, T. Anderson, On combining multiple classifiers using an evidential approach, in: Proc. of the Twenty-First National Conference on Artificial Intelligence (AAAI’06), 2006, pp. 324-329; Y. Bi, S.I. McClean, T. Anderson, On combining multiple classifiers using an evidential approach, in: Proc. of the Twenty-First National Conference on Artificial Intelligence (AAAI’06), 2006, pp. 324-329
[9] Breiman, L., Bagging predictors, Machine Learning, 24, 2, 123-140 (1996) · Zbl 0858.68080
[10] Dietterich, T., Machine learning research: Four current directions, AI Magazine, 18, 4, 97-136 (1997)
[11] Dietterich, T., An experimental comparison of three methods for constructing ensembles of decision trees: Bagging, boosting, and randomization, Machine Learning, 1, 22 (1998)
[12] T. Dietterich, Ensemble methods in machine learning, in: Proc. 2nd Int. Workshop on Multiple Classifier Systems MCS2000, LNCS, vol. 1857, 2000, pp. 1-15; T. Dietterich, Ensemble methods in machine learning, in: Proc. 2nd Int. Workshop on Multiple Classifier Systems MCS2000, LNCS, vol. 1857, 2000, pp. 1-15
[13] Dempster, A. P., Upper and lower probabilities induced by a multivalued mapping, Ann. Math. Stat., 38, 325-339 (1967) · Zbl 0168.17501
[14] Denoeux, T., Conjunctive and disjunctive combination of belief functions induced by nondistinct bodies of evidence, Artif. Intell., 172, 2-3, 234-264 (2008) · Zbl 1182.68298
[15] Denoeux, T.; Ben Yaghlane, A., Approximating the combination of belief functions using the fast Moebius transform in a coarsened frame, Internat. J. Approx. Reason., 31, 1-2, 77-101 (2002) · Zbl 1033.68114
[16] Denoeux, T., A neural network classifier based on Dempster-Shafer theory, IEEE Trans. Systems Man Cybernet. A, 30, 2, 131-150 (2000)
[17] Denoeux, T., A \(k\)-nearest neighbor classification rule based on Dempster-Shafer theory, IEEE Trans. Systems Man Cybern., 25, 5, 804-813 (1995)
[18] R.P.W. Duin, D.M.J. Tax, Experiments with classifier combining rules, in: J. Kittler, F. Roli (Eds.), Multiple Classifier Systems, 2000, pp. 16-29; R.P.W. Duin, D.M.J. Tax, Experiments with classifier combining rules, in: J. Kittler, F. Roli (Eds.), Multiple Classifier Systems, 2000, pp. 16-29
[19] Dzeroski, S.; Zenko, B., Is combining classifiers with stacking better than selecting the best one?, Machine Learning, 54, 3, 255-273 (2004) · Zbl 1101.68077
[20] Fleiss, J. L.; Cuzick, J., The reliability of dichotomous judgments: unequal numbers of judgments per subject, Appl. Psycholog. Meas., 3, 537-542 (1979)
[21] Y. Freund, R. Schapire, Experiments with a new boosting algorithm, in: Machine Learning: Proceedings of the Thirteenth International Conference, 1996, pp. 148-156; Y. Freund, R. Schapire, Experiments with a new boosting algorithm, in: Machine Learning: Proceedings of the Thirteenth International Conference, 1996, pp. 148-156
[22] Guan, J. W.; Bell, D. A., Evidence Theory and Its Applications, vols. 1-2, Studies in Computer Science and Artificial Intelligence, vols. 7-8 (1992), Elsevier, North-Holland · Zbl 0791.68134
[23] J.W. Guan, D.A. Bell, Efficient algorithms for automated reasoning in expert systems, in: The 3rd IASTED International Conference on Robotics and Manufacturing, 1995, pp. 336-339; J.W. Guan, D.A. Bell, Efficient algorithms for automated reasoning in expert systems, in: The 3rd IASTED International Conference on Robotics and Manufacturing, 1995, pp. 336-339
[24] Haenni, R., Are alternatives to Dempster’s rule of combination real alternatives?: Comments on “about the belief function combination and the conflict management problem” Lefèvre et al., Information Fusion, 3, 3, 237-239 (2002)
[25] Hansen, L. K.; Salamon, P., Neural network ensembles, IEEE Trans. Pattern Anal. Machine Intell., 12, 10, 993-1001 (1990)
[26] Ho, T. K., The random subspace method for constructing decision forests, IEEE Trans. Pattern Anal. Machine Intell., 20, 8, 832-844 (1998)
[27] Kittler, J.; Hatef, M.; Duin, R. P.W.; Matas, J., On combining classifiers, IEEE Trans. Pattern Anal. Machine Intell., 20, 3, 226-239 (1998)
[28] L. Kuncheva, Combining classifiers: Soft computing solutions, in: S.K. Pal, A. Pal (Eds.), Pattern Recognition: From Classical to Modern Approaches, 2001, pp. 427-451; L. Kuncheva, Combining classifiers: Soft computing solutions, in: S.K. Pal, A. Pal (Eds.), Pattern Recognition: From Classical to Modern Approaches, 2001, pp. 427-451
[29] Kuncheva, L.; Whitaker, C. J., Measures of diversity in classifier ensembles, Machine Learning, 51, 181-207 (2003) · Zbl 1027.68113
[30] Jain, A. K.; Duin, R. P.W.; Mao, J., Statistical pattern recognition: A review, IEEE Trans. Pattern Anal. Machine Intell., 22, 1, 4-37 (2000)
[31] Lam, L.; Suen, C. Y., Application of majority voting to pattern recognition: An analysis of its behavior and performance, IEEE Trans. Systems Man Cybernet., 27, 5, 553-568 (1997)
[32] L.S. Larkey, W.B. Croft, Combining classifiers in text categorization, in: Proceedings of SIGIR-96, 19th ACM International Conference on Research and Development in Information Retrieval, 1996, pp. 289-297; L.S. Larkey, W.B. Croft, Combining classifiers in text categorization, in: Proceedings of SIGIR-96, 19th ACM International Conference on Research and Development in Information Retrieval, 1996, pp. 289-297
[33] Liu, W.; Hong, J., Reinvestigating Dempster’s idea on evidence combination, Knowledge Inform. Syst., 2, 2, 223-241 (2000) · Zbl 1002.68606
[34] Liu, W., Analyzing the degree of conflict among belief functions, Artif. Intell., 170, 11, 909-924 (2006) · Zbl 1131.68539
[35] Mandler, E. J.; Schurmann, J., Combining the classification results of independent classifiers based on Dempster-Shafer theory of evidence, Pattern Recogn. Artif. Intell., X, 381-393 (1988)
[36] P. Melville, R.J. Mooney, Constructing diverse classifier ensembles using artificial training examples, in: Proc. of IJCAI-03, 2003, pp. 505-510; P. Melville, R.J. Mooney, Constructing diverse classifier ensembles using artificial training examples, in: Proc. of IJCAI-03, 2003, pp. 505-510
[37] Mitchell, T., Machine Learning (1997), McGraw Hill · Zbl 0913.68167
[38] Opitz, D., Feature selection for ensembles, (Proc. of AAAI-99 (1999), AAAI Press), 379-384
[39] Quost, B.; Denoeux, T.; Masson, M.-H., Pairwise classifier combination using belief functions, Pattern Recogn. Lett., 28, 5, 644-653 (2007)
[40] Sebastiani, F., Machine learning in automated text categorization, ACM Comput. Surv., 34, 1, 1-47 (2002)
[41] Rogova, G., Combining the results of several neural network classifiers, Neural Networks, 7, 5, 777-781 (1994)
[42] Shafer, G.; Logan, R., Implementing Dempster’s rule for hierarchical evidence, Artif. Intell., 33, 3, 271-298 (1987) · Zbl 0633.68093
[43] Shafer, G., Belief functions and possibility measures, (Bezdek, J. C., The Analysis of Fuzzy Information, vol. 1: Mathematics and Logic (1987), CRC Press), 51-84
[44] Shafer, G., A Mathematical Theory of Evidence (1976), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0359.62002
[45] Ph. Smets, The combination of evidence in the Transferable Belief Model, IEEE Trans. Pattern Anal. Machine Intell. 12 (5) 447-458; Ph. Smets, The combination of evidence in the Transferable Belief Model, IEEE Trans. Pattern Anal. Machine Intell. 12 (5) 447-458
[46] Ting, K. M.; Witten, I. H., Issues in stacked generalization, J. Artif. Intell. Res. (JAIR), 10, 271-289 (1999) · Zbl 0915.68075
[47] Tax, D. M.J.; van Breukelen, M.; Duin, R. P.W.; Kittler, J., Combining multiple classifiers by averaging or by multiplying, Pattern Recognition, 33, 9, 1475-1485 (2000)
[48] Tumer, K.; Robust, G. J., Combining of disparate classifiers through order statistics, Pattern Anal. Appl., 6, 1, 41-46 (2002)
[49] Xu, L.; Krzyzak, A.; Suen, C. Y., Several methods for combining multiple classifiers and their applications in handwritten character recognition, IEEE Trans. System Man Cybernet., 2, 3, 418-435 (1992)
[50] Zouhal, L. M.; Denoeux, T., An evidence-theoretic \(k\)-NN rule with parameter optimization, IEEE Trans. Systems Man Cybernet. C, 28, 2, 263-271 (1998)
[51] Y. Yang, T. Ault, T. Pierce, Combining multiple learning strategies for effective cross validation, in: Proc. of ICML’00, 2000, pp. 1167-1182; Y. Yang, T. Ault, T. Pierce, Combining multiple learning strategies for effective cross validation, in: Proc. of ICML’00, 2000, pp. 1167-1182
[52] Voorbraak, F., On the justification of Dempster’s rule of combination, Artif. Intell., 48, 2, 171-197 (1991) · Zbl 1117.68496
[53] Webb, G. I., MultiBoosting: A technique for combining boosting and wagging, Machine Learning, 40, 2, 159-196 (2000)
[54] Wolpert, D., Stacked generalization, Neural Networks, 5, 2, 241-259 (1992)
[55] Witten, I. H.; Frank, E., Data Mining: Practical Machine Learning Tools and Techniques (2005), Morgan Kaufmann: Morgan Kaufmann San Francisco · Zbl 1076.68555
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.