Exercise 7.9 The decision-tree learning algorithm of Figure 7.5 (page 300) has to stop if it runs out of features and not all examples agree.

Suppose that you are building a decision tree and you have come to the stage where there are no remaining features to split on and there are examples in the training set, n1 of which are positive and n0 of which are negative. Three strategies have been suggested:

i) Return whichever value has the most examples – return true if n1 > n0, false if n1 < n0, and either if n1 = n0.

ii) Return the empirical frequency, n1/(n0 + n1).

iii) Return (n1 + 1)/(n0 + n1 + 2).

Which of the following strategies has the least error on the training set?

(a) The error is defined as the sum of the absolute differences between the value of the example (1 = true and 0 = false) and the predicted values in the tree

(either 1 = true and 0 = false or the probability).

(b) The error is defined as the sum of the squares of the differences in values.

(c) The error is the entropy of the data.

Explain how you derived this answer.