Pruning Method of Belief Decision Trees

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.

Authors:

• Salsabil Trabelsi
• Zied Elouedi
• Khaled Mellouli

Keywords:

• machine learning
• uncertainty
• belief function theory
• belief decision tree
• pruning.

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.