Information about 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.
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 simple example of pruning.
Introduction
Decision trees are built with the available information and it is support tool in decision making process. Sometimes the given set of data may be irrelevant, erroneous or unnecessary. At that time, the decision tree formed may not be correct and this phenomenon is called overfitting. And also, too much information may misguide our decision policy. In these cases, we may need to remove the nodes from the decision tree. This 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 as1. 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 simple example of pruning.
Further Study
Pessimistic Decision tree pruning based on Tree size [1] MDL based decision tree pruning Decision tree pruning using backpropagation neural networksSee also
References
External Links
- [ http://www.cis.upenn.edu/~mkearns/papers/pruning.pdf] (Optimization Alogrithm)
- [ http://www.math.tau.ac.il/~mansour/ml-course/scribe11.ps] (Introduction to Decision tree pruning)
Mathematics (colloquially, maths or math) is the body of knowledge centered on such concepts as quantity, structure, space, and change, and also the academic discipline that studies them. Benjamin Peirce called it "the science that draws necessary conclusions".
..... Click the link for more information.
..... Click the link for more information.
Informatics includes the science of information, the practice of information processing, and the engineering of information systems. Informatics studies the structure, behavior, and interactions of natural and artificial systems that store, process and communicate information.
..... Click the link for more information.
..... Click the link for more information.
enumeration of a set is either a procedure for listing all members of the set in some definite sequence, or a count of objects of a specified kind. The two kinds of enumeration often, but not always, overlap.
..... Click the link for more information.
..... Click the link for more information.
In operations research, specifically in decision analysis, a decision tree (or tree diagram) is a decision support tool that uses a graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility.
..... Click the link for more information.
..... Click the link for more information.
In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will proceed through a well-defined series of successive states, eventually terminating in an
..... Click the link for more information.
..... Click the link for more information.
In operations research, specifically in decision analysis, a decision tree (or tree diagram) is a decision support tool that uses a graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility.
..... Click the link for more information.
..... Click the link for more information.
Alpha-beta pruning is a search algorithm that reduces the number of nodes that need to be 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 ...).
..... Click the link for more information.
..... Click the link for more information.
In operations research, specifically in decision analysis, a decision tree (or tree diagram) is a decision support tool that uses a graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility.
..... Click the link for more information.
..... Click the link for more information.
An artificial neural network (ANN), often just called a "neural network" (NN), is a mathematical model or computational model based on biological neural networks. It consists of an interconnected group of artificial neurons and processes information using a connectionist approach
..... Click the link for more information.
..... Click the link for more information.
In computer chess programs, the null-move heuristic is a heuristic technique used to enhance the speed of the alpha-beta pruning algorithm.
..... Click the link for more information.
Rationale
Alpha-beta pruning speeds the minimax algorithm by identifying cutoffs..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
