Page 322 - Introduction to Statistical Pattern Recognition

304 Introduction to Statistical Pattern Recognition

I

\

Fig. 7-1 Selection of neighbors.

(7.7)

Obviously, d I (X!&N,Xl')) 2 d, (X#k,Xl')), making the left-hand side of (7.7)
larger than the left-hand side of (7.6). Thus, Xi') is more likely to be
misclassified in the L method than in R method.
Also, note that, in order to find the NN sample, the distances to all sam-
ples must be computed and compared. Therefore, when d,(X$h,Xi!)) is
obtained, d,(XgN,X&')) must also be available. This means that the computa-
tion time needed to get both the L and R results is practically the same as the
time needed for the R method alone.

Voting RNN Procedure

The kNN approach mentioned above can be modified as follows. Instead
of selecting the kth NN from each class separately and comparing the distances,
the kNN's of a test sample are selected from the mixture of classes, and the