Decision Tree Pruning: Pre-Pruning and Post-Pruning

You train your first full decision tree. Training accuracy: 100%. You feel great. Then you check the test accuracy: 92.98%. You feel confused. The tree memorized every sample in training and learned almost nothing generalizable.

This is overfitting. Every unconstrained tree does it — it will grow until every leaf is pure, one leaf per sample if needed. Pruning is how you stop it. You can either stop the tree from growing too deep (pre-pruning) or grow the full tree and then cut away the weak branches (post-pruning).

Anchor dataset: Breast Cancer Wisconsin — 30 features, binary classification (malignant/benign), 569 samples.

from sklearn.datasets import load_breast_cancer
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
import numpy as np

data = load_breast_cancer()
X, y = data.data, data.target

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

What It Is

Pruning is regularization for trees. For linear models, you add a penalty on large coefficients. For trees, you limit how many splits they can make. Pre-pruning stops growth during training (via max_depth, min_samples_split, min_samples_leaf). Post-pruning grows the tree fully first, then removes subtrees that don't improve generalization enough (via ccp_alpha). This is not the same as feature selection — you're not choosing which features matter; you're controlling how much the tree can contort itself to fit the training data.

The Plan — Five Strategies to Tame Overfitting

We'll start by seeing how badly the unconstrained tree overfits. Then we try three pre-pruning strategies: max_depth, min_samples_split, and min_samples_leaf. We'll find the best combination with GridSearchCV. Finally, we try post-pruning with Cost Complexity Pruning (CCP) and compare the two approaches.

Strategy 1: See the Overfitting Gap

Let's see exactly how bad the overfitting is. We train a tree with no constraints (DecisionTreeClassifier with default params — which means no limit on depth or leaf size). We set random_state=42 for reproducibility — sklearn's tree uses randomness to break ties at splits, and a fixed seed ensures we get the same tree each time.

dt_full = DecisionTreeClassifier(random_state=42)
dt_full.fit(X_train, y_train)

print(f"Max depth:  {dt_full.get_depth()}")
print(f"Leaf count: {dt_full.get_n_leaves()}")
print(f"Train accuracy: {dt_full.score(X_train, y_train):.4f}")
print(f"Test accuracy:  {dt_full.score(X_test, y_test):.4f}")

Max depth:  7
Leaf count: 43
Train accuracy: 1.0000
Test accuracy:  0.9298

43 leaves for 455 training samples — roughly 10 samples per leaf on average. Some leaves contain 1–2 samples that happen to land there by training data quirks. Train accuracy is 100% (memorized) but test accuracy is 92.98% — a 7% gap.

✓ Overfitting confirmed. The unconstrained tree memorizes the training set.

Pre-Pruning Strategy 2: Limit max_depth

Goal: cap how deep the tree can grow before stopping.

print(f"{'depth':>6} | {'train':>8} | {'test':>8} | {'leaves':>7}")
for d in [1, 2, 3, 4, 5, 6, None]:
    dt = DecisionTreeClassifier(max_depth=d, random_state=42)
    dt.fit(X_train, y_train)
    tr = dt.score(X_train, y_train)
    te = dt.score(X_test, y_test)
    lv = dt.get_n_leaves()
    print(f"{str(d):>6} | {tr:>8.4f} | {te:>8.4f} | {lv:>7}")

depth |    train |     test | leaves
     1 |   0.8967 |   0.8860 |      2   ← underfit
     2 |   0.9385 |   0.9298 |      4
     3 |   0.9560 |   0.9561 |      7
     4 |   0.9714 |   0.9649 |     13   ← sweet spot
     5 |   0.9824 |   0.9561 |     22
     6 |   0.9978 |   0.9386 |     37
  None |   1.0000 |   0.9298 |     43   ← overfit

Train accuracy (orange dashed) rises monotonically to 1.0. Test accuracy (blue) peaks at depth=4 (96.5%) then falls as the tree starts memorizing training quirks. The gap between train and test widens after depth=4.

✓ Strategy 2 complete. Best max_depth = 4 (test accuracy 96.49%). Deeper = overfit, shallower = underfit.

Pre-Pruning Strategy 3: min_samples_split

A node is only split if it contains at least min_samples_split samples. This prevents creating splits on very small groups.

print(f"{'min_split':>10} | {'train':>8} | {'test':>8} | {'leaves':>7}")
for ms in [2, 5, 10, 20, 30, 50, 100]:
    dt = DecisionTreeClassifier(min_samples_split=ms, random_state=42)
    dt.fit(X_train, y_train)
    print(f"{ms:>10} | {dt.score(X_train, y_train):>8.4f} | {dt.score(X_test, y_test):>8.4f} | {dt.get_n_leaves():>7}")

min_split |    train |     test | leaves
         2 |   1.0000 |   0.9298 |     43
         5 |   1.0000 |   0.9298 |     43
        10 |   0.9978 |   0.9386 |     37
        20 |   0.9956 |   0.9561 |     27
        30 |   0.9824 |   0.9561 |     22
        50 |   0.9736 |   0.9649 |     17
       100 |   0.9429 |   0.9298 |      9

Increasing min_samples_split from 2 to 50 improves test accuracy from 92.98% to 96.49% by preventing splits on small, noisy groups. Beyond 100, underfitting sets in.

✓ Strategy 3 complete. Best min_samples_split = 50 (test accuracy 96.49%). Controls split frequency on small groups.

Pre-Pruning Strategy 4: min_samples_leaf

A leaf must contain at least min_samples_leaf samples. This is stricter than min_samples_split — it ensures both children of any split have enough samples.

for ml in [1, 2, 5, 10, 20]:
    dt = DecisionTreeClassifier(min_samples_leaf=ml, random_state=42)
    dt.fit(X_train, y_train)
    print(f"min_samples_leaf={ml:>3}: leaves={dt.get_n_leaves():>3}, test={dt.score(X_test, y_test):.4f}")

min_samples_leaf=  1: leaves= 43, test=0.9298
min_samples_leaf=  2: leaves= 32, test=0.9386
min_samples_leaf=  5: leaves= 19, test=0.9474
min_samples_leaf= 10: leaves= 12, test=0.9561
min_samples_leaf= 20: leaves=  7, test=0.9649

Each increase in min_samples_leaf removes small leaves and improves test accuracy up to a point.

✓ Strategy 4 complete. Best min_samples_leaf = 20 (test accuracy 96.49%). Controls minimum leaf size.

Strategy 5: Combine Them with GridSearchCV

Each parameter alone helps, but they interact. A deep tree with a large min_samples_leaf behaves differently from a shallow tree with a small one. GridSearchCV tries all combinations and uses cross-validation to pick the best. We set cv=10 for 10-fold cross-validation (each fold has ~55 test samples, stable for this dataset size). n_jobs=-1 runs all 60 combinations in parallel across CPU cores. We score on accuracy because the classes are fairly balanced.

from sklearn.model_selection import GridSearchCV

param_grid = {
    'max_depth': [3, 4, 5, 6, None],
    'min_samples_split': [2, 5, 10, 20],
    'min_samples_leaf': [1, 5, 10],
}
gs = GridSearchCV(
    DecisionTreeClassifier(random_state=42),
    param_grid, cv=10, scoring='accuracy', n_jobs=-1
)
gs.fit(X_train, y_train)
print(f"Best params: {gs.best_params_}")
print(f"Best CV accuracy: {gs.best_score_:.4f}")
print(f"Test accuracy: {gs.best_estimator_.score(X_test, y_test):.4f}")

Best params: {'max_depth': 4, 'min_samples_leaf': 5, 'min_samples_split': 10}
Best CV accuracy: 0.9647
Test accuracy: 0.9737

The best pre-pruned tree: depth=4, min_samples_leaf=5, min_samples_split=10. This matches our intuition from the individual sweeps.

✓ Strategy 5 complete. Best pre-pruning combo found: depth=4, min_leaf=5, min_split=10, test accuracy = 97.37%.

Post-Pruning: Cost Complexity Pruning (CCP)

Pre-pruning stops growth early. Post-pruning grows the full tree first, then removes subtrees that don't justify their complexity.

Here's the key idea in equation form: CART's cost complexity pruning adds a penalty $\alpha$ per leaf. The effective tree is the one that minimizes:

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

where $R(T)$ is the total leaf impurity and $|T|$ is the number of leaves. It's like ridge regression's penalty on coefficients — as $\alpha$ increases, leaves become more expensive and subtrees get pruned until only the root remains.

Let's get the pruning path from sklearn. The cost_complexity_pruning_path method returns all possible alpha values where some subtree would be pruned — 44 values for our tree.

dt_full = DecisionTreeClassifier(random_state=42)
path = dt_full.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas

print(f"Number of alpha values: {len(ccp_alphas)}")
print(f"Alpha range: [{ccp_alphas[0]:.6f}, {ccp_alphas[-1]:.4f}]")

Number of alpha values: 44
Alpha range: [0.000000, 0.4997]

clfs, train_scores, test_scores, leaf_counts = [], [], [], []
for alpha in ccp_alphas:
    clf = DecisionTreeClassifier(random_state=42, ccp_alpha=alpha)
    clf.fit(X_train, y_train)
    clfs.append(clf)
    train_scores.append(clf.score(X_train, y_train))
    test_scores.append(clf.score(X_test, y_test))
    leaf_counts.append(clf.get_n_leaves())

best_idx = np.argmax(test_scores)
print(f"Best alpha: {ccp_alphas[best_idx]:.6f}")
print(f"Best test accuracy: {test_scores[best_idx]:.4f}")
print(f"Leaves at best alpha: {leaf_counts[best_idx]}")

Best alpha: 0.005000
Best test accuracy: 0.9737
Leaves at best alpha: 12

At $\alpha =0.005$: 12 leaves, 97.37% test accuracy — identical to the pre-pruned GridSearch result. The optimal tree has 12 leaves whether found by pre-pruning or CCP.

✓ Post-pruning complete. Best CCP alpha = 0.005, 12 leaves, test accuracy = 97.37%.

Trace Table: Pruning Strategy Comparison

Left: leaf count decreases as $\alpha$ increases. Center: test accuracy (blue) peaks at $\alpha =0.005$, train (orange) decreases monotonically. Right: test accuracy peaks at 12 leaves, then drops at both extremes.

Pre-Pruning vs Post-Pruning

Pruning Parameter Summary

Related Concepts

Pruning is the earliest form of regularization in tree models. The same concept scales directly to ensemble methods: Random Forest controls variance by averaging many uncorrelated trees (not pruning individual ones), while Gradient Boosting controls it through learning rate and shallow max_depth on each weak learner. CCP's $\alpha$ penalty per leaf is directly analogous to the $\lambda$ regularization parameter in ridge regression — both penalize model complexity to reduce overfitting.

Honest Limitations

I learned the hard way that GridSearchCV doesn't scale. $5\times 4\times 3=60$ combinations with 10-fold CV means 600 tree fits — fast on 569 samples, but on a dataset with 1M samples each tree takes seconds. I once kicked off a full grid search before lunch and came back to find it had been running for 3 hours. Now I use HalvingGridSearchCV or random search capped at 50–100 iterations for anything larger than 10K samples.

Pre-pruning with max_depth has a subtle trap I've fallen into: it terminates splitting too early at a genuinely informative subtree. A node at depth=4 with high IG gets cut off because you hit the depth limit, regardless of how valuable that split is. CCP doesn't have this problem because it grows the full tree first and prunes backward — it's more principled, but it requires fitting $O(n_{\alpha })$ trees ($n_{\alpha }=44$ here). For large datasets, building the full tree first can itself be prohibitive.

Test Your Understanding

1. The fully grown tree has 43 leaves for 455 training samples (~10 samples/leaf). If a leaf contains exactly 2 samples with different classes (1 Yes, 1 No), what is its entropy? What class does it predict, and what is its local training accuracy?

2. At max_depth=4: train=97.14%, test=96.49%. At max_depth=5: train=98.24%, test=95.61%. The test accuracy drops from depth 4 to 5 despite more training accuracy. Describe what changes in the tree between depth=4 and depth=5 that could explain this.

3. CCP starts with the full tree (alpha=0) and increases alpha. At each alpha value, which subtrees are pruned first — the ones at the top of the tree or the leaves at the bottom? Why?

4. Both pre-pruning (GridSearchCV) and post-pruning (CCP) found 97.37% test accuracy with approximately 12 leaves. Does this guarantee they found the same tree? What would you compare to check?

5. You have 10,000 training samples and want to choose between min_samples_leaf=10 and min_samples_leaf=100. The dataset has a rare class that appears in only 2% of samples (200 examples). How does this class imbalance affect your choice of min_samples_leaf?