Problem:

Decision trees tend to overfit the training data because they keep splitting until every data point is perfectly classified, even if the splits capture noise.

🛑 How to Avoid Overfitting

1. Early Stopping (Pre-pruning)

Stop the tree from growing too deep.

• Define max_depth: Set a limit on how deep the tree can grow.
  • ✅ Pros: Simple to implement.
  • ❌ Cons: May stop useful splits on one side to maintain balance.
    • For example, in XOR problems, early stopping might halt growth at the root level because initial splits don’t improve accuracy.
• Other early stopping criteria:
  • Minimum number of samples per leaf (min_samples_leaf)
  • Minimum information gain required to split

2. Post-pruning (Pruning After Tree is Grown)

Let the tree grow fully, then prune branches that don't contribute much.

• Cost Complexity Pruning (a.k.a. Weakest Link Pruning):

  • Define a cost function:

    Cost = Error + α × Complexity

    • Error: Misclassification error (or Gini/entropy loss)
    • Complexity: Number of nodes (or depth)
    • α (alpha): Regularization parameter

  • For each non-leaf node:

    • Check if removing the split reduces the cost.
    • If yes, prune the node (turn it into a leaf).

✅ This balances model accuracy and simplicity, helping generalization.

💡 Summary