12.4. LEARNING FROM NEAREST NEIGHBORS
499
Beagles
Dachshunds
Chihuahuas
Figure 12.21: Voronoi diagram for the three breeds of dogs
between dogs of the same breed are shown dashed. Suppose a query example
q is provided. Note that q is a point in the space of Fig. 12.21. We ﬁnd the
region into which q falls, and give q the label of the training example to which
that region belongs. Note that it is not too hard to ﬁnd the region of q. We
have to determine to which side of certain lines q falls. This process is the same
as we used in Sections 12.2 and 12.3 to compare a vector x with a hyperplane
perpendicular to a vector w. In fact, if the lines that actually form parts of the
Voronoi diagram are preprocessed properly, we can make the determination in
O(log n) comparisons; it is not necessary to compare q with all of the O(n log n)
lines that form part of the diagram.
✷
12.4.3
Learning One-Dimensional Functions
Another simple and useful case of nearest-neighbor learning has one-dimensional
data. In this situation, the training examples are of the form ([x], y), and we
shall write them as (x, y), identifying a one-dimensional vector with its lone
component. In eﬀect, the training set is a collection of samples of the value
of a function y = f(x) for certain values of x, and we must interpolate the
function f at all points. There are many rules that could be used, and we shall
only outline some of the popular approaches. As discussed in Section 12.4.1,
the approaches vary in the number of neighbors they use, whether or not the
