Decision Tree Pruning

Pruning deliberately limits how large a decision tree is allowed to grow — trading a small amount of training accuracy for a tree that generalizes far better to new data.

Why an Unpruned Tree Overfits

Left unrestricted, a decision tree will keep splitting until every leaf is perfectly pure — often down to leaves containing a single training example. Such a tree hasn't learned a general pattern; it's essentially memorized the training set, including its noise. See Decision Tree Overfitting for this failure mode in full detail.

Full Tree vs Pruned Tree

Pre-Pruning — Stopping Growth Early

from sklearn.tree import DecisionTreeClassifier

model = DecisionTreeClassifier(
    max_depth=4,              # limit how many splits deep the tree can go
    min_samples_split=10,      # require at least 10 samples to consider splitting a node
    min_samples_leaf=5,         # require at least 5 samples in every leaf
    random_state=42,
)

Pre-pruning is fast — it stops the tree from growing in the first place, based on rules set before training.

Post-Pruning — Cost-Complexity Pruning

Grow the tree fully first, then trim back branches that don't improve validation performance enough to justify their added complexity — scikit-learn implements this via ccp_alpha:

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_score
import numpy as np

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

scores = []
for alpha in alphas:
    pruned_tree = DecisionTreeClassifier(random_state=42, ccp_alpha=alpha)
    cv_scores = cross_val_score(pruned_tree, X_train, y_train, cv=5)
    scores.append(cv_scores.mean())

best_alpha = alphas[np.argmax(scores)]
final_model = DecisionTreeClassifier(random_state=42, ccp_alpha=best_alpha).fit(X_train, y_train)

Larger \(\alpha\) values prune more aggressively — this loop finds, via cross-validation, the \(\alpha\) that best balances tree complexity against generalization.

Practical Use Cases

• Every production decision tree should use some form of pruning — an unpruned tree is rarely the right choice for deployment

Common Mistakes

• Only using pre-pruning parameters picked by intuition, without validating them via cross-validation.
• Pruning so aggressively the tree underfits — like choosing k in KNN, this is a tuning problem, not a one-shot decision.

Interview Relevance

Q: "What's the difference between pre-pruning and post-pruning?" Pre-pruning stops tree growth early using rules like max depth or minimum samples per leaf, set before training; post-pruning grows the full tree first, then trims back branches that don't sufficiently improve validation performance, using a complexity penalty like ccp_alpha.

Practice Question

You prune a tree with an increasingly large ccp_alpha and watch training accuracy steadily decrease. Is this itself evidence the pruning is a mistake? Explain.

Related ML Notes

• Decision Tree Overfitting
• Cross-Validation
• Hyperparameter Tuning