# Pruning (algorithm)

Pruning (algorithm)

Pruning is a term in mathematics and informatics which describes a method of enumeration, which allows to cut parts of a decision tree. Pruned parts of the tree are no longer considered because the algorithm knows based on already collected data (e.g. through sampling) that these subtrees do not contain the searched object. The decision tree is simplified by removing some decisions.

Introduction

Decision trees are built with the available information and they are supporting tools in a decision making process. However, sometimes the given set of data may be irrelevant, erroneous or unnecessary, in which case the decision tree formed may not be correct; this phenomenon is called overfitting. Also, too much information may misguide the decision policy. When this happens, it becomes necessary to remove the nodes from the decision tree. The process of making the decision tree smaller by removing nodes that are not helpful is called Pruning.

Illustration

Pruning is carried out as a step by step process. In general, it is performed as

1. Remove the interior node in the tree, a non-leaf node. 2. Evaluate the performance without the pruned part. 3. Repeat until no improvement is obtained from pruning 4. Retain the best performed tree as the decision tree.

Consider the decision tree as given below,

When a decision process is related to the selection of a flower, then the branch with the shape is irrelevant and not related to the flower branch. Hence that particular branch can be pruned to improve performance.

The above illustration is a simple example of pruning.

Further Study

Pessimistic Decision tree pruning based on Tree size [" [http://citeseer.ist.psu.edu/76752.html] "] MDL based decision tree pruningDecision tree pruning using backpropagation neural networks

* Alpha-beta pruning
* Decision tree
* Artificial neural network
* Null-move heuristic

References

* [ http://www.cis.upenn.edu/~mkearns/papers/pruning.pdf] (Optimization Algorithm)
* [ http://www.math.tau.ac.il/~mansour/ml-course/scribe11.ps] (Introduction to Decision tree pruning)

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Pruning (decision trees) — Pruning is a technique in machine learning that reduces the size of decision trees by removing sections of the tree that provide little power to classify instances. The dual goal of pruning is reduced complexity of the final classifier as well as …   Wikipedia

• Pruning (disambiguation) — Pruning is the practice of removing unwanted portions from a plant, but may also refer to: * Synaptic pruning, the reformation of neural structure by pruning excess neurons or neural clusters * Pruning (algorithm), a method of simplification of a …   Wikipedia

• Pruning (morphology) — The pruning algorithm is a technique used for digital image processing based on mathematical morphology. It is used as a complement to the skeleton and thinning algorithms to remove unwanted parasitic components.The process in itself will remove… …   Wikipedia

• Alpha-beta pruning — is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two player games (Tic tac toe, Chess, Go …   Wikipedia

• Search algorithm — In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer… …   Wikipedia

• Dijkstra's algorithm — Not to be confused with Dykstra s projection algorithm. Dijkstra s algorithm Dijkstra s algorithm runtime Class Search algorithm Data structure Graph Worst case performance …   Wikipedia

• Prim's algorithm — Graph and tree search algorithms Alpha beta pruning A* B* Beam Bellman–Ford algorithm Best first Bidirectional …   Wikipedia

• GSP Algorithm — ( Generalized Sequential Pattern algorithm) is an algorithm used for sequence mining. The algorithms for solving sequence mining problems are mostly based on the a priori (level wise) algorithm. One way to use the level wise paradigm is to first… …   Wikipedia

• C4.5 algorithm — C4.5 is an algorithm used to generate a decision tree developed by Ross Quinlan. C4.5 is an extension of Quinlan s earlier ID3 algorithm. The decision trees generated by C4.5 can be used for classification, and for this reason, C4.5 is often… …   Wikipedia

• alpha-beta pruning — noun An algorithm for pruning a search tree by eliminating any branch that is demonstrably inferior to a branch previously encountered …   Wiktionary