Overfitting and Underfitting in Decision Tree Construction

Overfitting

Overfitting is when the decision tree is grown to fit the training data too precisely — including random noise, outliers, and accidental coincidences — rather than the true underlying pattern. The tree gets very low (often zero) training error but performs poorly on unseen test data because it has memorised the training set instead of generalising.

Causes in decision trees:

• Growing the tree until every training tuple is perfectly classified (no pruning, or an extremely small minimum-leaf-size).
• Building a very deep, bushy tree that creates a separate branch/leaf for noisy or uncommon attribute combinations.
• Choosing splitting attributes that over-segment the data (accidental patterns in small partitions are treated as real structure).

Detection: a large gap between the training accuracy and hold-out/validation accuracy is a classic symptom.

Remedies:

• Pre-pruning — stop growing the tree early (e.g., when the information-gain of the best split falls below a threshold, or when a node contains fewer than a minimum number of tuples).
• Post-pruning — grow the full tree and then prune branches that do not improve accuracy on a validation set (cost-complexity or reduced-error pruning).
• Limit the maximum depth; use cross-validation to choose tree size; use ensembles such as random forests which average many trees and reduce variance.

Underfitting

Underfitting occurs when the decision tree is too simple to capture the structure of the data — for example, a tiny tree with only one or two leaves that ignores most attributes. Both training and test errors are high because the model cannot express the true decision boundary (a high-bias problem).

Remedies:

• Allow deeper trees / larger splits (relax the minimum-samples and pruning thresholds).
• Provide more informative features and more training data.
• Use a more expressive model (e.g., increase depth or switch to an ensemble / larger-capacity classifier).

Suitable Examples

• Overfitting example: In a "play tennis?" dataset, a fully grown tree may create a branch such as "Outlook = Sunny ∧ Humidity = 65 → No", created only to satisfy the one noisy training example sitting at that point. Training accuracy becomes 100%, but on a new day with Humidity = 65 the tree irrationally predicts "No", where the general pattern would suggest "Yes".
• Underfitting example: If the tree is limited to a single leaf ("always predict Play = Yes"), it is too simple to capture the seasonal/temperature structure in the data, giving a high error on both the training and test sets.

Trade-off

There is a bias–variance trade-off: underfitting ↔ high bias (too simple); overfitting ↔ high variance (too complex). The right tree complexity is usually chosen with cross-validation and pruning, so that the final tree generalises well while remaining interpretable.