Tree Pruning: Cost-Complexity Pruning
You'll learn why fully grown decision trees overfit and how cost-complexity pruning strategically trims them back for better generalization.
Why Fully Grown Trees Overfit
When you let a decision tree grow to its maximum depth (as CART does by default), it creates highly specific rules for your training data. Imagine a tree that splits until each leaf contains just one or two training examples—it memorizes the training set perfectly, including all its noise and outliers. This is classic overfitting: great training performance, poor test performance.
The Pruning Solution
Cost-complexity pruning (also called weakest link pruning) provides a systematic way to simplify trees by removing branches that don't substantially improve predictions.
The key idea: balance two competing goals:
- Model accuracy (lower error)
- Model simplicity (fewer nodes)
How Alpha (α) Controls the Tradeoff
Cost-complexity pruning introduces a parameter alpha (α) that penalizes tree complexity:
Cost = Training Error + α × (Number of Leaf Nodes)
- When α = 0: No penalty for complexity → keep the full tree
- When α is large: Heavy penalty → aggressive pruning → smaller tree
- When α is optimal: Sweet spot between underfitting and overfitting
Think of α like a budget: it costs you to keep branches in the tree. You only keep branches that "pay for themselves" by reducing error enough to justify their complexity cost.
The algorithm tests different α values, removes subtrees that don't pull their weight, and uses cross-validation to find the α that maximizes generalization performance.
Key Takeaway: Cost-complexity pruning prevents overfitting by removing decision tree branches that add complexity without proportional accuracy gains, controlled by the α hyperparameter that trades off fit quality against tree size.