Page 323 - Introduction to Statistical Pattern Recognition

7 Nonparametric Classification and Error Estimation 305

number of neighbors from each class among the k selected samples is counted.
The test sample is then classified to the class represented by a majority of the
kNN’s. That is,

kj=max{kl, ..., kL) + XEO, (7.8)

kI+. . .+k, = k ,
where kj is the number of neighbors from (i = 1,. . . ,L) among the kNN’s.
In order to avoid confusion between these two rwVN procedures, we will call
(7.8) the voting kNN procedure and (7.5) the volumetric kNN procedure.
For the voting kNN procedure, it is common practice to use the same
metric to measure the distances to samples from all classes, although each class
could use its own metric. Since the kj’s are integers and a ranking procedure is
used, it is hard to find a component of (7.8) analogous with the threshold of
(7.5).
It can be shown that the volumetric kiVN and voting (2k-1)NN pro-
cedures give identical classification results for the two-class problem using the
same metric for both classes. For example, let k and (2k-1) be 3 and 5 respec-
tively. In the voting 5NN procedure, a test sample is classified to ol, if 3, 4,
or S of the SNN’s belong to o,. This is equivalent to saying that the 3rd NN
from o1 is closer to the test sample than the 3rd NN from 02.

7.2 Voting kNN Procedure-Asymptotic Analysis

In this section, let us study the expected performance of the voting kNN
procedure. first for the asymptotic case (Nj = m) and later for the finite sample
case.

Twa-Class kNN

NN: We start our discussion with the simplest case, setting k = 1 and
L = 2 in (7.8). That is, in order to classify a test sample, X, the NN sample
XNN is found. Then, X is classified to either o1 or 02, depending on the class
membership of XNN. An error occurs when X E o1 but XNN E 02, or when
X E o2 but XNN E ol. Therefore, the conditional risk given X and XNN is
expressed by