THEORY AND PRACTICE OF DECISION TREE INDUCTION

Induction methods have recently been found to be useful in a wide vari ety of business related problems, including in the construction of exp ert systems. Decision tree induction is an important type of inductive learning method. Empirical results have shown that pruning a decision tree sometimes improves its accuracy. In this paper we summarize theo retical results of pruning and illustrate these results with an exampl e. We give a sample size sufficient for decision tree induction with p runing based on recently developed learning theory. For situations whe re it is difficult to obtain a large enough sample, we provide several methods for a posterior evaluation of the accuracy of a pruned decisi on tree. Finally we summarize conditions under which pruning is necess ary for better prediction accuracy.