Pruning (algorithm)

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. Pruning reduces the complexity of the final classifier, and hence improves predictive accuracy by the reduction of overfitting.

One of the questions that arises in a decision tree algorithm is the optimal size of the final tree. A tree that is too large risks overfitting the training data and poorly generalizing to new samples. A small tree might not capture important structural information about the sample space. However, it is hard to tell when a tree algorithm should stop because it is impossible to tell if the addition of a single extra node will dramatically decrease error. This problem is known as the horizon effect. A common strategy is to grow the tree until each node contains a small number of instances then use pruning to remove nodes that do not provide additional information.

Pruning should reduce the size of a learning tree without reducing predictive accuracy as measured by a cross-validation set. There are many techniques for tree pruning that differ in the measurement that is used to optimize performance.

Pruning can occur in a top down or bottom up fashion. A top down pruning will traverse nodes and trim subtrees starting at the root, while a bottom up pruning will start at the leaf nodes. Below are several popular pruning algorithms.

One of the simplest forms of pruning is reduced error pruning. Starting at the leaves, each node is replaced with its most popular class. If the prediction accuracy is not affected then the change is kept. While somewhat naive, reduced error pruning has the advantage of simplicity and speed.

Cost complexity pruning generates a series of trees ${\displaystyle T_{0}\dots T_{m}}$ where ${\displaystyle T_{0}}$ is the initial tree and ${\displaystyle T_{m}}$ is the root alone. At step ${\displaystyle i}$, the tree is created by removing a subtree from tree ${\displaystyle i-1}$ and replacing it with a leaf node with value chosen as in the tree building algorithm. The subtree that is removed is chosen as follows. Define the error rate of tree ${\displaystyle T}$ over data set ${\displaystyle S}$ as ${\displaystyle \operatorname {err} (T,S)}$. The subtree that minimizes ${\displaystyle {\frac {\operatorname {err} (\operatorname {prune} (T,t),S)-\operatorname {err} (T,S)}{\left\vert \operatorname {leaves} (T)\right\vert -\left\vert \operatorname {leaves} (\operatorname {prune} (T,t))\right\vert }}}$ is chosen for removal. The function ${\displaystyle \operatorname {prune} (T,t)}$ defines the tree gotten by pruning the subtrees ${\displaystyle t}$ from the tree ${\displaystyle T}$. Once the series of trees has been created, the best tree is chosen by generalized accuracy as measured by a training set or cross-validation.

...
Wikipedia