ID3 Algorithm

Abhijeet Singh Rajput

@abhijeetsingh

Created

Apr 28, 2025

Last Modified

2 weeks ago

$I D_{3}$ Algorithm

Construct the decision tree using the $I D_{3}$ algorithm for the given data set.

S.no	Age	Competition	Type	Profit (Class)
1	Old	Yes	Soft	Down
2	Old	No	Soft	Down
3	Old	No	Hard	Down
4	Mid	Yes	Soft	Down
5	Mid	Yes	Hard	Down
6	Mid	No	Hard	Up
7	Mid	No	Soft	Up
8	New	Yes	Soft	Up
9	New	No	Hard	Up
10	New	No	Soft	Up

🔧 Step 1: Initial Entropy of Dataset

E n t r o p y (S^{'}) = - p_{U p} l o g_{2} (p_{U p}) - p_{D o w n} l o g_{2} (p_{D o w n})

Where:

Total = 10
Down = 5 (1 to 5)
Up = 5 (6 to 10)

$p_{u p} = \frac{count of Up}{total} = \frac{5}{10}$
$p_{D o w n} = \frac{count of Down}{total} = \frac{5}{10}$

So:

E n t r o p y (S^{'}) = - \frac{5}{10} lo g_{2} (\frac{5}{10}) - \frac{5}{10} lo g_{2} (\frac{5}{10})

= - \frac{5}{10} l o g_{2} (\frac{1}{2}) - \frac{5}{10} l o g_{2} (\frac{1}{2})

= - \frac{5}{10} l o g_{2} (2)^{- 1} - \frac{5}{10} l o g_{2} (2)^{- 1}

= \frac{5}{10} l o g_{2} (2) + \frac{5}{10} l o g_{2} (2)

= \frac{5}{10} \cdot 1 + \frac{5}{10} \cdot 1

= 0.5 + 0.5

$lo g_{a} b^{c} = c lo g_{a} b$
$l o g_{a} a = 1$

✅ Entropy( $S^{'}$ ) = 1

Step 2: Calculate Information Gain for all attributes

Attribute 1: Age (Old, Mid, New)

$E n t r o p y (Old)$

Old: $S$ = [Down, Down, Down]

E = - \frac{3}{3} lo g_{2} \frac{3}{3}

E = 0

$E n t r o p y (Mid)$

Mid : $S$ = [Down, Down, Up, Up]

= - \frac{2}{4} l o g_{2} \frac{2}{4} - \frac{2}{4} l o g_{2} \frac{2}{4}

E = - 0.5 l o g_{2} 0.5 - 0.5 l o g_{2} 0.5

$E = 1$

$E n t r o p y (New)$

New: $S$ = [Up, Up, Up]

E = - \frac{3}{3} l o g_{2} \frac{3}{3}

E = 0

$G ain (S^{'}, A g e)$

= Entropy (S^{'}) - \frac{∣ S _{o l d} ∣}{∣ S ∣} \cdot Entropy (S_{o l d}) - \frac{∣ S _{mi d} ∣}{∣ S ∣} \cdot Entropy (S_{mi d}) - \frac{∣ S _{n e w} ∣}{∣ S ∣} \cdot Entropy (S_{n e w})

= 1 - (\frac{3}{10} \cdot 0 + \frac{4}{10} \cdot 1 + \frac{3}{10} \cdot 0)

1 - 0.4 = 0.6

✅ Gain(Age) = 0.6

Attribute 2: Competition (Yes, No)

$E n t r o p y (S_{Yes}^{'})$

Yes : $S$ = [Down, Down, Down, Up]

= - \frac{3}{4} l o g_{2} \frac{3}{4} - \frac{1}{4} l o g_{2} \frac{1}{4}

E = - 0.75 l o g_{2} 0.75 - 0.25 l o g_{2} 0.25

$E \approx 0.811$

$E n t r o p y (S_{No}^{'})$

No: $S$ = [Down, Down, Up, Up, Up, Up]

= - \frac{2}{6} l o g_{2} \frac{2}{6} - \frac{4}{6} l o g_{2} \frac{4}{6}

E = - 0.333 l o g_{2} 0.333 - 0.666 l o g_{2} 0.666

E \approx 0.918

$G ain (S^{'}, Competition)$

= 1 - (\frac{4}{10} \cdot 0.811 + \frac{6}{10} \cdot 0.918)

\approx 1 - (0.3244 + 0.5508) = 0.1248

✅ Gain(Competition) = 0.125

Attribute 3: Type (Soft, Hard)

$E n t r o p y (Soft)$

Soft: $S$ = [Down, Down, Down, Up, Up, Up]

E = - \frac{3}{6} l o g_{2} \frac{3}{6} - \frac{3}{6} l o g_{2} \frac{3}{6}

E = - \frac{1}{2} lo g_{2} \frac{1}{2} - \frac{1}{2} lo g_{2} \frac{1}{2}

E = - 0.5 lo g_{2} 2^{- 1} - 0.5 lo g_{2} 2^{- 1}

E = 0.5 \cdot 1 + 0.5 \cdot 1

E = 1

$E n t r o p y (Hard)$

Hard : $S$ = [Down, Down, Up, Up]

E = - \frac{2}{4} l o g_{2} \frac{2}{4} - \frac{2}{4} l o g_{2} \frac{2}{4}

E = - \frac{1}{2} lo g_{2} \frac{1}{2} - \frac{1}{2} lo g_{2} \frac{1}{2}

E = - 0.5 lo g_{2} 2^{- 1} - 0.5 lo g_{2} 2^{- 1}

E = 0.5 \cdot 1 + 0.5 \cdot 1

E = 1

$G ain (S^{'}, A g e)$

= 1 - (\frac{6}{10} \cdot 1 + \frac{4}{10} \cdot 1)

= 1 - (0.6 + 0.4) = 0

✅ Gain(Type) = 0

Find the maximum Gain

✅ Gain(Age) = 0.6

✅ Gain(Competition) = 0.125

✅ Gain(Type) = 0

max (0.6, 0.125, 0) = 0.6

Age gives the highest gain (0.6).

Thus, "Age" will be placed at the root of the Decision Tree.

The Decision Tree Formation

ID3 decision tree initial structure showing root node Age splitting into categories old, mid, and new

$Age = Old$

$S^{1}$ , a subset of $S^{'}$ for which Age = Old

Age	Competition	Type	Profit (Class)
Old	Yes	Soft	Down
Old	No	Soft	Down
Old	No	Hard	Down

Observation:

All 3 examples → Profit = Down
✅ Pure group!

thus

E n t r o p y (S^{1}) = 0

Leaf Node = "Down"

$Age = Mid$

$S^{2}$ a subset of $S^{'}$ for which Age = Mid

Age	Competition	Type	Profit (Class)
Mid	Yes	Soft	Down
Mid	Yes	Hard	Down
Mid	No	Hard	Up
Mid	No	Soft	Up

Observation:

2 examples → Down
2 examples → Up

E n t r o p y (S^{2}) = - \frac{2}{4} l o g_{2} \frac{2}{4} - \frac{2}{4} l o g_{2} \frac{2}{4}

$E n t r o p y (S^{2}) = 1$

✅ Mid group is impure (entropy = 1).
Further splitting is needed.

🔷Attribute 1: Competition(Yes, No)

$E n t r o p y (Yes)$

Yes: $S$ = [Down, Down]

E n t r o p y (Yes) = 0

$E n t r o p y (No)$

No: $S$ = [Up, Up]

E n t r o p y (No) = 0

$G ain (S^{2}, C o m p e t i t i o n)$

= 1 - (\frac{2}{4} \cdot 0 + \frac{2}{4} \cdot 0)

1 - 0 = 1

✅ Gain(Competition) = 1

🔷Attribute 2: Type(Soft, Hard)

$E n t r o p y (Soft)$

Soft: $S$ = [Down, Up]

- \frac{1}{2} l o g_{2} \frac{1}{2} - \frac{1}{2} l o g_{2} \frac{1}{2}

= 1

$E n t r o p y (Soft) = 0$

$E n t r o p y (Hard)$

Hard : $S$ = [Down, Up]

- \frac{1}{2} l o g_{2} \frac{1}{2} - \frac{1}{2} l o g_{2} \frac{1}{2}

= 1

$E n t r o p y (Hard) = 1$

$G ain (S^{2}, T y p e)$

= 1 - (\frac{2}{4} \cdot 1 + \frac{2}{4} \cdot 1)

1 - 1 = 0

✅ Gain(Type) = 1

Since the Gain is maximum for the attribute, putting the competition at Node 2

$Age = New$

$S^{3}$ a subset of $S^{'}$ for which Age = New

Age	Competition	Type	Profit (Class)
New	Yes	Soft	Up
New	No	Hard	Up
New	No	Soft	Up

All 3 examples → Profit = Up
✅ Pure group!

E n t r o p y (N e w) = 0

Leaf Node = "Up"

ID3 decision tree final structure with Age as root and Competition as child node leading to Up and Down classification

$Competition = Yes$

All the corresponding class labels are down in $S^{2}$
✅ Pure group!

E n t r o p y (N e w) = 0

Leaf Node = "Down"

$Competition = No$

All the corresponding class labels are up in $S^{2}$
✅ Pure group!

E n t r o p y (N e w) = 0

Leaf Node = "Up"

ID3 Algorithm

ID3​ Algorithm

Construct the decision tree using the ID3​ algorithm for the given data set.

🔧 Step 1: Initial Entropy of Dataset

Step 2: Calculate Information Gain for all attributes

Find the maximum Gain

The Decision Tree Formation

Age=Old

Age=Mid

Age=New

Competition=Yes

Competition=No