Inductive learning and ID3

Inductive learning is learning a general rule or concept from specific training examples (specific to general). Given examples with attribute values and class labels, the learner builds a hypothesis (such as a decision tree) that classifies new, unseen cases.

ID3 (Iterative Dichotomiser 3, Quinlan)

ID3 builds a decision tree top-down; at each node it picks the attribute with the highest information gain.

• Entropy: E(S) = −Σ p_i log₂ p_i
• Gain(S, A) = E(S) − Σ (|S_v| / |S|) · E(S_v)

Steps

1. If all examples in S belong to one class, make a leaf with that class.
2. If no attributes remain, make a leaf with the majority class.
3. Otherwise compute Gain for each attribute; choose the best A.
4. Create a node for A; split S by the values of A.
5. Recurse on each subset with A removed.

Example: Play Tennis (14 examples: 9 Yes, 5 No)

E(S) = −(9/14)log₂(9/14) − (5/14)log₂(5/14) = 0.940

Outlook has the highest gain, so it is the root.

• Overcast: all Yes, so leaf = Yes.
• Sunny (E = 0.971): gains: Humidity 0.971, Temperature 0.571, Wind 0.020. Choose Humidity: High gives No, Normal gives Yes.
• Rain (E = 0.971): Wind separates perfectly: Weak gives Yes, Strong gives No.

            Outlook
         /     |      \
    Sunny   Overcast   Rain
      |        |         |
  Humidity    Yes      Wind
   /    \               /   \
 High  Normal       Weak   Strong
  No    Yes          Yes     No

(Gains were computed by program.) The tree gives rules such as: IF Outlook = Sunny AND Humidity = Normal THEN Play = Yes.

Strengths: simple, readable rules, fast. Weaknesses: overfits noisy data (needs pruning), prefers attributes with many values.