Unit 4: Decision Trees & Ensemble Learning

Course - Machine Learning Algorithms (21CSC555J)
Assessment - Continuous Test 2 (CT-2)
Unit - Unit 4: Decision Trees (CART) & Ensemble Learning (AdaBoost)
Total Weightage - 40 Marks (Question 3: 20 Marks; Question 4: 20 Marks)

---

Question 3: CART Classification Tree Construction (20 Marks)

info

Question Statement

A retail company wants to build a CART classification tree to decide whether a customer will Buy (Yes) or Not Buy (No) a product based on two attributes: Age Group and Annual Income Level.

The training dataset is as follows:

Customer	Age Group	Income Level	Buy
C1	Young	Low	No
C2	Young	Medium	No
C3	Middle	Low	Yes
C4	Middle	High	Yes
C5	Senior	Medium	Yes
C6	Senior	High	Yes
C7	Senior	Low	No

• (a) Calculate the Gini Index for the parent node (root) before any split. (4 Marks)
• (b) Compute the Gini Index for each possible split based on: (8 Marks)
  • Age Group
  • Income Level
• (c) Determine the Best Attribute to Split using Gini Index criterion. (4 Marks)
• (d) Explain what would happen if both attributes had the same Gini value. (2 Marks)
• (e) Mention two advantages of CART over ID3 or C4.5 decision trees. (2 Marks)

---

Solution 3

📝 Exam-Ready Answer (Crisp 20-Mark Structure)

---

(a) Gini Index for the Parent Node (Root) (4 Marks)

• Step 1: Class Distribution & Probabilities (2 Marks)

  • Total samples: $N = 7$
  • Class counts: $N_{\text{Yes}} = 4$ (C3, C4, C5, C6), $\; N_{\text{No}} = 3$ (C1, C2, C7)
  • Probabilities: $p_{\text{Yes}} = \frac{4}{7}, \; p_{\text{No}} = \frac{3}{7}$

• Step 2: Formula & Calculation (2 Marks) $\text{Gini}(\text{Root}) = 1 - \sum p_i^2 = 1 - \left[ \left(\frac{4}{7}\right)^2 + \left(\frac{3}{7}\right)^2 \right] = 1 - \frac{25}{49} = \mathbf{\frac{24}{49} \approx 0.4898}$

---

(b) Compute Gini Index for Each Possible Split (8 Marks)

CART strictly uses binary splits. For an attribute with $k=3$ discrete categories, there are $2^{k-1} - 1 = 3$ candidate binary partitions: $\text{Gini}_{\text{split}} = \frac{N_L}{N}\text{Gini}(D_L) + \frac{N_R}{N}\text{Gini}(D_R)$

1. Splits for Age Group ($k=3$: Young, Middle, Senior) (4 Marks)

• Partition 1: $\{\text{Young}\}$ vs $\{\text{Middle, Senior}\}$

  • Left ($N_L = 2$, Young): 0 Yes, 2 No $\implies \text{Gini}(D_L) = 1 - (0 + 1) = \mathbf{0.0}$ (Pure Leaf)
  • Right ($N_R = 5$, Mid+Sen): 4 Yes, 1 No $\implies \text{Gini}(D_R) = 1 - \left[\left(\frac{4}{5}\right)^2 + \left(\frac{1}{5}\right)^2\right] = 1 - \frac{17}{25} = \mathbf{0.320}$
  • Weighted Gini: $\frac{2}{7}(0.0) + \frac{5}{7}(0.320) = \frac{1.6}{7} \approx \mathbf{0.2286}$

• Partition 2: $\{\text{Middle}\}$ vs $\{\text{Young, Senior}\}$

  • Left ($N_L = 2$, Middle): 2 Yes, 0 No $\implies \text{Gini}(D_L) = \mathbf{0.0}$ (Pure Leaf)
  • Right ($N_R = 5$, Young+Sen): 2 Yes, 3 No $\implies \text{Gini}(D_R) = 1 - \left[\frac{4}{25} + \frac{9}{25}\right] = \mathbf{0.480}$
  • Weighted Gini: $\frac{2}{7}(0.0) + \frac{5}{7}(0.480) = \frac{2.4}{7} \approx \mathbf{0.3429}$

• Partition 3: $\{\text{Senior}\}$ vs $\{\text{Young, Middle}\}$

  • Left ($N_L = 3$, Senior): 2 Yes, 1 No $\implies \text{Gini}(D_L) = 1 - \left[\frac{4}{9} + \frac{1}{9}\right] = \frac{4}{9} \approx \mathbf{0.4444}$
  • Right ($N_R = 4$, Young+Mid): 2 Yes, 2 No $\implies \text{Gini}(D_R) = 1 - \left[\frac{4}{16} + \frac{4}{16}\right] = \mathbf{0.500}$
  • Weighted Gini: $\frac{3}{7}\left(\frac{4}{9}\right) + \frac{4}{7}(0.500) = \frac{10}{21} \approx \mathbf{0.4762}$

$\mathbf{\text{Best Split for Age Group: } \{\text{Young}\} \text{ vs } \{\text{Middle, Senior}\} \implies \text{Gini} \approx 0.2286}$

2. Splits for Income Level ($k=3$: Low, Medium, High) (4 Marks)

• Partition 1: $\{\text{Low}\}$ vs $\{\text{Medium, High}\}$

  • Left ($N_L = 3$, Low): 1 Yes, 2 No $\implies \text{Gini}(D_L) = 1 - \left[\frac{1}{9} + \frac{4}{9}\right] = \frac{4}{9} \approx \mathbf{0.4444}$
  • Right ($N_R = 4$, Med+High): 3 Yes, 1 No $\implies \text{Gini}(D_R) = 1 - \left[\frac{9}{16} + \frac{1}{16}\right] = \frac{6}{16} = \mathbf{0.375}$
  • Weighted Gini: $\frac{3}{7}\left(\frac{4}{9}\right) + \frac{4}{7}(0.375) = \frac{8.5}{21} \approx \mathbf{0.4048}$

• Partition 2: $\{\text{Medium}\}$ vs $\{\text{Low, High}\}$

  • Left ($N_L = 2$, Medium): 1 Yes, 1 No $\implies \text{Gini}(D_L) = 1 - [0.25 + 0.25] = \mathbf{0.500}$
  • Right ($N_R = 5$, Low+High): 3 Yes, 2 No $\implies \text{Gini}(D_R) = 1 - \left[\frac{9}{25} + \frac{4}{25}\right] = \mathbf{0.480}$
  • Weighted Gini: $\frac{2}{7}(0.500) + \frac{5}{7}(0.480) = \frac{3.4}{7} \approx \mathbf{0.4857}$

• Partition 3: $\{\text{High}\}$ vs $\{\text{Low, Medium}\}$

  • Left ($N_L = 2$, High): 2 Yes, 0 No $\implies \text{Gini}(D_L) = \mathbf{0.0}$ (Pure Leaf)
  • Right ($N_R = 5$, Low+Med): 2 Yes, 3 No $\implies \text{Gini}(D_R) = 1 - \left[\frac{4}{25} + \frac{9}{25}\right] = \mathbf{0.480}$
  • Weighted Gini: $\frac{2}{7}(0.0) + \frac{5}{7}(0.480) = \frac{2.4}{7} \approx \mathbf{0.3429}$

$\mathbf{\text{Best Split for Income Level: } \{\text{High}\} \text{ vs } \{\text{Low, Medium}\} \implies \text{Gini} \approx 0.3429}$

---

(c) Best Attribute to Split (4 Marks)

• Impurity & Gain Comparison (2 Marks): $\Delta \text{Gini} = \text{Gini}(\text{Root}) - \text{Gini}_{\text{split}} = 0.4898 - \text{Gini}_{\text{split}}$

Attribute	Best Binary Split Condition	Resulting Gini	Gini Gain ($\Delta \text{Gini}$)
Age Group	$\{\text{Young}\}$ vs $\{\text{Middle, Senior}\}$	$\mathbf{0.2286}$	$\mathbf{0.2612}$ (Maximum Gain)
Income Level	$\{\text{High}\}$ vs $\{\text{Low, Medium}\}$	$0.3429$	$0.1469$

• Selection & Justification (2 Marks):
  • Selected Attribute: Age Group (with binary split condition $\text{Age Group} = \text{Young}$ vs $\text{Age Group} \in \{\text{Middle, Senior}\}$).
  • Reason: It minimizes weighted impurity ($0.2286$), achieves highest Gini Gain ($0.2612$), and immediately isolates a pure terminal leaf node for Young customers ($\text{Buy} = \text{No}$).

---

(d) Tie-Breaking Protocol for Identical Gini Values (2 Marks)

If two attributes produce identical Gini values, resolve the tie using:

1. Acquisition Cost: Choose the attribute cheaper or easier to collect in practice (e.g., Age Group over verified Income).
2. Subtree Balance: Pick the split creating more evenly balanced sample counts between child nodes.
3. Schema Order: Default to the attribute appearing first in the dataset schema.
4. Secondary Metric: Compute Information Gain (Entropy) to test if logarithmic divergence breaks the tie.

---

(e) Two Key Advantages of CART over ID3 or C4.5 (2 Marks)

1. Classification & Regression Support: CART natively constructs both Classification Trees (via Gini Index) and Regression Trees (via Variance Reduction / MSE). ID3 supports classification only.
2. Binary Splitting Avoids Fragmentation: Enforcing strictly 2 branches per split ($2^{k-1}-1$) prevents multi-way branch fragmentation (a flaw of ID3/C4.5), preserving statistical sample power in deeper child nodes.
3. Disciplined Cost-Complexity Pruning: Uses minimal cost-complexity $\alpha$-pruning parameterized with cross-validation, which is theoretically sounder than heuristic error pruning.

---

Question 4: AdaBoost Transaction Fraud Classification (20 Marks)

info

Question Statement

An online payment platform applies AdaBoost to classify transactions as Fraudulent or Genuine. Each weak learner is a decision stump based on one feature (like transaction amount or device ID).

• i) Explain why decision stumps are used as weak learners in AdaBoost. (4 Marks)
• ii) Describe how sample weights are updated after each iteration. (4 Marks)
• iii) Suppose a stump misclassifies 10% of samples - explain how its error and alpha (importance weight) are computed. (4 Marks)
• iv) Discuss how boosting reduces bias but can sometimes increase variance. (4 Marks)
• v) If the dataset has missing values in the "Device ID" feature, explain how AdaBoost handles this situation. (4 Marks)

---

Solution 4

Exam-Ready Answer (Crisp 20-Mark Structure)

---

(i) Why Decision Stumps are Used as Weak Learners (4 Marks)

1. Weak Learner: Only one simple split on a single feature threshold.
2. Low Variance: Extremely simple structure makes it less sensitive to training-data variations and prevents ensemble variance explosion.
3. Fast: Each stump is computationally cheap to train ($O(N \cdot D)$), allowing hundreds of iterations in real time.
4. Interpretable: Easy to understand and provides direct feature importance rankings.

Memory: One Split -> Low Variance -> Fast -> Interpretable

---

(ii) How Sample Weights are Updated After Each Iteration (4 Marks)

• Step 1 - Uniform Initialization: Give every sample equal initial weight: $w_i^{(1)} = \frac{1}{N}, \quad \forall i \in \{1, 2, \dots, N\}$

• Step 2 - Weighted Misclassification Error: Add the weights of incorrectly classified samples: $\epsilon_m = \sum_{i=1}^N w_i^{(m)} \cdot \mathbb{I}\left( y_i \ne h_m(\mathbf{x}_i) \right)$

• Step 3 - Learner Importance ($\alpha$): Calculate how much the stump is trusted: $\alpha_m = \frac{1}{2} \ln\left( \frac{1 - \epsilon_m}{\epsilon_m} \right)$ (Low error $\to$ High $\alpha$ $\to$ Stronger vote)

• Step 4 - Exponential Reweighting & Normalization:

  • Wrong samples: Weight increases ($w_i^{(m+1)} = w_i^{(m)} \cdot e^{+\alpha_m}$).
  • Correct samples: Weight decreases ($w_i^{(m+1)} = w_i^{(m)} \cdot e^{-\alpha_m}$).
  • Normalize: Divide by $Z_m = \sum w_i^{(m+1)}$ so weights sum to $1$.
  • Train the next stump using the updated sample weights.

Memory: Uniform -> Error -> Alpha -> Reweight -> Normalize -> Next Stump

---

(iii) Calculate Alpha When Error is 10% (4 Marks)

• Given: $\epsilon_m = 10\% = 0.10$

• Formula & Calculation: $\alpha_m = \frac{1}{2} \ln\left( \frac{1 - 0.10}{0.10} \right) = \frac{1}{2} \ln(9) = \frac{1}{2} \ln(3^2) = \ln(3) \approx \mathbf{1.0986}$

• Meaning:

  • Low error $\to$ High $\alpha$ $\to$ Strong positive vote in final ensemble.
  • This error and $\alpha$ belong specifically to this one stump/iteration.

---

(iv) How Boosting Reduces Bias but Can Increase Variance (4 Marks)

• Why Bias Decreases:

  • Individual decision stumps are simple and underfit alone.
  • Each successive stump explicitly focuses on samples misclassified by previous rounds.
  • Combining many weak learners creates a stronger, non-linear ensemble boundary.
  • Therefore, training bias decreases toward zero.

• Why Variance Can Increase:

  • Boosting aggressively focuses on hard-to-classify samples.
  • If those difficult instances are noise or outliers, their weights become exponentially inflated.
  • Subsequent stumps fit the noise rather than the underlying pattern, leading to overfitting.
  • Therefore, variance can increase.

Memory: Correct mistakes -> Bias $\downarrow$ | Chase noise -> Variance $\uparrow$

---

(v) Handling Missing Values in "Device ID" (4 Marks)

AdaBoost has no built-in missing value handling; it relies on preprocessing or base-learner capabilities:

1. Pre-processing / Imputation:
   • Impute missing values before boosting using mode or median, optionally adding a binary missingness indicator flag.
2. Missing as an Informative Category:
   • Treat Missing or Unknown as a distinct category, allowing stumps to learn if missingness itself predicts fraud.
3. Base Learner Handles Missing Values Natively:
   • CART stump: Uses surrogate splits as a backup feature if Device ID is missing.
   • C4.5-style stump: Distributes the instance's weight fractionally across all possible branches.

Memory: Impute -> Missing Category -> Native Handling