Entropy, information gain and ID3 tree

Entropy

Entropy measures the impurity (randomness) of a set S of examples:

Entropy(S) = − Σ pᵢ log₂ pᵢ

where pᵢ is the proportion of class i in S. It is 0 when all examples are of one class, and 1 (for two classes) when the classes are equally mixed.

Example: 9 Yes and 5 No: Entropy = −(9/14)log₂(9/14) − (5/14)log₂(5/14) = 0.940.

Information gain

Information gain is the expected reduction in entropy after splitting S on attribute A:

Gain(S, A) = Entropy(S) − Σ over values v of A [ (|Sᵥ|/|S|) · Entropy(Sᵥ) ]

The attribute with the highest gain gives the purest partitions, so it is used for the split.

Example (Play Golf): Outlook splits 14 records into Overcast (4 Yes, 0 No; E = 0), Sunny (2 Yes, 3 No; E = 0.971), Rainy (3 Yes, 2 No; E = 0.971). Gain(Outlook) = 0.940 − (4/14)(0) − (5/14)(0.971) − (5/14)(0.971) = 0.247. Gains of other attributes are lower (Humidity 0.152, Windy 0.048, Temperature 0.029), so Outlook is the root.

ID3 algorithm (Iterative Dichotomiser 3, Quinlan)

ID3(S, Attributes, Class)
1. Create a node N.
2. If all examples in S have the same class C
      return N as a leaf labelled C.
3. If Attributes is empty
      return N as a leaf labelled with the majority class of S.
4. For every attribute A compute Gain(S, A).
5. Choose A* with the highest information gain; label N with A*.
6. For each value v of A*:
      Sv = examples of S with A* = v
      if Sv is empty: add a leaf with the majority class of S
      else: add the subtree ID3(Sv, Attributes - {A*}, Class)
7. Return N.

ID3 uses a greedy, top-down search, handles only categorical attributes (continuous ones must be discretised), and does no backtracking or pruning. It tends to prefer attributes with many values.