Decision Tree using ID3 Algorithm (Iterative Dichotomiser3 Algorithm )- toy example

Experiment

Decision Tree using ID3 Algorithm (Iterative Dichotomiser3 Algorithm )

---

🎯 Objective

• To implement ID3 algorithm
• To compute:
  • Entropy
  • Information Gain
• To construct a decision tree for predicting Play Golf

---

📊 Dataset

Outlook      Windy          Play

Sunny     Weak         No

Sunny     Strong       No

Overcast  Weak        Yes

Rain      Weak        Yes

Rain      Strong      No

---

📚 Theory

1. Calculate Parent Entropy

The first step is to measure the uncertainty (impurity) of the current dataset $S$ before any split occurs.

$$H(S) = - \sum_{i=1}^{c} p_i \log_2 p_i$$

• $p_i$: The proportion of examples in class $i$ relative to the total number of examples in $S$
  
• $c$: The total number of target classes

---

2. Calculate Weighted Entropy After Split

For a candidate attribute $A$, calculate the Remainder, which is the weighted average entropy of the subsets created by splitting dataset $S$ based on $A$.

$$\text{Remainder}(S, A) = \sum_{v \in \text{Values}(A)} \frac{|S_v|}{|S|} \cdot H(S_v)$$

• Values(A): The set of all possible values for attribute $A$
  
• $S_v$: The subset of $S$ where attribute $A = v$
  
• $|S_v|$ and $|S|$: Number of elements in the subset and original dataset, respectively

---

3. Compute Information Gain

The Information Gain for attribute $A$ is the difference between the original entropy and the weighted entropy after the split:

$$\text{Gain}(S, A) = H(S) - \text{Remainder}(S, A)$$

---

4. Attribute Selection (ID3 Algorithm)

The ID3 algorithm computes the Information Gain for every available attribute and selects the one with the highest gain as the decision node.

---

💻 Python Program

import pandas as pd
import numpy as np
from math import log2
# -----------------------------------
# 1. Sample Dataset
# -----------------------------------
'''Outlook      Windy     Play
Sunny     Weak         No
Sunny     Strong      No
Overcast  Weak        Yes
Rain      Weak        Yes
Rain      Strong      No'''
data = {
    'Outlook': ['Sunny','Sunny','Overcast','Rainy','Rainy'],
   
      
    'Windy': ['Weak','Strong','Weak','Weak','Strong'],
    
    'Play': ['No','No','Yes','Yes','No']
}
df = pd.DataFrame(data)
# -----------------------------------
# 2. Entropy Function
# -----------------------------------
def entropy(target):
    values, counts = np.unique(target, return_counts=True)
    probs = counts / len(target)
    ent = 0
    for p in probs:
        ent += -p * log2(p)
    return ent
# -----------------------------------
# 3. Information Gain Function
# -----------------------------------
def info_gain(df, feature, target='Play'):
    # Total entropy
    total_entropy = entropy(df[target])
    # Unique values in feature
    values, counts = np.unique(df[feature], return_counts=True)
    # Weighted entropy
    weighted_entropy = 0
    for i in range(len(values)):
        subset = df[df[feature] == values[i]]
        subset_entropy = entropy(subset[target])
        weighted_entropy += (counts[i] / np.sum(counts)) * subset_entropy
    # Information Gain
    gain = total_entropy - weighted_entropy
    return gain
# -----------------------------------
# 4. ID3 Recursive Function
# -----------------------------------
def id3(df, features, target='Play', level=0):
    print("\n" + "="*60)
    print("LEVEL :", level)
    # -----------------------------------
    # Check if all target values same
    # -----------------------------------
    unique_classes = np.unique(df[target])
    if len(unique_classes) == 1:
        print("Leaf Node -->", unique_classes[0])
        return unique_classes[0]
    # -----------------------------------
    # If no features left
    # -----------------------------------
    if len(features) == 0:
        majority_class = df[target].mode()[0]
        print("Majority Class -->", majority_class)
        return majority_class
    # -----------------------------------
    # Compute Information Gain
    # -----------------------------------
    print("\nInformation Gains:\n")
    gains = []
    for feature in features:
        gain = info_gain(df, feature, target)
        gains.append(gain)
        print(feature, ":", round(gain, 4))
    # -----------------------------------
    # Select Best Feature
    # -----------------------------------
    best_feature = features[np.argmax(gains)]
    print("\nBest Feature Chosen -->", best_feature)
    # -----------------------------------
    # Create Tree
    # -----------------------------------
    tree = {best_feature: {}}
    # -----------------------------------
    # Recursive Splitting
    # -----------------------------------
    feature_values = np.unique(df[best_feature])
    for value in feature_values:
        print("\nSplitting:", best_feature, "=", value)
        subset = df[df[best_feature] == value]
        # Remove chosen feature
        remaining_features = [f for f in features if f != best_feature]
        # Recursive call
        subtree = id3(
            subset,
            remaining_features,
            target,
            level + 1
        )
        tree[best_feature][value] = subtree
    return tree
# -----------------------------------
# 5. Run ID3 Algorithm
# -----------------------------------
features = ['Outlook', 'Windy']
print("\nEntropy of Dataset:",
      round(entropy(df['Play']), 4))
# Build tree
decision_tree = id3(df, features)
# -----------------------------------
# 6. Final Decision Tree
# -----------------------------------
print("\n" + "="*60)
print("FINAL DECISION TREE\n")
print(decision_tree)

# -----------------------------------
# Prediction Function
# -----------------------------------
def predict(tree, sample):
    # Get root feature
    root = list(tree.keys())[0]
    # Get feature value from sample
    value = sample[root]
    # Move to subtree
    subtree = tree[root][value]
    # If subtree is another dictionary
    if isinstance(subtree, dict):
        return predict(subtree, sample)
    else:
        return subtree
new_sample = {
    'Outlook': 'Sunny',
     'Windy': 'Weak'
}
prediction = predict(decision_tree, new_sample)
print("\nPrediction for New Sample:")
print(prediction)

---

📈 Expected Output 

Entropy of Dataset: 0.971

============================================================
LEVEL : 0

Information Gains:

Outlook : 0.571
Windy : 0.42

Best Feature Chosen --> Outlook

Splitting: Outlook = Overcast

============================================================
LEVEL : 1
Leaf Node --> Yes

Splitting: Outlook = Rainy

============================================================
LEVEL : 1

Information Gains:

Windy : 1.0

Best Feature Chosen --> Windy

Splitting: Windy = Strong

============================================================
LEVEL : 2
Leaf Node --> No

Splitting: Windy = Weak

============================================================
LEVEL : 2
Leaf Node --> Yes

Splitting: Outlook = Sunny

============================================================
LEVEL : 1
Leaf Node --> No

============================================================
FINAL DECISION TREE

{'Outlook': {'Overcast': 'Yes', 'Rainy': {'Windy': {'Strong': 'No', 'Weak': 'Yes'}}, 'Sunny': 'No'}}

Prediction for New Sample:
No

---

🌳 Final Decision Tree (Based on ID3)

Outlook?
├── Overcast → Yes
├── Sunny → No
│   
│── Rainy → Windy?
            ├── Strong → Yes
            └── Weak → No

---

🔍 Explanation

Root Node:

👉 Outlook (highest information gain)

---

Branch 1: Overcast

👉 Always → Yes

---

Branch 1: Sunny

👉 Always → No

---

Branch 1: Rainy

👉 Split using Windy

👉 Strong→ Yes

👉 Weak → No

---

🧪 Lab Tasks

Task 1

Manually compute entropy of dataset

---

Task 2

Verify information gains 

---

📊 Key Insights

Concept	Observation
Entropy	Measures impurity
Info Gain	Feature selection
ID3	Greedy algorithm

---

🧠 Conclusion

• ID3 selects:
  • Best feature using information gain
• Builds tree:
  • Top-down
• Works well for:
  • Categorical data