Learn AI Create the Future — with Pranay
Main site

Classic Algorithms in Depth

Pruning a decision tree

Cost-complexity pruning charges a tree rent for every leaf it keeps, cutting away branches that memorised noise while keeping the ones that earn their keep.

Read these first

On this page 5
  1. Why it exists
  2. How it works
  3. A real example you have seen
  4. Remember this
  5. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

Pruning cuts back a fully grown decision tree until only the branches that genuinely help survive.

Think of a mango tree gone wild. Left alone it sprouts hundreds of thin twigs, each carrying a leaf or two. A gardener prunes it: any twig that costs more in water than it returns in fruit gets cut. What remains is smaller, stronger and yields better.

A decision tree grown without limits does the same sprouting. It keeps adding questions until every training example sits in its own perfect little leaf.

Why it exists

A fully grown tree scores 100% on its training data — and that is a symptom, not an achievement. Many of its deepest branches exist to explain individual noisy examples: the mislabeled fruit, the one strange customer. Those branches are memorisation, and they fail on new data. This is overfitting in its most visible form.

Cost-complexity pruning fixes it with an accountant's trick: charge the tree rent for every leaf. A branch survives only if the errors it prevents are worth more than the rent its leaves cost. The rent level is a knob called alpha. Zero rent keeps the wild tree. Infinite rent prunes everything down to a stump that answers one word.

How it works

alpha = 0        alpha = a little        alpha = too much

    grown wild        pruned sensibly          a stump
   ╱╲  ╱╲  ╱╲            ╱╲
  ╱╲╱╲╱╲╱╲╱╲            ╱  ╲                     │
 (27 leaves,          (8 leaves,             (1 leaf,
  memorised           kept what              knows
  the noise)          generalises)           nothing)

A real example you have seen

Exam preparation. One classmate memorises every past question, including the misprinted ones — brilliant on last year's paper, lost on a fresh one. Another learns the eight ideas the questions keep circling. Pruning turns the first student into the second, by charging rent per memorised detail.

Remember this

  • A fully grown tree memorises noise; its perfect training score is a warning sign.
  • Pruning charges rent per leaf — branches that don't pay for themselves get cut.
  • Alpha sets the rent: zero keeps the jungle, too much leaves a stump.

What to learn next

Developer — Code and libraries.

Setup

bash
pip install scikit-learn

Outputs verified with scikit-learn 1.7.2 on CPU.

Watch the rent do its work

prune.py
import numpy as np
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

# synthetic tabular data with deliberately noisy labels (flip_y)
X, y = make_classification(n_samples=400, n_features=8, n_informative=4,
                           flip_y=0.15, random_state=42)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.5, random_state=42)

for alpha in (0.0, 0.005, 0.01, 0.02, 0.05, 0.1):
    t = DecisionTreeClassifier(random_state=42, ccp_alpha=alpha).fit(Xtr, ytr)
    print(f"alpha={alpha:<6}: leaves={t.get_n_leaves():3d}  "
          f"train={t.score(Xtr, ytr):.2f}  test={t.score(Xte, yte):.2f}")
Output
alpha=0.0   : leaves= 27  train=1.00  test=0.79
alpha=0.005 : leaves= 23  train=0.99  test=0.82
alpha=0.01  : leaves= 10  train=0.93  test=0.82
alpha=0.02  : leaves=  8  train=0.91  test=0.82
alpha=0.05  : leaves=  5  train=0.84  test=0.82
alpha=0.1   : leaves=  1  train=0.51  test=0.50

The walkthrough

Read the first row like a doctor. 27 leaves, perfect training score, 0.79 on unseen data. The 0.21 gap is the tree's memorised noise — we planted that noise ourselves with flip_y=0.15, which mislabels 15% of examples on purpose.

Rows two to five are the point of this lesson. From 27 leaves down to 5 — a tree one-fifth the size — the test score holds at 0.82. Twenty-two leaves existed only to explain flipped labels. The pruned tree is also faster, smaller in memory, and shallow enough to read aloud.

The last row is the stump. Rent so high that no split pays; one leaf, coin-flip accuracy. Pruning is a dial between jungle and stump, and the useful setting lies between.

Choosing alpha honestly. The candidate alphas are not guesses — the fitted tree can enumerate every rent level at which some branch stops paying:

python
path = DecisionTreeClassifier(random_state=42).cost_complexity_pruning_path(Xtr, ytr)
print(len(path.ccp_alphas), "candidate alphas, e.g.", path.ccp_alphas[:3].round(4))
Output
18 candidate alphas, e.g. [0.     0.0046 0.0047]

Cross-validate over path.ccp_alphas (a GridSearchCV over ccp_alpha works) and keep the winner.

Common mistakes

Choosing alpha on the test set. Sweeping alpha, reading test scores, keeping the best — that quietly turns the test set into training data. Choose with cross-validation on the training half; touch the test set once.

Pruning instead of, rather than alongside, growth limits. max_depth and min_samples_leaf stop the jungle from growing; ccp_alpha trims what grew. They compose well — a mild depth cap plus tuned alpha is a robust default.

Expecting pruning to fix bad features. Pruning removes memorisation. It cannot create signal that the features never contained; a pruned tree on junk inputs is a small tree that is still wrong.

Pruning trees inside a random forest. Random forests counter overfitting by averaging many deliberately overgrown trees. Pruning each member usually hurts; leave forest trees wild.

Try it yourself

Set flip_y=0.0 — noise-free labels — and rerun the sweep. Predict first: will the unpruned tree's train/test gap shrink? Then find, by cross-validation over path.ccp_alphas, the alpha you would actually ship.

What to learn next

Researcher — Mathematics and papers.

The pruning objective

For a subtree $T$ of the fully grown tree $T_{max}$, define the cost-complexity criterion:

$$ R_\alpha(T) = R(T) + \alpha \, |\tilde{T}| $$

Where:

  • $R(T)$ — the training error (misclassification rate or total impurity) of subtree $T$.
  • $|\tilde{T}|$ — the number of terminal leaves in $T$.
  • $\alpha \geq 0$ — the complexity price per leaf: the "rent".

For each $\alpha$, the subtree minimising $R_\alpha$ is the pruned tree. As $\alpha$ rises from 0, the optimal subtrees form a nested sequence $T_{max} \supset T_1 \supset \dots \supset {root}$ — a key theorem of Breiman, Friedman, Olshen and Stone (1984), Classification and Regression Trees, ch. 3. Only $O(|\tilde{T}_{max}|)$ distinct alphas matter — the values returned by cost_complexity_pruning_path.

For any internal node $t$, collapsing its branch changes error by $R(t) - R(T_t)$ while removing $|\tilde{T}_t| - 1$ leaves, so the branch stops paying at:

$$ g(t) = \frac{R(t) - R(T_t)}{|\tilde{T}_t| - 1} $$

with $T_t$ the branch rooted at $t$ and $R(t)$ the error if $t$ became a leaf. Prune the node with the smallest $g(t)$ — the weakest link — record that $g$ as the next alpha, and repeat. The full sequence costs $O(|T|^2)$ worst case, $O(|T| \log |T|)$ typical.

Breiman's original protocol picks the final alpha by cross-validation, often with the 1-SE rule: among candidate subtrees, take the smallest whose CV error is within one standard error of the minimum — trading a statistically negligible score difference for a genuinely smaller model.

Relation to other regularisers

The $\alpha |\tilde{T}|$ penalty is an $\ell_0$-flavoured complexity charge, the tree cousin of the penalties in ridge and lasso: fit-plus-penalty with a dial trading them. Pre-pruning (depth caps, minimum leaf sizes) bounds the hypothesis space before fitting; post-pruning searches the grown tree's subtree lattice afterwards and can rescue splits that look weak early but enable strong ones below — the lookahead failure pre-pruning cannot fix.

Context: C4.5 uses a different scheme (pessimistic error-based pruning; Quinlan, 1993). Ensembles changed the economics — bagged and boosted trees regularise by averaging and shrinkage instead, which is why ccp_alpha defaults to 0 in scikit-learn and pruning is mainly used when a single interpretable tree is the deliverable.

What to learn next