508
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
the property that they are 0 for a node that is reached only by training examples
with a single class. Here are three of the most common impurity measures. Each
applies to a node reached by training examples with n classes, with pi being the
fraction of those training examples that belong the ith class, for i = 1, 2, . . ., n.
1. Accuracy: the fraction of the reaching inputs that are correctly classiﬁed,
or 1 −max(p1, p2, . . . , pn).
2. GINI Impurity: 1 −Pn
i=1(pi)2.
3. Entropy: Pn
i=1 pi log2(1/pi).
Example 12.15 : Consider the impurity of the root of Fig. 12.26. There are
four classes. Soccer is the favorite sport of 5/12 of the countries in the training
data. Baseball and Hockey are each the class of 1/6 of the training examples,
while Cricket is the class of 1/4 of the training examples. The impurity of the
root according to the accuracy measure is therefore 1 −5/12 = 7/12 = .583.
The GINI impurity of the root is 1 −(1/6)2 −(1/6)2 −(1/4)2 −(5/12)2 =
103/144 = 0.715. The entropy of the root is
1
6 log2(6) + 1
6 log2(6) + 1
4 log2(4) + 5
12 log2(12/5) = 1.875
Note the fact that these impurity measures have rather diﬀerent values is unim-
portant.
These measures have diﬀerent ranges of possible values; see Exer-
cise 12.5.2.
The left child of the root is much less impure.
It is reached by the six
countries in South America and Europe, of which ﬁve like Soccer and one likes
Cricket. The impurity of this node according to the accuracy measure is thus
1 −5/6 = 1/6 = .167, while the GINI impurity is 1 −(1/6)2 −(5/6)2 = 5/18 =
.278. The entropy of the left child of the root is 1
6 log2(6) + 5
6 log2(6/5) = .643.
✷
12.5.3
Designing a Decision-Tree Node
The goal of node design is to produce children whose weighted average impurity
is as small as possible, where the weighting of the children is proportional to
the number of training examples that reach the node. In principle, the test
at a node could be any function of the input. As this set of possibilities is
essentially inﬁnite, we need to restrict ourselves to simple tests at each node.
In what follows, we will limit the possible tests to binary decisions based on
one of two factors:
1. The comparison of one numerical feature of the input vector with a con-
stant.
2. A test whether one categorical feature of the input vector is in a set of
possible values.
