Course contentsShow
← Machine Learning and Deep Learning
Lesson 290 of 3,5386. Tree-Based MethodsFree lesson

Tree Pruning: Cost-Complexity Pruning

Why fully grown trees overfit, and how cost-complexity (alpha) pruning reduces tree size while maintaining performance.

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:

  1. Model accuracy (lower error)
  2. 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.