Database Reference
In-Depth Information
(4) How do we define 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 per-
haps not. If there is no weighting, then the kernel function need not be specified.
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 la-
beling function: take the label of the query to be the same as the label of the nearest neigh-
bor.
EXAMPLE
12.11
Figure 12.21
shows some of the examples of dogs that last appeared in
huas, two Dachshunds, and two Beagles. Since the height-weight vectors describing the
dogs are two-dimensional, there is a simple and efficient way to construct a
Voronoi dia-
gram
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 infinity
in one direction.
3
It is also a surprising fact that, even though there are
O
(
n
2
) perpendicular
bisectors for
n
points, the Voronoi diagram can be found in
O
(
n
log
n
) time.
Figure 12.21
Voronoi diagram for the three breeds of dogs
In
Fig. 12.21
we see the Voronoi diagram for the seven points. The boundaries that sep-
arate dogs of different breeds are shown solid, while the boundaries 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 find 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 find
the region of
q
. We have to determine to which side of certain lines
q
falls. This process
