Paper Info
Title
An efficient algorithm for optimal pruning of decision trees
Abstract
Pruning decision trees is a useful technique for improving the generalization performance in decision tree induction, acid for trading accuracy for simplicity in other applications. In this paper, a new algorithm called OPT-2 for optimal pruning of decision trees is introduced. The algorithm is based on dynamic programming. In its most basic form, the time and space complexities of OPT-2 are both Theta(nC), where n is the number of test nodes in the initial decision tree, and C is the number of leaves in the target (pruned) decision tree. This is an improvement over the recently published OPT algorithm of Bohanec and Bratko (which is the only known algorithm for optimal decision tree pruning) especially in the case of heavy pruning and when the tests of the given decision tree have many outcomes. If so desired, the space required by OPT-2 can further be reduced by a factor of r at the cost of increasing the execution time by a factor that is bounded above by (r + 1)/2 (this is a considerable overestimate, however). From a practical point of view, OPT-2 enjoys considerable flexibility in various aspects, and is easy to implement.
Year
DOI
Venue
1996
10.1016/0004-3702(95)00060-7
Artif. Intell.
Keywords
Field
DocType
optimal pruning,decision tree,efficient algorithm,space complexity
Decision tree,Killer heuristic,Artificial intelligence,ID3 algorithm,Decision stump,Mathematical optimization,Principal variation search,Algorithm,Pruning (decision trees),Machine learning,Decision tree learning,Mathematics,Incremental decision tree
Journal
Volume
Issue
ISSN
83
2
0004-3702
Citations 
PageRank 
References 
18
1.15
5
Authors
1
Name
Order
Citations
PageRank
Hussein Almuallim1547138.58