How to create a Decision Tree using the ID3 algorithm?

Question

NASA wants to be able to discriminate between Martians (M) and Humans (H) based on the
following characteristics: Green ∈{N, Y }, Legs ∈{2, 3}, Height ∈{S, T}, Smelly ∈{N, Y }.
Our available training data is as follows:

a) Greedily learn a decision tree using the ID3 algorithm and draw the tree.
b) Write the learned concept for Martian as a set of conjunctive rules (e.g., if (green=Y
and legs=2 and height=T and smelly=N), then Martian; else if ... then Martian; ...; else
Human).

Answer 1

a) See the following figure for the ID3 decision tree:

b) Only the disjunction of conjunctions for Martians was required:

$\begin{aligned} &(\text { Legs }=3) \vee \\ &(\text { Legs }=2 \wedge \text { Green }=\text { Yes } \wedge \text { Height }=\text { Tall }) \vee \\ &(\text { Legs }=2 \wedge \text { Green }=\text { No } \wedge \text { Height }=\text { Short } \wedge \text { Smelly }=\text { Yes }) \end{aligned}$

Python Code

Step 1: Organize the Dataset

Our data has the following features and values:

• Species: Target variable (M or H)
• Features:
  • Green: $N$ or $Y$
  • Legs: $2$ or $3$
  • Height: $S$ or $T$
  • Smelly: $N$ or $Y$

Index	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

Step 2: Calculate the Initial Entropy for the Target Variable (Species)

We start by calculating the entropy of the target variable, Species, which has two classes: M (Martian) and H (Human).

Total Counts

• Martians (M): 5
• Humans (H): 5
• Total: 10

Entropy Formula

The entropy $E$ for a binary classification is calculated as:

$$E = -p_+ \log_2(p_+) - p_- \log_2(p_-)$$

Where:

• $p_+$: Probability of positive class (M)
• $p_-$: Probability of negative class (H)

Calculation

$$p(M) = \frac{5}{10} = 0.5$$

$$p(H) = \frac{5}{10} = 0.5$$

$$E(Species) = -0.5 \cdot \log_2(0.5) - 0.5 \cdot \log_2(0.5)$$

$$= -0.5 \cdot (-1) - 0.5 \cdot (-1)$$

$$= 1.0$$

Step 3: Calculate Entropy and Information Gain for Each Feature

We’ll calculate the entropy for each feature split and determine the information gain.

Feature: Green

Green can be either Y or N.

For Green = Y:

• Martians (M): 3
• Humans (H): 1
• Total: 4

Entropy:

$$E(Green = Y) = -\left(\frac{3}{4}\right) \log_2\left(\frac{3}{4}\right) - \left(\frac{1}{4}\right) \log_2\left(\frac{1}{4}\right)$$

$$= -0.75 \cdot \log_2(0.75) - 0.25 \cdot \log_2(0.25)$$

$$= -0.75 \cdot (-0.415) - 0.25 \cdot (-2)$$

$$= 0.311 + 0.5 = 0.811$$

For Green = N:

• Martians (M): 2
• Humans (H): 4
• Total: 6

Entropy:

$$E(Green = N) = -\left(\frac{2}{6}\right) \log_2\left(\frac{2}{6}\right) - \left(\frac{4}{6}\right) \log_2\left(\frac{4}{6}\right)$$

$$= -0.333 \cdot \log_2(0.333) - 0.667 \cdot \log_2(0.667)$$

$$= -0.333 \cdot (-1.585) - 0.667 \cdot (-0.585)$$

$$= 0.528 + 0.389 = 0.917$$

Weighted Entropy for Green

$$E(Green) = \frac{4}{10} \cdot 0.811 + \frac{6}{10} \cdot 0.917$$

$$= 0.3244 + 0.5502 = 0.8746$$

Information Gain for Green

$$IG(Species, Green) = E(Species) - E(Green)$$

$$= 1.0 - 0.8746 = 0.1254$$

Continue this process to calculate the entropy and information gain for each feature (Legs, Height, and Smelly) similarly.