A Cost-Complexity Pruning Calculation Workshop

Why Pruning Calculations Need a Clear Denominator

A classification tree assigns a predicted class to each terminal node, or leaf. A deeper tree can reduce its training errors by creating more leaves, but a complicated tree may fit patterns that do not generalize. Cost-complexity pruning compares the reduction in training error with the cost of retaining additional leaves. Validation error then provides a separate way to compare candidate pruned trees.

The arithmetic is straightforward only when the quantities being compared are clear. A branch’s errors are not the same as a full tree’s errors if observations also reach leaves outside that branch. Likewise, a branch has a local number of leaves, while the full tree has all its leaves. In a valid full-tree comparison, unchanged errors and leaves outside the branch must be included in both alternatives, or explicitly identified as common contributions that cancel.

Definition: For a classification tree \(T\) fitted to \(N\) training observations, the error count \(E(T)\) is the number of observations classified incorrectly at the leaves. The normalized training risk is \(R(T)=E(T)/N\), and \(|T|\) is the number of terminal leaves. Under the cost-complexity convention used here, the criterion at penalty \(\alpha\geq 0\) is \(R_\alpha(T)=R(T)+\alpha|T|\). A smaller criterion is preferred. The same \(\alpha\) and the same training sample denominator \(N\) must be used when comparing candidate trees.

At each leaf, the predicted class is the most numerous class among the training observations in that leaf. If the leaf contains class counts \(n_1,\ldots,n_K\), its training error count is \(n-\max_k n_k\), where \(n=\sum_k n_k\). A stated tie-breaking rule determines the predicted class in a tie, although the number of errors is unchanged when tied classes have the same count.

For a candidate pruning step, a subtree \(T_t\) below a node \(t\) is replaced by a single leaf at \(t\). Let \(E_t\) be the errors among observations that reach the subtree before pruning, and let \(E_t^{\mathrm{leaf}}\) be the errors if they instead reach the collapsed leaf. If the subtree has \(L_t\) leaves, the collapse removes \(L_t-1\) leaves. Its critical penalty is

\alpha_t= \frac{E_t^{\mathrm{leaf}}-E_t} {N(L_t-1)}

This is a threshold comparison, not a claim that the branch’s error rate is the risk of the whole tree. At \(\alpha=\alpha_t\), the two alternatives have equal criterion contributions from that branch. Below the threshold, retaining the subtree has the smaller criterion; above it, collapsing the subtree has the smaller criterion, assuming the rest of the tree is unchanged.

Why the Pruning Threshold Has This Form

The threshold follows by writing both full-tree criteria. Suppose the unchanged part of the tree contributes \(E_{\mathrm{out}}\) errors and \(L_{\mathrm{out}}\) leaves. Before collapse, the full tree has \(E_{\mathrm{out}}+E_t\) errors and \(L_{\mathrm{out}}+L_t\) leaves. After collapse, it has \(E_{\mathrm{out}}+E_t^{\mathrm{leaf}}\) errors and \(L_{\mathrm{out}}+1\) leaves. At equality of criteria,

\frac{E_{\mathrm{out}}+E_t}{N}+\alpha(L_{\mathrm{out}}+L_t) = \frac{E_{\mathrm{out}}+E_t^{\mathrm{leaf}}}{N}+\alpha(L_{\mathrm{out}}+1).

Subtract the common outside contribution from each side. Rearranging gives

\alpha(L_t-1)=\frac{E_t^{\mathrm{leaf}}-E_t}{N}, \qquad \alpha= \frac{E_t^{\mathrm{leaf}}-E_t}{N(L_t-1)}.

This derivation explains both the numerator and the denominator. The numerator is the extra number of training errors caused by collapsing the subtree; the denominator accounts for the \(L_t-1\) leaves removed, with training risk normalized by the full sample size \(N\). The outside contributions cancel only because they are identical in the two candidate trees.

Important distinction: \(E_t/N\) is the branch’s contribution to the full-sample normalized risk, not the error rate within the branch. The branch error rate is \(E_t/N_t\), where \(N_t\) is the number of observations reaching the branch. Cost-complexity comparisons as defined here use full-sample risk, so use \(N\), not \(N_t\).

Worked Calculations

Worked Example: Comparing a Branch With Its Collapsed Leaf

A classification tree is fitted to \(N=100\) observations. A branch receives 40 observations and has two leaves. Their class counts are \((18,3)\) and \((4,15)\), respectively. The remaining 60 observations reach three other leaves, where they produce 8 errors. Calculate the full-tree criteria before and after collapsing the branch, and decide which tree is preferred at \(\alpha=0.10\) and \(\alpha=0.12\).

Method. At each leaf, predict the class with the larger count. For the first branch leaf, the counts \((18,3)\) give \(3\) errors. For the second, \((4,15)\) give \(4\) errors. Thus, the subtree contributes \(3+4=7\) errors before pruning.

The branch totals are \(18+4=22\) for the first class and \(3+15=18\) for the second. If collapsed, the branch predicts the first class and makes \(18\) errors. The full tree before pruning therefore has \(7+8=15\) errors and \(2+3=5\) leaves. After pruning, it has \(18+8=26\) errors and \(1+3=4\) leaves.

The full-tree criteria are

R_\alpha(T_{\mathrm{retain}})=\frac{15}{100}+5\alpha, \qquad R_\alpha(T_{\mathrm{collapse}})=\frac{26}{100}+4\alpha.

At \(\alpha=0.10\), these are \(0.15+0.50=0.65\) and \(0.26+0.40=0.66\), so retain the branch. At \(\alpha=0.12\), they are \(0.15+0.60=0.75\) and \(0.26+0.48=0.74\), so collapse it. The threshold is \((18-7)/(100(2-1))=0.11\), which confirms the two decisions. This full-tree calculation avoids treating the branch’s risk contribution as the risk of the full tree.

Worked Example: Finding the First Pruning Step

A tree is fitted to \(N=160\) observations. A branch contains 120 observations, has four leaves, and has class counts \((10,1)\), \((2,9)\), \((81,4)\), and \((3,10)\) at those leaves. Outside the branch are two leaves with 6 errors in total. First calculate the threshold for collapsing the whole branch. Then calculate the threshold for collapsing the two-leaf twig formed by the first two leaves, and identify which proposed collapse has the smaller threshold.

Method. The four branch leaves make \(1+2+4+3=10\) errors. Their combined class totals are \(10+2+81+3=96\) and \(1+9+4+10=24\). A single collapsed leaf predicts the first class, giving \(24\) branch errors. Collapsing the whole branch removes three leaves, so its threshold is

\alpha_{\mathrm{branch}}=\frac{24-10}{160(4-1)} =\frac{14}{480}=0.02917\ldots.

For the twig, the first leaf has \(1\) error and the second has \(2\), so the twig has \(3\) errors before pruning. Its combined counts are \((10+2,1+9)=(12,10)\), giving \(10\) errors after collapse. It removes one leaf, so its threshold is

\alpha_{\mathrm{twig}}=\frac{10-3}{160(2-1)} =\frac{7}{160}=0.04375.

The whole-branch threshold is smaller, so among these two proposed collapses it reaches the equality point first as \(\alpha\) increases. As a check on the denominator and the outside contribution, the full tree initially has \(10+6=16\) errors and \(4+2=6\) leaves. Collapsing the whole branch gives \(24+6=30\) errors and \(1+2=3\) leaves. The full-tree criterion difference is therefore \(14/160-3\alpha\), which equals zero at \(14/480\). The outside six errors and two leaves are present on both sides; they do not disappear from the full-tree criterion.

Worked Example: Comparing Candidate Trees and Validation Error

Three nested candidate trees, all fitted to the same \(N=100\) training observations, have the following training error counts and leaf counts: \(T_1\) has 10 errors and 8 leaves; \(T_2\) has 14 errors and 5 leaves; \(T_3\) has 19 errors and 3 leaves. At \(\alpha=0.04\), find the tree with the smallest cost-complexity criterion. Then, using a separate validation sample of 50 observations on which the trees make 12, 7, and 8 errors, select by validation error.

Method. Compute the training criteria with the same \(N=100\) denominator. For \(T_1\), the criterion is \(10/100+0.04(8)=0.10+0.32=0.42\). For \(T_2\), it is \(14/100+0.04(5)=0.14+0.20=0.34\). For \(T_3\), it is \(19/100+0.04(3)=0.19+0.12=0.31\). Thus \(T_3\) has the smallest cost-complexity criterion.

Validation error is a different comparison. The validation error proportions are \(12/50=0.24\), \(7/50=0.14\), and \(8/50=0.16\). The validation choice is \(T_2\), not \(T_3\). This result is possible because pruning penalizes training complexity, while validation error measures performance on observations not used to fit the tree. The calculation avoids selecting a tree by comparing validation error counts with the training-based cost-complexity criterion.

How to Check a Pruning Calculation

For a supplied tree, keep the calculations organized so that local and full-tree quantities cannot be confused. A compact workflow is:

Count leaf errors.
For each leaf, subtract its largest class count from its total count. Add the leaf errors to obtain the tree’s training error count.

Write down the denominator and leaf count.
Use the full training size \(N\) for normalized training risk. Count every terminal leaf in the candidate full tree.

Calculate both alternatives.
For a collapse, recompute the errors at the new parent leaf. Add the errors and leaves outside the branch to both full-tree totals.

Compare criteria or thresholds.
Use \(R(T)+\alpha|T|\) for each full tree, or use the threshold formula for a local collapse with unchanged outside contributions.

Use validation results for selection when supplied.
Calculate each candidate’s validation error on the same validation sample and select according to the stated rule.

A frequent exam trap is to divide a branch’s errors by the number of observations in that branch and then insert that branch rate into a full-tree cost-complexity criterion. That changes the scale of the risk and can produce an incorrect threshold. Another trap is to omit outside-branch errors or leaves from a purported full-tree criterion. Omitting them is valid only when explicitly comparing local contributions, because those outside terms are identical and cancel.

Key takeaway: A pruning calculation requires a consistent comparison. For full-tree criteria, include every training error and terminal leaf. For a local threshold, label the quantities as branch contributions and use the full training size \(N\) in the risk normalization. Validation error is then evaluated separately on the validation sample.

Check Your Understanding

For each problem, compute the requested quantity before checking the answer.

A training set has \(N=80\). A two-leaf branch has 2 and 5 errors, while its collapsed leaf would have 13 errors. Find the branch’s collapse threshold. (Answer: \(6/80=0.075\).)
A full tree has 9 errors and 6 leaves. A proposed collapse changes the branch errors from 3 to 8 and removes one leaf. The training set has \(N=100\). Find the full-tree error count, leaf count, and criterion after collapse at \(\alpha=0.02\). (Answer: 14 errors, 5 leaves, and criterion \(0.14+0.02(5)=0.24\).)
For \(N=120\), a branch has three leaves with 2, 3, and 4 errors; collapsing it gives 17 errors. Find the collapse threshold. (Answer: \((17-9)/(120(3-1))=1/30\approx0.0333\).)
Two candidate trees have training errors and leaf counts \((12,6)\) and \((17,3)\) on \(N=100\). At \(\alpha=0.04\), which has the smaller cost-complexity criterion? (Answer: The second tree; its criterion is \(0.17+0.12=0.29\), versus \(0.12+0.24=0.36\).)
Three trees make 9, 6, and 8 errors on a validation sample of 40 observations. Which tree is selected by minimum validation error, and what is that error proportion? (Answer: The second tree, with validation error \(6/40=0.1500\).)

These calculations are aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus. Their central discipline is to identify exactly which tree, sample, errors, and leaves each quantity describes before comparing candidates.

What You'll Learn