Artificial Intelligence and Machine Learning
Module -3
Decision Tree Learning in Machine Learning
1) Decision Tree Representation
A Decision Tree is a tree-structured model used to represent decisions and their possible
outcomes. It is widely used for classification and regression tasks in Machine Learning.
1.1 Structure of a Decision Tree
A decision tree consists of:
• Root Node
o Represents the entire dataset
o First decision is made here
• Internal Nodes
o Represent tests on attributes (features)
o Example: Is Temperature > 30°C?
• Branches (Edges)
o Outcomes of a test on a feature
o Example: Sunny/Rain (When tested on the feature “Outlook”)
• Leaf Nodes (Terminal Nodes)
o Final output (class label)
o Example: Play ? Yes/No
Example
Consider a simple dataset for deciding whether to play tennis:
Outlook Humidity Play
Sunny High No
Sunny Normal Yes
Rain High Yes
Decision Tree Representation:
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 1 of 11
1.2 How to Interpret
• Start at the root: Outlook
• Follow the branch based on the instance
• Continue until you reach a leaf node
Example:
If:
• Outlook = Sunny
• Humidity = High
Path:
• Outlook → Sunny
• Humidity → High
• Result → No
Summary
Decision Tree Representation → How knowledge is structured as a tree of decisions
2) Introduction to Decision Tree Learning
Decision Tree Learning is the process of automatically constructing a decision tree from training
data.
It is a supervised learning method where the data has :
• Features (attributes)
• Class label
Goal
To learn a tree that:
• Correctly classifies training examples
• Generalizes well for unseen data
2.1 How it Works?
The algorithm builds the tree top-down using a divide-and-conquer approach:
1. Start with all training data
2. Select the best attribute to split the data
3. Partition the dataset based on that attribute
4. Repeat recursively for each subset
5. Stop when:
o All examples belong to same class OR
o No attributes remain
2.2 Attribute Selection
The “best” attribute is chosen using measures like:
• Information Gain
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 2 of 11
• Gini Index
2.3 Advantages
• Simple and interpretable
• No need for feature scaling
• Handles nonlinear relationships
2.4 Limitations
• Can overfit (very deep trees)
• Sensitive to small changes in data
• Greedy approach → may not find global optimum
Summary
• Decision Tree Learning → How the tree is automatically built from data
3) ID3 (Iterative Dichotomiser 3) Algorithm
ID3 is a supervised learning algorithm used to build a decision tree for classification
problems. It was introduced by Ross Quinlan.
3.1 Purpose of ID3
To construct a decision tree by:
• Selecting the best attribute at each step
• Splitting the dataset recursively
• Until the data is perfectly classified (or no further split is possible)
3.2 Key Idea
ID3 uses Information Gain to decide:
“Which attribute should be the root (or next node)?”
The attribute that gives the highest reduction in uncertainty (entropy) is chosen.
3.3 Important Concepts
(a) Entropy
• If all examples belong to one class → Entropy = 0 (pure)
• If evenly mixed → Entropy is maximum
(b) Information Gain
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 3 of 11
It is the measure of how much an attribute reduces entropy.
4. ID3 Algorithm
Step 1: Start with full dataset
• All training examples at the root
Step 2: Compute entropy of dataset
Step 3: For each attribute
• Compute Information Gain
Step 4: Select best attribute
• Choose attribute with highest Information Gain
• Make it the decision node
Step 5: Split dataset
• Create branches for each attribute value
Step 6: Repeat recursively
For each subset:
• If all examples belong to same class → make leaf
• If no attributes left → use majority class
• Else → repeat process
Step 7: Stop when
• All data is classified, or
• No further gain is possible
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 4 of 11
6. Illustrative Example ID3 Algorithm
Concept : Tennis Game (Can a Game be played or not?)
a) Computation of Entropy for Dataset (S)
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 5 of 11
b) Information Gain on Attribute : Wind
c) Information Gain on Attribute : Outlook
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 6 of 11
d) Information Gain on Attribute : Temperature
e) Information Gain on Attribute : Humidity
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 7 of 11
f) Selection of Attribute
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 8 of 11
Graphical Representation of Partitioning of Data Points and learning a
decision Tree
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 9 of 11
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 10 of 11
*** End of Document ***
_____________________________________________________________________________________________________________________
Compiled by : Narayana Maddala, Professor of Practice, NHCE Page 11 of 11