19.2 Analysis 259
Figure 19.1An illustration of the decision boundaries of the 1-NN rule. The points
depicted are the sample points, and the predicted label of any new point will be the
label of the sample point in the center of the cell it belongs to. These cells are called a
Voronoi Tessellation of the space.
k-NN
input:a training sampleS= (x 1 ,y 1 ),...,(xm,ym)
output:for every pointx∈X,
return the majority label among{yπi(x):i≤k}
Whenk= 1, we have the 1-NN rule:
hS(x) = yπ 1 (x).
A geometric illustration of the 1-NN rule is given in Figure 19.1.
For regression problems, namely,Y=R, one can define the prediction to be
the average target of theknearest neighbors. That is,hS(x) =^1 k
∑k
i=1yπi(x).
More generally, for some functionφ: (X ×Y)k→Y, thek-NN rule with respect
toφis:
hS(x) =φ
(
(xπ 1 (x),yπ 1 (x)),...,(xπk(x),yπk(x))
)
. (19.1)
It is easy to verify that we can cast the prediction by majority of labels (for
classification) or by the averaged target (for regression) as in Equation (19.1) by
an appropriate choice ofφ. The generality can lead to other rules; for example, if
Y=R, we can take a weighted average of the targets according to the distance
fromx:
hS(x) =
∑k
i=1
ρ(x,xπi(x))
∑k
j=1ρ(x,xπj(x))
yπi(x).
19.2 Analysis
Since the NN rules are such natural learning methods, their generalization prop-
erties have been extensively studied. Most previous results are asymptotic con-
sistency results, analyzing the performance of NN rules when the sample size,m,
