Tree Pruning and Hyperparameters

From Decision Tree Learning you know the default tree memorizes: depth 31, 604 leaves, train accuracy 1.000. Pre-pruning answers that with rules that stop the recursion before it can carve a leaf for every row. Each knob is a different definition of "this split is not worth it":

min_samples_leaf deserves special attention because it does more than cap size: requiring every leaf to hold a minimum number of rows forces the tree to average over data instead of memorizing it. A leaf with one row predicts that row; a leaf with 50 rows predicts their majority, so noise gets smoothed away. In practice min_samples_leaf and max_depth together kill most of the memorization signature — the toy from the previous chapter drops from depth 31 to something honest:

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import GridSearchCV, StratifiedKFold

base = DecisionTreeClassifier(random_state=42)
param_grid = {
    "max_depth": [4, 6, 8, 12, None],
    "min_samples_leaf": [1, 5, 20, 50],
    "min_samples_split": [2, 10, 40],
    "max_leaf_nodes": [15, 31, 63, None],
}
cv = StratifiedKFold(5, shuffle=True, random_state=42)
search = GridSearchCV(base, param_grid, cv=cv, scoring="f1", n_jobs=-1)
search.fit(X_tr, y_tr)
search.best_params_   # e.g. {'max_depth': 8, 'min_samples_leaf': 20, ...}

Before trusting any of those numbers, diagnose first: fit the unconstrained tree and inspect get_depth(), get_n_leaves(), and the train/validation gap. Depth 3 with a large gap means size is not the problem (look at features or label noise instead); depth 30 with a large gap is textbook overfitting, and the knobs above are the right lever. Size limits double as an interpretability tool — a depth-6 tree is at most 63 printable rules a stakeholder can audit, while depth 30 is a database nobody reviews.

Now the failure mode, which is the reason pre-pruning alone is not enough. Tree growth is greedy, so a split that looks useless today may be the doorway to an excellent split two levels down. A classic instance: parent 100 rows, 60/40; the best available split produces children 31/19 and 29/21 — pure 0.5 everywhere, information gain 0. The rule "stop when gain ≈ 0" halts here, yet one level deeper both children might split to near-purity. The famous artificial case is XOR: either single feature has zero gain against the label, so any myopic tree with a gain threshold refuses to split at all and stays at the majority guess, while the same tree two levels deep solves it perfectly. This is the horizon problem — early stopping optimizes the next step, not the final tree.

Two operational notes. First, max_features is not a size limit but a per-split feature subsampling rate; for classification its default in a single tree is all features (the sqrt heuristic belongs to random forests), and lowering it speeds training on wide datasets while injecting randomness. Second, tune pre-pruning limits inside cross-validation, never on the test set — with a grid this large and 5 folds you are fitting 300 trees, which is still fast, and the alternative is reporting a number you chose by staring at the test results. Pre-pruning is cheap and human-readable, but there is a second family of methods that lets the tree grow fully first and then removes what never earned its place — and that family has a theory-backed advantage you are about to compute by hand.

Post-pruning takes a different philosophy: grow the tree all the way down so every structure the greedy search could use exists, then delete the branches whose contribution does not justify their complexity. The deletion rule is a single regularized objective, the tree analogue of ridge and lasso:

R_alpha(T) = R(T) + alpha * |T~|

R(T)   = weighted impurity of the leaves (sum over leaves of n_t/n * impurity_t)
|T~|   = number of effective leaves (terminal nodes)
alpha  = the price you charge for each leaf

The objective is a direct trade: every subtree is worth keeping only if the impurity it removes exceeds alpha times the leaves it costs. Work the arithmetic on a subtree t with 3 leaves that currently reduces the training error of its would-be pruned replacement by 4 mistakes:

keep t:  error 6 + alpha * 3        # subtree contributes 3 leaves
prune t: error 10 + alpha * 1       # replaced by a single leaf
break-even: 6 + 3a = 10 + a  ->  2a = 4  ->  alpha* = 2

alpha < 2  -> keep the subtree (error savings outweigh the leaf tax)
alpha > 2  -> replace it with one leaf
alpha = 0  -> no pruning at all: the fully grown tree minimizes R_0

General rule: a subtree is cut when alpha exceeds (R(t) − R(T_t)) / (|T̃_t| − 1) — the error it saves divided by the extra leaves it needs. As alpha rises from 0, trees get cut in a fixed order — the weakest links first, which gives the algorithm its name, weakest-link cutting — so one growing sequence produces every candidate tree you might want, with alpha as the single dial.

scikit-learn exposes that sequence directly. ccp_alpha is its pruning parameter, and cost_complexity_pruning_path computes the whole ladder before you commit to anything:

import numpy as np
from sklearn.tree import DecisionTreeClassifier

tree = DecisionTreeClassifier(random_state=42)
tree.fit(X_tr, y_tr)
path = tree.cost_complexity_pruning_path(X_tr, y_tr)
alphas, impurities = path.ccp_alphas, path.impurities
print(alphas[:8])   # [0.  0.0012  0.0019  0.0044  ...] ascending, one per cut

# every candidate tree, cheap to evaluate:
forest = [DecisionTreeClassifier(ccp_alpha=a, random_state=42).fit(X_tr, y_tr)
          for a in alphas]
print([t.get_n_leaves() for t in forest])   # monotonically shrinking

The pruning path is computed bottom-up: each internal node gets its own break-even alpha, the node with the smallest alpha collapses first, and the tree is re-evaluated upward — a single pass that yields the complete nesting of subtrees. That is why the returned ccp_alphas array is ascending and each value corresponds to one more cut: index 0 is alpha = 0 (fully grown), and the last entry prunes everything to the root. You get a total ordering of candidate models for the price of one fit.

Two precision points interviewers use to separate readers of docs from users of trees. First, sklearn's R(T) is computed with leaf impurity (gini/entropy), not misclassification rate — the same formula shape, a more sensitive measure, and identical in spirit to the break-even math above. Second, alpha values are dataset-specific and scale with the impurity units of your labels, so the number 0.0044 means nothing portable — you always select it relative to the candidate list via cross-validation, which is exactly the next chapter's job. Also note pruning never adds structure: the pruned tree is always a subtree of the fully grown one, so if the greedy search never considered a useful split, no alpha will recover it. That limit is shared with pre-pruning and is the reason ensembles exist — averaging many diverse trees sidesteps any single tree's blind spots.

You now have two levers — pre-pruning limits and cost-complexity alpha — and one rule for both: select them by cross-validation on the training folds, freeze the choice, and evaluate the test set exactly once. The full workflow for alpha looks like this:

import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import GridSearchCV, StratifiedKFold, train_test_split
from sklearn.metrics import accuracy_score

X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.2,
                                           stratify=y, random_state=42)

path = DecisionTreeClassifier(random_state=42).fit(X_tr, y_tr) \
             .cost_complexity_pruning_path(X_tr, y_tr)
alphas = np.unique(path.ccp_alphas)[::5]          # subsample the ladder

grid = GridSearchCV(
    DecisionTreeClassifier(random_state=42),
    {"ccp_alpha": alphas},
    cv=StratifiedKFold(5, shuffle=True, random_state=42),
    scoring="accuracy", n_jobs=-1)
grid.fit(X_tr, y_tr)
print("best alpha:", grid.best_params_["ccp_alpha"])
print("test score:", accuracy_score(y_te, grid.predict(X_te)))  # ONCE

What the CV curve looks like as alpha varies tells you where you stand. At alpha = 0 the candidates are deep, memorized trees: training score is pinned at 1.0 while validation score sags — classic variance. At very large alpha the tree collapses to its root (one leaf predicting the majority class), and train and validation scores converge downward at the majority-class baseline — classic bias, the same lazy-model shape you met in Class Imbalance Remedies. The chosen alpha sits where the validation curve peaks, between the two. Watching those three regions form is the most efficient way to internalize what regularization does in trees.

A subtle and common mistake: selecting alpha by training score, or by the number of leaves you find aesthetically pleasing. Training score is monotonically best at alpha = 0 by construction, so it can never choose the cut; only held-out folds estimate generalization. The other common leak is tuning alpha after looking at test results — then the test set has quietly become a validation set and your final number is optimistic. Keep one held-out set pristine, or use nested CV if the dataset is small enough that you cannot spare it.

Read the chosen alpha for signal, too. If CV picks the smallest candidate, the data barely wanted regularization — suspect label noise or duplicated rows before celebrating. If it picks the largest (the tree collapses toward one leaf), the features carry almost no signal at that granularity, and no amount of pruning arithmetic will rescue them; the honest response is feature work or a different model class, not a tighter grid. A best alpha in the middle with a clear validation peak is the healthy case the technique exists for.

Pre-pruning versus post-pruning is a standard discussion question, so have a position ready. Pre-pruning is cheap (one tree, no extra passes), gives you interpretable size limits directly, and stops runaway depth early — but it is myopic: gain-zero halting can strand a tree before it reaches splits that would have paid off, and it interacts poorly with greedy search (the XOR trap). Post-pruning sees the full structure first, then trims by a principled cost that trades error against leaves, and empirically generalizes better — at the price of growing a possibly huge tree first and a CV loop over the alpha ladder. Many practitioners combine them: a generous max_depth/min_samples_leaf to bound the worst case, then ccp_alpha tuned by CV for the actual regularization.

Also fix these habits while the workflow is in front of you: set random_state everywhere so results reproduce; remember ccp_alpha interacts with class_weight on imbalanced data (weights change the impurity that pruning is pricing); and understand what happens next in the roadmap — a single pruned tree is a decent baseline, but the phase's remaining topics remove the single-tree ceiling. Random Forests starts there: average many decorrelated trees, and each tree's individual pruning errors cancel instead of compounding.