A Dynamic Programming Based Pruning Method for Decision Trees
Xiao‐Bai Li, James R. Sweigart, James T. C. Teng, Joan M. Donohue, Lori A. Thombs · INFORMS journal on computing · 2001
This paper concerns a decision-tree pruning method, a key issue in the development of decision trees. We propose a new method that applies the classical optimization technique, dynamic programming, to a decision-tree pruning procedure. We show that the proposed method generates a sequence of pruned trees that are optimal with respect to tree size. The dynamic-programming-based pruning (DPP) algorithm is then compared with cost-complexity pruning (CCP) in an experimental study. The results of our study indicate that DPP performs better than CCP in terms of classification accuracy.