ID3 Algorithm for Decision Tree Construction — Description & Limitations

Overview

ID3 (Iterative Dichotomiser 3), by J. Ross Quinlan, builds a decision tree top-down, greedily, choosing the attribute with the highest Information Gain (based on entropy) at each node.

Entropy — the impurity of a data set $D$ with $m$ classes is

$$H(D) = -\sum_{i=1}^{m} p_i \log_2 p_i$$

where $p_i$ is the fraction of tuples in $D$ belonging to class $C_i$.

Information Gain of partitioning $D$ on attribute $A$ with distinct values $\{a_1, \dots, a_v\}$:

$$\text{Gain}(A) = H(D) - \sum_{j=1}^{v} \frac{|D_j|}{|D|}\, H(D_j)$$

where $D_j$ is the subset of $D$ with $A = a_j$.

Algorithm Steps

Algorithm ID3(D: training set, Attributes)
1. Create a root node for D.
2. If all tuples in D belong to the same class C → label node C and return.
3. If Attributes is empty → label node with majority class and return.
4. Else pick A_best = the attribute with maximum Gain(A).
5. Label node with A_best; for each distinct value a_j of A_best create one branch.
6. For each branch: D_j = {tuples with A_best = a_j}
   - if D_j empty → leaf labelled with majority class of D
   - else recursively run ID3(D_j, Attributes − {A_best})
7. Return the resulting tree.

Why ID3 is unsuitable — main limitations

1. Handles only categorical attributes — continuous/numeric data must be discretized first; it cannot branch on < / <= thresholds.
2. Bias toward multi-valued attributes — information gain favours an attribute with many distinct values (e.g. a "customer-ID" attribute would give maximal gain yet be useless), producing poor generalisation. This is fixed in C4.5 by using the gain ratio.
3. No pruning → overfitting — it grows the tree until it fits the training data perfectly, thereby memorising noise and hurting accuracy on unseen test data.
4. Greedy, no backtracking — a locally optimal split may lead to a globally sub-optimal tree.
5. Handles missing values / noise poorly and is unstable — small changes in the training data produce quite different trees.

Despite these limitations, ID3 is the foundation for C4.5 / C5.0 (adding gain ratio, continuous attributes, and pruning) and further scalable classifiers such as CART, SLIQ, SPRINT, and RainForest.