Pruning & Tree Regularization

Why Decision Trees Need Pruning

If you train a Decision Tree without stopping constraints, it will continue splitting nodes until every leaf is completely pure (often containing just 1 sample).

  UNPRUNED DEEP TREE (High Variance / Overfitting):
  - 100% Accuracy on Training Data (Memorized Noise!)
  - Terrible Accuracy on Test Data (Fails to Generalize!)

  PRUNED BALANCED TREE (Low Variance / Good Generalization):
  - 94% Accuracy on Training Data
  - 93% Accuracy on Test Data (Learned True Patterns!)

Tree Pruning trims away weak branches that capture noise, simplifying the tree structure.

┌──────────────────────────┬──────────────────────────┐
│ 1. PRE PRUNING           │ 2. POST PRUNING          │
├──────────────────────────┼──────────────────────────┤
│ Early stopping rules     │ Grows a full deep tree   │
│ applied DURING training. │ first, then collapses    │
│ Fast, but risks stopping │ subtrees BACKWARD.       │
│ split discovery early.   │ Cost Complexity Pruning! │
└──────────────────────────┴──────────────────────────┘

1. Pre-Pruning (Early Stopping)

Pre-Pruning stops expanding tree nodes during training as soon as a stopping rule is triggered:

1. max_depth: Caps maximum vertical tree depth (e.g. max_depth = 5).
2. min_samples_split: Minimum samples required in a node to attempt a split (e.g. min_samples_split = 20).
3. min_samples_leaf: Minimum samples required in every final leaf node (e.g. min_samples_leaf = 10).
4. max_leaf_nodes: Caps total leaf count across the entire tree.

Pros and Cons

• Pros: Fast training speed. Prevents building deep unneeded subtrees.
• Cons: Horizon Effect (A split that looks unpromising now might unlock powerful combined splits deeper down).

2. Post-Pruning (Cost Complexity Pruning)

Post-Pruning allows the tree to grow to its full depth first, discovering complex multi split interactions.

Then, it collapses non essential subtrees backward using Cost Complexity Pruning ($\alpha$ pruning):

$$R_\alpha(T) = R(T) + \alpha |T|$$

• $R(T)$: Total training error or impurity of tree $T$.
• $|T|$: Number of leaf nodes in tree $T$.
• $\alpha$ (ccp_alpha in scikit-learn): Complexity penalty parameter.

How Cost Complexity Pruning Works

1. Compute effective $\alpha$ value for every non-leaf subtree node.
2. Slowly increase $\alpha$ from $0.0$ upwards.
3. Prune subtrees whose removal causes the smallest increase in training error per leaf node saved.
4. Select the optimal $\alpha$ using 5-fold cross validation.

Say this out loud

Tree Pruning trims decision tree branches to eliminate overfitting. Pre-Pruning uses early stopping constraints like max depth and min samples per leaf during training. Post-Pruning grows a full deep tree first, then uses Cost Complexity Pruning to collapse subtrees that add excessive leaf complexity relative to validation accuracy gain.

Followups to expect

1. How do you choose ccp_alpha in scikit-learn? Extract ccp_alphas from clf.cost_complexity_pruning_path(X_train, y_train), train trees for each alpha, and select the alpha yielding highest cross validation score.
2. Is pruning necessary for Random Forests? Less necessary. Random Forests average hundreds of unpruned trees together to reduce variance. However, setting light pre pruning (like max_depth or min_samples_leaf) speeds up training and reduces model file size.