---
title: "ID3 steps, overfitting, TP/FP/recall"
subject: "Data Mining"
chapter: 3
key: "semester_7/data_mining:id3-steps-overfitting-recall"
source: https://www.bctengineer.com/q/semester_7/data_mining/id3-steps-overfitting-recall
site: BCT Engineering
---

# ID3 steps, overfitting, TP/FP/recall

Data Mining · Chapter 3: Classification

- Asked in: year not given, 3+2+6 marks
- Video: [Lec-9: Introduction to Decision Tree 🌲 with Real life examples](https://www.youtube.com/watch?v=mvveVcbHynE) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/data_mining/id3-steps-overfitting-recall
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-3

## Question

Explain the parameters and steps that the ID3 algorithm follows to build a tree. How do you avoid over-fitting? Calculate TP rate, FP rate and Recall value from the following confusion matrix generated by WEKA from sales data.

| a | b | <-- classified as |
| --- | --- | --- |
| 9 | 2 | a = yes |
| 3 | 5 | b = no |

## Short answer

ID3 uses entropy and information gain, selects the highest-gain attribute, branches for each value, and recurses until pure or exhausted. Overfitting is avoided by pre-pruning, post-pruning, validation data, removing noise, or more data. For class yes, TP=9, FN=2, FP=3, TN=5, so TP rate=0.818, FP rate=0.375, recall=0.818.

## Answer

#### Parameters and steps of ID3
**Parameters**: the training set S, the list of candidate attributes, and the class attribute. The splitting measure is information gain, using Entropy(S) = −Σ pᵢ log₂ pᵢ and Gain(S, A) = Entropy(S) − Σ (|Sᵥ|/|S|)·Entropy(Sᵥ).

**Steps**
1. Compute the entropy of the whole data set for the class attribute.
2. For every attribute compute the weighted entropy of its partitions and hence its information gain.
3. Select the attribute with the highest gain as the root; make a branch for each of its values.
4. For each branch, repeat with the subset of records and the remaining attributes.
5. Stop when all records in a subset are of one class (leaf), no attributes remain (majority class leaf) or the subset is empty (majority class of parent).

#### Avoiding over-fitting
- **Pre-pruning**: stop early using a minimum number of records per node, minimum gain, or maximum depth.
- **Post-pruning**: grow the full tree and replace subtrees by leaves when validation error does not rise (reduced-error pruning).
- Use a validation set or cross-validation, remove noise, and collect more training data.

#### Confusion matrix calculation
Rows are actual classes. For a = yes as positive: TP = 9, FN = 2, FP = 3, TN = 5; total = 19.

- TP rate = 9/(9 + 2) = 9/11 = **0.818**
- FP rate = 3/(3 + 5) = 3/8 = **0.375**
- Recall = TP/(TP + FN) = 9/11 = **0.818** (same as the TP rate)
- Precision = 9/(9 + 3) = 0.750

For class b = no: TP rate = recall = 5/8 = 0.625, FP rate = 2/11 = 0.182, precision = 5/7 = 0.714.

**Answer: for class "yes", TP rate = 0.818, FP rate = 0.375, recall = 0.818 (overall accuracy 14/19 = 73.7%).**

## Check yourself

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

1. What is done first in ID3?
   A. Prune the tree
   B. Compute the confusion matrix
   C. Compute the entropy of the whole data set for the class attribute
   D. Pick the last attribute as root
   Answer: C. Then compute gain for each attribute. (Key point: ID3 steps)

2. Which is an example of pre-pruning?
   A. Replacing a subtree by a leaf after full growth
   B. Adding more hidden layers
   C. Removing the root
   D. Stopping when a node has fewer than a minimum number of records
   Answer: D. Pre-pruning stops growth early. (Key point: Avoiding overfitting)

3. For matrix [9 2; 3 5] with 'yes' positive, recall equals:
   A. 9/11 = 0.818, same as TP rate
   B. 9/12 = 0.750
   C. 3/8 = 0.375
   D. 5/8 = 0.625
   Answer: A. Recall = TP/(TP+FN) = 9/(9+2). (Key point: Recall)

4. FP rate for 'yes' in the same matrix is:
   A. 3/12 = 0.250
   B. 3/8 = 0.375
   C. 2/11 = 0.182
   D. 9/12 = 0.750
   Answer: B. FP/(FP+TN) = 3/(3+5). (Key point: FP rate)

## Related in Data Mining

- [ID3 and TP rate, FP rate, precision](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aid3-weka-tp-fp-precision) — 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
- [FP-tree on HotDogs data](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-tree-hotdogs) — Data Mining, chapter 4
- [FP-tree on t1-t5 data](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-tree-t1-t5) — Data Mining, chapter 4
- [Confusion matrix and performance measures](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aconfusion-matrix-measures) — Data Mining, chapter 3