Deciding when to stop growing a recursively partitioned decision tree cannot be settled by early stopping — halting a branch when the best single-variable split yields negligible error improvement — because a greedy one-variable-at-a-time search is blind to interaction effects, where no individual split helps but a sequence of splits does. The accepted alternative is to grow the tree fully until each leaf holds fewer than a small minimum number of observations, then prune back: reduced error pruning collapses internal nodes while a held-out validation set does not worsen, whereas cost-complexity (weakest-link) pruning selects, among the subtrees of the fully grown tree, the one minimising average prediction error plus alpha times the number of leaves. The complexity parameter alpha, which trades accuracy against tree size, is chosen by cross validation, placing tree pruning within the general regularized model-selection framework shared with ridge regression and the lasso.
Deciding when to stop growing a recursively partitioned decision tree cannot be settled by early stopping — halting a branch when the best single-variable split yields negligible error improvement — …