A new pruning method for decision tree based on structural risk of leaf node

Luo, Linkai; Zhang, Xiaodong; Peng, Hong; Lv, Weihang; Zhang, Yan
May 2013
Neural Computing & Applications;May2013 Supplement, Vol. 22, p17
Academic Journal
Pruning is an effective technique in improving the generalization performance of decision tree. However, most of the existing methods are time-consuming or unsuitable for small dataset. In this paper, a new pruning algorithm based on structural risk of leaf node is proposed. The structural risk is measured by the product of the accuracy and the volume (PAV) in leaf node. The comparison experiments with Cost-Complexity Pruning using cross-validation (CCP-CV) algorithm on some benchmark datasets show that PAV pruning largely reduces the time cost of CCP-CV, while the test accuracy of PAV pruning is close to that of CCP-CV.


Related Articles

  • FBP: A Frontier-Based Tree-Pruning Algorithm. Xiaoming Huo; Seoung Bum Kim; Kwok-Leung Tsui; Shuchun Wang // INFORMS Journal on Computing;Fall2006, Vol. 18 Issue 4, p494 

    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 A, it...

  • IMPLEMENTATION OF THE BINARY CODING SCHEME AND THE TREE TRAVERSAL ALGORITHMS TO TEST FOR ANCESTORDESCENDANT RELATIONSHIPS IN K-ARY TREES. Fly, Pervis; Meghanathan, Natarajan; Isokpehi, Raphael // International Journal of Research & Reviews in Applied Sciences;2011, Vol. 8 Issue 3, p386 

    This paper discusses the implementation of the binary coding scheme and its comparison with the post-order, preorder and in-order traversal techniques to test for ancestor-descendant relationships in k-ary trees (a tree in which any leaf node has up to k children). The approach used is assigning...

  • Influence Diagram Retrospective. Howard, Ronald A.; Matheson, James E. // Decision Analysis;Sep2005, Vol. 2 Issue 3, p144 

    Since the invention of Influence diagrams in the mid-1970s, they have become a ubiquitous tool for representing uncertain situations. This single diagram replaced awkward manipulations of decision trees and nature's trees with a single representation that displays both the sequential and...

  • Algorithms for the optimum communication spanning tree problem. Sharma, Prabha // Annals of Operations Research;Mar2006, Vol. 143 Issue 1, p203 

    Optimum Communication Spanning Tree Problem is a special case of the Network Design Problem. In this problem given a graph, a set of requirements r ij and a set of distances d ij for all pair of nodes ( i, j), the cost of communication for a pair of nodes ( i, j), with respect to a spanning...

  • Dimensions of Tight Spans. Develin, Mike // Annals of Combinatorics;2006, Vol. 10 Issue 1, p53 

    Given a finite metric, one can construct its tight span, a geometric object representing the metric. The dimension of a tight span encodes, among other things, the size of the space of explanatory trees for that metric; for instance, if the metric is a tree metric, the dimension of the tight...

  • Accumulation Phylogenies. Baroni, Mihaela; Steel, Mike // Annals of Combinatorics;2006, Vol. 10 Issue 1, p19 

    Directed acyclic graphs provide a convenient representation of reticulate evolution in systematic biology. In this paper we formalize and analyse a simple model in which evolved characteristics are passed on to all descendant species. We show that the resulting observed sets of characteristics...

  • Self-similar fragmentations derived from the stable tree I. Miermont, Gr�gory // Probability Theory & Related Fields;2003, Vol. 127 Issue 3, p423 

    The basic object we consider is a certain model of continuum random tree, called the stable tree. We construct a fragmentation process (F[sup -](t),t=0) out of this tree by removing the vertices located under height t. Thanks to a self-similarity property of the stable tree, we show that the...

  • A Formula About Tree. Ayache, Ahmed; Sharif, Walied H.; Vu Dinh Hoa // Vietnam Journal of Mathematics;Sep2005, Vol. 33 Issue 3, p343 

    Let G be a tree. It is proved that for any vertex v of G ∣V∣ + ∑q∊V [d(q) - 2]l(v,q) = 1 in which d(q) is the degree of the vertex q, and l(v, q) is the distance between v and q in G. This result enable us to derive a formula concerning the average distance for some...

  • The Mean and Variance of the Numbers of r-Pronged Nodes and r-Caterpillars in Yule-Generated Genealogical Trees. Rosenberg, Noah A. // Annals of Combinatorics;2006, Vol. 10 Issue 1, p129 

    The Yule model is a frequently-used evolutionary model that can be utilized to generate random genealogical trees. Under this model, using a backwards counting method differing from the approach previously employed by Heard ( Evolution 46: 1818–1826), for a genealogical tree of n...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics