Theory and practice of decision tree induction

Induction methods have recently been found to be useful in a wide variety of business related problems, including in the construction of expert 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. This paper summarizes theoretical results of pruning and illustrates these results with an example. It gives a sample size sufficient for decision tree induction with pruning based on recently developed learning theory. For situations where it is difficult to obtain a large enough sample, the paper provides several methods for a posterior evaluation of the accuracy of a pruned decision tree. Finally, it summarizes conditions under which purning is necessary for better prediction accuracy.