- Year not given
C4.5 vs ID3; gain, gain ratio, Gini
Short answer
C4.5 overcomes ID3's bias toward many-valued attributes by using gain ratio, handles continuous and missing values, and prunes trees. Information gain measures entropy reduction but favors many splits; gain ratio normalizes it; Gini index is a faster impurity measure used in CART.
How does C4.5 overcome the problem of ID3 Algorithm? Compare Information Gain, Gain ratio and Gini Index.
How C4.5 overcomes the problems of ID3
C4.5 (Quinlan) is the successor of ID3. It improves ID3 in these ways:
| ID3 problem | C4.5 solution |
|---|---|
| Biased to attributes with many values (e.g. an ID attribute) | Uses gain ratio = Gain / SplitInfo |
| Only categorical attributes | Handles continuous attributes by choosing a threshold (A ≤ t, A > t) |
| Cannot handle missing values | Distributes the record over branches with fractional weights, or ignores it while computing the gain |
| Overfitting, no pruning | Pruning (pessimistic error-based post-pruning) |
| Rules not produced | Converts the tree into simplified rules |
| No attribute costs | Allows attributes with different costs |
Comparison of splitting measures
- Information gain = Entropy(S) − Σ (|Sᵥ|/|S|) Entropy(Sᵥ), where Entropy = −Σ pᵢ log₂ pᵢ.
- Gain ratio = Gain(A)/SplitInfo(A), SplitInfo(A) = −Σ (|Sᵥ|/|S|) log₂(|Sᵥ|/|S|).
- Gini index = 1 − Σ pᵢ²; for a split, Gini_split = Σ (|Sᵥ|/|S|) Gini(Sᵥ).
| Basis | Information gain | Gain ratio | Gini index |
|---|---|---|---|
| Used in | ID3 | C4.5 | CART, SLIQ |
| Idea | Reduction in entropy | Gain normalised by split info | Reduction in impurity |
| Choose | Maximum | Maximum | Minimum Gini_split |
| Many-valued bias | Yes | Corrected | Yes (favours multiway), CART uses binary splits |
| Cost | Logarithms | Logarithms | Only squares, faster |
Example (Play Golf, 9 yes, 5 no, split on Outlook): Entropy = 0.940, Gain = 0.247, SplitInfo = 1.577, Gain ratio = 0.156. Gini(S) = 0.459, Gini_split = (5/14)(0.48) + (4/14)(0) + (5/14)(0.48) = 0.343, so Gini reduction = 0.116.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Entropy, information gain and ID3 tree · Data Mining, chapter 3
- ID3 algorithm and WEKA confusion matrix · Data Mining, chapter 3
- ID3 algorithm and why greedy · Data Mining, chapter 3
- Overfitting in ID3 and decision tree rules · Data Mining, chapter 3
- ID3 and TP rate, FP rate, precision · Data Mining, chapter 3
- ID3 steps, overfitting, TP/FP/recall · Data Mining, chapter 3
- Compare industrial age and information age · Technology, Environment and Society, chapter 1 · asked 2×
- Modified B/C ratio for the required-receipts problem · Engineering Economics, chapter 3
- File system layers; linked list vs index · Operating System, chapter 5
- Detection gain of SSB-SC vs DSB-SC · Communication Systems, chapter 9 · asked 2×