FBP: A frontier-based tree-pruning algorithm

FBP: A frontier-based tree-pruning algorithm

0.00 Avg rating0 Votes
Article ID: iaor200924649
Country: United States
Volume: 18
Issue: 4
Start Page Number: 494
End Page Number: 505
Publication Date: Oct 2006
Journal: INFORMS Journal On Computing
Authors: , , ,
Keywords: networks: path
Abstract:

A frontier–based tree–pruning algorithm (FBP) is proposed. The new method has an order of computational complexity comparable to cost–complexity pruning (CCP). Regarding tree pruning, it provides a full spectrum of information: namely, (1) given the value of the penalization parameter λ, it gives the decision tree specified by the complexity–penalization approach; (2) given the size of a decision tree, it provides the range of the penalization parameter λ, within which the complexity–penalization approach renders this tree size; (3) it finds the tree sizes that are inadmissible—no matter what the value of the penalty parameter is, the resulting tree based on a complexity–penalization framework will never have these sizes. Simulations on real data sets reveal a ‘surprise’: in the complexity–penalization approach, most of the tree sizes are inadmissible. FBP facilitates a more faithful implementation of cross validation (CV), which is favored by simulations. Using FBP, a stability analysis of CV is proposed.

Reviews

Required fields are marked *. Your email address will not be published.