skip to main content skip to footer

An Extension of CART's Pruning Algorithm CART

Kim, Sung Ho
Publication Year:
Report Number:
RR-91-34, PSRTR-91-11
ETS Research Report
Document Type:
Page Count:
Subject/Key Words:
Algorithms, Classification and Regression Trees Software (CART), Data Analysis, Graphical Analysis, Mathematical Logic, Tree Structures (Graphs)


Among the computer-based methods used for the construction of trees such as AID, THAID, CART and FACT, the only one that uses an algorithm that first grows a tree and then prunes the tree is CART. The pruning component of CART is analogous in spirit to the backward elimination approach in regression analysis. This idea provides a tool in controlling the tree sizes to some extent and thus estimating the prediction error by the tree within a certain range of tree size. In the CART pruning process, Breiman, Friedman, Olshen, and Stone (1984) use a linear combination of the expected loss of the decisions by the tree and the total number of the terminal nodes of the tree. In this paper, CART's pruning is extended by considering a function of all the nodes of the tree in addition to the factors involved in the linear combination. For example, if we consider the cost of observing a variable at each node as is the main concern of this paper, or the structural complexity of the tree, we can see such an extension. (29pp.)

Read More