12.4. LEARNING FROM NEAREST NEIGHBORS
501
point x are x1 and x2. Suppose ﬁrst that x1 < x < x2. Then the weight
of x1, the inverse of its distance from x, is 1/(x −x1), and the weight of
x2 is 1/(x2 −x). The weighted average of the labels is
y1
x −x1
+
y2
x2 −x

/
1
x −x1
+
1
x2 −x

which, when we multiply numerator and denominator by (x−x1)(x2 −x),
simpliﬁes to
y1(x2 −x) + y2(x −x1)
x2 −x1
This expression is the linear interpolation of the two nearest neighbors, as
shown in Fig. 12.23(a). When both nearest neighbors are on the same side
of the query x, the same weights make sense, and the resulting estimate is
an extrapolation. We see extrapolation in Fig. 12.23(a) in the range x = 0
to x = 1. In general, when points are unevenly spaced, we can ﬁnd query
points in the interior where both neighbors are on one side.
4. Average of Three Nearest Neighbors. We can average any number of the
nearest neighbors to estimate the label of a query point. Figure 12.23(b)
shows what happens on our example training set when the three nearest
neighbors are used, with no weighting. Weighting the three neighbors,
such as in inverse proportion to their distances to the point in question,
is another option.
✷
1
2
3
4
5
6
7
1
2
3
4
5
6
7
(a) Weighted average of two neighbors
(b) Average of three neighbors
Figure 12.23: Results of applying the last two rules in Example 12.12
