Experiment No 5: To construct a decision tree using the ID3 algorithm on a simple
classification dataset.
Objective: To write python code to construct a decision tree using the ID3 algorithm on a simple
classification dataset
Theory:
Decision trees classify instances by sorting them down the tree from the root to some leaf node,
which provides the classification of the instance. Each node in the tree specifies a test of some
attribute of the instance, and each branch descending from that node corresponds to one of the
possible values for this attribute. An instance is classified by starting at the root node of the tree,
testing the attribute specified by this node, then moving down the tree branch corresponding to
the value of the attribute in the given example. This process is then repeated for the subtree
rooted at the new node.
Code:
import pandas as pd
import numpy as np
from math import log2
class DecisionTreeID3:
def __init__(self):
[Link] = {}
def entropy(self, data, target_attr):
"""Calculate the entropy of the target attribute."""
values, counts = [Link](data[target_attr], return_counts=True)
entropy = -sum((counts[i] / sum(counts)) * log2(counts[i] / sum(counts)) for i in
range(len(values)))
return entropy
def information_gain(self, data, split_attr, target_attr):
"""Calculate the information gain of a feature."""
total_entropy = [Link](data, target_attr)
values, counts = [Link](data[split_attr], return_counts=True)
weighted_entropy = sum((counts[i] / sum(counts)) * [Link](data[data[split_attr] ==
values[i]], target_attr) for i in range(len(values)))
info_gain = total_entropy - weighted_entropy
return info_gain
def id3(self, data, original_data, features, target_attr, parent_node=None):
"""Recursive function to build the decision tree."""
# If all target values are the same, return the label
if len([Link](data[target_attr])) <= 1:
return [Link](data[target_attr])[0]
# If dataset is empty, return the majority label of the parent dataset
elif len(data) == 0:
return [Link](original_data[target_attr])
[[Link]([Link](original_data[target_attr], return_counts=True)[1])]
# If no features are left, return the majority label of the current dataset
elif len(features) == 0:
return [Link](data[target_attr])[[Link]([Link](data[target_attr],
return_counts=True)[1])]
else:
# Select the feature with the highest information gain
info_gains = [self.information_gain(data, feature, target_attr) for feature in features]
best_feature = features[[Link](info_gains)]
# Create the tree structure
tree = {best_feature: {}}
# Remove the best feature from the list
features = [f for f in features if f != best_feature]
# For each unique value of the best feature, grow the tree recursively
for value in [Link](data[best_feature]):
subset = data[data[best_feature] == value]
subtree = self.id3(subset, original_data, features, target_attr)
tree[best_feature][value] = subtree
return tree
def fit(self, data, target_attr):
"""Fit the decision tree to the data."""
features = list([Link])
[Link](target_attr)
[Link] = self.id3(data, data, features, target_attr)
def predict(self, query):
"""Predict the class label for a single query."""
tree = [Link]
while isinstance(tree, dict):
root_node = list([Link]())[0]
if query[root_node] in tree[root_node]:
tree = tree[root_node][query[root_node]]
else:
return None # Value not found in the tree
return tree
# Example dataset: PlayTennis
data = [Link]({
'Outlook': ['Sunny', 'Sunny', 'Overcast', 'Rain', 'Rain', 'Rain', 'Overcast', 'Sunny', 'Sunny', 'Rain',
'Sunny', 'Overcast', 'Overcast', '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', 'Normal', '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']
})
# Train the decision tree
id3 = DecisionTreeID3()
[Link](data, 'PlayTennis')
# Print the decision tree
print("Decision Tree:")
print([Link])
# Example prediction
query = {'Outlook': 'Sunny', 'Temperature': 'Cool', 'Humidity': 'High', 'Wind': 'Strong'}
print("Prediction:", [Link](query))
Output:
Decision Tree:
{'Outlook': {'Overcast': 'Yes', 'Rain': {'Wind': {'Strong': 'No', 'Weak': 'Yes'}}, 'Sunny':
{'Humidity': {'High': 'No', 'Normal': 'Yes'}}}}
Prediction: No