ID3 algorithm and why greedy

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.