498
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
12.4.1
The Framework for Nearest-Neighbor Calculations
The training set is ﬁrst preprocessed and stored. The decisions take place when
a new example, called the query example arrives and must be classiﬁed.
There are several decisions we must make in order to design a nearest-
neighbor-based algorithm that will classify query examples.
We enumerate
them here.
1. What distance measure do we use?
2. How many of the nearest neighbors do we look at?
3. How do we weight the nearest neighbors? Normally, we provide a function
(the kernel function) of the distance between the query example and its
nearest neighbors in the training set, and use this function to weight the
neighbors. If there is no weighting, then the kernel function need not be
speciﬁed.
4. How do we deﬁne the label to associate with the query? This label is
some function of the labels of the nearest neighbors, perhaps weighted by
the kernel function, or perhaps not.
12.4.2
Learning with One Nearest Neighbor
The simplest cases of nearest-neighbor learning are when we choose only the
one neighbor that is nearest the query example. In that case, there is no use
for weighting the neighbors, so the kernel function is omitted. There is also
typically only one possible choice for the labeling function: take the label of the
query to be the same as the label of the nearest neighbor.
Example 12.11 : Figure 12.21 shows some of the examples of dogs that last
appeared in Fig. 12.1. We have dropped most of the examples for simplicity,
leaving only three Chihuahuas, two Dachshunds, and two Beagles. Since the
height-weight vectors describing the dogs are two-dimensional, there is a simple
and eﬃcient way to construct a Voronoi diagram for the points, in which the
perpendicular bisectors of the lines between each pair of points is constructed.
Each point gets a region around it, containing all the points to which it is
the nearest. These regions are always convex, although they may be open to
inﬁnity in one direction.2 It is also a surprising fact that, even though there are
O(n2) perpendicular bisectors for n points, the Voronoi diagram can be found
in O(n log n) time.
In Fig. 12.21 we see the Voronoi diagram for the seven points. The bound-
aries that separate dogs of diﬀerent breeds are shown solid, while the boundaries
2While the region belonging to any one point is convex, the union of the regions for two or
more points might not be convex. Thus, in Fig. 12.21 we see that the region for all Dachshunds
and the region for all Beagles are not convex. That is, there are points p1 and p2 that are
both classiﬁed Dachshunds, but the midpoint of the line between p1 and p2 is classiﬁed as a
Beagle, and vice versa.
