Building a Decision Tree Using Entropy and Information Gain

Last updated

Problem Setup

Scenario:Build a decision tree that predicts whether a borrower is approved by selecting the most informative feature at each split.

Given:A labeled dataset of 9 borrower records with four candidate features and Approved as the target class.

Task:Apply the ID3 algorithm by calculating entropy and information gain, select the highest-gain feature at each node, and continue splitting the resulting subsets until the final decision tree is formed.

Need a quick refresher? Review Decision Tree theory

Training Dataset

Each row represents a borrower's features and known approval outcome. The target record has no known approval label and will be classified using the decision tree built from these examples.

Data Point
Credit_History✎
Employment✎
Income_Level✎
Owns_Property✎
Approved
P1
Good
Stable
High
Yes
Yes
P2
Good
Stable
Medium
No
Yes
P3
Poor
Unstable
Low
No
No
P4
Poor
Stable
Medium
Yes
No
P5
Good
Unstable
High
Yes
Yes
P6
Poor
Unstable
High
No
No
P7
Good
Stable
Low
No
Yes
P8
Poor
Stable
Low
Yes
No
P9
Good
Unstable
Low
No
No
Target
Good
Unstable
High
No
?

Step-by-Step Solution

Iteration: 1

Context: Root

1. Entropy of Target Class, Entropy (S)
Entropy(S)=−PP+Nlog⁡2(PP+N)−NP+Nlog⁡2(NP+N)\mathrm{Entropy}(S) = - \dfrac{P}{P+N} \log_2\left(\dfrac{P}{P+N}\right) - \dfrac{N}{P+N} \log_2\left(\dfrac{N}{P+N}\right)

Positives (P) for 'Yes' = 4

Negatives (N) for 'No' = 5

Calculation:

Entropy(S)=−49log⁡2(49)−59log⁡2(59)\mathrm{Entropy}(S) = -\dfrac{4}{9}\log_2\left(\dfrac{4}{9}\right) - \dfrac{5}{9}\log_2\left(\dfrac{5}{9}\right)
=−(0.444)log⁡2(0.444)−(0.556)log⁡2(0.556)= -(0.444)\log_2(0.444) - (0.556)\log_2(0.556)
=−(0.444)(−1.17)−(0.556)(−0.848)= -(0.444)(-1.17) - (0.556)(-0.848)
=0.52+0.471= 0.52 + 0.471
Entropy(S)=0.991\mathrm{Entropy}(S) = 0.991
2. Subset Information Required
Entropy(Pi,Ni)=−PiPi+Nilog⁡2(PiPi+Ni)−NiPi+Nilog⁡2(NiPi+Ni)\text{Entropy}(P_i, N_i) = - \dfrac{P_i}{P_i+N_i} \log_2\left(\dfrac{P_i}{P_i+N_i}\right) - \dfrac{N_i}{P_i+N_i} \log_2\left(\dfrac{N_i}{P_i+N_i}\right)
Evaluating Feature: Credit_History
ValuePiNi
Good41
Poor04

Detailed Entropy Calculation

Value: Good

I(Pi,Ni)=−45log⁡2(45)−15log⁡2(15)I(P_i,N_i) = -\dfrac{4}{5}\log_2\left(\dfrac{4}{5}\right) - \dfrac{1}{5}\log_2\left(\dfrac{1}{5}\right)
=−(0.8)log⁡2(0.8)−(0.2)log⁡2(0.2)= -(0.8)\log_2(0.8) - (0.2)\log_2(0.2)
=−(0.8)(−0.322)−(0.2)(−2.322)= -(0.8)(-0.322) - (0.2)(-2.322)
=0.258+0.464= 0.258 + 0.464
I(Pi,Ni)=0.722I(P_i,N_i) = 0.722

Value: Poor

Pi=0,Ni=4,Pi+Ni=4P_i = 0,\quad N_i = 4,\quad P_i + N_i = 4
Since Pi=0 or Ni=0,Entropy(Pi,Ni)=0\text{Since } P_i = 0 \text{ or } N_i = 0,\quad \text{Entropy}(P_i,N_i) = 0
I(Pi,Ni)=0I(P_i,N_i) = 0

Evaluated Feature: Credit_History

ValuePiNiI (Pi, Ni)
Good410.722
Poor040
Evaluating Feature: Employment
ValuePiNi
Stable32
Unstable13

Detailed Entropy Calculation

Value: Stable

I(Pi,Ni)=−35log⁡2(35)−25log⁡2(25)I(P_i,N_i) = -\dfrac{3}{5}\log_2\left(\dfrac{3}{5}\right) - \dfrac{2}{5}\log_2\left(\dfrac{2}{5}\right)
=−(0.6)log⁡2(0.6)−(0.4)log⁡2(0.4)= -(0.6)\log_2(0.6) - (0.4)\log_2(0.4)
=−(0.6)(−0.737)−(0.4)(−1.322)= -(0.6)(-0.737) - (0.4)(-1.322)
=0.442+0.529= 0.442 + 0.529
I(Pi,Ni)=0.971I(P_i,N_i) = 0.971

Value: Unstable

I(Pi,Ni)=−14log⁡2(14)−34log⁡2(34)I(P_i,N_i) = -\dfrac{1}{4}\log_2\left(\dfrac{1}{4}\right) - \dfrac{3}{4}\log_2\left(\dfrac{3}{4}\right)
=−(0.25)log⁡2(0.25)−(0.75)log⁡2(0.75)= -(0.25)\log_2(0.25) - (0.75)\log_2(0.75)
=−(0.25)(−2)−(0.75)(−0.415)= -(0.25)(-2) - (0.75)(-0.415)
=0.5+0.311= 0.5 + 0.311
I(Pi,Ni)=0.811I(P_i,N_i) = 0.811

Evaluated Feature: Employment

ValuePiNiI (Pi, Ni)
Stable320.971
Unstable130.811
Evaluating Feature: Income_Level
ValuePiNi
High21
Medium11
Low13

Detailed Entropy Calculation

Value: High

I(Pi,Ni)=−23log⁡2(23)−13log⁡2(13)I(P_i,N_i) = -\dfrac{2}{3}\log_2\left(\dfrac{2}{3}\right) - \dfrac{1}{3}\log_2\left(\dfrac{1}{3}\right)
=−(0.667)log⁡2(0.667)−(0.333)log⁡2(0.333)= -(0.667)\log_2(0.667) - (0.333)\log_2(0.333)
=−(0.667)(−0.585)−(0.333)(−1.585)= -(0.667)(-0.585) - (0.333)(-1.585)
=0.39+0.528= 0.39 + 0.528
I(Pi,Ni)=0.918I(P_i,N_i) = 0.918

Value: Medium

Pi=1,Ni=1,Pi+Ni=2P_i = 1,\quad N_i = 1,\quad P_i + N_i = 2
Since Pi=Ni,Entropy(Pi,Ni)=1\text{Since } P_i = N_i,\quad \text{Entropy}(P_i,N_i) = 1
I(Pi,Ni)=1I(P_i,N_i) = 1

Value: Low

I(Pi,Ni)=−14log⁡2(14)−34log⁡2(34)I(P_i,N_i) = -\dfrac{1}{4}\log_2\left(\dfrac{1}{4}\right) - \dfrac{3}{4}\log_2\left(\dfrac{3}{4}\right)
=−(0.25)log⁡2(0.25)−(0.75)log⁡2(0.75)= -(0.25)\log_2(0.25) - (0.75)\log_2(0.75)
=−(0.25)(−2)−(0.75)(−0.415)= -(0.25)(-2) - (0.75)(-0.415)
=0.5+0.311= 0.5 + 0.311
I(Pi,Ni)=0.811I(P_i,N_i) = 0.811

Evaluated Feature: Income_Level

ValuePiNiI (Pi, Ni)
High210.918
Medium111
Low130.811
Evaluating Feature: Owns_Property
ValuePiNi
Yes22
No23

Detailed Entropy Calculation

Value: Yes

Pi=2,Ni=2,Pi+Ni=4P_i = 2,\quad N_i = 2,\quad P_i + N_i = 4
Since Pi=Ni,Entropy(Pi,Ni)=1\text{Since } P_i = N_i,\quad \text{Entropy}(P_i,N_i) = 1
I(Pi,Ni)=1I(P_i,N_i) = 1

Value: No

I(Pi,Ni)=−25log⁡2(25)−35log⁡2(35)I(P_i,N_i) = -\dfrac{2}{5}\log_2\left(\dfrac{2}{5}\right) - \dfrac{3}{5}\log_2\left(\dfrac{3}{5}\right)
=−(0.4)log⁡2(0.4)−(0.6)log⁡2(0.6)= -(0.4)\log_2(0.4) - (0.6)\log_2(0.6)
=−(0.4)(−1.322)−(0.6)(−0.737)= -(0.4)(-1.322) - (0.6)(-0.737)
=0.529+0.442= 0.529 + 0.442
I(Pi,Ni)=0.971I(P_i,N_i) = 0.971

Evaluated Feature: Owns_Property

ValuePiNiI (Pi, Ni)
Yes221
No230.971
3. Weighted Feature Entropy
Entropy(A)=∑[pi+niP+N]×Entropy(Pi,Ni)\text{Entropy}(A) = \sum \left[ \dfrac{p_i + n_i}{P + N} \right] \times \text{Entropy}(P_i, N_i)
Detailed Weighted Entropy: Credit_History

Calculation:

Entropy(CreditHistory)=(59)×0.722+(49)×0\text{Entropy}(Credit_History) = \left(\dfrac{5}{9}\right) \times 0.722 + \left(\dfrac{4}{9}\right) \times 0
=(0.556)×0.722+(0.444)×0= \left(0.556\right) \times 0.722 + \left(0.444\right) \times 0
=0.401+0= 0.401 + 0
=0.401= 0.401
Entropy(CreditHistory)=0.401\text{Entropy}(Credit_History) = 0.401
Detailed Weighted Entropy: Employment

Calculation:

Entropy(Employment)=(59)×0.971+(49)×0.811\text{Entropy}(Employment) = \left(\dfrac{5}{9}\right) \times 0.971 + \left(\dfrac{4}{9}\right) \times 0.811
=(0.556)×0.971+(0.444)×0.811= \left(0.556\right) \times 0.971 + \left(0.444\right) \times 0.811
=0.539+0.361= 0.539 + 0.361
=0.9= 0.9
Entropy(Employment)=0.9\text{Entropy}(Employment) = 0.9
Detailed Weighted Entropy: Income_Level

Calculation:

Entropy(IncomeLevel)=(39)×0.918+(29)×1+(49)×0.811\text{Entropy}(Income_Level) = \left(\dfrac{3}{9}\right) \times 0.918 + \left(\dfrac{2}{9}\right) \times 1 + \left(\dfrac{4}{9}\right) \times 0.811
=(0.333)×0.918+(0.222)×1+(0.444)×0.811= \left(0.333\right) \times 0.918 + \left(0.222\right) \times 1 + \left(0.444\right) \times 0.811
=0.306+0.222+0.361= 0.306 + 0.222 + 0.361
=0.889= 0.889
Entropy(IncomeLevel)=0.889\text{Entropy}(Income_Level) = 0.889
Detailed Weighted Entropy: Owns_Property

Calculation:

Entropy(OwnsProperty)=(49)×1+(59)×0.971\text{Entropy}(Owns_Property) = \left(\dfrac{4}{9}\right) \times 1 + \left(\dfrac{5}{9}\right) \times 0.971
=(0.444)×1+(0.556)×0.971= \left(0.444\right) \times 1 + \left(0.556\right) \times 0.971
=0.444+0.539= 0.444 + 0.539
=0.984= 0.984
Entropy(OwnsProperty)=0.984\text{Entropy}(Owns_Property) = 0.984
4. Feature Information Gain
Formula: Gain(S,A)=Entropy(S)−Entropy(A)\text{Gain}(S, A) = \text{Entropy}(S) - \text{Entropy}(A)
Credit_History0.991 - 0.401 =Gain:0.59
Employment0.991 - 0.9 =Gain:0.091
Income_Level0.991 - 0.889 =Gain:0.102
Owns_Property0.991 - 0.984 =Gain:0.007
5. Feature Selection Decision

Credit_History generated the highest Information Gain (0.59). It is selected as the optimal splitting node for this subset.

Resulting Split
Credit_History ?
Good
Class: ?
Poor
Class: No

Iteration: 2

Context: Credit_History = Good

Current Data: Filtered by Credit_History = Good5 Rows
Data PointCredit_HistoryEmploymentIncome_LevelOwns_PropertyApproved
P1GoodStableHighYesYes
P2GoodStableMediumNoYes
P5GoodUnstableHighYesYes
P7GoodStableLowNoYes
P9GoodUnstableLowNoNo
1. Entropy of Target Class, Entropy (S)
Entropy(S)=−PP+Nlog⁡2(PP+N)−NP+Nlog⁡2(NP+N)\mathrm{Entropy}(S) = - \dfrac{P}{P+N} \log_2\left(\dfrac{P}{P+N}\right) - \dfrac{N}{P+N} \log_2\left(\dfrac{N}{P+N}\right)

Positives (P) for 'Yes' = 4

Negatives (N) for 'No' = 1

Calculation:

Entropy(S)=−45log⁡2(45)−15log⁡2(15)\mathrm{Entropy}(S) = -\dfrac{4}{5}\log_2\left(\dfrac{4}{5}\right) - \dfrac{1}{5}\log_2\left(\dfrac{1}{5}\right)
=−(0.8)log⁡2(0.8)−(0.2)log⁡2(0.2)= -(0.8)\log_2(0.8) - (0.2)\log_2(0.2)
=−(0.8)(−0.322)−(0.2)(−2.322)= -(0.8)(-0.322) - (0.2)(-2.322)
=0.258+0.464= 0.258 + 0.464
Entropy(S)=0.722\mathrm{Entropy}(S) = 0.722
2. Subset Information Required
Entropy(Pi,Ni)=−PiPi+Nilog⁡2(PiPi+Ni)−NiPi+Nilog⁡2(NiPi+Ni)\text{Entropy}(P_i, N_i) = - \dfrac{P_i}{P_i+N_i} \log_2\left(\dfrac{P_i}{P_i+N_i}\right) - \dfrac{N_i}{P_i+N_i} \log_2\left(\dfrac{N_i}{P_i+N_i}\right)
Evaluating Feature: Employment
ValuePiNi
Stable30
Unstable11

Detailed Entropy Calculation

Value: Stable

Pi=3,Ni=0,Pi+Ni=3P_i = 3,\quad N_i = 0,\quad P_i + N_i = 3
Since Pi=0 or Ni=0,Entropy(Pi,Ni)=0\text{Since } P_i = 0 \text{ or } N_i = 0,\quad \text{Entropy}(P_i,N_i) = 0
I(Pi,Ni)=0I(P_i,N_i) = 0

Value: Unstable

Pi=1,Ni=1,Pi+Ni=2P_i = 1,\quad N_i = 1,\quad P_i + N_i = 2
Since Pi=Ni,Entropy(Pi,Ni)=1\text{Since } P_i = N_i,\quad \text{Entropy}(P_i,N_i) = 1
I(Pi,Ni)=1I(P_i,N_i) = 1

Evaluated Feature: Employment

ValuePiNiI (Pi, Ni)
Stable300
Unstable111
Evaluating Feature: Income_Level
ValuePiNi
High20
Medium10
Low11

Detailed Entropy Calculation

Value: High

Pi=2,Ni=0,Pi+Ni=2P_i = 2,\quad N_i = 0,\quad P_i + N_i = 2
Since Pi=0 or Ni=0,Entropy(Pi,Ni)=0\text{Since } P_i = 0 \text{ or } N_i = 0,\quad \text{Entropy}(P_i,N_i) = 0
I(Pi,Ni)=0I(P_i,N_i) = 0

Value: Medium

Pi=1,Ni=0,Pi+Ni=1P_i = 1,\quad N_i = 0,\quad P_i + N_i = 1
Since Pi=0 or Ni=0,Entropy(Pi,Ni)=0\text{Since } P_i = 0 \text{ or } N_i = 0,\quad \text{Entropy}(P_i,N_i) = 0
I(Pi,Ni)=0I(P_i,N_i) = 0

Value: Low

Pi=1,Ni=1,Pi+Ni=2P_i = 1,\quad N_i = 1,\quad P_i + N_i = 2
Since Pi=Ni,Entropy(Pi,Ni)=1\text{Since } P_i = N_i,\quad \text{Entropy}(P_i,N_i) = 1
I(Pi,Ni)=1I(P_i,N_i) = 1

Evaluated Feature: Income_Level

ValuePiNiI (Pi, Ni)
High200
Medium100
Low111
Evaluating Feature: Owns_Property
ValuePiNi
Yes20
No21

Detailed Entropy Calculation

Value: Yes

Pi=2,Ni=0,Pi+Ni=2P_i = 2,\quad N_i = 0,\quad P_i + N_i = 2
Since Pi=0 or Ni=0,Entropy(Pi,Ni)=0\text{Since } P_i = 0 \text{ or } N_i = 0,\quad \text{Entropy}(P_i,N_i) = 0
I(Pi,Ni)=0I(P_i,N_i) = 0

Value: No

I(Pi,Ni)=−23log⁡2(23)−13log⁡2(13)I(P_i,N_i) = -\dfrac{2}{3}\log_2\left(\dfrac{2}{3}\right) - \dfrac{1}{3}\log_2\left(\dfrac{1}{3}\right)
=−(0.667)log⁡2(0.667)−(0.333)log⁡2(0.333)= -(0.667)\log_2(0.667) - (0.333)\log_2(0.333)
=−(0.667)(−0.585)−(0.333)(−1.585)= -(0.667)(-0.585) - (0.333)(-1.585)
=0.39+0.528= 0.39 + 0.528
I(Pi,Ni)=0.918I(P_i,N_i) = 0.918

Evaluated Feature: Owns_Property

ValuePiNiI (Pi, Ni)
Yes200
No210.918
3. Weighted Feature Entropy
Entropy(A)=∑[pi+niP+N]×Entropy(Pi,Ni)\text{Entropy}(A) = \sum \left[ \dfrac{p_i + n_i}{P + N} \right] \times \text{Entropy}(P_i, N_i)
Detailed Weighted Entropy: Employment

Calculation:

Entropy(Employment)=(35)×0+(25)×1\text{Entropy}(Employment) = \left(\dfrac{3}{5}\right) \times 0 + \left(\dfrac{2}{5}\right) \times 1
=(0.6)×0+(0.4)×1= \left(0.6\right) \times 0 + \left(0.4\right) \times 1
=0+0.4= 0 + 0.4
=0.4= 0.4
Entropy(Employment)=0.4\text{Entropy}(Employment) = 0.4
Detailed Weighted Entropy: Income_Level

Calculation:

Entropy(IncomeLevel)=(25)×0+(15)×0+(25)×1\text{Entropy}(Income_Level) = \left(\dfrac{2}{5}\right) \times 0 + \left(\dfrac{1}{5}\right) \times 0 + \left(\dfrac{2}{5}\right) \times 1
=(0.4)×0+(0.2)×0+(0.4)×1= \left(0.4\right) \times 0 + \left(0.2\right) \times 0 + \left(0.4\right) \times 1
=0+0+0.4= 0 + 0 + 0.4
=0.4= 0.4
Entropy(IncomeLevel)=0.4\text{Entropy}(Income_Level) = 0.4
Detailed Weighted Entropy: Owns_Property

Calculation:

Entropy(OwnsProperty)=(25)×0+(35)×0.918\text{Entropy}(Owns_Property) = \left(\dfrac{2}{5}\right) \times 0 + \left(\dfrac{3}{5}\right) \times 0.918
=(0.4)×0+(0.6)×0.918= \left(0.4\right) \times 0 + \left(0.6\right) \times 0.918
=0+0.551= 0 + 0.551
=0.551= 0.551
Entropy(OwnsProperty)=0.551\text{Entropy}(Owns_Property) = 0.551
4. Feature Information Gain
Formula: Gain(S,A)=Entropy(S)−Entropy(A)\text{Gain}(S, A) = \text{Entropy}(S) - \text{Entropy}(A)
Employment0.722 - 0.4 =Gain:0.322
Income_Level0.722 - 0.4 =Gain:0.322
Owns_Property0.722 - 0.551 =Gain:0.171
5. Feature Selection Decision

Employment generated the highest Information Gain (0.322). It is selected as the optimal splitting node for this subset.

Resulting Split
Employment ?
Stable
Class: Yes
Unstable
Class: ?

Iteration: 3

Context: Employment = Unstable

Current Data: Filtered by Employment = Unstable2 Rows
Data PointCredit_HistoryEmploymentIncome_LevelOwns_PropertyApproved
P5GoodUnstableHighYesYes
P9GoodUnstableLowNoNo
1. Entropy of Target Class, Entropy (S)
Entropy(S)=−PP+Nlog⁡2(PP+N)−NP+Nlog⁡2(NP+N)\mathrm{Entropy}(S) = - \dfrac{P}{P+N} \log_2\left(\dfrac{P}{P+N}\right) - \dfrac{N}{P+N} \log_2\left(\dfrac{N}{P+N}\right)

Positives (P) for 'Yes' = 1

Negatives (N) for 'No' = 1

Calculation:

Entropy(S)=−12log⁡2(12)−12log⁡2(12)\mathrm{Entropy}(S) = -\dfrac{1}{2}\log_2\left(\dfrac{1}{2}\right) - \dfrac{1}{2}\log_2\left(\dfrac{1}{2}\right)
=−(0.5)log⁡2(0.5)−(0.5)log⁡2(0.5)= -(0.5)\log_2(0.5) - (0.5)\log_2(0.5)
=−(0.5)(−1)−(0.5)(−1)= -(0.5)(-1) - (0.5)(-1)
=0.5+0.5= 0.5 + 0.5
Entropy(S)=1\mathrm{Entropy}(S) = 1
2. Subset Information Required
Entropy(Pi,Ni)=−PiPi+Nilog⁡2(PiPi+Ni)−NiPi+Nilog⁡2(NiPi+Ni)\text{Entropy}(P_i, N_i) = - \dfrac{P_i}{P_i+N_i} \log_2\left(\dfrac{P_i}{P_i+N_i}\right) - \dfrac{N_i}{P_i+N_i} \log_2\left(\dfrac{N_i}{P_i+N_i}\right)
Evaluating Feature: Income_Level
ValuePiNi
High10
Low01

Detailed Entropy Calculation

Value: High

Pi=1,Ni=0,Pi+Ni=1P_i = 1,\quad N_i = 0,\quad P_i + N_i = 1
Since Pi=0 or Ni=0,Entropy(Pi,Ni)=0\text{Since } P_i = 0 \text{ or } N_i = 0,\quad \text{Entropy}(P_i,N_i) = 0
I(Pi,Ni)=0I(P_i,N_i) = 0

Value: Low

Pi=0,Ni=1,Pi+Ni=1P_i = 0,\quad N_i = 1,\quad P_i + N_i = 1
Since Pi=0 or Ni=0,Entropy(Pi,Ni)=0\text{Since } P_i = 0 \text{ or } N_i = 0,\quad \text{Entropy}(P_i,N_i) = 0
I(Pi,Ni)=0I(P_i,N_i) = 0

Evaluated Feature: Income_Level

ValuePiNiI (Pi, Ni)
High100
Low010
Evaluating Feature: Owns_Property
ValuePiNi
Yes10
No01

Detailed Entropy Calculation

Value: Yes

Pi=1,Ni=0,Pi+Ni=1P_i = 1,\quad N_i = 0,\quad P_i + N_i = 1
Since Pi=0 or Ni=0,Entropy(Pi,Ni)=0\text{Since } P_i = 0 \text{ or } N_i = 0,\quad \text{Entropy}(P_i,N_i) = 0
I(Pi,Ni)=0I(P_i,N_i) = 0

Value: No

Pi=0,Ni=1,Pi+Ni=1P_i = 0,\quad N_i = 1,\quad P_i + N_i = 1
Since Pi=0 or Ni=0,Entropy(Pi,Ni)=0\text{Since } P_i = 0 \text{ or } N_i = 0,\quad \text{Entropy}(P_i,N_i) = 0
I(Pi,Ni)=0I(P_i,N_i) = 0

Evaluated Feature: Owns_Property

ValuePiNiI (Pi, Ni)
Yes100
No010
3. Weighted Feature Entropy
Entropy(A)=∑[pi+niP+N]×Entropy(Pi,Ni)\text{Entropy}(A) = \sum \left[ \dfrac{p_i + n_i}{P + N} \right] \times \text{Entropy}(P_i, N_i)
Detailed Weighted Entropy: Income_Level

Calculation:

Entropy(IncomeLevel)=(12)×0+(12)×0\text{Entropy}(Income_Level) = \left(\dfrac{1}{2}\right) \times 0 + \left(\dfrac{1}{2}\right) \times 0
=(0.5)×0+(0.5)×0= \left(0.5\right) \times 0 + \left(0.5\right) \times 0
=0+0= 0 + 0
=0= 0
Entropy(IncomeLevel)=0\text{Entropy}(Income_Level) = 0
Detailed Weighted Entropy: Owns_Property

Calculation:

Entropy(OwnsProperty)=(12)×0+(12)×0\text{Entropy}(Owns_Property) = \left(\dfrac{1}{2}\right) \times 0 + \left(\dfrac{1}{2}\right) \times 0
=(0.5)×0+(0.5)×0= \left(0.5\right) \times 0 + \left(0.5\right) \times 0
=0+0= 0 + 0
=0= 0
Entropy(OwnsProperty)=0\text{Entropy}(Owns_Property) = 0
4. Feature Information Gain
Formula: Gain(S,A)=Entropy(S)−Entropy(A)\text{Gain}(S, A) = \text{Entropy}(S) - \text{Entropy}(A)
Income_Level1 - 0 =Gain:1
Owns_Property1 - 0 =Gain:1
5. Feature Selection Decision

Income_Level generated the highest Information Gain (1). It is selected as the optimal splitting node for this subset.

Resulting Split
Income_Level ?
High
Class: Yes
Low
Class: No

Final Decision Tree

Credit_History ?
Good
Employment ?
Stable
Class: Yes
Unstable
Income_Level ?
High
Class: Yes
Low
Class: No
Poor
Class: No

Final Answer

Prediction:Yes

Decision path:Good → Unstable → High

The target borrower reaches the Yes leaf because the Good credit-history branch splits on Employment, and the Unstable branch then uses Income_Level. Owns_Property is not evaluated on this path, showing that a decision tree uses only the features needed to reach its prediction.

Exam Takeaway

  • Choose splits using Information Gain: ID3 compares the reduction in weighted entropy for each available feature. A feature with more distinct values is not automatically the best split.
  • Handle equal Information Gain consistently: When features tie for the highest gain, follow the specified tie-breaking rule. Different choices can produce trees that classify the training records equally well but give different predictions for an unseen record.
  • Recalculate entropy within each branch: After a split, use only the records belonging to that branch. A feature that was not selected at the root may become the best choice for a smaller subset.
  • Stop splitting when a subset becomes pure: If all records at a node have the same class, its entropy is 00 and it becomes a leaf. When classifying a new record, follow only the features along its decision path.