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 \cdots \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 2,180 words, 15 min read) adds 2 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.