A tree left to grow freely will keep splitting until every leaf is pure — memorizing the training set, noise and all. The art of a single good tree is controlling its size: how to grow it, when to stop, and how to cut it back. This chapter covers the greedy growth algorithm, the stopping (pre-pruning) hyperparameters, and the principled alternative — cost-complexity (post-)pruning.

The CART growth algorithm

CART grows a tree by greedy recursive binary splitting: starting at the root with all data, find the single feature–threshold split that most reduces impurity, partition into two children, and recurse on each. It is greedy (best split now, no lookahead) and produces strictly binary trees. Left unchecked it grows until leaves are pure or contain one point — a perfect, useless overfit.

Pre-pruning: stop early

Pre-pruning (early stopping) halts growth using hyperparameters — it is fast and the everyday way to control trees:

  • max_depth — the maximum number of question levels (the single biggest knob).

  • min_samples_split — don’t split a node with too few samples.

  • min_samples_leaf — require each leaf to keep at least this many samples (smooths predictions).

  • max_leaf_nodes / min_impurity_decrease — cap total leaves / require a minimum gain to split.

The danger of pre-pruning is horizon effect: a weak split that unlocks a great split below it gets blocked, because the algorithm cannot see past the next step.

Cost-complexity (post-)pruning

Cost-complexity pruning grows a large tree \(T_0\), then prunes it back to minimize a penalized error \[R_\alpha(T) = R(T) + \alpha\,|T|,\] where \(R(T)\) is the training error (misclassification or MSE), \(|T|\) is the number of leaves, and \(\alpha\ge 0\) is the complexity parameter. Larger \(\alpha\) favors smaller trees.

As \(\alpha\) increases from \(0\), cost-complexity pruning produces a nested sequence of ever-smaller subtrees — and remarkably, the best subtree of each size lies on this sequence (weakest-link pruning). You then pick \(\alpha\) (hence tree size) by cross-validation, choosing the simplest tree within one standard error of the best. This separates growing (greedy, fast) from model selection (principled, validated) — generally beating pre-pruning at the cost of more computation.

Categorical splits and missing values

For categorical features, CART considers splits that send a subset of categories left and the rest right; with \(q\) categories there are \(2^{q-1}-1\) possible binary groupings, though efficient algorithms avoid brute force for ordered targets. Missing values are handled either by surrogate splits (a backup feature that mimics the primary split) in classic CART, or by learning a default direction (XGBoost/LightGBM) — more in Chapter [ch:practical].

Don’t tune by training error — it always prefers the biggest tree. Always select depth/\(\alpha\) on a validation set or by cross-validation. And remember: pruning matters far less once you ensemble. In a random forest you deliberately grow deep, unpruned trees (variance is killed by averaging, Chapter [ch:randomforests]); in gradient boosting you grow shallow trees (depth 3–8) and control complexity with the learning rate and number of trees. Heavy single-tree pruning is mostly for when you need one interpretable tree.

The growth/stop/prune trio is the original regularization story of machine learning, predating weight decay and dropout: \(R_\alpha(T)=R(T)+\alpha|T|\) is loss-plus-complexity-penalty, exactly the template of modern regularized objectives. XGBoost makes this explicit — its objective adds \(\gamma T + \tfrac12\lambda\sum w_j^2\), penalizing the number of leaves \(T\) and leaf weights, a direct descendant of cost-complexity pruning baked into the training loss (Chapter [ch:moderngbm]).

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import cross_val_score
X, y = load_breast_cancer(return_X_y=True)
path = DecisionTreeClassifier(random_state=0).cost_complexity_pruning_path(X, y)
for a in path.ccp_alphas[::6]:                 # sweep the complexity parameter
    clf = DecisionTreeClassifier(ccp_alpha=a, random_state=0)
    print(f"alpha={a:.4f}  cv acc={cross_val_score(clf, X, y, cv=5).mean():.3f}")

Chapter summary

  • CART grows by greedy recursive binary splitting; unchecked, it overfits to pure leaves.

  • Pre-pruning stops early via max_depth, min_samples_leaf, etc. — fast, but suffers the horizon effect.

  • Cost-complexity pruning minimizes \(R(T)+\alpha|T|\), giving a nested subtree sequence; pick \(\alpha\) by cross-validation.

  • Never select tree size by training error; use validation/CV (and the one-standard-error rule for simplicity).

  • In ensembles, pruning matters less: forests grow deep, boosting grows shallow — the penalty \(R+\alpha|T|\) foreshadows regularized boosting objectives.