Ex.
No:2 ID3 (Iterative Dichotomiser 3) algorithm using Decision Tree
The aim of the ID3 (Iterative Dichotomiser 3) algorithm is to:
Construct a decision tree for classification tasks.
Select attributes that provide the highest information gain (i.e., best separation of
classes) at each step.
Produce a simple, interpretable model that can classify unseen data based on learned
rules.
⚙️Algorithm (Step-by-Step)
1. Input:
A dataset with categorical attributes and a target class label.
o
2. Calculate Entropy of the dataset:
Entropy(S)=-\sum _{i=1}^cp_i\log _2(p_i)
3. where p_i is the proportion of class i in dataset S.
4. For each attribute:
o Partition the dataset based on the attribute’s values.
o Compute the entropy of each subset.
o Calculate the Information Gain:
Gain(S,A)=Entropy(S)-\sum _{v\in Values(A)}\frac{|S_v|}{|S|}\cdot Entropy(S_v)
5. Select the attribute with the highest information gain as the decision node.
6. Split the dataset into subsets based on the chosen attribute.
7. Repeat recursively for each subset until:
o All samples in a subset belong to the same class (leaf node).
o No attributes remain (assign majority class).
o Dataset is empty (assign default class).
8. Output:
A decision tree that can be used for classification.
import math
import pandas as pd
# Sample dataset: Play Tennis
data = {
'Outlook':
['Sunny','Sunny','Overcast','Rain','Rain','Rain','Overcast','Sunny','Sunny','Rain','Sunny','Overcast','Ove
rcast','Rain'],
'Temperature':
['Hot','Hot','Hot','Mild','Cool','Cool','Cool','Mild','Cool','Mild','Mild','Mild','Hot','Mild'],
'Humidity':
['High','High','High','High','Normal','Normal','Normal','High','Normal','Normal','Normal','High','Norma
l','High'],
'Wind':
['Weak','Strong','Weak','Weak','Weak','Strong','Strong','Weak','Weak','Weak','Strong','Strong','Weak'
,'Strong'],
'PlayTennis': ['No','No','Yes','Yes','Yes','No','Yes','No','Yes','Yes','Yes','Yes','Yes','No']
df = [Link](data)
# Function to calculate entropy
def entropy(target_col):
elements, counts = [Link](target_col, return_counts=True)
entropy_val = 0
for i in range(len(elements)):
prob = counts[i]/sum(counts)
entropy_val += -prob * math.log2(prob)
return entropy_val
# Function to calculate information gain
def info_gain(data, split_attribute, target_attribute):
# Total entropy
total_entropy = entropy(data[target_attribute])
# Values and counts for the split attribute
vals, counts = [Link](data[split_attribute], return_counts=True)
# Weighted entropy
weighted_entropy = 0
for i in range(len(vals)):
subset = data[data[split_attribute] == vals[i]]
weighted_entropy += (counts[i]/sum(counts)) * entropy(subset[target_attribute])
# Information gain
return total_entropy - weighted_entropy
# Recursive ID3 function
def ID3(data, original_data, features, target_attribute, parent_node_class=None):
# If all target values are the same → return that class
if len([Link](data[target_attribute])) <= 1:
return [Link](data[target_attribute])[0]
# If dataset empty → return majority class of original dataset
elif len(data) == 0:
return [Link](original_data[target_attribute])
[[Link]([Link](original_data[target_attribute], return_counts=True)[1])]
# If no features left → return parent node class
elif len(features) == 0:
return parent_node_class
else:
# Majority class of current node
parent_node_class = [Link](data[target_attribute])
[[Link]([Link](data[target_attribute], return_counts=True)[1])]
# Choose best feature
gains = [info_gain(data, feature, target_attribute) for feature in features]
best_feature = features[[Link](gains)]
# Build tree
tree = {best_feature:{}}
# Remove chosen feature
features = [f for f in features if f != best_feature]
# Split dataset
for value in [Link](data[best_feature]):
sub_data = data[data[best_feature] == value]
subtree = ID3(sub_data, original_data, features, target_attribute, parent_node_class)
tree[best_feature][value] = subtree
return tree
# Run ID3
import numpy as np
features = [Link][:-1] # all except target
tree = ID3(df, df, features, 'PlayTennis')
print("Decision Tree:")
print(tree)
output
Decision Tree:
{'Outlook': {
'Overcast': 'Yes',
'Sunny': {'Humidity': {'High': 'No', 'Normal': 'Yes'}},
'Rain': {'Wind': {'Weak': 'Yes', 'Strong': 'No'}}
}}