12.5. DECISION TREES
507
Continent =
60 < Pop < 70
35 < Pop < 200
Continent =
NA
Cricket
Soccer
Hockey
Cricket
Baseball
Y
Y
Y
Y
N
N
N
N
SA or Eur
Figure 12.26: A decision tree for the favorite sports of countries
asks us to test whether the population of Spain is between 60 and 70 million.
It is not, so we go to the right child, which is a leaf telling us correctly that the
favorite sport of Spain is Soccer.
However, there are many countries not in the table of Fig. 12.25, and the
decision tree does not do too well on these. For example, consider Pakistan, a
country in Asia with a population of 182 million. Starting at the root, we ﬁnd
the condition there not satisﬁed, since Pakistan is not a European or South-
American country. Thus, we go to the right child of the root. Since the pop-
ulation of Pakistan is in the range between 35 and 200 million, we move left,
whereupon we are told that the favorite sport in Pakistan is Hockey.
The problem we face is overﬁtting. That is, the test at the root makes sense;
Soccer is most popular in South America and Europe. But tests on population
are probably useless, since it is unlikely that the size of a country has anything
to do with what sport its people like. We have, in this example, simply used
the population to distinguish among the small number of countries in Fig. 12.25
that reach a node of the tree. But unlike the root, the tests at the second level
don’t really say anything that applies to the larger, unseen set of countries.
✷
12.5.2
Impurity Measures
To design a decision tree, we need to choose good tests at the various nonleaf
nodes of the tree. We would like to use as few levels as possible, so that new
data points can be classiﬁed quickly, and we have a chance of avoiding the
overﬁtting that we saw in Example 12.14. Ideally, we would like all the inputs
that reach a certain node to have the same class, since then we can make that
node a leaf and correctly classify all the training examples that reach the node.
We can formalize the property we would like for a node by the notion of
impurity. There are many impurity measures we could use, but they all have
