---
title: "Entropy, information gain and ID3 tree"
subject: "Data Mining"
chapter: 3
key: "semester_7/data_mining:id3-entropy-information-gain"
source: https://www.bctengineer.com/q/semester_7/data_mining/id3-entropy-information-gain
site: BCT Engineering
---

# Entropy, information gain and ID3 tree

Data Mining · Chapter 3: Classification

- Asked in: year not given, 3+7 marks
- Video: [How to find the Entropy and Information Gain in Decision Tree Learning by Mahesh Huddar](https://www.youtube.com/watch?v=y6VwIcZAUkI) — Mahesh Huddar
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/data_mining/id3-entropy-information-gain
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-3

## Question

What is entropy and information gain? Explain with algorithm how the ID3 tree can be generated.

## Short answer

Entropy measures impurity: Entropy(S) = -sum pi log2 pi, being 0 for one class and 1 for an even two-class mix. Information gain is the entropy reduction after splitting on an attribute. ID3 recursively chooses the highest-gain attribute, branches on its values, and stops at pure or exhausted nodes.

## Answer

#### Entropy
**Entropy** measures the impurity (randomness) of a set S of examples:

Entropy(S) = − Σ pᵢ log₂ pᵢ

where pᵢ is the proportion of class i in S. It is 0 when all examples are of one class, and 1 (for two classes) when the classes are equally mixed.

*Example*: 9 Yes and 5 No: Entropy = −(9/14)log₂(9/14) − (5/14)log₂(5/14) = 0.940.

#### Information gain
**Information gain** is the expected reduction in entropy after splitting S on attribute A:

Gain(S, A) = Entropy(S) − Σ over values v of A [ (|Sᵥ|/|S|) · Entropy(Sᵥ) ]

The attribute with the highest gain gives the purest partitions, so it is used for the split.

*Example (Play Golf)*: Outlook splits 14 records into Overcast (4 Yes, 0 No; E = 0), Sunny (2 Yes, 3 No; E = 0.971), Rainy (3 Yes, 2 No; E = 0.971).
Gain(Outlook) = 0.940 − (4/14)(0) − (5/14)(0.971) − (5/14)(0.971) = **0.247**. Gains of other attributes are lower (Humidity 0.152, Windy 0.048, Temperature 0.029), so Outlook is the root.

#### ID3 algorithm (Iterative Dichotomiser 3, Quinlan)
```text
ID3(S, Attributes, Class)
1. Create a node N.
2. If all examples in S have the same class C
      return N as a leaf labelled C.
3. If Attributes is empty
      return N as a leaf labelled with the majority class of S.
4. For every attribute A compute Gain(S, A).
5. Choose A* with the highest information gain; label N with A*.
6. For each value v of A*:
      Sv = examples of S with A* = v
      if Sv is empty: add a leaf with the majority class of S
      else: add the subtree ID3(Sv, Attributes - {A*}, Class)
7. Return N.
```

ID3 uses a greedy, top-down search, handles only categorical attributes (continuous ones must be discretised), and does no backtracking or pruning. It tends to prefer attributes with many values.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does entropy measure and what is its value for a pure set?
   A. Purity; 1 for a pure set
   B. Distance between records; 0 for a pure set
   C. Impurity of a set; 0 for a pure set
   D. Number of attributes; 0 for a pure set
   Answer: C. Entropy is 0 when all examples belong to one class. (Key point: Entropy)

2. What is information gain of attribute A?
   A. The entropy of A itself
   B. The number of branches of A
   C. The sum of the class probabilities
   D. Expected reduction in entropy after splitting on A
   Answer: D. Gain = Entropy(S) - weighted entropy of the partitions. (Key point: Information gain)

3. With 9 Yes and 5 No, the entropy is about:
   A. 0.940
   B. 0.247
   C. 0.971
   D. 1.577
   Answer: A. -(9/14)log2(9/14) - (5/14)log2(5/14) = 0.940. (Key point: Worked example)

4. In the Play Golf example, why is Outlook the root?
   A. It has the lowest gain
   B. It has the highest gain (0.247)
   C. It has the fewest values
   D. It was listed first
   Answer: B. Humidity 0.152, Windy 0.048, Temperature 0.029 are lower. (Key point: Root choice)

## Related in Data Mining

- [C4.5 vs ID3; gain, gain ratio, Gini](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Ac45-gain-ratio-gini) — Data Mining, chapter 3
- [ID3 algorithm and WEKA confusion matrix](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aid3-algorithm-weka-confusion) — Data Mining, chapter 3
- [Overfitting in ID3 and decision tree rules](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aid3-overfitting-rules) — Data Mining, chapter 3
- [ID3 algorithm and why greedy](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aid3-greedy) — Data Mining, chapter 3
- [ID3 steps, overfitting, TP/FP/recall](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aid3-steps-overfitting-recall) — Data Mining, chapter 3
- [Decision tree classifier and Hunt's algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Adecision-tree-hunt) — Data Mining, chapter 3

## Related in other subjects

- [Define information and entropy](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Adefine-information-entropy) — Data Communication, chapter 8, asked 3×
- [Entropy, information and channel capacity](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ainformation-entropy-capacity) — Data Communication, chapter 8
- [Entropy and information rate, 5 outcomes](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aentropy-info-rate-5-outcomes) — Data Communication, chapter 8
- [Message vs information; entropy](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Amessage-vs-information-entropy) — Communication Systems, chapter 6