The Nested Cost-Complexity Pruning Sequence

Why Pruning Produces a Sequence

A grown classification tree can be represented by a set of terminal leaves, each of which assigns a class to the observations that reach it. Pruning replaces an entire subtree with a single leaf. This reduces the number of leaves, but can increase the number of training observations classified incorrectly. Cost-complexity pruning puts these competing quantities in one objective: training fit is rewarded, while tree size is penalized.

The key feature is that pruning does not search among arbitrary new trees at every penalty value. It repeatedly removes the weakest links from the current tree. Each step leaves a subtree of the tree that came before it, producing a nested sequence. The successive thresholds describe when each simplification becomes worthwhile in the penalized objective.

Definition: For a classification tree $T$, let $|T|$ be its number of terminal leaves and let $R(T)$ be its training misclassification count. For a nonnegative complexity penalty $\alpha$, the cost-complexity objective is $$ R_\alpha(T)=R(T)+\alpha |T|. $$ For an internal node $t$, let $T_t$ be the subtree rooted at $t$, and let $R(t)$ be the training errors if that whole subtree is replaced by a single leaf at $t$. The weakest-link threshold at $t$ is $$ g(t)=\frac{R(t)-R(T_t)}{|T_t|-1}. $$

This definition uses a fixed training set and unweighted misclassification counts. The replacement leaf predicts the majority class among the training observations reaching $t$; if there is a tie, a fixed tie-breaking rule is used. The denominator is the number of leaves removed: replacing $|T_t|$ leaves by one removes $|T_t|-1$. If risk is measured as a proportion rather than a count, the same formulas apply, but $\alpha$ must use the corresponding proportion-per-leaf scale.

The numerator $R(t)-R(T_t)$ is the training-error increase caused by collapsing the subtree. Under majority-class prediction at a leaf, this increase is nonnegative. A threshold is therefore the error increase per leaf removed. The weakest link is an internal node with the smallest threshold among the eligible nodes in the current tree.

Why the Threshold Determines the Pruning Step

Consider replacing $T_t$ by a leaf at $t$, leaving the rest of the tree unchanged. The training error rises by $R(t)-R(T_t)$, and the leaf count falls by $|T_t|-1$. Consequently, the change in the cost-complexity objective is

\begin{aligned} \Delta R_\alpha &=R(t)-R(T_t)-\alpha(|T_t|-1)\\ &=(|T_t|-1)\bigl(g(t)-\alpha\bigr). \end{aligned}

This calculation explains the decision rule. If $\alpha<g(t)$, the objective increases when $T_t$ is pruned, so the collapse is not yet justified by the penalty. If $\alpha>g(t)$, the objective decreases, so collapsing that subtree improves the penalized criterion. At $\alpha=g(t)$, the two alternatives have equal cost. As $\alpha$ increases, a penalty that once favored a larger subtree can therefore make its simpler replacement preferable.

In the weakest-link procedure, calculate $g(t)$ for internal nodes in the current tree and prune the node or nodes attaining the minimum. Recalculate thresholds on the resulting tree and continue until only the root leaf remains. If several eligible links have the same minimum threshold, they can be pruned together. Alternatively, tied steps can be represented in an equivalent order, provided the tie convention is applied consistently.

Why the Sequence Is Nested

Each pruning operation collapses a subtree that is present in the current tree; it does not add a split or change a split elsewhere. Thus the result of a step is necessarily a subtree of the tree before that step. Repeating this operation gives trees $T_0,T_1,\ldots$ such that every later tree is contained in the preceding one.

The thresholds used along this sequence do not decrease. Here is a short justification for the weakest-link update. Suppose the current minimum threshold is $\alpha_0$, and pruning a selected subtree removes $d$ leaves and raises its training error by $\alpha_0d$. For an ancestor node $s$ of the pruned subtree, write $D=|T_s|-1$ and $N=R(s)-R(T_s)$ before pruning. Its threshold is $N/D$, which is at least $\alpha_0$, since $\alpha_0$ is the current minimum. After pruning, the ancestor’s subtree has $D-d$ removable leaves and its risk has risen by $\alpha_0d$. Its updated threshold is

\frac{N-\alpha_0d}{D-d}\geq\alpha_0,

because $N\geq\alpha_0D$. The same argument applies if several disjoint weakest links tied at $\alpha_0$ are pruned: use their total removed leaves for $d$. Thresholds for unaffected, disjoint subtrees do not change, and descendants of a collapsed node are no longer eligible. Thus no newly eligible threshold falls below the one just used. This supports the step-by-step construction of the nested pruning sequence.

Pruning cannot reduce the training misclassification count under this setup: a replacement leaf uses the majority class at its node, and its error count is at least the subtree’s error count. Leaf count falls at every nontrivial pruning step, while training error either rises or stays the same. Neither fact alone says which tree will perform best on new data; here, the focus is the training-based pruning sequence and its penalized objective.

Worked Example: Following Three Weakest-Link Steps

Method: Calculate each current threshold, prune the minimum, and then update errors and leaves. A hypothetical training set gives a tree with two branches, $A$ and $B$. Branch $A$ has three leaves and 2 training errors; collapsing it would give 8 errors. Branch $B$ has two leaves and 4 errors; collapsing it would give 8 errors. The root collapse would give 26 errors. Find the pruning sequence and its thresholds.

Initially, the tree has $3+2=5$ leaves and $2+4=6$ training errors. For branch $A$, collapsing removes $3-1=2$ leaves and increases errors by $8-2=6$, so $g(A)=6/2=3$. For branch $B$, collapsing removes $2-1=1$ leaf and increases errors by $8-4=4$, so $g(B)=4/1=4$. The initial root threshold is $(26-6)/(5-1)=20/4=5$. The minimum is 3, so prune $A$.

After pruning $A$, the tree has $1+2=3$ leaves. Its total training errors are $8+4=12$. Branch $B$ still has threshold 4. The root threshold is now $(26-12)/(3-1)=14/2=7$. The minimum is 4, so prune $B$. The tree then has $1+1=2$ leaves and $8+8=16$ training errors. Its root threshold is $(26-16)/(2-1)=10$, so the final step collapses the root.

The sequence is therefore $5$ leaves and $6$ errors, then $3$ leaves and $12$ errors, then $2$ leaves and $16$ errors, then $1$ leaf and $26$ errors. The successive thresholds are 3, 4, and 10. The calculations check: each error increase is the threshold multiplied by the number of leaves removed—for example, pruning $A$ raises errors by $3(3-1)=6$. The method avoids assuming that a threshold calculated on the original tree must remain unchanged after pruning.

Interpreting Leaf and Error Changes

A pruning threshold is not the total change in training errors. It is an average increase in errors per leaf removed for a particular subtree in the current tree. To recover the total error change, multiply the threshold by the number of leaves removed. This distinction matters especially when a subtree has more than two leaves.

Worked Example: Converting a Threshold to Total Errors

Method: Use the threshold definition to recover the local error increase, then add that increase to the unchanged part of the tree. In a hypothetical current tree, there are 5 leaves and 14 training errors. The selected subtree has 3 leaves. Its threshold is 2.5, and after it is collapsed the subtree contributes 5 errors. Find the new total training errors and the training-error change.

The pruning removes $3-1=2$ leaves. By the threshold definition, the local error increase is $2.5(2)=5$. Since the collapsed subtree contributes 5 errors, its error count before pruning was $5-5=0$. The other parts of the tree therefore contribute all 14 of the original errors and remain unchanged.

After pruning, the total error count is $14+5=19$. The new tree has $5-2=3$ leaves, and the training-error change is $19-14=5$, an increase of 5. The calculation checks both ways: the local subtree changes from 0 to 5 errors, and the threshold times leaves removed is $2.5(5-3)=5$. A common mistake is to report an increase of 2.5, confusing the per-leaf threshold with the total increase.

Worked Example: Comparing Trees at Different Penalties

Method: Evaluate $R_\alpha(T)=R(T)+\alpha|T|$ for each candidate tree. A hypothetical nested sequence has these training results: $T_0$ has 6 leaves and 5 errors, $T_1$ has 4 leaves and 11 errors, and $T_2$ has 2 leaves and 19 errors. Determine the preferred candidate at $\alpha=2$, $3.5$, and $5$.

The transition threshold from $T_0$ to $T_1$ is $(11-5)/(6-4)=6/2=3$. The transition threshold from $T_1$ to $T_2$ is $(19-11)/(4-2)=8/2=4$. At $\alpha=2$, the three costs are $5+2(6)=17$, $11+2(4)=19$, and $19+2(2)=23$; choose $T_0$.

At $\alpha=3.5$, the costs are $5+3.5(6)=26$, $11+3.5(4)=25$, and $19+3.5(2)=26$; choose $T_1$. At $\alpha=5$, the costs are $5+5(6)=35$, $11+5(4)=31$, and $19+5(2)=29$; choose $T_2$. The results are consistent with the thresholds: the smaller tree becomes preferable after the penalty passes the relevant transition value. The common mistake avoided here is choosing a tree from training error alone while ignoring the leaf penalty.

Common Interpretations to Check

Do not treat $g(t)$ as the total error increase. Multiply by $|T_t|-1$ to obtain that increase.
Recalculate on the current tree. An ancestor’s threshold can change after one of its descendant subtrees is pruned.
Do not expect training error to fall after pruning. A majority-class replacement leaf cannot classify its node’s training observations better than the subtree did.
Keep the penalty’s scale consistent. A penalty paired with an error count is not numerically interchangeable with one paired with an error proportion.
Distinguish a nested sequence from a claim about future accuracy. Nesting describes how candidate trees are formed; it does not, by itself, establish which tree predicts best on new observations.

Key takeaway: At each step, prune the current weakest link, whose threshold is the increase in training errors per leaf removed. Recompute thresholds after pruning. The resulting trees are nested, their leaf counts decrease, and their training errors cannot decrease.

Check Your Understanding

For each problem, use training-error counts and the cost-complexity objective defined above.

A subtree has 4 leaves and 3 training errors; replacing it with one leaf gives 12 errors. Calculate its weakest-link threshold. (Answer: 3)
A current tree has 7 leaves and 18 errors. Pruning a selected subtree reduces the leaf count by 2; the subtree’s collapsed error count is 8 and its current error count is 2. Find the new total errors, new leaf count, and threshold. (Answer: 24 errors, 5 leaves, threshold 3)
Two disjoint weakest links tie at threshold 3. Link $U$ has 2 leaves and 1 error before collapse, with 4 errors after collapse. Link $V$ has 3 leaves and 2 errors before collapse, with 8 errors after collapse. If the whole tree initially has 6 leaves and 6 errors, find the errors and leaves after both are pruned. (Answer: 15 errors and 3 leaves)
Three nested candidates have (leaves, training errors) equal to $(5,4)$, $(3,10)$, and $(1,19)$. At $\alpha=3.5$, calculate all three penalized costs and identify the minimum. (Answer: costs 21.5, 20.5, and 22.5; choose the 3-leaf tree)
A subtree has 3 leaves and 1 training error; collapsing it gives 7 errors. If $\alpha=2.5$, does pruning lower the objective? Calculate the change in objective. (Answer: No; the objective increases by 1, so retain the subtree)

What You'll Learn