Decision Tree Algorithm:
Tree where internal nodes test attribute, branches = values, leaves = class. Learns by greedy top-down, divide-and-conquer.

Algorithm (ID3/C4.5):

1. If all examples same class or attributes empty → leaf.
2. Choose best attribute $A$ by Information Gain $Gain(S,A)=Entropy(S)-\sum_v (|S_v|/|S|)Entropy(S_v)$ (or Gain Ratio, Gini).
3. Split $S$ by $A$ values, recurse on subsets.

Entropy: $H(S)= -\sum p_i \log_2 p_i$

Issues in Decision Tree Induction:

1. Choosing attribute selection measure: Gain biases to many-valued attributes → Gain Ratio (C4.5) or Gini (CART).
2. Overfitting: Tree grows until pure, memorizes noise. Solutions: pre-pruning (stop early, min samples/chi-square), post-pruning (reduced-error pruning, cost-complexity), validation set.
3. Underfitting / Bias: Too shallow tree misses pattern.
4. Handling continuous attributes: Need discretization — find best split threshold $x < t$.
5. Handling missing values: Surrogate splits, fractional examples, imputation (C4.5).
6. Incorporating costs / noisy data: Different misclassification costs, pruning for noise robustness.
7. Inconsistent data / Large hypothesis space: Exponential $3^n$ possible trees; greedy may get local optimum, not globally optimal (NP-hard).
8. Instability: Small data change → large tree change; ensemble methods (Random Forest) mitigate.
9. Class imbalance, oblique splits, scalability for large datasets.