ID3 and TP rate, FP rate, precision

How ID3 works

ID3 (Iterative Dichotomiser 3) grows a decision tree top-down, always splitting on the attribute with the highest information gain, Gain(S, A) = Entropy(S) − Σ (|Sᵥ|/|S|)·Entropy(Sᵥ), with Entropy(S) = −Σ pᵢ log₂ pᵢ.

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.

Leaves are labelled with the class; a new record is classified by following the tests from the root to a leaf. ID3 is greedy, accepts only categorical attributes, and can overfit.

Confusion matrix calculation

Rows are actual classes, columns are the classified ones. Total = 7 + 2 + 3 + 2 = 14.

For class a = yes (taken as positive): TP = 7, FN = 2, FP = 3 (actual "no" classified as "yes"), TN = 2.

• TP rate = TP/(TP + FN) = 7/(7 + 2) = 7/9 = 0.778
• FP rate = FP/(FP + TN) = 3/(3 + 2) = 3/5 = 0.600
• Precision = TP/(TP + FP) = 7/(7 + 3) = 7/10 = 0.700

For class b = no (taken as positive): TP = 2, FN = 3, FP = 2, TN = 7.

• TP rate = 2/5 = 0.400, FP rate = 2/9 = 0.222, precision = 2/4 = 0.500.

Accuracy = (7 + 2)/14 = 64.3%.

Answer: for the class "yes", TP rate = 0.778, FP rate = 0.600, precision = 0.700.