12.5. DECISION TREES
505
! (b) Would the boundaries always consist of straight line segments for any
training data?
Exercise 12.4.2: Suppose we have the following training set
([1, 2], +1)
([2, 1], −1)
([3, 4], −1)
([4, 3], +1)
which is the training set used in Example 12.9.
If we use nearest-neighbor
learning with the single nearest neighbor as the estimate of the label of a query
point, which query points are labeled +1?
Exercise 12.4.3: Consider the one-dimensional training set
(1, 1), (2, 2), (4, 3), (8, 4), (16, 5), (32, 6)
Describe the function f(q), the label that is returned in response to the query
q, when the interpolation used is:
(a) The label of the nearest neighbor.
(b) The average of the labels of the two nearest neighbors.
! (c) The average, weighted by distance, of the two nearest neighbors.
(d) The (unweighted) average of the three nearest neighbors.
! Exercise 12.4.4: Apply the kernel function of Example 12.13 to the data of
Exercise 12.4.3. For queries q in the range 2 < q < 4, what is the label of q?
Exercise 12.4.5: What is the function that estimates the label of query points
using the data of Example 12.12 and the average of the four nearest neighbors?
!! Exercise 12.4.6: Simple weighting functions such as those in Example 12.12
need not deﬁne a continuous function. We can see that the constructed functions
in Fig. 12.22 and Fig. 12.23(b) are not continuous, but Fig. 12.23(a) is. Does the
weighted average of two nearest neighbors always give a continuous function?
12.5
Decision Trees
A decision tree is a branching program that uses properties of a feature vector to
produce the class to which that input belongs. We generally show the decisions
made in the form of a tree. In this section, we shall discuss how to design
trees that correctly classify training data. In a decision tree, each nonleaf node
represents a test on the input. Its children are either tests (which we denote by
ellipses) or a leaf that is a conclusion about the output (denoted by a rectangle).
The children of a test node are labeled by the outcome of the test. Typically,
