12.5. DECISION TREES
511
populations for the row in question and the next row. Thus, in each row, we
have Im≤
= 1 −(pS≤)2 −(pC≤)2 and Im>
= 1 −(pS>)2 −(pC>)2. For
instance, in the row for Spain, we have Im≤
= 1 −12 −02 = 0 and
Im>
= 1 −(3/4)2 −(1/4)2 = 3/8
Finally, the last column is the weighted GINI impurity for the two children,
weighted by the number of countries that reach each of these children. For
example, in the row for Spain, if we divide between the populations of Spain and
the next more populous country, Italy, then two countries go to the left child and
four to the right child. Thus, the weighted impurity is (2/6)0+(4/6)(3/8) = 1/4.
Of the ﬁve rows after which a split is possible, we ﬁnd the smallest weighted
impurity to be 2/9, which we get by splitting after Italy. That is, we would use
a test like “Population < 60” to send Argentina, Spain, and Italy, all of whom
like Soccer, to the left. The other three countries, two of which like Soccer and
one Cricket, are sent to the right child. Since the left child is pure, it is a leaf
declaring Soccer to be the sport, while the right child will need to be split again.
Technically, we also have to consider that the test at the left child of the
root does not involve population at all, but rather is a test on the continent.
However, we cannot do better by splitting Europe from South America; that
gives a weighted GINI impurity of 1/4.
✷
12.5.5
Selecting a Test Using a Categorical Feature
Now consider how we might split the training examples that reach a node, using
the value of a categorical feature A. To avoid having to consider all possible
subsets of the values of A, we shall only consider the case where there are
two classes. In our running example, we might suppose that the two classes
are Soccer (S) and anything but soccer (N). When there are two classes, we
can order the values of A by the fraction of training examples with that value
belonging to the ﬁrst class.
Since there are only two classes, the partition of values with the lowest
impurity will surely be based on a set of values that is a preﬁx of this order.
That is, this set consists of the values of A whose fractions in the ﬁrst class
are above some threshold. Thus, the examples going to the left child will have
many examples in the ﬁrst class, while the examples going right will have many
in the second class.
The process of ﬁnding the split in the ordered list of values that minimizes
the weighted impurity is then essentially the same as for numerical features,
which we explained in Section 12.5.4. The diﬀerence is that now we are going
down a list of values of A, rather than down a list of training examples. We shall
work an example, based on the categorical feture Continent from our running
example.
Example 12.18 : Let us see how we might design the root of Fig. 12.26, as-
suming that we recognized only two classes: Soccer (S) and other sports (N).
