Decision Trees & Rule-Based Learning: ID3, Overfitting, Rule Extraction

TAKEAWAYS:

• Decision trees split data recursively using attributes (e.g., age, car type) to classify outcomes (e.g., loan approval), with ID3 using information gain to select splits.
• Overfitting occurs when a tree memorizes noise (e.g., a leaf node for a single data point), while underfitting happens when splits are too shallow (e.g., ignoring key attributes like Car Type).
• Rule extraction converts a decision tree into IF-THEN rules (e.g., IF Age ≤ 30 AND Car Type = Sports THEN Class = High).
• Pruning (pre- or post-) fixes overfitting by simplifying the tree (e.g., merging nodes with similar classes).
• Laplace smoothing adjusts probabilities for unseen attribute values (e.g., P(Class=High|Age ≤ 30) = (count + 1)/(total + classes)).
• Real-world use: Banks use decision trees to approve loans (e.g., NMB Bank’s IF Credit Score > 700 THEN Approve), while eSewa predicts user churn (e.g., IF Last Login > 30 Days THEN Flag for Retention).

1. Decision Trees: The Core Idea

Decision trees classify data by splitting it based on attribute values. Each internal node tests an attribute (e.g., Age ≤ 30?), branches represent outcomes, and leaves hold class labels (e.g., High/Low risk).

How ID3 Works: Step-by-Step

ID3 (Iterative Dichotomiser 3) builds trees using information gain, a measure of how much an attribute reduces uncertainty (entropy). The algorithm:

1. Selects the best attribute to split on (highest information gain).
2. Splits the data into subsets.
3. Repeats until all leaves are pure (all samples belong to one class) or no attributes remain.

graph TD
    A["Root: Class?"] -->|"Age ≤ 30"| B["Left: High Risk"]
    A -->|"Age > 30"| C["Right: Split on Car Type"]
    C -->|"Car Type = Family"| D["Leaf: Low Risk"]
    C -->|"Car Type = Sports"| E["Leaf: High Risk"]

Example: Train ID3 on the dataset below to classify loan approval (High/Low):

Step 1: Calculate Entropy of the Target (Class) Entropy measures disorder. For this dataset:

• High: 3/4 samples, Low: 1/4 samples.
• Entropy = $-(3/4{\log }_2(3/4)+1/4{\log }_2(1/4))=0.811$.

Step 2: Compute Information Gain for Each Attribute

• Attribute Age:

  • Split 1: Age ≤ 30 → 2 samples (High, High) → Entropy = 0.
  • Split 2: Age > 30 → 2 samples (High, Low) → Entropy = 1.
  • Weighted entropy = $(2/4\times 0)+(2/4\times 1)=0.5$.
  • Information Gain = Entropy before (0.811) – Entropy after (0.5) = 0.311.

• Attribute Car Type:

  • Split 1: Family → 2 samples (High, Low) → Entropy = 1.
  • Split 2: Sports → 2 samples (High, High) → Entropy = 0.
  • Weighted entropy = $(2/4\times 1)+(2/4\times 0)=0.5$.
  • Information Gain = 0.811 – 0.5 = 0.311.
  • Tie: Choose Age first (alphabetical order in ID3).

Step 3: Build the Tree

1. Split on Age ≤ 30:
   • Left branch: Both samples are High → Leaf node: High.
   • Right branch: Mixed (High, Low) → Recurse.
2. For Age > 30, split on Car Type:
   • Family → Low (leaf).
   • Sports → High (leaf).

Final Tree:

graph TD
    A["Class?"] -->|"Age ≤ 30"| B["High"]
    A -->|"Age > 30"| C["Car Type?"]
    C -->|"Family"| D["Low"]
    C -->|"Sports"| E["High"]

2. Overfitting and Underfitting: The Pitfalls

• Overfitting: The tree fits training data too closely, capturing noise (e.g., a leaf for a single outlier). Symptom: High training accuracy but poor test performance.

  • Example: A tree with 10 levels for 4 samples is overfit.
  • Detection: Compare training vs. validation accuracy (large gap = overfitting).

• Underfitting: The tree is too simple, ignoring important patterns (e.g., stopping at root node).

  • Example: A tree that always predicts High for all samples.

3. Fixing Overfitting: Pruning Techniques

Example: Prune the earlier tree by merging nodes where classes are close (e.g., Age > 30 and Car Type = Family could merge with High if α is small).

4. Extracting Rules from Decision Trees

Convert trees to IF-THEN rules for interpretability:

1. Start at the root, traverse to a leaf.
2. Write conditions for each split (e.g., Age ≤ 30).
3. Assign the leaf’s class as the conclusion.

From the Tree Above:

• Rule 1: IF Age ≤ 30 THEN Class = High.
• Rule 2: IF Age > 30 AND Car Type = Family THEN Class = Low.
• Rule 3: IF Age > 30 AND Car Type = Sports THEN Class = High.

5. Handling Missing Values and Laplace Smoothing

ID3 assumes no missing values. For real data:

• Preprocessing: Replace missing values with mode (most frequent) or mean.
• Laplace Smoothing: Adjusts probabilities to avoid zero counts.
  • Formula: $P(X|Y)=\frac{\text{count}(X,Y)+1}{\text{count}(Y)+\text{number of classes}}$.
  • Example: If Class=High appears 3 times for Age ≤ 30 and there are 2 classes: $P(\text{High}|\text{Age}\le 30)=\frac{3+1}{4+2}=0.5$.

6. Real-World Applications

In the Real World

1. NMB Bank (Nepal):

   • Use: Decision trees classify loan applications.
   • How: Splits on Credit Score, Income, and Loan Amount to predict Approved/Rejected.
   • Rule Example: IF Credit Score > 700 AND Income > 50,000 THEN Approve Loan.

2. eSewa (Nepal):

   • Use: Predicts user churn (whether a user will stop using the app).
   • How: Trees split on Last Login Date, Transaction Frequency, and Device Type.
   • Rule Example: IF Last Login > 30 Days AND Transactions < 3 THEN Flag for Retention Campaign.

3. Google Play Store (Global):

   • Use: Recommends apps based on user history.
   • How: Decision trees split on User Age, Download Frequency, and App Category to suggest new apps.
   • Rule Example: IF Age 18-25 AND Downloads > 10 Apps/Month THEN Recommend Gaming Apps.

Worked Example: Daraz Order Fulfillment

Daraz uses decision trees to route orders to warehouses based on:

• Attributes: Order Value, Customer Location, Product Type.
• Class: Warehouse ID (e.g., Kathmandu, Lalitpur).

Dataset:

Tree Construction:

1. Split on Location (highest information gain):
   • Kathmandu → Split on Value:
     • ≤5000 → Kathmandu.

     • 5000 → Kathmandu (only one sample).

   • Bhaktapur → Lalitpur.

Final Rule: IF Location = Kathmandu AND Value ≤ 5000 THEN Route to Kathmandu Warehouse.

7. Comparing Decision Trees to Other Methods

8. Exam Tip: How to Score Full Marks

1. Define Key Terms Precisely:

   • Overfitting: "A model fits training data too closely, performing poorly on unseen data."
   • Information Gain: "Reduction in entropy after splitting on an attribute."

2. Show Calculations Step-by-Step:

   • For ID3, always:
     1. Calculate entropy of the target.
     2. Compute information gain for each attribute.
     3. Select the attribute with highest gain.
   • Example: In the loan dataset, show entropy before/after splits for both Age and Car Type.

3. Draw the Tree:

   • Use Mermaid or ASCII art to visualize splits. Label nodes with attributes and leaves with classes.
   • Example:

     [Age ≤ 30?]
          /       \
     [High]      [Car Type?]
                 /          \
            [Family: Low] [Sports: High]
     

4. Explain Pruning:

   • Mention pre-pruning (early stopping) and post-pruning (reduced-error pruning).
   • Link to overfitting: "Pruning reduces variance by simplifying the tree."

5. Relate to Real-World Scenarios:

   • For questions on applications, tie to banks (loan approval), e-commerce (order routing), or telecom (churn prediction).
   • Example Answer:

     "Ncell uses decision trees to predict customer churn by splitting on Call Duration, Data Usage, and Payment History. A rule like IF Call Duration < 30 mins/month THEN Classify as Churn Risk helps target retention offers."

6. Avoid Common Mistakes:

   • ❌ Using Gini impurity instead of entropy for ID3.
   • ❌ Forgetting to normalize information gain by split size.
   • ❌ Ignoring missing values in the dataset.

9. Practice Questions (Exam-Style)

1. Train an ID3 classifier on the following data and draw the tree:

   TID	Outlook	Temperature	Humidity	Windy	Play Tennis
   1	Sunny	Hot	High	Weak	No
   2	Sunny	Hot	High	Strong	No
   3	Overcast	Hot	High	Weak	Yes

2. Explain how Laplace smoothing improves rule accuracy in decision trees. Provide a numerical example.

3. How would you detect overfitting in a decision tree? Describe two methods and their tradeoffs.

10. Summary Checklist

Before the exam, ensure you can:

• Calculate entropy and information gain for any dataset.
• Build a decision tree from scratch using ID3.
• Identify overfitting/underfitting in a tree.
• Apply pruning techniques (pre/post).
• Extract rules from a decision tree.
• Explain real-world applications (banks, e-commerce, telecom).