MDL-based decision tree pruning
Manish Mehta, J. Rissanen, Rakesh Agrawal · 1995
This paper explores the application of the Minimum Description Length principle for pruning decision trees. We present a new algorithm that intuitively captures the primary goal of reducing the misclassification error. An experimental comparison is presented with three other pruning algorithms. The results show that the MDL pruning algorithm achieves good accuracy, small trees, and fast execution times. Introduction Construction or "induction" of decision trees from examples has been the subject of extensive research in the past [Breiman et. al. 84, Quinlan 86]. It is typically performed in two steps. First, training data is used to grow a decision tree. Then in the second step, called pruning, the tree is reduced to prevent "overfitting". There are two broad classes of pruning algorithms. The first class includes algorithms like cost-complexity pruning [Breiman et. al., 84], that use a separate set of samples for pruning, distinct from the set used to grow the tree. In many cases, ...
Cited by 178 works.
Authors
References
- Classification and Regression Trees.
- Induction of Decision Trees
- Simplifying decision trees
- Stochastic Complexity in Statistical Inquiry
- Inferring decision trees using the minimum description lenght principle
- Universal noiseless coding
- An Empirical Comparison of Pruning Methods for Decision Tree Induction
- Mega induction: a Test Flight
- The performance of universal encoding
- Coding Decision Trees