ID3 Algorithm — Worked Examples
ID3 Decision Tree Algorithm
Two Fully Worked Examples with Complete Step-by-Step Calculations
Example 1: PlayTennis Dataset
Example 2: NASA Martian vs. Human Classification
Page 1
ID3 Algorithm — Worked Examples
Core Concept: How ID3 Works
The ID3 (Iterative Dichotomiser 3) algorithm builds a decision tree by repeatedly choosing the attribute that best separates
the data into pure classes. "Best" is measured using Information Gain, which is based on Entropy — a measure of uncertainty
or impurity in a set of data.
The Three Formulas
Entropy = −(p / (p+n))·log₂(p / (p+n)) − (n / (p+n))·log₂(n / (p+n))
Entropy (amount of uncertainty in a dataset with p positive and n negative examples):
I(Attribute) = Σᵢ [ (pᵢ + nᵢ) / (p + n) ] × Entropy(Aᵢ)
Average Information (weighted entropy after splitting on an attribute A with branches i):
Gain(Attribute) = Entropy(S) − I(Attribute)
Information Gain (reduction in entropy achieved by splitting on an attribute):
The Algorithm, Step by Step
● 1. Compute the overall Entropy(S) for the current dataset.
● 2. For every remaining attribute, compute the entropy of each of its value-subsets.
● 3. Combine those into the Average Information I(Attribute) for that attribute.
● 4. Calculate the Information Gain for each attribute: Gain = Entropy(S) − I(Attribute).
● 5. Pick the attribute with the highest Gain — this becomes the decision node.
● 6. Split the dataset by that attribute's values. Any branch that is already pure (entropy = 0) becomes a leaf
immediately.
● 7. For every branch that is still mixed, repeat the whole process (steps 1–6) using only that subset of rows and the
remaining attributes.
● 8. Stop when every branch ends in a pure leaf, or no attributes remain.
Page 2
ID3 Algorithm — Worked Examples
Example 1 — The PlayTennis Dataset
We have 14 records describing weather conditions on different days, with four attributes — Outlook, Temperature, Humidity,
and Windy — and we want to predict whether tennis will be played (PlayTennis).
[Link] Outlook Temperature Humidity Windy PlayTennis
1 Sunny Hot High Weak No
2 Sunny Hot High Strong No
3 Overcast Hot High Weak Yes
4 Rainy Mild High Weak Yes
5 Rainy Cool Normal Weak Yes
6 Rainy Cool Normal Strong No
7 Overcast Cool Normal Strong Yes
8 Sunny Mild High Weak No
9 Sunny Cool Normal Weak Yes
10 Rainy Mild Normal Weak Yes
11 Sunny Mild Normal Strong Yes
12 Overcast Mild High Strong Yes
13 Overcast Hot Normal Weak Yes
14 Rainy Mild High Strong No
Total = 14 rows. P (Yes) = 9, N (No) = 5.
Step 1 — Entropy of the Whole Dataset
Entropy(S) = -(9/14)·log₂(9/14) - (5/14)·log₂(5/14)
= -(0.643)·log₂(0.643) - (0.357)·log₂(0.357)
= -(0.643)×(-0.637) - (0.357)×(-1.485)
= 0.410 + 0.531
= 0.940
This is our baseline — the dataset is fairly mixed, so entropy starts high (close to the maximum possible value of 1.0).
Step 2 — Compute Gain for Every Attribute (Root Node)
(a) Outlook — values: Sunny, Overcast, Rainy
Entropy(Outlook=Sunny) = -(2/5)·log₂(2/5) - (3/5)·log₂(3/5)
= -(0.400)·log₂(0.400) - (0.600)·log₂(0.600)
= -(0.400)×(-1.322) - (0.600)×(-0.737)
= 0.529 + 0.442
= 0.971
Entropy(Outlook=Rainy) = -(3/5)·log₂(3/5) - (2/5)·log₂(2/5)
= -(0.600)·log₂(0.600) - (0.400)·log₂(0.400)
= -(0.600)×(-0.737) - (0.400)×(-1.322)
= 0.442 + 0.529
= 0.971
Entropy(Outlook=Overcast) = -(4/4)·log₂(4/4) - (0/4)·log₂(0/4)
Entropy(Outlook=Overcast) = 0 (all 4 examples belong to one class → pure
subset)
I(Outlook) = (5/14)×0.971 + (5/14)×0.971 + (4/14)×0.000
= 0.347 + 0.347 + 0.000
= 0.694
Page 3
ID3 Algorithm — Worked Examples
Gain(Outlook) = Entropy(S) − I(Outlook) = 0.940 − 0.694 = 0.247
(b) Temperature — values: Hot, Mild, Cool
Entropy(Temp=Hot) = -(2/4)·log₂(2/4) - (2/4)·log₂(2/4)
= -(0.500)·log₂(0.500) - (0.500)·log₂(0.500)
= -(0.500)×(-1.000) - (0.500)×(-1.000)
= 0.500 + 0.500
= 1.000
Entropy(Temp=Mild) = -(4/6)·log₂(4/6) - (2/6)·log₂(2/6)
= -(0.667)·log₂(0.667) - (0.333)·log₂(0.333)
= -(0.667)×(-0.585) - (0.333)×(-1.585)
= 0.390 + 0.528
= 0.918
Entropy(Temp=Cool) = -(3/4)·log₂(3/4) - (1/4)·log₂(1/4)
= -(0.750)·log₂(0.750) - (0.250)·log₂(0.250)
= -(0.750)×(-0.415) - (0.250)×(-2.000)
= 0.311 + 0.500
= 0.811
I(Temperature) = (4/14)×1.000 + (6/14)×0.918 + (4/14)×0.811
= 0.286 + 0.394 + 0.232
= 0.911
Gain(Temperature) = Entropy(S) − I(Temperature) = 0.940 − 0.911 = 0.029
(c) Humidity — values: High, Normal
Entropy(Humidity=High) = -(3/7)·log₂(3/7) - (4/7)·log₂(4/7)
= -(0.429)·log₂(0.429) - (0.571)·log₂(0.571)
= -(0.429)×(-1.222) - (0.571)×(-0.807)
= 0.524 + 0.461
= 0.985
Entropy(Humidity=Normal) = -(6/7)·log₂(6/7) - (1/7)·log₂(1/7)
= -(0.857)·log₂(0.857) - (0.143)·log₂(0.143)
= -(0.857)×(-0.222) - (0.143)×(-2.807)
= 0.191 + 0.401
= 0.592
I(Humidity) = (7/14)×0.985 + (7/14)×0.592
= 0.493 + 0.296
= 0.788
Gain(Humidity) = Entropy(S) − I(Humidity) = 0.940 − 0.788 = 0.152
(d) Windy — values: Strong, Weak
Entropy(Windy=Strong) = -(3/6)·log₂(3/6) - (3/6)·log₂(3/6)
= -(0.500)·log₂(0.500) - (0.500)·log₂(0.500)
= -(0.500)×(-1.000) - (0.500)×(-1.000)
= 0.500 + 0.500
= 1.000
Entropy(Windy=Weak) = -(6/8)·log₂(6/8) - (2/8)·log₂(2/8)
= -(0.750)·log₂(0.750) - (0.250)·log₂(0.250)
= -(0.750)×(-0.415) - (0.250)×(-2.000)
Page 4
ID3 Algorithm — Worked Examples
= 0.311 + 0.500
= 0.811
I(Windy) = (6/14)×1.000 + (8/14)×0.811
= 0.429 + 0.464
= 0.892
Gain(Windy) = Entropy(S) − I(Windy) = 0.940 − 0.892 = 0.048
Comparison of All Gains
Attribute Gain
Outlook 0.247 ← highest
Humidity 0.152
Windy 0.048
Temperature 0.029
Root Node: Outlook
Page 5
ID3 Algorithm — Worked Examples
Step 3 — Split by Outlook
● Outlook = Overcast → all 4 rows are "Yes" → Entropy = 0 → pure leaf: "Yes". No further splitting needed.
● Outlook = Sunny → mixed (2 Yes, 3 No) → needs further splitting.
● Outlook = Rainy → mixed (3 Yes, 2 No) → needs further splitting.
We now repeat the entire Gain calculation separately on the Sunny subset and the Rainy subset.
Step 4 — Branch: Outlook = Sunny
Subset (5 rows): Sunny rows only — P = 2, N = 3
Entropy(S_sunny) = -(2/5)·log₂(2/5) - (3/5)·log₂(3/5)
= -(0.400)·log₂(0.400) - (0.600)·log₂(0.600)
= -(0.400)×(-1.322) - (0.600)×(-0.737)
= 0.529 + 0.442
= 0.971
Humidity (within Sunny)
Entropy(Humidity (within Sunny)=High) = -(0/3)·log₂(0/3) - (3/3)·log₂(3/3)
Entropy(Humidity (within Sunny)=High) = 0 (all 3 examples belong to one class
→ pure subset)
Entropy(Humidity (within Sunny)=Normal) = -(2/2)·log₂(2/2) - (0/2)·log₂(0/2)
Entropy(Humidity (within Sunny)=Normal) = 0 (all 2 examples belong to one
class → pure subset)
I(Humidity (within Sunny)) = (3/5)×0.000 + (2/5)×0.000
= 0.000 + 0.000
= 0.000
Gain(Humidity (within Sunny)) = Entropy(S) − I(Humidity (within Sunny)) = 0.971
− 0.000 = 0.971
Windy (within Sunny)
Entropy(Windy (within Sunny)=Strong) = -(1/2)·log₂(1/2) - (1/2)·log₂(1/2)
= -(0.500)·log₂(0.500) - (0.500)·log₂(0.500)
= -(0.500)×(-1.000) - (0.500)×(-1.000)
= 0.500 + 0.500
= 1.000
Entropy(Windy (within Sunny)=Weak) = -(1/3)·log₂(1/3) - (2/3)·log₂(2/3)
= -(0.333)·log₂(0.333) - (0.667)·log₂(0.667)
= -(0.333)×(-1.585) - (0.667)×(-0.585)
= 0.528 + 0.390
= 0.918
I(Windy (within Sunny)) = (2/5)×1.000 + (3/5)×0.918
= 0.400 + 0.551
= 0.951
Gain(Windy (within Sunny)) = Entropy(S) − I(Windy (within Sunny)) = 0.971 −
0.951 = 0.020
Page 6
ID3 Algorithm — Worked Examples
Temperature (within Sunny)
Entropy(Temperature (within Sunny)=Cool) = -(1/1)·log₂(1/1) - (0/1)·log₂(0/1)
Entropy(Temperature (within Sunny)=Cool) = 0 (all 1 examples belong to one
class → pure subset)
Entropy(Temperature (within Sunny)=Hot) = -(0/2)·log₂(0/2) - (2/2)·log₂(2/2)
Entropy(Temperature (within Sunny)=Hot) = 0 (all 2 examples belong to one
class → pure subset)
Entropy(Temperature (within Sunny)=Mild) = -(1/2)·log₂(1/2) - (1/2)·log₂(1/2)
= -(0.500)·log₂(0.500) - (0.500)·log₂(0.500)
= -(0.500)×(-1.000) - (0.500)×(-1.000)
= 0.500 + 0.500
= 1.000
I(Temperature (within Sunny)) = (1/5)×0.000 + (2/5)×0.000 + (2/5)×1.000
= 0.000 + 0.000 + 0.400
= 0.400
Gain(Temperature (within Sunny)) = Entropy(S) − I(Temperature (within Sunny)) =
0.971 − 0.400 = 0.571
Attribute Gain
Humidity 0.971 ← highest
Temperature 0.571
Windy 0.020
Node under Sunny: Humidity
Since High → all No and Normal → all Yes, both resulting children are pure leaves (entropy = 0). No further splitting is
needed under the Sunny branch.
Page 7
ID3 Algorithm — Worked Examples
Step 5 — Branch: Outlook = Rainy
Subset (5 rows): Rainy rows only — P = 3, N = 2
Entropy(S_rainy) = -(3/5)·log₂(3/5) - (2/5)·log₂(2/5)
= -(0.600)·log₂(0.600) - (0.400)·log₂(0.400)
= -(0.600)×(-0.737) - (0.400)×(-1.322)
= 0.442 + 0.529
= 0.971
Humidity (within Rainy)
Entropy(Humidity (within Rainy)=High) = -(1/2)·log₂(1/2) - (1/2)·log₂(1/2)
= -(0.500)·log₂(0.500) - (0.500)·log₂(0.500)
= -(0.500)×(-1.000) - (0.500)×(-1.000)
= 0.500 + 0.500
= 1.000
Entropy(Humidity (within Rainy)=Normal) = -(2/3)·log₂(2/3) - (1/3)·log₂(1/3)
= -(0.667)·log₂(0.667) - (0.333)·log₂(0.333)
= -(0.667)×(-0.585) - (0.333)×(-1.585)
= 0.390 + 0.528
= 0.918
I(Humidity (within Rainy)) = (2/5)×1.000 + (3/5)×0.918
= 0.400 + 0.551
= 0.951
Gain(Humidity (within Rainy)) = Entropy(S) − I(Humidity (within Rainy)) = 0.971
− 0.951 = 0.020
Windy (within Rainy)
Entropy(Windy (within Rainy)=Strong) = -(0/2)·log₂(0/2) - (2/2)·log₂(2/2)
Entropy(Windy (within Rainy)=Strong) = 0 (all 2 examples belong to one class
→ pure subset)
Entropy(Windy (within Rainy)=Weak) = -(3/3)·log₂(3/3) - (0/3)·log₂(0/3)
Entropy(Windy (within Rainy)=Weak) = 0 (all 3 examples belong to one class →
pure subset)
I(Windy (within Rainy)) = (2/5)×0.000 + (3/5)×0.000
= 0.000 + 0.000
= 0.000
Gain(Windy (within Rainy)) = Entropy(S) − I(Windy (within Rainy)) = 0.971 −
0.000 = 0.971
Temperature (within Rainy)
Entropy(Temperature (within Rainy)=Cool) = -(1/2)·log₂(1/2) - (1/2)·log₂(1/2)
= -(0.500)·log₂(0.500) - (0.500)·log₂(0.500)
= -(0.500)×(-1.000) - (0.500)×(-1.000)
= 0.500 + 0.500
= 1.000
Entropy(Temperature (within Rainy)=Mild) = -(2/3)·log₂(2/3) - (1/3)·log₂(1/3)
= -(0.667)·log₂(0.667) - (0.333)·log₂(0.333)
= -(0.667)×(-0.585) - (0.333)×(-1.585)
Page 8
ID3 Algorithm — Worked Examples
= 0.390 + 0.528
= 0.918
I(Temperature (within Rainy)) = (2/5)×1.000 + (3/5)×0.918
= 0.400 + 0.551
= 0.951
Gain(Temperature (within Rainy)) = Entropy(S) − I(Temperature (within Rainy)) =
0.971 − 0.951 = 0.020
Attribute Gain
Windy 0.971 ← highest
Humidity 0.020
Temperature 0.020
Node under Rainy: Windy
Since Strong → all No and Weak → all Yes, both resulting children are pure leaves. Done.
Final Decision Tree
Outlook
/ | \
Sunny Overcast Rainy
| | |
Humidity Yes Windy
/ \ / \
High Normal Strong Weak
| | | |
No Yes No Yes
Reading it as rules:
● If Outlook = Overcast → Play (Yes), always.
● If Outlook = Sunny and Humidity = High → No.
● If Outlook = Sunny and Humidity = Normal → Yes.
● If Outlook = Rainy and Windy = Strong → No.
● If Outlook = Rainy and Windy = Weak → Yes.
Page 9
ID3 Algorithm — Worked Examples
Example 2 — NASA: Martian vs. Human Classification
NASA wants to discriminate between Martians (M) and Humans (H) using four characteristics: Green ∈ {N, Y}, Legs ∈ {2,
3}, Height ∈ {S, T}, Smelly ∈ {N, Y}. We are asked to find the root node and the first left node using ID3.
# Species Green Legs Height Smelly
1 M N 3 S Y
2 M Y 2 T N
3 M Y 3 T N
4 M N 2 S Y
5 M Y 3 T N
6 H N 2 T Y
7 H N 2 S N
8 H N 2 T N
9 H Y 2 S N
10 H N 2 T Y
Total = 10 rows. M = 5, H = 5 (treat M as "p", H as "n").
Step 1 — Entropy of the Whole Dataset
Entropy(S) = -(5/10)·log₂(5/10) - (5/10)·log₂(5/10)
= -(0.500)·log₂(0.500) - (0.500)·log₂(0.500)
= -(0.500)×(-1.000) - (0.500)×(-1.000)
= 0.500 + 0.500
= 1.000
Perfectly mixed — maximum possible uncertainty. This is our baseline.
Step 2 — Compute Gain for Every Attribute (Root Node)
(a) Green — values: N, Y
N: rows 1,4,6,7,8,10
Entropy(Green=N) = -(2/6)·log₂(2/6) - (4/6)·log₂(4/6)
= -(0.333)·log₂(0.333) - (0.667)·log₂(0.667)
= -(0.333)×(-1.585) - (0.667)×(-0.585)
= 0.528 + 0.390
= 0.918
Y: rows 2,3,5,9
Entropy(Green=Y) = -(3/4)·log₂(3/4) - (1/4)·log₂(1/4)
= -(0.750)·log₂(0.750) - (0.250)·log₂(0.250)
= -(0.750)×(-0.415) - (0.250)×(-2.000)
= 0.311 + 0.500
= 0.811
I(Green) = (6/10)×0.918 + (4/10)×0.811
= 0.551 + 0.325
= 0.875
Gain(Green) = Entropy(S) − I(Green) = 1.000 − 0.875 = 0.125
(b) Legs — values: 2, 3
Legs=3: rows 1,3,5
Page 10
ID3 Algorithm — Worked Examples
Entropy(Legs=3) = -(3/3)·log₂(3/3) - (0/3)·log₂(0/3)
Entropy(Legs=3) = 0 (all 3 examples belong to one class → pure subset)
Legs=2: rows 2,4,6,7,8,9,10
Entropy(Legs=2) = -(2/7)·log₂(2/7) - (5/7)·log₂(5/7)
= -(0.286)·log₂(0.286) - (0.714)·log₂(0.714)
= -(0.286)×(-1.807) - (0.714)×(-0.485)
= 0.516 + 0.347
= 0.863
I(Legs) = (3/10)×0.000 + (7/10)×0.863
= 0.000 + 0.604
= 0.604
Gain(Legs) = Entropy(S) − I(Legs) = 1.000 − 0.604 = 0.396
(c) Height — values: S, T
S: rows 1,4,7,9
Entropy(Height=S) = -(2/4)·log₂(2/4) - (2/4)·log₂(2/4)
= -(0.500)·log₂(0.500) - (0.500)·log₂(0.500)
= -(0.500)×(-1.000) - (0.500)×(-1.000)
= 0.500 + 0.500
= 1.000
T: rows 2,3,5,6,8,10
Entropy(Height=T) = -(3/6)·log₂(3/6) - (3/6)·log₂(3/6)
= -(0.500)·log₂(0.500) - (0.500)·log₂(0.500)
= -(0.500)×(-1.000) - (0.500)×(-1.000)
= 0.500 + 0.500
= 1.000
I(Height) = (4/10)×1.000 + (6/10)×1.000
= 0.400 + 0.600
= 1.000
Gain(Height) = Entropy(S) − I(Height) = 1.000 − 1.000 = 0.000
(d) Smelly — values: N, Y
Y: rows 1,4,6,10
Entropy(Smelly=Y) = -(2/4)·log₂(2/4) - (2/4)·log₂(2/4)
= -(0.500)·log₂(0.500) - (0.500)·log₂(0.500)
= -(0.500)×(-1.000) - (0.500)×(-1.000)
= 0.500 + 0.500
= 1.000
N: rows 2,3,5,7,8,9
Entropy(Smelly=N) = -(3/6)·log₂(3/6) - (3/6)·log₂(3/6)
= -(0.500)·log₂(0.500) - (0.500)·log₂(0.500)
= -(0.500)×(-1.000) - (0.500)×(-1.000)
= 0.500 + 0.500
= 1.000
I(Smelly) = (4/10)×1.000 + (6/10)×1.000
= 0.400 + 0.600
Page 11
ID3 Algorithm — Worked Examples
= 1.000
Gain(Smelly) = Entropy(S) − I(Smelly) = 1.000 − 1.000 = 0.000
Comparison of All Gains
Attribute Gain
Legs 0.396 ← highest
Green 0.125
Height 0.000
Smelly 0.000
Root Node: Legs
This makes intuitive sense: Height and Smelly split the data 50/50 in both branches with zero separating power, while Legs =
3 perfectly isolates a pure group of Martians — a highly informative split.
Page 12
ID3 Algorithm — Worked Examples
Step 3 — Split by Legs
● Legs = 3 → rows 1, 3, 5 → all Martian (M) → Entropy = 0 → pure leaf: "M". Done, no further splitting.
● Legs = 2 → rows 2,4,6,7,8,9,10 (M = 2, H = 5) → still mixed → needs further splitting.
Since Legs = 2 is the branch requiring more work, this is our left node to expand next.
Step 4 — Find the First Left Node (Legs = 2 Subset)
# Species Green Height Smelly
2 M Y T N
4 M N S Y
6 H N T Y
7 H N S N
8 H N T N
9 H Y S N
10 H N T Y
Subset entropy (already derived above as "Legs=2"):
Entropy(S_legs2) = -(2/7)·log₂(2/7) - (5/7)·log₂(5/7)
= -(0.286)·log₂(0.286) - (0.714)·log₂(0.714)
= -(0.286)×(-1.807) - (0.714)×(-0.485)
= 0.516 + 0.347
= 0.863
(a) Green — values: N, Y
Y: rows 2,9
Entropy(Green=Y) = -(1/2)·log₂(1/2) - (1/2)·log₂(1/2)
= -(0.500)·log₂(0.500) - (0.500)·log₂(0.500)
= -(0.500)×(-1.000) - (0.500)×(-1.000)
= 0.500 + 0.500
= 1.000
N: rows 4,6,7,8,10
Entropy(Green=N) = -(1/5)·log₂(1/5) - (4/5)·log₂(4/5)
= -(0.200)·log₂(0.200) - (0.800)·log₂(0.800)
= -(0.200)×(-2.322) - (0.800)×(-0.322)
= 0.464 + 0.258
= 0.722
I(Green) = (2/7)×1.000 + (5/7)×0.722
= 0.286 + 0.516
= 0.801
Gain(Green) = Entropy(S) − I(Green) = 0.863 − 0.801 = 0.062
(b) Height — values: S, T
S: rows 4,7,9
Entropy(Height=S) = -(1/3)·log₂(1/3) - (2/3)·log₂(2/3)
= -(0.333)·log₂(0.333) - (0.667)·log₂(0.667)
= -(0.333)×(-1.585) - (0.667)×(-0.585)
= 0.528 + 0.390
= 0.918
Page 13
ID3 Algorithm — Worked Examples
T: rows 2,6,8,10
Entropy(Height=T) = -(1/4)·log₂(1/4) - (3/4)·log₂(3/4)
= -(0.250)·log₂(0.250) - (0.750)·log₂(0.750)
= -(0.250)×(-2.000) - (0.750)×(-0.415)
= 0.500 + 0.311
= 0.811
I(Height) = (3/7)×0.918 + (4/7)×0.811
= 0.394 + 0.464
= 0.857
Gain(Height) = Entropy(S) − I(Height) = 0.863 − 0.857 = 0.006
(c) Smelly — values: N, Y
Y: rows 4,6,10
Entropy(Smelly=Y) = -(1/3)·log₂(1/3) - (2/3)·log₂(2/3)
= -(0.333)·log₂(0.333) - (0.667)·log₂(0.667)
= -(0.333)×(-1.585) - (0.667)×(-0.585)
= 0.528 + 0.390
= 0.918
N: rows 2,7,8,9
Entropy(Smelly=N) = -(1/4)·log₂(1/4) - (3/4)·log₂(3/4)
= -(0.250)·log₂(0.250) - (0.750)·log₂(0.750)
= -(0.250)×(-2.000) - (0.750)×(-0.415)
= 0.500 + 0.311
= 0.811
I(Smelly) = (3/7)×0.918 + (4/7)×0.811
= 0.394 + 0.464
= 0.857
Gain(Smelly) = Entropy(S) − I(Smelly) = 0.863 − 0.857 = 0.006
Comparison
Attribute Gain
Green 0.062 ← highest
Height 0.006
Smelly 0.006
First Left Node (under Legs = 2): Green
Final Answer Summary
Legs
/ \
(=2) (=3)
| |
Green M <- pure leaf
/ \
(=Y) (=N)
? ? <- still mixed, tree continues
Node chosen Gain Reasoning
Page 14
ID3 Algorithm — Worked Examples
Root Legs 0.396 Legs = 3 perfectly isolates a pure Martian group
First left node Green 0.062 Best of the remaining weak candidates; children
(Legs = 2) still mixed, tree would continue
Note: Height and Smelly are essentially useless predictors in this dataset — Gain = 0 at the root and barely above 0 in the
sub-branch — while Legs does almost all of the discriminating work, exactly as ID3's gain calculation correctly reveals.
Page 15