Decision Tree Algorithm
A Decision Tree is a supervised machine learning algorithm used for both
classification problems. The main goal of a decision tree is to split the dataset into
smaller subsets based on features (attributes) so that each subset becomes as pure
as possible
Key Terms
1. Root Node
o The topmost node of the tree.
o It represents the attribute that gives the highest information gain (best split).
2. Decision Node
o These are intermediate nodes where the data is further split based on another
attribute.
3. Leaf/Terminal Node
o The final node that gives the decision or class label (like “Play = Yes” or “No”).
4. Branch
o A path connecting nodes representing the outcome of a decision.
Algorithm Steps (General ID3 / C4.5 Process)
1. Calculate the entropy of the entire dataset (measures impurity).
2. For each attribute, calculate the information gain (how much that attribute helps
reduce entropy).
3. Choose the attribute with the highest information gain as the root node.
4. Split the dataset based on that attribute’s possible values.
5. Repeat the process recursively for each subset until:
o All records belong to one class (pure), or
o No more attributes are left.
Advantages
1. Easy to understand and interpret (like human reasoning).
2. Handles both numerical and categorical data.
3. No need for data normalization
Disadvantages
1. Can overfit (memorize training data).
2. Small changes in data can change the entire tree.
3. Biased toward features with many levels (values).
For Example:-
The matches are scheduled for the month of June. Kindly check the weather conditions and confirm the
feasibility so that we can finalize the decision accordingly
Step 1: Dataset
Day Weather Temperature Humidity Wind Play Football
1 Sunny Hot High Weak No
2 Sunny Hot High Strong No
3 Overcast Hot High Weak Yes
4 Rain Mild High Weak Yes
5 Rain Cool Normal Weak Yes
6 Rain Cool Normal Strong No
7 Overcast Cool Normal Strong Yes
8 Sunny Mild High Weak No
9 Sunny Cool Normal Weak Yes
10 Rain Mild Normal Weak Yes
11 Sunny Mild Normal Strong Yes
12 Overcast Mild High Strong Yes
13 Overcast Hot Normal Weak Yes
14 Rain Mild High Strong No
Total = 14 samples
Play = Yes → 9
Play = No → 5
Step 2: Calculate Entropy of the Target Attribute (“Play Football”)
Step 3: Calculate Information Gain for Each Attribute
(a) Attribute: Weather
Weather Yes No
Sunny 2 3
Overcast 4 0
Rain 3 2
Entropy(Sunny) = −(2/5)log₂(2/5) − (3/5)log₂(3/5) = 0.971
Entropy(Overcast) = 0 (all Yes)
Entropy(Rain) = −(3/5)log₂(3/5) − (2/5)log₂(2/5) = 0.971
Gain(Weather)=0.940−0.693=0.247
(b) Attribute: Temperature
Temperature Yes No
Hot 2 2
Mild 4 2
Cool 3 1
Entropy(Hot) = 1.0
Entropy(Mild) = 0.918
Entropy(Cool) = 0.811
(c) Attribute: Humidity
Humidity Yes No
High 3 4
Normal 6 1
Entropy(High) = 0.985
Entropy(Normal) = 0.592
(d) Attribute: Wind
Wind Yes No
Weak 6 2
Strong 3 3
Entropy(Weak) = 0.811
Entropy(Strong) = 1.0
Step 4: Choose the Attribute with Maximum Gain
Attribute Information Gain
Weather 0.247
Humidity 0.151
Wind 0.048
Temperature 0.029
Best attribute = Weather
Step 5: Create the Root Node
Step 6: Expand Each Branch
Case 1: Weather = Overcast
All “Yes”
Leaf = Yes
Case 2: Weather = Sunny
Subset (Sunny):
Temp Humidity Wind Play
Hot High Weak No
Hot High Strong No
Mild High Weak No
Cool Normal Weak Yes
Mild Normal Strong Yes
→ Entropy(Sunny) = 0.971
→ Next best attribute = Humidity (highest gain within subset)
If Humidity = High → Play = No
If Humidity = Normal → Play = Yes
Case 3: Weather = Rain
Subset (Rain):
Temp Humidity Wind Play
Mild High Weak Yes
Cool Normal Weak Yes
Cool Normal Strong No
Mild Normal Weak Yes
Mild High Strong No
Next best attribute = Wind
If Wind = Weak → Yes
If Wind = Strong → No
:
Final Decision Tree (ID3)
Predictions
If Weather = Overcast → Yes
If Weather = Sunny and Humidity = High → No
If Weather = Sunny and Humidity = Normal → Yes
If Weather = Rain and Wind = Weak → Yes
If Weather = Rain and Wind = Strong → No