12.5. DECISION TREES
515
Find a node N that has only leaves as children. Build a new tree by replacing
N and its children by a leaf, and give that leaf its majority class as its output.
Then, compare the performance of the old and new trees on data that was not
used as training examples when we designed the tree. If there is little diﬀerence
between the error rates of the old and new trees, then the decision made at the
node N probably contributed to overﬁtting and was not addressing a property
of the entire set of examples for which the decision tree was intended.
We
can discard the old tree and replace it by the new, simpler tree. On the other
hand, if the new tree has a signiﬁcantly higher error rate than the old, then the
decision made at node N really reﬂects a property of the data, and we need
to retain the old tree and discard the new. In either case, we should continue
looking at other nodes whose children are leaves, and see if these can be replaced
by leaves without a signiﬁcant increase in the error rate.
Example 12.19 : Let us consider the node in Fig. 12.26 with the test “Conti-
nent = NA.” It has two leaves as children and so it can play the role of node
N above. In the training data of Fig. 12.25 N is reached by three training
examples, Cuba, the US, and Australia. As two of these three go to the leaf
labeled “Baseball,” we shall consider replacing N by a leaf labeled “Baseball.”
Consider what happens if the old and new trees are applied to the entire
set of countries of the world.
First, note that to reach node N, a country
has to be in one of the continents North America, Asia, Australia, or Africa.
Moreover, it has to be either a small country (less than 35 million population)
or a populous country (more than 200 million). There are many such countries,
such as small countries in Africa, or large countries like China or Indonesia, none
of which have either cricket or baseball as their favorite sport. If we consider
the Carribean and Central-American countries as belonging to North America,
then N is reached by many more countries, only a few of which have baseball
as their favorite sport.
The conclusion is that whether or not N is replaced by a “Baseball” leaf,
the tree will have a signiﬁcant error rate on these countries, and therefore the
error rate of the two trees applied to all countries will be about the same. We
conclude that this node N reﬂects only artifacts of the small and atypical set
of twelve training examples that we chose. Thus, N can safely be replaced by
a leaf without much increase in the error rate on the full set of countries.
✷
12.5.8
Decision Forests
Because a single decision tree with many levels is likely to have many nodes at
the lower levels that represent overﬁtting, there is another approach to the use
of decision trees that has proven quite useful in practice. It is common to use
decision forests of many trees that vote on the class to which a given data point
belongs. Each tree in the forest is designed using randomly or systematically
chosen features, and is restricted to only a small number of levels, often one or
two. Thus, each tree has a high impurity at each of its leaves, but collectively
