Cost-Complexity Regression Tree Pruning
Compare every rooted subtree and see how a leaf penalty changes the selected regression tree.
By Riano · Published · Updated · Report a correction
Cost-Complexity Regression Tree Pruning
Concept Overview
Cost-complexity pruning is a technique used to avoid overfitting in decision trees by finding the right balance between a tree's predictive power on training data and its structural complexity. We start from a fully grown tree and prune it by removing subtrees, thereby penalizing the total number of leaves according to a parameter α.
Worked Example
Let's consider a regression tree built from an asymmetric sample divided into 4 groups: [[0, 0], [2, 2], [4, 4], [8, 8]].
| Subtree | Leaves | SSE | Objective (α=8) |
|---|---|---|---|
| LL|LR|RL|RR (Full) | 4 | 0.0 | 32.0 |
| L|RL|RR | 3 | 4.0 | 28.0 |
| L|R | 2 | 20.0 | 36.0 |
| Root (Single Leaf) | 1 | 70.0 | 78.0 |
With α = 8, the subtree `L|RL|RR` achieves the lowest objective score (28.0) and is chosen as the optimal pruned tree. Note that pruning minimizes raw training SSE plus alpha times the leaf count.
Experiment
Follow these steps to observe the impact of the cost-complexity penalty:
- Select the Asymmetric option in the "Tree sample" dropdown control.
- Set the Penalty alpha to 0 to observe the unpruned tree with 4 leaves and SSE of 0.
- Gradually increase the Penalty alpha to 8. Observe how the optimal tree changes to the 3-leaf subtree `L|RL|RR`.
- Further increase the penalty to 50. Notice that the entire tree is pruned back to just the Root node, with 1 leaf, maximizing simplification over raw training accuracy.
Limitations
There are a few key limitations to keep in mind when applying this technique:
- This example focuses purely on minimizing raw training SSE plus a penalty. It does not perform actual cross-validation to guarantee out-of-sample improvement.
- The parameter α (alpha) here is a raw absolute penalty multiplier, unlike scikit-learn's `ccp_alpha` which normalizes by sample weight.
- The tree is pre-defined with a depth of two; typical implementations handle arbitrarily deep trees.
References
For more in-depth mathematical background, consult the following resources:
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Cost-Complexity Regression Tree Pruning module.
Try Cost-Complexity Regression Tree Pruning on Riano →