---
title: "ID3 algorithm and why greedy"
subject: "Data Mining"
chapter: 3
key: "semester_7/data_mining:id3-greedy"
source: https://www.bctengineer.com/q/semester_7/data_mining/id3-greedy
site: BCT Engineering
---

# ID3 algorithm and why greedy

Data Mining · Chapter 3: Classification

- Asked in: year not given
- Video: [Lec-10: Decision Tree 🌲 ID3 Algorithm with Example & Calculations 🧮](https://www.youtube.com/watch?v=CWzpomtLqqs) — 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-greedy
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-3

## Question

Describe Iterative Dichotomizer 3 (ID3) algorithm. What makes ID3 algorithm "greedy"?

## Short answer

ID3 builds a decision tree by selecting the attribute with maximum information gain at each node. It is greedy because it makes the locally optimal choice without backtracking, never reconsidering earlier splits, which may not yield the globally optimal tree.

## Answer

**ID3 (Iterative Dichotomiser 3)**, developed by J. Ross Quinlan, builds a decision tree from categorical training data. At each node it chooses the attribute that gives the highest **information gain**, splits the data by that attribute's values and repeats recursively.

#### Algorithm
1. Compute Entropy(S) = −Σ pᵢ log₂ pᵢ for the data at the node.
2. For each remaining attribute A find Gain(S, A) = Entropy(S) − Σ (|Sᵥ|/|S|) Entropy(Sᵥ).
3. Choose the attribute with maximum gain and create a branch for each value.
4. Recurse on every branch with the remaining attributes.
5. Stop (leaf) when all records have the same class, no attributes are left (majority class), or the subset is empty (parent's majority class).

*Example*: for the 14-tuple buys-computer data, Gain(age) = 0.247 is greatest, so age is the root.

#### Why ID3 is "greedy"
- At each step it makes the **locally best choice** (the attribute with highest gain now) and **never backtracks** or reconsiders earlier splits.
- It does not look ahead to see whether a different split would give a smaller overall tree; so it does not guarantee the globally optimal (smallest, most accurate) tree.
- An attribute chosen once cannot be revised, and the tree can overfit.

Greedy search keeps ID3 fast, but the resulting tree is a good, not necessarily the best, one. Limitations: only categorical attributes, bias to many-valued attributes, sensitivity to noise and missing values, which C4.5 improves.

## Check yourself

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

1. What makes ID3 greedy?
   A. It tests all possible trees
   B. It looks ahead for the smallest tree
   C. It picks the locally best attribute at each step and never backtracks
   D. It uses random splits
   Answer: C. No reconsideration of earlier splits. (Key point: Why greedy)

2. Because ID3 is greedy, the tree is:
   A. Always globally optimal
   B. Always the smallest
   C. Always the most accurate
   D. Good but not necessarily optimal
   Answer: D. No look-ahead guarantee. (Key point: Consequence)

3. ID3 makes a leaf when:
   A. All records have the same class, no attributes remain, or the subset is empty
   B. The tree depth is 1
   C. Gain is highest
   D. A new attribute appears
   Answer: A. Majority class used for the last two. (Key point: Algorithm stop)

4. Which is a limitation of ID3 that C4.5 improves?
   A. It cannot use entropy
   B. Only categorical attributes and bias to many-valued attributes
   C. It needs class labels removed
   D. It cannot build trees
   Answer: B. C4.5 handles continuous values and uses gain ratio. (Key point: Limitation)

## Related in Data Mining

- [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
- [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
- [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 steps, overfitting, TP/FP/recall](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aid3-steps-overfitting-recall) — Data Mining, chapter 3
- [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
- [Buys computer: ID3 and Naive Bayes](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Abuys-computer-id3-naive-bayes) — Data Mining, chapter 3

## Related in other subjects

- [Greedy best-first drawbacks; A*](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Agreedy-best-first-vs-astar) — Artificial Intelligence, chapter 3
- [Recursion; iterative vs recursive choice](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adefine-recursion-iterative-vs-recursive) — Data Structure and Algorithm, chapter 5