Decision Tree Pruning: Pre-Pruning and Post-Pruning

An unconstrained decision tree will grow until every leaf is pure — one sample per leaf if necessary. On training data this achieves 100% accuracy. On test data it fails badly: the tree has memorized noise rather than learned a generalizable pattern. Pruning limits tree growth to prevent this.

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
)

Why Trees Overfit Without Constraints

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}")

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 quirks of the training data. Train accuracy is 100% (memorized) but test accuracy is 92.98% — a 7% gap from overfitting.

Pre-Pruning Strategy 1: max_depth

Limit 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}")

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.

Pre-Pruning Strategy 2: 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}")

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.

Pre-Pruning Strategy 3: 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}")

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

Finding the Best Combination with GridSearchCV

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}")

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

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.

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. As $\alpha$ increases, leaves become more expensive — subtrees get pruned until only the root remains.

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}]")

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]}")

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.

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

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?