Chapter 107 – Decision Tree Pruning Explained
1. What Is Pruning?
Unrestricted trees grow until leaves are pure, often memorizing noise and overfitting. Pruning cuts weak branches so the tree stays smaller, simpler, and more reliable on unseen data. Two main approaches: pre-pruning and post-pruning.
2. Pre-Pruning (Early Stopping)
Stops growth during construction using limits such as:
- max_depth — maximum vertical levels
- min_samples_split — minimum samples required to split a node
- min_samples_leaf — minimum samples in a leaf (e.g. 5)
- Statistical thresholds — stop if Information Gain or Gini improvement is too small
Pros: fast, memory-efficient, simpler trees from the start.
Cons: greedy “horizon effect”—may cut a branch that looks weak now but would become useful deeper down.
3. Post-Pruning (Cost-Complexity / CCP)
Grow a full tree, then trim weak sub-trees using a complexity penalty:
Cost-Complexity = Sub-tree Error + (α × Tree Complexity)
- Small α — light pruning, most structure kept
- Large α — aggressive pruning; too large can drop accuracy toward ~50%
Pros: considers the whole tree, avoids the horizon effect, faster inference on the final small tree.
Cons: higher training cost (full tree first).
4. Pre-Pruning vs Post-Pruning
| Dimension |
Pre-Pruning |
Post-Pruning (CCP) |
| Timing |
During growth |
After full tree |
| Mechanism |
max_depth, min_samples_* |
ccp_alpha (α) |
| Training speed |
Faster |
Slower |
| Search |
Greedy (horizon effect) |
Exhaustive over sub-trees |
5. Python with Scikit-Learn
Data: 600-sample make_moons, noise=0.25, 70/30 split.
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score
X, y = make_moons(n_samples=600, noise=0.25, random_state=42)
X_train, X_test, y_train, y_test = train_test_split(
X, y, test_size=0.3, random_state=42
)
Pre-pruning loop (max_depth + min_samples_leaf=5):
for d in range(1, 16):
clf = DecisionTreeClassifier(
max_depth=d, min_samples_leaf=5, random_state=42
)
clf.fit(X_train, y_train)
# record train/test accuracy
In this setup, depth ~4 often balances accuracy (~90%) without clear overfitting.
Post-pruning with CCP:
full_tree = DecisionTreeClassifier(random_state=42)
full_tree.fit(X_train, y_train)
path = full_tree.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas
for alpha in ccp_alphas:
clf = DecisionTreeClassifier(ccp_alpha=alpha, random_state=42)
clf.fit(X_train, y_train)
# record train/test accuracy
Small α keeps high test accuracy; very large α over-prunes and accuracy can fall toward ~50%. A useful range is often around 0.01–0.02.
