ML0080 Decision Tree Pruning

An unconstrained decision tree grows until every leaf is pure, which on real data means it memorizes noise: training accuracy hits 100% while test accuracy sags. Pruning is the cure, and it comes in two forms. Pre-pruning stops growth early with rules like maximum depth, minimum samples per leaf, or minimum impurity decrease. Post-pruning grows the full tree first, then cuts back the branches whose complexity is not repaid by fit, using a validation-based criterion such as cost-complexity pruning. Post-pruning is usually stronger because a split that looks useless alone may unlock a highly valuable subtree below it; pre-pruning can never see that.

(1) Why Trees Overfit: depth adds one axis-aligned cut per level, so a deep tree carves the training set into tiny pure cells, which is high variance by construction.
(2) Pre- vs Post-Pruning: pre-pruning is cheap but myopic (it can miss XOR-style interactions); post-pruning explores the full tree and then removes only the provably weakest links.
(3) Production Default: scikit-learn implements minimal cost-complexity pruning via the ccp_alpha parameter: its documented example shows an unpruned tree at 100% train / 88% test accuracy, while sweeping the pruning path finds ccp_alpha near 0.015 maximizing test accuracy.

Figure 1: The pruning path: as ccp_alpha grows, more of the tree is cut, training accuracy declines, and test accuracy peaks where complexity is repaid by generalization (the sklearn example peaks near 0.015).

Cost-complexity pruning scores each subtree by its error plus a per-leaf penalty, so a branch survives only if it reduces impurity enough to pay for its leaves. Pruning proceeds weakest-link-first: at each step the node whose removal costs the least accuracy per leaf is collapsed, producing a nested sequence of subtrees indexed by alpha. You then pick alpha by cross-validation rather than by training-set performance, which is what makes the chosen tree a generalization-optimal member of the sequence.

Figure 2: Post-pruning in action: the full tree (left) contains branches fitted to noise; the dashed subtrees are the weakest links, and the pruned tree (right) collapses them into leaves.

Mathematical Formulation:

Where:

• is the total (sample-weighted) impurity of the leaves of tree , and is its number of terminal nodes.
• is the complexity parameter (ccp_alpha in scikit-learn); larger alpha prunes more aggressively.
• is the effective alpha of node : the penalty value at which keeping its branch costs exactly as much as collapsing it, so the node with the smallest value is pruned first.