512
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
As before, we shall use GINI as the measure of impurity for nodes. Figure 12.28
summarizes our calculation. In the columns labeled S and N, we see the counts
of training examples from Fig. 12.25 for which the favorite sport is Soccer and
anything else. The continents are ordered by the fraction of their countries in
the Soccer class. Thus, South America is ﬁrst, because 100% of its training
examples are in the class S. Then comes Europe, where 75% of its training
examples are in class S. The remaining three continents have 0% in the Soccer
class, and could have been ordered in any way.
Cont.
S
N
nS
nN
pS≤
pN≤
pS>
pN>
Im≤
Im>
Wtd.
SA
2
0
2
0
1
0
3/10
7/10
0
21/50
7/20
Eur
3
1
5
1
5/6
1/6
0
1
5/18
0
5/36
NA
0
3
5
4
5/9
4/9
0
1
40/81
0
10/27
Asia
0
2
5
6
5/11
6/11
0
1
60/121
0
5/11
Aus
0
1
5
7
5/12
7/12
–
–
–
–
–
Figure 12.28: Computing the GINI index for sets of continents
The next columns in Fig. 12.28 are nS and nN. These are the cumulative
sums of the number of examples in class S and not in class S, respectively,
counting from the top. For instance, the row for North America has nS = 5
and nN = 4, because among the ﬁrst three rows there are ﬁve examples in the
class S and four in the class N. Note that, as for numerical features, we can
compute the cumulative sum by a single pass from the top to the bottom. Also,
we can get the numbers in each class among all the rows below by subtracting
nS or nN from its corresponding value at the bottom row.
The next two columns are the fractions in each class for that row and above.
That is, pS≤= nS/(nS + nN) and pN≤= nN/(nS + nN). After those come
the two columns pS> amd pN> that give the fractions in the classes S and
N among all the rows below. For example, in the row for NA, there are zero
members of the class S below, which we can see because nS = 5 in both the row
for NA and the bottom row. Also, there are 3 members of the class N below,
since the value of nN for row NA is 4, while the value of nN in the bottom row
is 7.
The columns Im≤and Im> follow. As in Example 12.17, these are the GINI
impurities of the left and right children, assuming the row in question and all
rows above are sent to the left child and all rows below are sent to the right child.
Then, the last column gives the weighted GINI impurity of the children. For
instance, consider the entries in the row for NA. If we use the test for whether the
Continent is one of SA, Eur, and NA to send examples to the left child, then nine
of the training examples will go left, and the remaining three will go right. Thus,
the weighted GINI impurity for this split is (9/12)(40/81) + (3/12)0 = 10/27.
By far the best split comes after Eur, with a weighted impurity of 5/36.
That was the split we used in Fig. 12.26.
✷
