12.5. DECISION TREES
509
Example 12.16 : Notice that the tests at the children of the root in Fig. 12.26
do not satisfy condition (1) for numerical features.
For example, the right
child of the root is the logical AND of two comparisons, population > 55 and
population < 200. However, we could use both these conditions if we replaced
the single node by two nodes, each testing one of the conditions. The root
is a test for membership of the value of feature Continent in the set of two
continents SA and Eur, so it does satisfy condition (2).
✷
Suppose we are given a node of the decision tree that is reached by a subset
of the training examples. If the node is pure, i.e., all these training examples
have the same output, then we make the node a leaf with that output as value.
However, if the impurity is greater than zero, we want to ﬁnd the test that
gives the greatest reduction in impurity. When selecting this test, we are free
to choose any feature of the input vector. If we choose a numerical feature,
we can choose any constant to divide the training examples into two sets, one
going to the left child and the other going to the right child. Alternatively, if
we choose a categorical feature, then we may choose any set of values for the
membership test. We shall consider each of these cases in turn.
12.5.4
Selecting a Test Using a Numerical Feature
Suppose we want to split a set of training examples based on a numerical
feature A. In our running example, A could only be Population, one of the two
features – Population and Continent – that are components of feature vectors
(recall we assume we do not see the country name; that name is used only to
identify each training example). To select the best breakpoint, we
1. Order the training examples according to their value of A. Let the values
of A in this order be a1, a2, . . . , an.
2. For j = 1, 2, . . . , n, compute the number of training examples in each class
among a1, a2, . . . , aj. Note that these counts can be done incrementally,
since the count for a class after the jth example is either the same as the
count for j −1 (if the jth example in not in this class) or one more than
the count for j −1 (if the jth example is in this class).
3. From the counts computed in the previous step, compute the weighted-
average impurity assuming the test sends the ﬁrst j training examples
to the left child and the remaining n −j examples to the right node.
Here, we must assume the impurity can be computed from the counts for
each class. That is surely the case for the three measures of impurity –
accuracy, GINI, and entropy – that we discussed in Section 12.5.2.
4. Select that value of j that minimizes the weighted-average impurity. How-
ever, note that not every possible value of j can be used at this step, since
it is possible that aj = aj+1. We need to restrict our choice of j to those
