Cost-Complexity Pruning

A decision tree can keep splitting until it perfectly fits the training data—like memorizing every example. The problem is that “perfect memory” usually means worse predictions on new data. Cost-complexity pruning is a principled way to trim a tree back to the size that generalizes well.

What it is and what it optimizes

Cost-complexity pruning (also called weakest-link pruning) chooses a subtree by balancing two things: how well the tree fits the training data and how complicated the tree is. It does this with an objective like:

R_α(T) = R(T) + α · |T|

Here R(T) is the training error (for classification, impurity-based error; for regression, squared error), |T| is the number of leaves (a proxy for complexity), and α controls how much you penalize complexity. Larger α pushes toward smaller trees.

How the pruning actually happens

You start with a fully grown tree, then repeatedly remove the “weakest link”: the internal node whose removal increases training error the least per leaf removed. This generates a sequence of nested subtrees from large to small. You then pick the best subtree by evaluating candidates—typically with cross-validation—over different α values.

Why it matters in real supervised tasks

• Spam detection: prevents rules that key off rare, quirky words seen only in training.
• Credit scoring: avoids overly specific splits that look great historically but fail on new applicants.
• House price prediction: reduces sensitivity to noise (e.g., one odd sale driving a deep branch).

In scikit-learn, this is exposed via minimal cost-complexity pruning using ccp_alpha in DecisionTreeClassifier/DecisionTreeRegressor, and you can inspect candidate alphas with cost_complexity_pruning_path.