506
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
there are only two outcomes – true or false (yes or no) – but there could be any
number of outcomes of a test.
Also in this section, we examine ways to exploit parallelism while looking
for the most eﬃcient tree. As overﬁtting is a common problem, we shall also
talk about how to simplify the tree by removing nodes, to reduce overﬁtting
without losing too much accuracy.
12.5.1
Using a Decision Tree
Let us begin with an example of some training data and a tree that might
be constructed from this data. The table in Fig. 12.25 gives 12 countries, their
population (in millions), their continent, and their favorite sport. We shall treat
Population and Continent as features of the input vector and the favorite sport
as the class, or output. We assume the countries themselves are not known, and
we want to predict the favorite sport just from the continent and population.
In particular, we want to predict the favorite sport of countries other than these
12, from their continent and population only.
Country
Continent
Population
Sport
Argentina
SA
44
Soccer
Australia
Aus
34
Cricket
Brazil
SA
211
Soccer
Canada
NA
36
Hockey
Cuba
NA
11
Baseball
Germany
Eur
80
Soccer
India
Asia
1342
Cricket
Italy
Eur
59
Soccer
Russia
Asia
143
Hockey
Spain
Eur
46
Soccer
United Kingdom
Eur
65
Cricket
United States
NA
326
Baseball
Figure 12.25: Favorite sports of countries
Example 12.14 : In Fig. 12.26 is a tree that correctly classiﬁes the twelve
countries of Fig. 12.25. To classify a country, given its population and continent,
we start at the root and apply the test at the root. We go to the left child if
the outcome of the test is true and to the right child if not. Whenever we are
at a nonleaf node, we apply the test at that node and again move to the left or
right child, depending on whether or not the test is satisﬁed. When we reach a
leaf, we output the class at that leaf.
You can check that each of the twelve countries is correctly classiﬁed by this
tree. For example, consider Spain. The continent of Spain is Europe, so the
test at the root is satisﬁed. Thus, we go the the left child of the root, which
