Open AccessAN EXTENSION OF CART'S PRUNING ALGORITHM
Author(s) -
Kim SungHo
Publication year - 1991
Publication title -
ets research report series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.235
H-Index - 5
ISSN - 2330-8516
DOI - 10.1002/j.2333-8504.1991.tb01401.x
Subject(s) - cart , pruning , tree (set theory) , computer science , node (physics) , algorithm , interval tree , incremental decision tree , k ary tree , tree structure , extension (predicate logic) , mathematics , search tree , range (aeronautics) , decision tree , artificial intelligence , decision tree learning , binary tree , search algorithm , combinatorics , agronomy , mechanical engineering , materials science , structural engineering , composite material , biology , programming language , engineering
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 controling 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 extention.