500
CHAPTER 12. LARGE-SCALE MACHINE LEARNING
neighbors are weighted, and if so, how the weight varies with distance.
Suppose we use a method with k nearest neighbors, and x is the query point.
Let x1, x2, . . . , xk be the k nearest neighbors of x, and let the weight associated
with training point (xi, yi) be wi. Then the estimate of the label y for x is
Pk
i=1 wiyi/ Pk
i=1 wi. Note that this expression gives the weighted average of
the labels of the k nearest neighbors.
Example 12.12 : We shall illustrate four simple rules, using the training set
(1, 1), (2, 2), (3, 4), (4, 8), (5, 4), (6, 2), and (7, 1). These points represent a
function that has a peak at x = 4 and decays exponentially on both sides.
Note that this training set has values of x that are evenly spaced. There is no
requirement that the points be evenly spaced or have any other regular pattern.
Some possible ways to interpolate values are:
1
2
3
4
5
6
7
1
2
3
4
5
6
7
(a) One nearest neighbor
(b) Average of two nearest neighbors
Figure 12.22: Results of applying the ﬁrst two rules in Example 12.12
1. Nearest Neighbor. Use only the one nearest neighbor. There is no need
for a weighting. Just take the value of any f(x) to be the label y associ-
ated with the training-set point nearest to query point x. The result of
using this rule on the example training set described above is shown in
Fig. 12.22(a).
2. Average of the Two Nearest Neighbors. Choose 2 as the number of nearest
neighbors to use. The weights of these two are each 1/2, regardless of how
far they are from the query point x. The result of this rule on the example
training set is in Fig. 12.22(b).
3. Weighted Average of the Two Nearest Neighbors. We again choose two
nearest neighbors, but we weight them in inverse proportion to their dis-
tance from the query point. Suppose the two neighbors nearest to query
