FBP: A frontier-based tree-pruning algorithm

Xiaoming Huo, Seoung Bum Kim, Kwok Leung Tsui, Shuchun Wang

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)494-505
Number of pages12
JournalINFORMS Journal on Computing
Issue number4
Publication statusPublished - 2006 Sept
Externally publishedYes


  • Classification
  • Data mining
  • Decision trees
  • Tree pruning

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'FBP: A frontier-based tree-pruning algorithm'. Together they form a unique fingerprint.

Cite this