Skip to main content

Overfitting in ID3 and decision tree rules

Short answer

Overfitting in ID3 is solved by pre-pruning, post-pruning with a validation set, rule post-pruning, more data or ensembles. ID3 splits on the attribute with highest information gain, makes one branch per value, and stops when all examples share one class, no attributes remain, or no examples remain.

How could you solve the problem of over fitting in ID3 implementation? Explain the rules and conditions to generate decision tree using ID3.

Overfitting in ID3

A tree grown until every leaf is pure fits the noise and special cases in the training data. Training accuracy is high but accuracy on new data is poor. It is reduced by pruning and by limiting the growth of the tree.

Solutions

  1. Pre-pruning (early stopping): stop growing when a node
    • has fewer than a minimum number of records,
    • has information gain below a threshold (or a χ² test shows the split is not significant),
    • reaches a maximum depth, or has a high enough class purity.
  2. Post-pruning: grow the full tree, then replace a subtree by a leaf (majority class) if error on a separate validation set does not increase (reduced-error pruning), or use pessimistic error / MDL cost.
  3. Rule post-pruning: convert the tree to rules and drop conditions that do not reduce accuracy.
  4. Use more training data, remove noisy records, or use ensembles (random forest).

Rules and conditions to generate the tree with ID3

  1. Select the attribute with the highest information gain (lowest remaining entropy) as the splitting attribute. An attribute used on a path is not used again on that path.
  2. Make one branch for every value of the attribute and divide the examples.
  3. Stop and make a leaf when:
    • all examples at the node belong to one class (entropy = 0);
    • no attributes remain: label with the majority class;
    • no examples remain for a branch: label with the majority class of the parent.
  4. Otherwise repeat recursively on each branch.

Entropy(S) = −Σ pᵢ log₂ pᵢ; Gain(S, A) = Entropy(S) − Σ (|Sᵥ|/|S|)·Entropy(Sᵥ).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Mining chapter 3 questions →