Prune decision trees.

A fully grown decision tree memorizes the training set and shatters on new data. Pruning is the disciplined rollback that trades a little training accuracy for a lot of test accuracy.

Why grow then prune. Greedy recursive binary splitting picks the best split locally at each node. A split that looks weak now may enable a strong split below. So you grow a deliberately large tree $T_0$ (each leaf hits a minimum size, say 5 observations), then prune back. Stopping early (pre-pruning) is short-sighted: it kills good descendants because their parent looked uninformative.

Cost-complexity criterion. Define training-set risk $R(T)$: for regression, residual sum of squares; for classification, misclassification rate weighted by node size. The penalized criterion is:

$$R_\alpha(T) = R(T) + \alpha\,|T|$$

$\alpha = 0$ keeps the full tree $T_0$. As $\alpha$ climbs, branches drop off because each terminal node now costs $\alpha$ units of penalty. Eventually only the root survives.

KEY: $\alpha$ is the price of a leaf, measured in the same units as $R(T)$. One extra leaf has to reduce $R$ by at least $\alpha$ to be worth keeping.

Common mistakes

• Searching all $2^{|T_0|}$ subtrees. Cost-complexity pruning is not exhaustive. Weakest-link pruning visits only $|T_0|$ candidates because the optimal subtrees are nested. Brute-force search wastes compute and earns no extra accuracy.
• Using Gini for the prune step. Gini and cross-entropy grow the tree well but exaggerate impurity gaps for the prune decision. Switch to misclassification rate when computing $R(T)$ for cost-complexity pruning on classification trees.
• Picking $\alpha$ on the training set. Training error is monotone decreasing in $|T|$, so it always prefers $T_0$ with $\alpha=0$. You must use cross-validation or a held-out validation set, never re-substitution error, to select $\alpha$.

Bottom line

• Why prune: a fully grown tree has low bias and explosive variance; pruning collapses high-variance leaves to lower test error.
• Grow a deliberately large tree first, then prune. Pre-pruning is myopic because it stops on locally weak splits that enable strong later ones.
• Cost-complexity pruning minimizes $R_\alpha(T) = R(T) + \alpha|T|$, where $|T|$ is the number of terminal nodes and $\alpha \ge 0$ is the complexity penalty.
• Weakest-link pruning yields a nested sequence $T_0 \supset T_1 \supset \dots \supset T_m$, collapsing the node with smallest $g(t) = (R(t) - R(T_t)) / (|T_t| - 1)$ first.

Exam shortcut

If a question gives you the nested sequence and an $\alpha$, find the largest $\alpha_k$ with $\alpha_k \le \alpha$ and return $T_k$. Do not interpolate. If a question lists subtree risks and asks which collapses first, compute $g(t)$ for each candidate and pick the smallest.

The full lesson (about 3,015 words, 20 min read) adds 7 worked examples, all 6 common mistakes, a self-check, free in the app.

Learning objectives

• C2

Browse all free MAS-II lessons or jump into free MAS-II practice questions.