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 (Structured for 20 Marks)

---

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

1. Step 1: Class Frequency Distribution at Root Node (1 Mark)

   • Total number of customer instances ($N$): $N = 7$
   • Number of instances with $\text{Buy} = \text{Yes}$: $N_{\text{Yes}} = 4$ (Customers: C3, C4, C5, C6)
   • Number of instances with $\text{Buy} = \text{No}$: $N_{\text{No}} = 3$ (Customers: C1, C2, C7)

2. Step 2: Class Probabilities at Root (1 Mark) $P(\text{Buy} = \text{Yes}) = p_1 = \frac{4}{7}$ $P(\text{Buy} = \text{No}) = p_2 = \frac{3}{7}$

3. Step 3: State the Gini Index Formula (1 Mark) $\text{Gini}(D) = 1 - \sum_{i=1}^C p_i^2 = 1 - \left( p_1^2 + p_2^2 \right)$

4. Step 4: Substitution and Calculation (1 Mark) $\text{Gini}(\text{Root}) = 1 - \left[ \left(\frac{4}{7}\right)^2 + \left(\frac{3}{7}\right)^2 \right] = 1 - \left[ \frac{16}{49} + \frac{9}{49} \right]$ $\text{Gini}(\text{Root}) = 1 - \frac{25}{49} = \frac{24}{49} \approx \mathbf{0.4898} \quad (\approx 0.490)$

---

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

In the Classification and Regression Trees (CART) methodology, trees are constructed strictly via binary splits. For an attribute with $k$ discrete categories, there are $2^{k-1} - 1$ unique binary partitions.

---

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

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

  • Left Node ($D_L$: Young, $N_L = 2$):
    • C1 (No), C2 (No) $\implies \text{Yes} = 0, \text{No} = 2$. $\text{Gini}(D_L) = 1 - \left[ \left(\frac{0}{2}\right)^2 + \left(\frac{2}{2}\right)^2 \right] = 1 - 1 = \mathbf{0.0} \quad (\text{Pure Node})$
  • Right Node ($D_R$: Middle + Senior, $N_R = 5$):
    • C3 (Yes), C4 (Yes), C5 (Yes), C6 (Yes), C7 (No) $\implies \text{Yes} = 4, \text{No} = 1$. $\text{Gini}(D_R) = 1 - \left[ \left(\frac{4}{5}\right)^2 + \left(\frac{1}{5}\right)^2 \right] = 1 - \left( \frac{16}{25} + \frac{1}{25} \right) = 1 - \frac{17}{25} = \frac{8}{25} = \mathbf{0.320}$
  • Weighted Gini for Partition 1: $\text{Gini}_{\text{split}}(\{\text{Young}\} \text{ vs } \{\text{Middle, Senior}\}) = \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 Node ($D_L$: Middle, $N_L = 2$):
    • C3 (Yes), C4 (Yes) $\implies \text{Yes} = 2, \text{No} = 0$. $\text{Gini}(D_L) = 1 - \left[ \left(\frac{2}{2}\right)^2 + 0 \right] = \mathbf{0.0} \quad (\text{Pure Node})$
  • Right Node ($D_R$: Young + Senior, $N_R = 5$):
    • C1 (No), C2 (No), C5 (Yes), C6 (Yes), C7 (No) $\implies \text{Yes} = 2, \text{No} = 3$. $\text{Gini}(D_R) = 1 - \left[ \left(\frac{2}{5}\right)^2 + \left(\frac{3}{5}\right)^2 \right] = 1 - \frac{13}{25} = \frac{12}{25} = \mathbf{0.480}$
  • Weighted Gini for Partition 2: $\text{Gini}_{\text{split}}(\{\text{Middle}\} \text{ vs } \{\text{Young, Senior}\}) = \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 Node ($D_L$: Senior, $N_L = 3$):
    • C5 (Yes), C6 (Yes), C7 (No) $\implies \text{Yes} = 2, \text{No} = 1$. $\text{Gini}(D_L) = 1 - \left[ \left(\frac{2}{3}\right)^2 + \left(\frac{1}{3}\right)^2 \right] = 1 - \frac{5}{9} = \frac{4}{9} \approx \mathbf{0.4444}$
  • Right Node ($D_R$: Young + Middle, $N_R = 4$):
    • C1 (No), C2 (No), C3 (Yes), C4 (Yes) $\implies \text{Yes} = 2, \text{No} = 2$. $\text{Gini}(D_R) = 1 - \left[ \left(\frac{2}{4}\right)^2 + \left(\frac{2}{4}\right)^2 \right] = 1 - 0.500 = \mathbf{0.500}$
  • Weighted Gini for Partition 3: $\text{Gini}_{\text{split}}(\{\text{Senior}\} \text{ vs } \{\text{Young, Middle}\}) = \frac{3}{7}\left(\frac{4}{9}\right) + \frac{4}{7}(0.500) = \frac{4}{21} + \frac{2}{7} = \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. Candidate Binary Splits for Income Level ($k = 3$: Low, Medium, High)

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

  • Left Node ($D_L$: Low, $N_L = 3$):
    • C1 (No), C3 (Yes), C7 (No) $\implies \text{Yes} = 1, \text{No} = 2$. $\text{Gini}(D_L) = 1 - \left[ \left(\frac{1}{3}\right)^2 + \left(\frac{2}{3}\right)^2 \right] = 1 - \frac{5}{9} = \frac{4}{9} \approx \mathbf{0.4444}$
  • Right Node ($D_R$: Medium + High, $N_R = 4$):
    • C2 (No), C4 (Yes), C5 (Yes), C6 (Yes) $\implies \text{Yes} = 3, \text{No} = 1$. $\text{Gini}(D_R) = 1 - \left[ \left(\frac{3}{4}\right)^2 + \left(\frac{1}{4}\right)^2 \right] = 1 - \frac{10}{16} = \frac{6}{16} = \mathbf{0.375}$
  • Weighted Gini for Partition 1: $\text{Gini}_{\text{split}}(\{\text{Low}\} \text{ vs } \{\text{Medium, High}\}) = \frac{3}{7}\left(\frac{4}{9}\right) + \frac{4}{7}(0.375) = \frac{4}{21} + \frac{1.5}{7} = \frac{4 + 4.5}{21} = \frac{8.5}{21} \approx \mathbf{0.4048}$

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

  • Left Node ($D_L$: Medium, $N_L = 2$):
    • C2 (No), C5 (Yes) $\implies \text{Yes} = 1, \text{No} = 1$. $\text{Gini}(D_L) = 1 - \left[ \left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2 \right] = 1 - 0.500 = \mathbf{0.500}$
  • Right Node ($D_R$: Low + High, $N_R = 5$):
    • C1 (No), C3 (Yes), C4 (Yes), C6 (Yes), C7 (No) $\implies \text{Yes} = 3, \text{No} = 2$. $\text{Gini}(D_R) = 1 - \left[ \left(\frac{3}{5}\right)^2 + \left(\frac{2}{5}\right)^2 \right] = 1 - \frac{13}{25} = \frac{12}{25} = \mathbf{0.480}$
  • Weighted Gini for Partition 2: $\text{Gini}_{\text{split}}(\{\text{Medium}\} \text{ vs } \{\text{Low, High}\}) = \frac{2}{7}(0.500) + \frac{5}{7}(0.480) = \frac{1}{7} + \frac{2.4}{7} = \frac{3.4}{7} \approx \mathbf{0.4857}$

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

  • Left Node ($D_L$: High, $N_L = 2$):
    • C4 (Yes), C6 (Yes) $\implies \text{Yes} = 2, \text{No} = 0$. $\text{Gini}(D_L) = 1 - \left[ \left(\frac{2}{2}\right)^2 + 0 \right] = \mathbf{0.0} \quad (\text{Pure Node})$
  • Right Node ($D_R$: Low + Medium, $N_R = 5$):
    • C1 (No), C2 (No), C3 (Yes), C5 (Yes), C7 (No) $\implies \text{Yes} = 2, \text{No} = 3$. $\text{Gini}(D_R) = 1 - \left[ \left(\frac{2}{5}\right)^2 + \left(\frac{3}{5}\right)^2 \right] = 1 - \frac{13}{25} = \frac{12}{25} = \mathbf{0.480}$
  • Weighted Gini for Partition 3: $\text{Gini}_{\text{split}}(\{\text{High}\} \text{ vs } \{\text{Low, Medium}\}) = \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}$

---

Alternative: Multi-Way Attribute Gini Summary (Standard Exam Reference)

If evaluated under the non-binary multi-way split definition ($\text{Gini}(D, A) = \sum \frac{|D_v|}{|D|} \text{Gini}(D_v)$):

• Age Group: $\text{Gini}(D, \text{Age Group}) = \frac{2}{7}(0.0) + \frac{2}{7}(0.0) + \frac{3}{7}\left(\frac{4}{9}\right) = \frac{4}{21} \approx \mathbf{0.1905}$
• Income Level: $\text{Gini}(D, \text{Income Level}) = \frac{3}{7}\left(\frac{4}{9}\right) + \frac{2}{7}(0.500) + \frac{2}{7}(0.0) = \frac{4}{21} + \frac{1}{7} = \frac{7}{21} \approx \mathbf{0.3333}$

---

(c) Best Attribute to Split Using Gini Index Criterion (4 Marks)

1. Step 1: Compare Gini Values & Gini Gain (2 Marks) In decision tree learning, the optimal split is the one that minimizes the resulting weighted Gini index (or equivalently, maximizes the Gini Gain $\Delta \text{Gini} = \text{Gini}(\text{Root}) - \text{Gini}_{\text{split}}$):

Attribute	Candidate Binary Split	Resulting Gini ($\text{Gini}_{\text{split}}$)	Gini Gain ($\Delta \text{Gini} = 0.4898 - \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$

(Under the multi-way formulation, Age Group $\text{Gini} = 0.1905$ vs Income Level $\text{Gini} = 0.3333$).

2. Step 2: Conclusion & Selection (2 Marks)
   • Selected Best Attribute: Age Group (with binary split condition $\text{Age Group} = \text{Young}$ vs $\text{Age Group} \in \{\text{Middle, Senior}\}$).
   • Reasoning: It produces the minimum weighted impurity ($0.2286$) and achieves the highest impurity reduction ($\Delta \text{Gini} = 0.2612$). It immediately isolates a completely pure terminal leaf node for Young customers ($\text{Buy} = \text{No}$ with $100\%$ certainty).

---

(d) Tie-Breaking: What Happens if Both Attributes Have the Same Gini Value? (2 Marks)

If two attributes produce identical Gini index values, standard CART algorithms resolve the tie using the following established protocols:

1. Domain-Specific / Cost Priority: Select the attribute that is cheaper, faster, or less intrusive to acquire in real-world production (e.g., Age Group may be easier to collect than verified Income).
2. Subtree Balance / Child Node Distribution: Choose the split that creates more evenly distributed subset sizes (minimizing sample variance between child nodes).
3. Deterministic Heuristic: Follow a consistent tie-breaking rule, such as selecting the attribute that appears first in the dataset schema (e.g., column index order).
4. Secondary Information Metric: Compute Information Gain (Entropy) or Gain Ratio to assess if higher-order divergence distinguishes the attributes.

---

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

1. Unified Framework for Classification & Regression:
   • CART seamlessly builds both Classification Trees (using the Gini Index for categorical targets) and Regression Trees (using Mean Squared Error / Variance Reduction for continuous numerical targets). In contrast, ID3 is strictly limited to classification, and C4.5 requires separate extensions.
2. Binary Splitting Avoids Multi-Way Fragmentation:
   • CART strictly enforces binary splits ($2$ child nodes per split), preventing the exponential data fragmentation problem seen in ID3 (which creates a separate branch for every category). This preserves sample statistical power in lower nodes and naturally prevents overfitting on high-cardinality nominal attributes.
3. Rigorous Cost-Complexity Pruning:
   • CART uses a mathematically disciplined Minimal Cost-Complexity Pruning algorithm ($\alpha$-pruning parameterized with cross-validation), which is theoretically superior to the greedy heuristic error-based pruning utilized in C4.5.

---

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 (Structured for 20 Marks)

---

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

A decision stump is a 1-level decision tree consisting of a single root split node (testing exactly one attribute threshold) connected directly to two terminal leaf nodes.

1. Satisfaction of Weak Learner Condition (1 Mark):
   • Boosting theory (Freund & Schapire) requires base learners to perform only slightly better than random guessing (error $\epsilon < 0.5$ in binary classification). A simple 1-feature stump easily satisfies this minimal requirement without needing complex parameter tuning.
2. High Bias, Ultra-Low Variance Structure (1 Mark):
   • Stumps are extreme high-bias, low-variance models. Since boosting is fundamentally designed to reduce ensemble bias by additively combining weak models, starting with low-variance base learners prevents the ensemble from exploding in variance.
3. Computational Speed & Scalability (1 Mark):
   • Training a stump requires scanning only $O(N \cdot D)$ candidate thresholds. In production transaction systems (such as high-frequency fraud detection), hundreds of boosting rounds can be trained in seconds.
4. Interpretability & Feature Ranking (1 Mark):
   • Because each stump isolates a single feature (e.g., $\text{Amount} > 500$), aggregating the stump weights provides an intuitive, mathematically exact measure of cumulative feature importance.

---

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

1. Step 1: Initialization (1 Mark)

   • At iteration $m = 1$, all $N$ transaction samples are initialized with equal, uniform weights: $w_i^{(1)} = \frac{1}{N}, \quad \forall i \in \{1, 2, \dots, N\}$

2. Step 2: Weighted Error Rate Computation (1 Mark)

   • For the $m$-th weak learner $h_m(\mathbf{x})$, the weighted misclassification error $\epsilon_m$ is computed as the sum of weights of incorrectly predicted transactions: $\epsilon_m = \sum_{i=1}^N w_i^{(m)} \cdot \mathbb{I}\left( y_i \ne h_m(\mathbf{x}_i) \right)$ where $y_i \in \{-1, +1\}$ and $\mathbb{I}(\cdot)$ is the indicator function.

3. Step 3: Learner Importance Weight $\alpha_m$ (1 Mark)

   • The voting weight assigned to stump $h_m$ is: $\alpha_m = \frac{1}{2} \ln\left( \frac{1 - \epsilon_m}{\epsilon_m} \right)$

4. Step 4: Multiplicative Weight Update & Renormalization (1 Mark)

   • Sample weights for iteration $m + 1$ are updated exponentially based on whether the transaction was correctly or incorrectly classified: $w_i^{(m+1)} = \frac{w_i^{(m)} \cdot \exp\left( -\alpha_m y_i h_m(\mathbf{x}_i) \right)}{Z_m}$
   • For Correctly Classified Samples ($y_i h_m(\mathbf{x}_i) = +1$): $w_i^{(m+1)} = w_i^{(m)} \cdot e^{-\alpha_m} \quad (\text{weight is penalized/decreased})$
   • For Misclassified Samples ($y_i h_m(\mathbf{x}_i) = -1$): $w_i^{(m+1)} = w_i^{(m)} \cdot e^{+\alpha_m} \quad (\text{weight is boosted/increased})$
   • $Z_m$ is the normalization factor ensuring $\sum_{i=1}^N w_i^{(m+1)} = 1$: $Z_m = \sum_{i=1}^N w_i^{(m)} \exp\left( -\alpha_m y_i h_m(\mathbf{x}_i) \right)$
   • Core Insight: Transactions misclassified as genuine when fraudulent are amplified in weight, forcing subsequent stumps to concentrate heavily on resolving these hard-to-detect frauds.

---

(iii) Error and Alpha Computation for a Stump with 10% Misclassifications (4 Marks)

1. Step 1: Compute Weighted Error Rate ($\epsilon_m$) (1 Mark)

   • Given that the stump misclassifies $10\%$ of the total sample weight: $\epsilon_m = 10\% = \mathbf{0.10}$

2. Step 2: State the Formula for Importance Weight ($\alpha_m$) (1 Mark) $\alpha_m = \frac{1}{2} \ln\left( \frac{1 - \epsilon_m}{\epsilon_m} \right)$

3. Step 3: Step-by-Step Numerical Evaluation (1 Mark)

   • Evaluate the odds ratio: $\frac{1 - \epsilon_m}{\epsilon_m} = \frac{1 - 0.10}{0.10} = \frac{0.90}{0.10} = 9$
   • Substitute into the logarithm: $\alpha_m = \frac{1}{2} \ln(9) = \frac{1}{2} \ln(3^2) = \ln(3)$
   • Using $\ln(3) \approx 1.09861$: $\mathbf{\alpha_m \approx 1.0986}$

4. Step 4: Mathematical & Practical Interpretation (1 Mark)

   • High Positive Weight: Because $\epsilon_m = 0.10 \ll 0.50$ (substantially better than random guessing), $\alpha_m \approx 1.099$ is strongly positive.
   • Voting Influence: In the final ensemble decision rule: $H(\mathbf{x}) = \text{sign}\left( \sum_{m=1}^M \alpha_m h_m(\mathbf{x}) \right)$ this high-performing stump receives a powerful voting weight of $+1.0986$, significantly influencing the fraud classification outcome.

---

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

1. How Boosting Reduces Bias (2 Marks):

   • Additive Sequential Correction: Individual decision stumps have severe underfitting (high bias) because a single threshold cannot capture complex decision surfaces.
   • Progressive Residual Modeling: Each successive learner is trained on the reweighted distribution of samples misclassified by preceding learners.
   • Non-Linear Boundary Synthesis: Linearly combining numerous piecewise linear stumps forms highly expressive, intricate, non-linear decision boundaries: $\lim_{M \to \infty} \text{Bias}^2 \to 0$ This guarantees that the ensemble training error drops exponentially toward zero as iterations increase.

2. Why Boosting Can Sometimes Increase Variance (2 Marks):

   • Extreme Sensitivity to Outliers & Label Noise: If a payment dataset contains mislabeled transactions (e.g., an abnormal genuine purchase falsely flagged as fraud) or anomalous outliers, AdaBoost repeatedly misclassifies them.
   • Exponential Weight Explosion: The weight of these noisy points escalates exponentially ($e^{m \alpha}$), causing the algorithm to over-focus on learning isolated noise points rather than generalizable fraud patterns.
   • Overfitting & Decision Boundary Fragmentation: The ensemble boundary contorts into irregular, sharp pockets around noisy outliers, leading to high variance, brittle predictions, and deteriorated test accuracy.
   • Mitigation: Employing shrinkage (learning rate $\eta < 1$), limiting maximum boosting iterations $M$, or using robust variants like Gradient Boosting with Huber loss.

---

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

In practical fraud detection, "Device ID" is frequently missing due to private browsing modes, cookie blocking, or emulator masking. AdaBoost handles this through several robust mechanisms:

1. Feature Bypassing via Alternative Stumps (Primary CART/Stump Defense) (1.5 Marks):
   • In AdaBoost, each weak learner selects only one best feature to split on at each iteration. If "Device ID" contains extensive missing entries that degrade its split quality, the algorithm automatically selects an alternative, fully observed attribute (e.g., Transaction Amount, IP Geolocation, or Time of Transaction) that yields a lower weighted error $\epsilon_m$.
2. Missing as an Informative Predictive Category (1 Mark):
   • In cyber-fraud analysis, a missing Device ID is rarely random (it is Missing Not At Random, MNAR). Fraudsters deliberately conceal device fingerprints. AdaBoost treats Missing / Null as a separate, dedicated categorical level (Device_ID = Unknown). This category often becomes an exceptionally powerful indicator of fraudulent intent.
3. Surrogate Split Rule (CART-Specific Mechanism) (1 Mark):
   • If a stump insists on evaluating Device ID, CART constructs a surrogate split using an auxiliary feature (e.g., IP Address or Browser Type) that mimics the Device ID split with maximum mutual correlation, routing missing transactions along the surrogate branch.
4. Weighted Proportional Assignment (0.5 Marks):
   • When encountering a missing value during split evaluation, the sample's weight can be split proportionally across both branches according to the relative weight distribution of observed transactions in the child nodes.