FBP : A frontier-based tree-pruning algorithm

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

14 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)494-505
Journal / PublicationINFORMS Journal on Computing
Volume18
Issue number4
Publication statusPublished - Sep 2006
Externally publishedYes

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. © 2006 INFORMS.

Research Area(s)

  • Classification, Data mining, Decision trees, Tree pruning

Citation Format(s)

FBP : A frontier-based tree-pruning algorithm. / Huo, Xiaoming; Kim, Seoung Bum; Tsui, Kwok-Leung; Wang, Shuchun.

In: INFORMS Journal on Computing, Vol. 18, No. 4, 09.2006, p. 494-505.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal