---
title: "Overfitting in ID3 and decision tree rules"
subject: "Data Mining"
chapter: 3
key: "semester_7/data_mining:id3-overfitting-rules"
source: https://www.bctengineer.com/q/semester_7/data_mining/id3-overfitting-rules
site: BCT Engineering
---

# Overfitting in ID3 and decision tree rules

Data Mining · Chapter 3: Classification

- Asked in: year not given, 4+4 marks
- Video: [How to Avoid Overfitting in Decision Tree Learning | Machine Learning | Data Mining by Mahesh Huddar](https://www.youtube.com/watch?v=__syf8H9-Pg) — 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-overfitting-rules
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-3

## Question

How could you solve the problem of over fitting in ID3 implementation? Explain the rules and conditions to generate decision tree using ID3.

## Short answer

Overfitting in ID3 is solved by pre-pruning, post-pruning with a validation set, rule post-pruning, more data or ensembles. ID3 splits on the attribute with highest information gain, makes one branch per value, and stops when all examples share one class, no attributes remain, or no examples remain.

## Answer

#### Overfitting in ID3
A tree grown until every leaf is pure fits the noise and special cases in the training data. Training accuracy is high but accuracy on new data is poor. It is reduced by **pruning** and by limiting the growth of the tree.

#### Solutions
1. **Pre-pruning (early stopping)**: stop growing when a node
   - has fewer than a minimum number of records,
   - has information gain below a threshold (or a χ² test shows the split is not significant),
   - reaches a maximum depth, or has a high enough class purity.
2. **Post-pruning**: grow the full tree, then replace a subtree by a leaf (majority class) if error on a separate **validation set** does not increase (reduced-error pruning), or use pessimistic error / MDL cost.
3. **Rule post-pruning**: convert the tree to rules and drop conditions that do not reduce accuracy.
4. Use more training data, remove noisy records, or use ensembles (random forest).

#### Rules and conditions to generate the tree with ID3
1. Select the attribute with the **highest information gain** (lowest remaining entropy) as the splitting attribute. An attribute used on a path is not used again on that path.
2. Make one branch for every value of the attribute and divide the examples.
3. **Stop and make a leaf** when:
   - all examples at the node belong to one class (entropy = 0);
   - no attributes remain: label with the majority class;
   - no examples remain for a branch: label with the majority class of the parent.
4. Otherwise repeat recursively on each branch.

Entropy(S) = −Σ pᵢ log₂ pᵢ; Gain(S, A) = Entropy(S) − Σ (|Sᵥ|/|S|)·Entropy(Sᵥ).

## Check yourself

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

1. What characterises an overfitted tree?
   A. Low training accuracy but good test accuracy
   B. Low accuracy on both
   C. High training accuracy but poor accuracy on new data
   D. Very small tree depth
   Answer: C. It fits noise in the training data. (Key point: Overfitting)

2. What is post-pruning?
   A. Stopping growth when information gain is below a threshold
   B. Removing noisy records before training
   C. Using only one attribute
   D. Growing the full tree, then replacing subtrees by leaves if validation error does not increase
   Answer: D. Stopping early is pre-pruning; post-pruning cuts the fully grown tree. (Key point: Pre vs post pruning)

3. Which attribute does ID3 choose to split on?
   A. The one with the highest information gain
   B. The one with the lowest information gain
   C. The one with the most values
   D. The first attribute in the list
   Answer: A. Highest gain means lowest remaining entropy. (Key point: Splitting attribute)

4. If no examples remain for a branch, how is the leaf labelled?
   A. With the class 'no'
   B. With the majority class of the parent
   C. With the class of the root only
   D. It is left unlabelled
   Answer: B. Empty subsets get the parent's majority class. (Key point: Leaf conditions)

## Related in Data Mining

- [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
- [Extracting rules from decision tree](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Arules-from-decision-tree) — Data Mining, chapter 3
- [Rules generation using ID3](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aid3-rules-generation) — Data Mining, chapter 3
- [Entropy, information gain and ID3 tree](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aid3-entropy-information-gain) — Data Mining, chapter 3
- [Short note: Decision tree](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Adecision-tree-note) — 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

- [Explain decision tree analysis](https://www.bctengineer.com/question.md?key=semester_6%2Fengineering_economics%3Aexplain-decision-tree) — Engineering Economics, chapter 6, asked 5×
- [Decision tree for plant improvement alternatives](https://www.bctengineer.com/question.md?key=semester_6%2Fengineering_economics%3Adecision-tree-plant-alternatives) — Engineering Economics, chapter 6, asked 2×
- [Decision tree; infinite source blocking formulas](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Adecision-tree-infinite-sources) — Telecommunications, chapter 6, asked 2×
- [Decision tree; finite source blocking formulas](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Adecision-tree-finite-sources) — Telecommunications, chapter 6, asked 2×