Decision Trees & Ensembles: Splits, Pruning, Boosting & Bagging

Key Concepts and Definitions

Decision Trees

A decision tree is a supervised learning algorithm used for both classification and regression tasks. It works by recursively partitioning the feature space into subsets based on feature values, creating a tree-like structure of decisions.

How Decision Trees Work

1. Root Node: Represents the entire dataset.
2. Internal Nodes: Represent features (attributes) and the decision rules based on those features.
3. Branches: Represent the decision rules or splits.
4. Leaf Nodes: Represent the final outcome or class label.

Splitting Criteria

Decision trees use splitting criteria to determine the best feature and threshold to split the data at each node. Common criteria include:

• Gini Impurity: Measures the impurity or disorder in a set of data. Lower values indicate purer nodes. $$Gini(D)=1-\sum _{i=1}^c{p}_i^2$$ where $p_i$ is the probability of class $i$ in the dataset $D$.

• Entropy: Measures the disorder or uncertainty in a dataset. Lower entropy means more information gain. $$Entropy(D)=-\sum _{i=1}^c{p}_i{\log }_2{p}_i$$

• Information Gain: The reduction in entropy after a dataset is split on an attribute. $$InformationGain(D,A)=Entropy(D)-\sum _{v\in Values(A)}\frac{|D_v|}{|D|}Entropy(D_v)$$

Worked Example: Splitting a Dataset

Consider a dataset with features Outlook (Sunny, Overcast, Rainy) and Humidity (High, Normal) to predict Play Tennis (Yes, No). Let’s use the Gini impurity to decide the best split.

Dataset:

Step 1: Calculate Gini for the Root Node

• Class distribution: Play Tennis = Yes (3), No (4)
• Gini(Root) = $1-(3/7{)}^2-(4/7{)}^2=0.489$

Step 2: Calculate Gini for Possible Splits

• Split on Outlook = Sunny:

  • Left subset (Sunny): Yes (1), No (2) → Gini = $1-(1/3{)}^2-(2/3{)}^2=0.444$
  • Right subset (Overcast, Rainy): Yes (3), No (2) → Gini = $1-(3/5{)}^2-(2/5{)}^2=0.480$
  • Weighted Gini = $(3/7)\ast 0.444+(4/7)\ast 0.480=0.466$

• Split on Humidity = High:

  • Left subset (High): Yes (1), No (3) → Gini = $1-(1/4{)}^2-(3/4{)}^2=0.375$
  • Right subset (Normal): Yes (2), No (1) → Gini = $1-(2/3{)}^2-(1/3{)}^2=0.444$
  • Weighted Gini = $(4/7)\ast 0.375+(3/7)\ast 0.444=0.407$

The split on Humidity = High has the lowest weighted Gini (0.407), so it is chosen.

Visualizing a Decision Tree

graph TD
    A["Humidity = High?"] -->|"Yes"| B["Outlook = Sunny?"]
    A -->|"No"| C["Play Tennis = Yes"]
    B -->|"Yes"| D["Play Tennis = No"]
    B -->|"No"| E["Play Tennis = Yes"]

Overfitting and Pruning

Decision trees can overfit the training data, meaning they capture noise and perform poorly on unseen data. Pruning is used to simplify the tree and improve generalization.

Types of Pruning

1. Pre-pruning (Early Stopping):

   • Stop splitting a node if:
     • The node has fewer than a minimum number of samples.
     • The impurity is below a threshold.
     • The depth of the tree exceeds a maximum limit.

2. Post-pruning (Cost-Complexity Pruning):

   • Build the full tree first, then prune it by removing the least significant nodes based on a cost function.
   • The cost function balances the tree's complexity and its performance on a validation set.

Worked Example: Pruning a Decision Tree

Suppose we have a full decision tree with the following structure (simplified for illustration):

graph TD
    A["Root"] --> B["Feature X > 0.5"]
    B -->|"Yes"| C["Feature Y > 0.3"]
    B -->|"No"| D["Class A"]
    C -->|"Yes"| E["Class B"]
    C -->|"No"| F["Class A"]

After evaluating the tree on a validation set, we find that node C (Feature Y > 0.3) does not significantly improve performance. We prune it, replacing it with a leaf node predicting the majority class of its children (Class A).

Ensembles: Combining Weak Learners

Ensembles combine multiple models (weak learners) to create a stronger model. Two popular ensemble methods are Bagging and Boosting.

Bagging (Bootstrap Aggregating)

Bagging trains multiple models on different subsets of the data (with replacement) and averages their predictions. Random Forest is a popular bagging method that also introduces randomness in feature selection.

How Random Forest Works

1. Bootstrap Sampling: Create multiple subsets of the training data by sampling with replacement.
2. Feature Randomness: For each tree, randomly select a subset of features to consider for splitting.
3. Aggregate Predictions: Combine the predictions of all trees (majority vote for classification, average for regression).

Worked Example: Random Forest for Loan Approval

Suppose a bank wants to predict loan approval using features like Income, Credit Score, and Employment Status. A Random Forest with 100 trees might:

• Sample 80% of the data for each tree.
• Randomly select 3 features out of 10 for each split.
• Aggregate predictions to decide whether to approve a loan.

Multiple decision trees in a Random Forest, each trained on a different data subset. (Image: Jeremybeauchamp, CC BY-SA 4.0, via Wikimedia Commons)

Boosting

Boosting sequentially trains models, where each new model focuses on the errors of the previous ones. AdaBoost is a popular boosting algorithm.

How AdaBoost Works

1. Initialize Weights: Assign equal weights to all training examples.
2. Train Weak Learner: Train a weak learner (e.g., a shallow decision tree) on the weighted data.
3. Calculate Error: Compute the weighted error of the weak learner.
4. Update Weights: Increase the weights of misclassified examples.
5. Combine Models: Combine the weak learners into a strong ensemble, weighted by their performance.

Worked Example: AdaBoost for Fraud Detection in eSewa

eSewa uses AdaBoost to detect fraudulent transactions. Suppose:

• Weak learners are shallow decision trees trained on features like Transaction Amount, Time of Day, and Location.
• Misclassified fraudulent transactions get higher weights in subsequent iterations.
• The final model combines predictions from all weak learners to flag suspicious transactions.

Comparison of Decision Trees and Ensembles

In the Real World

1. eSewa Fraud Detection:

   • Idea Used: AdaBoost ensemble.
   • How: eSewa trains multiple weak learners (shallow decision trees) on transaction data. Each tree focuses on misclassified fraud cases from previous iterations. The ensemble combines predictions to flag fraudulent transactions with high accuracy.

2. Pathao Route Optimization:

   • Idea Used: Decision Trees + Random Forest.
   • How: Pathao uses decision trees to classify driver availability based on time, location, and demand. Random Forest ensembles improve robustness by aggregating predictions from multiple trees, ensuring reliable route suggestions even with noisy data.

3. Nepal Rastra Bank Loan Approval:

   • Idea Used: Random Forest.
   • How: The bank uses Random Forest to evaluate loan applications. Each tree in the forest considers a random subset of features (e.g., income, credit history, employment status) and votes on approval. This reduces bias and improves fairness in lending decisions.

Exam Tip

For exams, focus on:

1. Splitting Criteria: Know how to calculate Gini impurity and information gain. Be ready to compute splits for small datasets.
2. Pruning: Understand pre-pruning and post-pruning. Explain why pruning reduces overfitting with an example.
3. Ensembles: Compare bagging (Random Forest) and boosting (AdaBoost). Draw a diagram of how AdaBoost reweights misclassified examples.
4. Real-World Applications: Relate decision trees to classification tasks (e.g., loan approval) and ensembles to robustness (e.g., fraud detection). Use small numerical examples to illustrate concepts.
5. Visuals: Always draw decision trees and ensemble workflows. Label nodes clearly (e.g., "Feature X > 0.5").

Summary

• Decision trees split data recursively using Gini or entropy.
• Pruning (pre/post) prevents overfitting.
• Ensembles like Random Forest (bagging) and AdaBoost (boosting) improve accuracy.
• Real-world uses: Fraud detection (AdaBoost), route optimization (Random Forest), loan approval (ensembles).