Pruning Method of Belief Decision Trees

Authors: Salsabil Trabelsi, Zied Elouedi, Khaled Mellouli

Abstract:

The belief decision tree (BDT) approach is a decision tree in an uncertain environment where the uncertainty is represented through the Transferable Belief Model (TBM), one interpretation of the belief function theory. The uncertainty can appear either in the actual class of training objects or attribute values of objects to classify. In this paper, we develop a post-pruning method of belief decision trees in order to reduce size and improve classification accuracy on unseen cases. The pruning of decision tree has a considerable intention in the areas of machine learning.

Keywords: machine learning, uncertainty, belief function theory, belief decision tree, pruning.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330211

References:

[1] Breiman, L., Friedman, J. H., Olshen, R. A., Stone, C. J.: Classification and Regression Trees. Wadsworth, Belmont, CA(1984).
[2] Denoeux, T., Skarstien-Bajanger, M.: Induction of decision trees for partially classified data. In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. Nashiville, USA (2000) 2923-2928.
[3] Elouedi, Z., Mellouli, K., Smets, P.: Decision trees using the belief function theory. In Proceedings of the international conference on Information Processing and Management of Uncertainty IPMU-2000, Vol.1, Madrid, Spain(2000)141-148
[4] Elouedi, Z., Mellouli, K., Smets, P.: Belief decision trees: Theoretical foundations. In International Journal of Approximate Journal IJAR, Vol.28(2-3), (2001) 91-124.
[5] Elouedi, Z., Mellouli, K., Smets, P.: A Pre-Pruning Method in Belief Decision Trees. The Ninth International conference on Information Processing and Management of uncertainty in knowledge-Based Systems IPMU 2002, Vol.1, Annecy, France(2002) 579-586.
[6] H¨ullermeier, E. : Possibilistic Induction in decision tree learning. In Proceedings of the 13 Th European Conference on Machine Learning. ECML2002. Helsinki (2002), Finland (2002) 173-184.
[7] Jenhani, I. Elouedi, Z. Ben Amor, N. & Mellouli, K.:Qualitative inference in possibilistic option decision trees. In Proceedings of the Eight European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty.(2005)
[8] Mingers, J.: Expert systems - rule induction with statistical data. Journal of the operational research society. Vol 38.(1987) 39-47.
[9] Niblett, T. Bratko, I.: Learning decision rules in noisy domains. Proc. Expert Systems 86, Cambridge: Cambridge University Press.(1986)
[10] Quinlan, J.R.: Simplifying decision trees. International Journal of Man-Machine studies, (1987) 221-234.
[11] Quinlan, J.R.: Probabilistic decision tree. In R.S. Michalski, J.G. Carbonell, & T.M Michell (Eds.), Machine Learning, Vol.3, Chap. 5, Morgan Kaufmann(1990) 267-301).
[12] Quinlan, J.R.: C4.5: Programs for Machine learning. Morgan Kaufman, San Mateo, California (1993).
[13] Shafer, G.: A mathematical theory of evidence. Princeton University Press. Princeton, NJ(1976).
[14] Smets, P.: Belief functions. In P. Smets, E. H. Mamdani, D. Dubois, H. Prade (Eds.): Non standard logics for automated reasoning. Academic Press, London (1988) 253-286.
[15] Smets, P., & Kennes, R.: The transferable belief model. Artificial Intelligence,Vol 66,(1994) 191-236.
[16] Smets, P.: The application of belief transferable belief model to diagnostic problems. International Journal of Intelligent Systems, Vol.13, (1998) 127-157.
[17] Zeidler, J.,& Schlosser, M.: Continuous valued attributes in fuzzy decision trees. In Procedings of the sixth International Conference on Information Processing and Management of Uncertainty , Vol.1,. Granada, Spain(1996) 395-400.