Building a Decision Tree Using Entropy and Information Gain
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)
Positives (P) for 'Yes' = 4
Negatives (N) for 'No' = 5
Calculation:
2. Subset Information Required
| Value | Pi | Ni |
|---|---|---|
| Good | 4 | 1 |
| Poor | 0 | 4 |
Detailed Entropy Calculation
Value: Good
Value: Poor
Evaluated Feature: Credit_History
| Value | Pi | Ni | I (Pi, Ni) |
|---|---|---|---|
| Good | 4 | 1 | 0.722 |
| Poor | 0 | 4 | 0 |
| Value | Pi | Ni |
|---|---|---|
| Stable | 3 | 2 |
| Unstable | 1 | 3 |
Detailed Entropy Calculation
Value: Stable
Value: Unstable
Evaluated Feature: Employment
| Value | Pi | Ni | I (Pi, Ni) |
|---|---|---|---|
| Stable | 3 | 2 | 0.971 |
| Unstable | 1 | 3 | 0.811 |
| Value | Pi | Ni |
|---|---|---|
| High | 2 | 1 |
| Medium | 1 | 1 |
| Low | 1 | 3 |
Detailed Entropy Calculation
Value: High
Value: Medium
Value: Low
Evaluated Feature: Income_Level
| Value | Pi | Ni | I (Pi, Ni) |
|---|---|---|---|
| High | 2 | 1 | 0.918 |
| Medium | 1 | 1 | 1 |
| Low | 1 | 3 | 0.811 |
| Value | Pi | Ni |
|---|---|---|
| Yes | 2 | 2 |
| No | 2 | 3 |
Detailed Entropy Calculation
Value: Yes
Value: No
Evaluated Feature: Owns_Property
| Value | Pi | Ni | I (Pi, Ni) |
|---|---|---|---|
| Yes | 2 | 2 | 1 |
| No | 2 | 3 | 0.971 |
3. Weighted Feature Entropy
Calculation:
Calculation:
Calculation:
Calculation:
4. Feature Information Gain
5. Feature Selection Decision
Credit_History generated the highest Information Gain (0.59).
It is selected as the optimal splitting node for this subset.
Iteration: 2
Context: Credit_History = Good
| Data Point | Credit_History | Employment | Income_Level | Owns_Property | Approved |
|---|---|---|---|---|---|
| P1 | Good | Stable | High | Yes | Yes |
| P2 | Good | Stable | Medium | No | Yes |
| P5 | Good | Unstable | High | Yes | Yes |
| P7 | Good | Stable | Low | No | Yes |
| P9 | Good | Unstable | Low | No | No |
1. Entropy of Target Class, Entropy (S)
Positives (P) for 'Yes' = 4
Negatives (N) for 'No' = 1
Calculation:
2. Subset Information Required
| Value | Pi | Ni |
|---|---|---|
| Stable | 3 | 0 |
| Unstable | 1 | 1 |
Detailed Entropy Calculation
Value: Stable
Value: Unstable
Evaluated Feature: Employment
| Value | Pi | Ni | I (Pi, Ni) |
|---|---|---|---|
| Stable | 3 | 0 | 0 |
| Unstable | 1 | 1 | 1 |
| Value | Pi | Ni |
|---|---|---|
| High | 2 | 0 |
| Medium | 1 | 0 |
| Low | 1 | 1 |
Detailed Entropy Calculation
Value: High
Value: Medium
Value: Low
Evaluated Feature: Income_Level
| Value | Pi | Ni | I (Pi, Ni) |
|---|---|---|---|
| High | 2 | 0 | 0 |
| Medium | 1 | 0 | 0 |
| Low | 1 | 1 | 1 |
| Value | Pi | Ni |
|---|---|---|
| Yes | 2 | 0 |
| No | 2 | 1 |
Detailed Entropy Calculation
Value: Yes
Value: No
Evaluated Feature: Owns_Property
| Value | Pi | Ni | I (Pi, Ni) |
|---|---|---|---|
| Yes | 2 | 0 | 0 |
| No | 2 | 1 | 0.918 |
3. Weighted Feature Entropy
Calculation:
Calculation:
Calculation:
4. Feature Information Gain
5. Feature Selection Decision
Employment generated the highest Information Gain (0.322).
It is selected as the optimal splitting node for this subset.
Iteration: 3
Context: Employment = Unstable
| Data Point | Credit_History | Employment | Income_Level | Owns_Property | Approved |
|---|---|---|---|---|---|
| P5 | Good | Unstable | High | Yes | Yes |
| P9 | Good | Unstable | Low | No | No |
1. Entropy of Target Class, Entropy (S)
Positives (P) for 'Yes' = 1
Negatives (N) for 'No' = 1
Calculation:
2. Subset Information Required
| Value | Pi | Ni |
|---|---|---|
| High | 1 | 0 |
| Low | 0 | 1 |
Detailed Entropy Calculation
Value: High
Value: Low
Evaluated Feature: Income_Level
| Value | Pi | Ni | I (Pi, Ni) |
|---|---|---|---|
| High | 1 | 0 | 0 |
| Low | 0 | 1 | 0 |
| Value | Pi | Ni |
|---|---|---|
| Yes | 1 | 0 |
| No | 0 | 1 |
Detailed Entropy Calculation
Value: Yes
Value: No
Evaluated Feature: Owns_Property
| Value | Pi | Ni | I (Pi, Ni) |
|---|---|---|---|
| Yes | 1 | 0 | 0 |
| No | 0 | 1 | 0 |
3. Weighted Feature Entropy
Calculation:
Calculation:
4. Feature Information Gain
5. Feature Selection Decision
Income_Level generated the highest Information Gain (1).
It is selected as the optimal splitting node for this subset.
Final Decision Tree
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 and it becomes a leaf. When classifying a new record, follow only the features along its decision path.