Issues in Decision Tree Learning:

1. Determining Correct Depth / Overfitting: Fully grown tree overfits training data (memorizes noise). Need pruning.

   • Pre-pruning: Stop early via max_depth, min_samples_split, $\chi^2$ test, information gain threshold.
   • Post-pruning: Grow full, then prune using validation set (reduced-error pruning, cost-complexity pruning in CART with $\alpha$).

2. Attribute Selection Measure: Information Gain biases to many-valued attributes (e.g., ID column). Gain Ratio (C4.5) normalizes by SplitInfo, Gini index (CART), or use least biased measures.

3. Handling Continuous Attributes: Need to find optimal threshold $t$ for split $A \le t$ vs $>t$ by sorting values and evaluating gain for candidate mid-points — $O(n\log n)$ per attribute.

4. Handling Missing Values: Training: ignore missing or distribute fractionally (C4.5). Testing: follow both branches weighted. Alternatives: surrogate splits (CART), imputation.

5. Handling Noisy Data & Outliers: Noise causes incorrect splits; pruning and robust measures (e.g., use majority voting at leaves) help.

6. Inconsistent Data: Same feature vector with different labels → cannot achieve 100% accuracy; need probabilistic leaves.

7. Computational Complexity: Finding optimal tree is NP-hard; greedy heuristics may produce locally optimal but globally suboptimal trees. Ensembles mitigate.

8. Data Fragmentation: Splits reduce sample per leaf, estimates unreliable at deep levels.

9. Instability / High Variance: Small data perturbations → very different tree (solved by Random Forest bagging).

10. Class Imbalance: Majority class dominates gain; need weighted entropy, stratified sampling, cost-sensitive splits.

11. Replicated Subtrees & Oblique Splits: Axis-parallel splits cannot represent diagonal boundaries efficiently → need multivariate trees.