A dynamic programming based pruning method for decision trees
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.
dynamic programming pruning method decision trees classification data mining