Decision Trees

Decision Trees

1. Idea

Recursively split by the feature + threshold that best separates $y$. Leaf predicts majority (classification) or mean (regression). Path root → leaf = readable rule.

2. Split Criteria

• Classification: Gini $= 1 - \text{sum } p_{c}²$ or entropy $= - \text{sum } p_{c} log p_{c}$ (written with $log$ plain). Pick split with largest impurity drop (information gain).
• Regression: largest variance reduction.

Gini example: [6+,4-] → 1 - (0.36+0.16) = 0.48
split on x₁>5 gives pure children → gain = 0.48 - 0 = 0.48 (best)

3. Overfitting Control

Full tree memorizes. Prune via max depth, min samples per leaf, cost-complexity ($α$ penalty on leaves), tuned by CV.

4. Strengths / Limits

Interpretable, handles mixed types, no scaling needed. But high variance (small data change → different tree) and axis-aligned only → forests fix this (Module 4).

5. Exam Points

• Gini / entropy + gain numerical — 7 marks, very frequent.
• Tree trace on tiny dataset — 5 marks, frequent.
• Pruning parameters — 3 marks, frequent.