21 · Tree pruning: pre-pruning, post-pruning & ccp_alpha
Stop or trim the tree before it memorises noise — pruning is the regularization mechanism for decision trees.
Stop or trim the tree before it memorises noise — pruning is the regularization mechanism for decision trees.
Without this:
Without pruning, a single tree perfectly fits the training data and fails on anything new.
Every decision tree we've grown so far eventually overfits unless we stop it. Two strategies exist: pre-pruning (stop early during growth) and post-pruning (grow the full tree, then remove branches).
Pre-pruning: early stopping hyperparameters
These are applied during tree construction and prevent nodes from splitting further:
| Parameter | Effect | |---|---| | max_depth | Maximum depth from root to deepest leaf — simplest knob | | min_samples_split | Minimum samples at a parent node BEFORE it is allowed to split | | min_samples_leaf | Minimum samples required in EVERY resulting child leaf | | max_leaf_nodes | Cap on the total number of leaf nodes |
Setting any of these acts as a hard stopping criterion: the tree stops growing wherever the constraint fires.
Post-pruning: cost-complexity pruning (ccp_alpha)
Sklearn implements Minimal Cost-Complexity Pruning. The idea: grow the full tree T₀, then measure how much accuracy you sacrifice by collapsing (pruning) a subtree to a leaf. If the accuracy sacrifice is smaller than the regularization budget α, prune it.
Formally, minimize the penalised cost:
R(T) + α · |leaves(T)|
where R(T) is the training error and |leaves(T)| is the leaf count. Larger α → heavier penalty for leaf count → more aggressive pruning.
sklearn's cost_complexity_pruning_path() returns the full sequence of (α, impurity) values from the full tree (α=0) down to the root (α=max). You pick the best α by cross-validation.
The analogy to L1/L2 regularization
Ridge adds λ·||w||² to the loss — penalizing complexity (large weights). CCP pruning adds α·|leaves(T)| to the loss — penalizing complexity (many leaves). The mechanism is different but the principle is identical: trade a small increase in training error for a large reduction in model complexity.
Python (in browser)
The fully grown tree hits 100% training accuracy on 300 samples — it has memorised the training set by growing deep enough to create a leaf for each training region. The depth-3 tree accepts ~5-10% lower training accuracy in exchange for a notably better test score. This is the classic bias-variance tradeoff operationalised through a single hyperparameter.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
`cost_complexity_pruning_path` returns every alpha at which a branch would be pruned, from 0 (full tree) to a large value (root only). Fitting one tree per alpha and plotting train/test accuracy reveals the classic regularization arch: training accuracy monotonically decreases while test accuracy first rises (reducing overfit) then falls (too much underfit). The optimal alpha is at the peak of the test-accuracy arch.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
In production you don't need to plot the alpha curve manually — wrap `DecisionTreeClassifier` in a `GridSearchCV` over the alpha values from `cost_complexity_pruning_path`. The grid search internally uses k-fold cross-validation on the training set to estimate each alpha's generalisation performance. The resulting `best_estimator_` is the appropriately pruned tree.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
The three-tier rubric maps to increasing complexity: `max_depth` is one number and easy to explain to stakeholders; `min_samples_leaf` adds robustness without changing the interpretable depth; `ccp_alpha` is the principled option when you want optimal pruning with a clear theoretical grounding. For most problems, `max_depth` alone is sufficient.
Setting `max_depth=1` produces a tree with how many internal split nodes?
- Pre-pruning (max_depth, min_samples_split, min_samples_leaf, max_leaf_nodes) stops the tree from growing further when a constraint fires. It is simple, fast, and interpretable.
- Post-pruning (ccp_alpha) grows the full tree first, then removes branches whose accuracy sacrifice is below the budget α. The optimal α is found by cross-validation.
- Cost-complexity pruning minimises R(T) + α·|leaves(T)| — a direct analogy to L2 regularization which minimises training error + λ·||w||².
- min_samples_split requires N at the PARENT before a split is considered. min_samples_leaf requires N at EVERY resulting child. The leaf constraint is stricter — prefer it when in doubt.
- A max_depth=1 tree is called a 'decision stump' — one split, two leaves. It is the base learner of AdaBoost and the simplest non-trivial tree.
Every random forest and gradient boosting tree is pruned via max_depth (5–8 is typical). XGBoost's max_depth, LightGBM's num_leaves — same pruning hyperparameters under different names.
If you remove it: Trees would overfit perfectly on every problem — useless without their regularization knobs.