Tree Pruning in Data Mining

A decision tree that's allowed to grow without limit will keep splitting until every leaf is perfectly pure — often down to a single training record per leaf — which drives training accuracy to 100% while doing nothing to guarantee the tree still works on data it hasn't seen. Tree pruning is the set of techniques for deliberately keeping a tree smaller than the one that fits the training data most exactly, because the most exact fit and the most generalizable one are rarely the same tree. This is the same overfitting risk covered with a hand-verified cross-validation example in the lesson on major issues in data mining, applied specifically to the mechanics of trees.

Two Strategies, Applied at Two Different Times

Pre-pruning (early stopping) limits tree growth while the tree is being built, using a stopping rule such as a maximum depth, a minimum number of records required to justify a further split, or a minimum information gain (covered with a full worked calculation in the lesson on attribute selection measures) below which a split isn't worth making. Its main weakness is that it has to guess where to stop without seeing what a deeper split further down might have revealed — a split that looks unhelpful in isolation can still be the first step toward a genuinely useful pattern one level further down, and pre-pruning has no way to look ahead and check.

Post-pruning (backward pruning) takes the opposite approach: grow the full, maximally-overfit tree first, then remove branches afterward, once their actual effect on held-out performance can be measured directly rather than guessed at in advance. This costs more computation up front (the full tree has to be built before anything gets removed) but consistently produces more accurate final trees, because every pruning decision is based on measured performance rather than a stopping rule chosen before the data's real structure was visible.

Cost-Complexity Pruning: A Concrete Post-Pruning Method

"Remove branches that don't help" is the right idea for post-pruning, but it needs a precise rule to actually apply. Cost-complexity pruning (also called weakest-link pruning, and used by CART-style trees) makes the trade-off explicit with a single formula that scores a tree by combining its error with a penalty for its size:

R_alpha(T) = R(T) + alpha x |leaves(T)|

R(T) is the tree's error rate, |leaves(T)| is its number of leaves, and alpha is a complexity parameter that controls how much a simpler tree is worth relative to a small accuracy loss. At alpha = 0, this formula reduces to plain error minimization, which always favors the largest, most overfit tree available; as alpha increases, the penalty for extra leaves eventually outweighs the accuracy gained by adding them, and the formula starts favoring smaller subtrees instead. In practice, alpha isn't picked by hand — it's chosen using the same cross-validation approach covered in the lesson on major issues in data mining, by trying several candidate trees at different pruning levels and keeping whichever one performs best on held-out data rather than on the training set it was grown from.

Why a Perfect-Looking Branch Can Still Be the One to Cut

The core intuition worth internalizing is this: a branch's presence can produce zero training error and still hurt generalization, because a branch that exists to correctly classify one or two unusual training records has fit noise specific to those records, not a pattern that will reappear in new data. Removing that branch and replacing it with a single leaf — predicting the majority class for everything that would have reached it — trades a small amount of training accuracy for a tree that no longer depends on quirks that happened to be present only in the training set. This is exactly the bias-variance trade-off referenced throughout the classification lessons in this series: an unpruned tree sits at the high-variance end (it fits its specific training data extremely well but varies wildly if you trained it again on a different sample), and pruning deliberately moves it back toward the center, accepting a little more bias in exchange for a lot less variance.

Pre-Pruning vs. Post-Pruning at a Glance

Neither strategy is universally correct — a very large dataset where training the full tree is expensive may favor pre-pruning purely on computational grounds, while a smaller dataset where accuracy matters more than training time favors post-pruning's ability to measure rather than guess.