AN INVESTIGATION ON THE CONDITIONS OF PRUNING AN INDUCED DECISION TREE

Empirical studies have shown that pruning a decision tree can increase the accuracy of a learned concept. A recent result identified conditi ons under which pruning techniques increase prediction accuracy. Howev er, this result is based on samples of size three. This paper provides a generalization of previous results and investigates conditions wher e pruning is beneficial for concept accuracy as well as concept simpli fication. We show that pruning is theoretically useful in many situati ons.