510
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
values such that aj < aj+1, so that we can use A < (aj + aj+1)/2 as the
comparison.
Example 12.17 : Suppose we use the root comparison from Fig. 12.26, which
sends the six countries from Europe and South America to the left child, and
the other six to the right. Now, we need to divide the six countries reaching
the left child in such a way that the weighted impurity of the two children of
the root’s left child is as small as possible. We could use either the Continent
or Population feature to do the division, and we must consider both in order
to ﬁnd the split that minimizes the impurity.
Here, we shall consider only
Population, since that is the only numerical feature. In Fig. 12.27 we see the
six countries that reach the left child of the root, ordered by their population.
Ctry.
Pop.
Sp.
nS
nC
pS≤
pC≤
pS>
pC>
Im≤
Im>
Wtd.
Arg.
44
S
1
0
1
0
4/5
1/5
0
8/25
4/15
Spain
46
S
2
0
1
0
3/4
1/4
0
3/8
1/4
Italy
59
S
3
0
1
0
2/3
1/3
0
4/9
2/9
UK
65
C
3
1
3/4
1/4
1
0
3/8
0
1/4
Ger.
80
S
4
1
4/5
1/5
1
0
8/25
0
4/15
Bra.
211
S
5
1
5/6
1/6
–
–
–
–
–
Figure 12.27: Computing the GINI index for each possible separation
The columns explain the calculation as follows. First, the column labeled
“Sp” is the favorite sport, which for this set of countries is either Soccer (S) or
Cricket (C). The columns nS and nC are the cumulative counts of the number
of rows with sport Soccer and Cricket, respectively. For instance, in the row
for Germany, we see nS = 4, since four of the ﬁve rows from Argentina down
to Germany have sport Soccer. In that row, we also have nC = 1, since only
one of the ﬁrst ﬁve rows has sport Cricket.
The next two columns, labeled pS≤and pC≤are the fractions of the rows
down to and including the row in question, that have sport Soccer and Cricket,
respeectively. For example, in the row for Germany, four of the ﬁve rows from
Argentina to Germany have sport Soccer, so pS≤= 4/5. The two columns
after that, labeled pS> and pC>, are the same fractions, but for the rows
that are below the row in question. For example, in the row for Spain we see
pS> = 3/4, since three of the four rows from Italy down to Brazil have sport
Soccer, and one of these rows has sport Cricket. Note that we do not have
to do a cumulative count working up the rows. We can get the count 3 by
subtracting nS = 2 for Spain from the bottom value of nS (that for Brazil),
which is 5. Similarly we know there is one row below Spain with sport Cricket
because 1 is the diﬀerence between nC for Brazil and Spain.
Next, we see the columns for impurities, Im≤and Im>. These are the GINI
impurities of the left and right children of the node we are designing, assuming
that we use a comparison “population < c,” for some c that lies between the
