ID3 algorithm and WEKA confusion matrix

ID3 algorithm

ID3 builds a decision tree top-down. At every node it picks the attribute with the highest information gain, where Gain(S, A) = Entropy(S) − Σ (|Sᵥ|/|S|)·Entropy(Sᵥ) and 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.

Significance of the confusion matrix generated by WEKA

The confusion matrix tabulates the actual class of the test records (rows) against the class predicted by the model (columns). For two classes:

It shows not only how many records were classified correctly (the diagonal) but also which kind of mistakes are made, and so it is the basis for the performance measures:

• Accuracy = (TP + TN)/total; error rate = 1 − accuracy.
• TP rate (recall, sensitivity) = TP/(TP + FN); FP rate = FP/(FP + TN).
• Precision = TP/(TP + FP); F-measure = 2·P·R/(P + R).

It is useful for imbalanced classes (accuracy alone can mislead), for comparing classifiers, and for judging whether a particular type of error (e.g. missing a patient) is acceptable. Off-diagonal cells show which classes are confused with each other.