- Year not given · 3+2+6 marks
ID3 steps, overfitting, TP/FP/recall
Short answer
ID3 uses entropy and information gain, selects the highest-gain attribute, branches for each value, and recurses until pure or exhausted. Overfitting is avoided by pre-pruning, post-pruning, validation data, removing noise, or more data. For class yes, TP=9, FN=2, FP=3, TN=5, so TP rate=0.818, FP rate=0.375, recall=0.818.
Explain the parameters and steps that the ID3 algorithm follows to build a tree. How do you avoid over-fitting? Calculate TP rate, FP rate and Recall value from the following confusion matrix generated by WEKA from sales data.
| a | b | <-- classified as |
|---|---|---|
| 9 | 2 | a = yes |
| 3 | 5 | b = no |
Parameters and steps of ID3
Parameters: the training set S, the list of candidate attributes, and the class attribute. The splitting measure is information gain, using Entropy(S) = −Σ pᵢ log₂ pᵢ and Gain(S, A) = Entropy(S) − Σ (|Sᵥ|/|S|)·Entropy(Sᵥ).
Steps
- Compute the entropy of the whole data set for the class attribute.
- For every attribute compute the weighted entropy of its partitions and hence its information gain.
- Select the attribute with the highest gain as the root; make a branch for each of its values.
- For each branch, repeat with the subset of records and the remaining attributes.
- Stop when all records in a subset are of one class (leaf), no attributes remain (majority class leaf) or the subset is empty (majority class of parent).
Avoiding over-fitting
- Pre-pruning: stop early using a minimum number of records per node, minimum gain, or maximum depth.
- Post-pruning: grow the full tree and replace subtrees by leaves when validation error does not rise (reduced-error pruning).
- Use a validation set or cross-validation, remove noise, and collect more training data.
Confusion matrix calculation
Rows are actual classes. For a = yes as positive: TP = 9, FN = 2, FP = 3, TN = 5; total = 19.
- TP rate = 9/(9 + 2) = 9/11 = 0.818
- FP rate = 3/(3 + 5) = 3/8 = 0.375
- Recall = TP/(TP + FN) = 9/11 = 0.818 (same as the TP rate)
- Precision = 9/(9 + 3) = 0.750
For class b = no: TP rate = recall = 5/8 = 0.625, FP rate = 2/11 = 0.182, precision = 5/7 = 0.714.
Answer: for class "yes", TP rate = 0.818, FP rate = 0.375, recall = 0.818 (overall accuracy 14/19 = 73.7%).
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- ID3 and TP rate, FP rate, precision · Data Mining, chapter 3
- ID3 algorithm and WEKA confusion matrix · Data Mining, chapter 3
- Overfitting in ID3 and decision tree rules · Data Mining, chapter 3
- FP-tree on HotDogs data · Data Mining, chapter 4
- FP-tree on t1-t5 data · Data Mining, chapter 4
- Confusion matrix and performance measures · Data Mining, chapter 3