M2-022M2: Classical Machine LearningDecision TreesEasy
⚡Flashcard Drill➔Mastery:

Explain Decision Tree Splitting Criteria: Information Gain, Gain Ratio, and Gini Impurity

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M2-023 →
📐 Mathematical Definition
Gini=1−∑kpk2,IG=H(D)−∑v∣Dv∣∣D∣H(Dv)\text{Gini}=1-\sum_k p_k^2,\qquad \text{IG}=H(D)-\sum_v\frac{|D_v|}{|D|}H(D_v)
⚡ One-Sentence Core Answer
Decision trees split nodes to maximize the reduction in impurity: Information Gain uses Shannon Entropy, Gain Ratio normalizes by split entropy, and Gini Impurity uses quadratic misclassification probability.

📌 Key Takeaways

  • •
    Entropy (ID3): H(S)=−∑k=1Kpklog⁡2pkH(S) = -\sum_{k=1}^K p_k \log_2 p_k; Information Gain IG(S,A)=H(S)−∑v∣Sv∣∣S∣H(Sv)\text{IG}(S, A) = H(S) - \sum_{v} \frac{|S_v|}{|S|} H(S_v).
  • •
    Gain Ratio (C4.5): GR(S,A)=IG(S,A)SplitInfo(S,A)\text{GR}(S, A) = \frac{\text{IG}(S, A)}{\text{SplitInfo}(S, A)}, penalizing high-cardinality features.
  • •
    Gini Impurity (CART): G(S)=1−∑k=1Kpk2G(S) = 1 - \sum_{k=1}^K p_k^2; computationally faster (no logarithms), standard in scikit-learn.

📐 Mathematical Derivations

Gini Impurity interpretation: G(S)=∑k=1Kpk(1−pk)=1−∑k=1Kpk2G(S) = \sum_{k=1}^K p_k (1 - p_k) = 1 - \sum_{k=1}^K p_k^2. This represents the probability that a randomly chosen element from the set would be incorrectly labeled if it were randomly labeled according to the class distribution. Comparison with Entropy: Taylor expanding log⁡2(pk)\log_2(p_k) around 11: ln⁡(pk)=ln⁡(1−(1−pk))≈−(1−pk)\ln(p_k) = \ln(1 - (1 - p_k)) \approx -(1 - p_k). Thus H(S)=−∑pkln⁡pk≈∑pk(1−pk)=G(S)H(S) = -\sum p_k \ln p_k \approx \sum p_k (1 - p_k) = G(S). In binary classification with p=P(y=1)p = P(y=1): G(p)=2p(1−p)G(p) = 2p(1-p) is a parabola with maximum 0.50.5 at p=0.5p=0.5; Entropy H(p)=−plog⁡2p−(1−p)log⁡2(1−p)H(p) = -p\log_2 p - (1-p)\log_2(1-p) peaks at 1.01.0. Both are strictly concave, ensuring that any split strictly reduces expected impurity.

🏭 Production Trade-offs

Algorithmic choices: (1) ID3 vs C4.5: ID3 suffers from extreme bias toward high-cardinality features (e.g. Splitting on User_ID creates NN pure leaves with IG=H(S)\text{IG} = H(S), but zero generalization power). C4.5 divides by SplitInfo=−∑∣Sv∣∣S∣log⁡∣Sv∣∣S∣\text{SplitInfo} = -\sum \frac{|S_v|}{|S|}\log\frac{|S_v|}{|S|} to penalize broad fan-outs. (2) CART: Uses Gini impurity and strictly binary splits, eliminating the need for expensive logarithmic evaluations and producing balanced binary trees.
⚠️ Common Interview Pitfalls
  • ✕
    Using Information Gain on high-cardinality IDs or timestamps without Gain Ratio normalization.
  • ✕
    Believing Gini and Entropy produce substantially different decision trees (in 98% of cases, both select identical split points).
🎯 Interviewer Follow-up Inquiries
  • ?
    Why does CART enforce strictly binary splits while C4.5 allows multi-way splits?
  • ?
    What is the variance reduction split criterion used for regression trees in CART?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM2-021: Define Selection Bias in Model Selection and How to Prevent Leakage in Predictive Pipelines📋 Back to BankNext →M2-023: Detail Pre-Pruning and Post-Pruning Strategies to Prevent Overfitting in Decision Trees