Home / Summaries / COMP 3711 / split-post-pruning-records

Classification - Overfitting & Pruning

4 important questions on Classification - Overfitting & Pruning

What is overfitting in the context of decision trees?

Overfitting occurs when the tree grows too large and fits the specific noise or quirks of the training data — memorising class labels for rare or coincidental patterns rather than learning general rules. Result: very high training accuracy, poor test accuracy. The tree fails to generalise.

What are the stopping criteria that prevent a node from splitting further?

All records at the node belong to the same class → pure leaf, nothing to split
All records have identical attribute values → no split is possible
The number of records falls below a minimum threshold → too few records to support a reliable split
(Pre-pruning) Information gain of the best split falls below a threshold → split not worth making

Compare pre-pruning and post-pruning. Which is generally better and why?

Pre-pruning (early stopping):

When: stop growing during induction
Mechanism: halt if gain falls below threshold
Risk: XOR/Matching Pennies problem — stops before discovering jointly-useful attributes

Post-pruning:

When: grow full tree, then trim
Mechanism: remove branches failing statistical test (e.g., χ²)
Risk: may overfit during growth phase

Post-pruning is generally superior because it can discover complex joint feature interactions (like XOR) that pre-pruning would miss by stopping when individual gains are zero. Pre-pruning is faster but can be fooled by individually-uninformative-but-jointly-predictive attributes.

What is χ² pruning?

χ² pruning is a statistical significance test applied during post-pruning. It tests whether the class distribution in a node's children is significantly different from what would be expected by random chance (the null hypothesis of independence).
If the difference is not statistically significant, the split is pruned — the branch is replaced by a leaf. This prevents the tree from fitting noise that happened to appear in the training sample.

The question on the page originate from the summary of the following study material:

COMP 3711

View summary