Course contentsShow
← Computer Science
Lesson 2851 of 2,87263. Classical ML AlgorithmsFree lesson

Cost-Complexity Pruning

Using a complexity parameter to balance tree size against training accuracy when post-pruning a decision tree.

Cost-Complexity Pruning

What you'll learn: How to use a complexity parameter to automatically find the optimal balance between tree size and training accuracy when post-pruning a decision tree.

The Problem with Unpruned Trees

You've seen that decision trees can overfit by growing too large. Post-pruning removes branches after the tree is fully grown, but how much should you prune? Remove too little, and you still overfit. Remove too much, and you underfit.

The Core Idea

Cost-Complexity Pruning (also called "weakest link pruning") uses a complexity parameter α (alpha) to balance two competing goals:

  1. Accuracy on training data (lower error)
  2. Simplicity (fewer leaf nodes)

For every subtree T, we calculate a cost-complexity criterion:

Cost(T) = TrainingError(T) + α × |Leaves(T)|

Where |Leaves(T)| is the number of leaf nodes in subtree T.

How It Works

  • Small α: Penalizes complexity weakly → larger trees survive
  • Large α: Penalizes complexity strongly → aggressive pruning
  • Process: Start with the full tree, gradually increase α, and prune the subtree that increases cost-complexity the least at each step

This produces a sequence of progressively simpler trees. You then use cross-validation to pick the α (and corresponding tree size) that generalizes best.

Analogy

Think of α as a "tidiness tax." Each leaf in your tree costs α dollars. When α is low, you can afford a messy, detailed tree. As α increases, you're forced to justify every leaf—keeping only the branches that meaningfully reduce error.

Key Takeaway: Cost-complexity pruning uses parameter α to generate candidate pruned trees, balancing training accuracy against tree complexity, with the optimal α chosen via validation data.