Cost-Complexity Pruning

Why Prune a Tree That Fits the Training Data?

A tree can reduce its training error by adding splits: each split gives the model more regions in which to make separate predictions. But a very large tree may capture chance patterns in the training sample, produce complicated rules, and predict poorly on new cases. Pruning addresses this trade-off by starting with a fitted tree and considering simpler trees formed by removing branches.

The cost-complexity objective makes the trade-off explicit. It adds a penalty for tree size to the training loss. A larger penalty favors smaller trees; a smaller penalty gives more weight to fitting the training data. The objective can be used with regression or classification, provided the training loss is defined consistently for every candidate tree.

For a regression tree, a common choice for \(R(T)\) is the residual sum of squares (RSS) on the training data. For a classification tree, one possible choice is the number of training cases misclassified by the tree. Other loss definitions can be used, but their scale matters: changing the loss scale without changing \(\alpha\) changes the balance between fit and size.

The penalty is charged per terminal node, not per split or per level of depth. A tree with five terminal nodes therefore receives penalty \(5\alpha\), regardless of whether its branches are balanced. If an implementation reports an objective using a scaled loss or a different size convention, its numerical penalty parameter need not be directly comparable to an \(\alpha\) defined here.

What It Means to Prune a Branch

A branch, or subtree, consists of an internal node and all of its descendants. Pruning that branch removes its descendant splits and replaces the entire branch with one terminal node at its root. The rest of the tree is unchanged. In particular, pruning a branch with several leaves does not remove the leaves elsewhere in the tree.

If the branch being considered has \(L\) terminal nodes before pruning, collapsing it changes the total leaf count by \(L-1\): those \(L\) leaves are replaced by one. When the leaf predictions are refitted according to the chosen tree-fitting rule, merging regions cannot improve the optimal training loss relative to keeping them separate. Thus, the training loss usually increases or stays the same as a result of pruning.

Why the Pruning Rule Holds

The rule follows by comparing the objective before and after a single branch is collapsed. Let the tree outside the branch have training loss \(R_{\text{outside}}\) and \(K\) terminal nodes. Before pruning, the branch contributes loss \(R_{\text{sub}}\) and \(L\) leaves. After pruning, it contributes loss \(R_{\text{leaf}}\) and one leaf. Any loss and leaves outside the branch appear in both candidate objectives.

Subtracting the objective before pruning from the objective after pruning cancels the contributions outside the branch:

The pruned version is at least as good when this difference is nonpositive. Rearranging gives \(\Delta R\leq\alpha(L-1)\), as stated. This derivation also explains the two competing effects: pruning pays an increase in training loss, but saves the penalty on \(L-1\) leaves.

Regression and Classification Use the Same Structure

The cost-complexity comparison has the same form for either task. What changes is the definition of training loss. With regression RSS, a loss increase is measured in squared outcome units. With classification misclassification loss, it is measured in cases (or, if divided by the sample size, in a proportion). The value of \(\alpha\) must be interpreted on the same scale as the chosen loss.

Practical Interpretation and Exam Traps

Cost-complexity pruning is a post-growth simplification: it considers branches in a tree that has already been fitted, rather than preventing a split from being created in the first place. This distinguishes pruning from pre-pruning rules such as stopping growth at a specified depth or minimum node size. The earlier material on tree-growth stopping rules addresses those restrictions; the criterion here evaluates the fit-size trade-off for candidate subtrees.

The chosen loss needs to be stated before making a numerical comparison. For example, an RSS value and a misclassification count cannot be combined in one objective without a defined conversion. Likewise, if a classification loss is recorded as a proportion rather than a count, the penalty must be on a compatible scale. The objective is a comparison tool, not a claim that every unit of training loss has the same practical meaning across problems.

The main arithmetic traps are straightforward but consequential:

• Counting leaves rather than removed splits. The penalty is based on terminal nodes. Collapsing a subtree with \(L\) leaves saves \(\alpha(L-1)\), not simply \(\alpha\) unless \(L=2\).
• Counting the resulting leaves incorrectly. A collapsed branch contributes one leaf, but leaves outside it remain. If two separate branches are collapsed, each contributes one leaf.
• Reversing the comparison. The pruned objective minus the original objective is \(\Delta R-\alpha(L-1)\). A negative value favors pruning; a positive value favors retaining the branch.
• Ignoring ties. If the difference is zero, both candidates have equal cost-complexity objective. The criterion alone does not select uniquely between them.
• Mixing loss scales. A penalty value has meaning only in relation to the chosen definition of \(R(T)\) and its scale.

The penalty term explains why a larger tree is not automatically better, even when it fits the training data more closely. A tree’s training loss generally rewards additional flexibility, while the terminal-node penalty charges for it. Pruning is worthwhile when the reduction in complexity penalty is at least as large as the resulting increase in training loss.