The effects of pruning methods on the predictive accuracy of induced decision trees

DOI10.1002/(SICI)1526-4025(199910/12)15:4%3C277::AID-ASMB393%3E3.0.CO;2-BMaRDI QIDQ2711697zbMATH OpenWikidataFDO

Authors Floriana Esposito, Donato Malerba, Giovanni Semeraro, Valentina Tamma

Publication date 25 April 2001

Published in Applied Stochastic Models in Business and Industry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/(SICI)1526-4025(199910/12)15:4%3C277::AID-ASMB393%3E3.0.CO;2-B

zbMATH Keywords

cross- validation studydecision tree pruninginduction of decision treesstate space

Mathematics Subject Classification ID

Trees (05C05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Empirical decision procedures; empirical Bayes procedures (62C12) Inference from stochastic processes and prediction (62M20) Graph theory (including graph drawing) in computer science (68R10)

Review text

Various heuristic methods have been proposed for the construction of a decision tree, among which the most widely known is the top-down approach. In top-down induction of decision trees it is possible to identify three tasks: (1) the assignment of each leaf with a class; (2) the selection of the splits according to a selection measure; (3) the decision when to declare a node terminal or to continue splitting it. Methods that control the growth of a decision tree during its construction are called pre-pruning methods, while the others are called post-pruning methods. NEWLINENEWLINENEWLINEMany post-pruning (or simply pruning) methods have been proposed in the literature, some of which are: reduced error pruning, minimum error pruning, pessimistic error pruning, critical value pruning, cost-complexity pruning, and error-based pruning. A previous comparative study has already pointed out both their similarities and their differences and investigated the real effect of some of these methods on both the predictive accuracy and the size of the induced tree. In that study, optimally pruned trees have been used to evaluate the maximum improvement produced by an ideal pruning algorithm. NEWLINENEWLINENEWLINEThe main purpose of this paper is that of providing a further comparison of these pruning methods. This article presents a unifying framework according to which any pruning method can be defined as a four-tuple (space, operators, evaluation function, search strategy), and the pruning process can be cast as an optimization problem. A new empirical analysis of the effect of post-pruning on both the predictive accuracy and the size od induced decision trees is reported. The experimental comparison of the pruning methods involves 14 data sets and is based on the cross-validation procedure. The results confirm most of the conclusions drawn in a previous comparison based on the holdout procedure.

Recommendations

• A comparison of pruning criteria for probability trees
• PAC-learning a decision tree with pruning
• Post-pruning in decision tree induction using multiple performance measures
• Trading accuracy for simplicity in decision trees

Cites work

• An efficient estimator of pattern recognition system error probability
• Asymptotics for and against cross-validation
• Bibliography on estimation of misclassification
• Bootstrap methods: another look at the jackknife
• Bootstrap Techniques for Error Estimation
• Coding decision trees
• scientific article; zbMATH DE number 3860199 (Why is no real title available?)
• scientific article; zbMATH DE number 3551724 (Why is no real title available?)
• Inferring decision trees using the minimum description length principle
• Occam's razor
• Statistical Properties of Error Estimators in Performance Assessment of Recognition Systems

Cited in

(21)

• Averaging over decision trees
• PAC-learning a decision tree with pruning
• Trading accuracy for simplicity in decision trees
• An investigation on the conditions of pruning an induced decision tree
• PUBLIC: A decision tree classifier that integrates building and pruning
• A comparison of pruning criteria for probability trees
• Embedding and extraction of knowledge in tree ensemble classifiers
• scientific article; zbMATH DE number 1700379 (Why is no real title available?)
• A dynamic programming based pruning method for decision trees
• scientific article; zbMATH DE number 5158877
• scientific article; zbMATH DE number 67806 (Why is no real title available?)
• scientific article; zbMATH DE number 1753147 (Why is no real title available?)
• 10.1162/jmlr.2003.3.4-5.621
• Analysis of a complexity-based pruning scheme for classification trees
• scientific article; zbMATH DE number 2101258 (Why is no real title available?)
• scientific article; zbMATH DE number 2101262 (Why is no real title available?)
• scientific article; zbMATH DE number 2219698 (Why is no real title available?)
• The difficulty of reduced error pruning of leveled branching programs
• Defective products management in a furniture production company: a data mining approach
• Post-pruning in decision tree induction using multiple performance measures
• Maximum a posteriori pruning on decision trees and its application to bootstrap bumping

This page was built for publication: The effects of pruning methods on the predictive accuracy of induced decision trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2711697)