An iterative growing and pruning algorithm for classification tree design

Abstract

A critical issue in classification tree design is obtaining right-sized trees, i.e., trees which neither underfit nor overfit the data. Instead of using stopping rules to halt partitioning, we follow the approach of growing a large tree with pure terminal nodes and selectively pruning it back. A new efficient iterative method is proposed to grow and prune classification trees. This method divides the data sample into two subsets and iteratively grows a tree with one subset and prunes it with the other subset, successively interchanging the roles of the two subsets. The convergence and other properties of the algorithm are established. Theoretical and practical considerations suggest that the iterative tree growing and pruning algorithm should perform better and require less computation than other widely used tree growing and pruning algorithms. Numerical results on a waveform recognition problem are presented to support this view.