Page 367 - Introduction to Statistical Pattern Recognition

7 Nonparametric Classification and Error Estimation 349

One comment is in order regarding the application of Option 4 to kNN
estimation. In Step 2 of Option 4 of the Parzen case, it is fairly simple to
remove the effect of Xf) (the test sample) from the density estimates of all the
other samples using (7.58). There is no analogous simple modification in the
kNN case. In order to remove the effect of Xf) from all other density esti-
mates, one must remove Xf’ from the table of nearest neighbors, rearrange the
NN table, and recalculate all of the density estimates. This procedure would
have to be repeated to test each of the samples in the design set, resulting in a
fairly drastic increase in computation time. In practice, modifying each of the
density estimates to remove the effect of Xf) is not nearly as important as
finding the threshold by minimizing the error among the remaining N, + Nz-1
samples. That is, modifying the estimates of the likelihood ratios in Step 2 is
not necessary to get reliable results - we do it in the Parzen case primarily
because it is easy. Thus for kNN estimation, Step 2 of Option 4 involves
finding and sorting L(X:)) for all samples Xy) # Xf), finding the value of t
which minimizes the error among these Nl+N2-1 samples, and using this
value oft to classify xj,?.
Figure 7-14 shows the results of applying Option 4 to the kNN estima-
tion problem. For comparison, the results obtained using t = 0 are also shown.

Experiment 14: Estimation of the kNN error, L and R
Same as Experiment 4, except
Metric: A I = C I and A = C2 (Instead of kernel)
No. of neighbors: k = 1-30 (Instead of kernel size)
Threshold: Option 4 and t = 0
Results: Fig. 7-14 [12]

As in the Parzen case, the threshold plays its most significant role when the
covariances of the data are different, and particularly when the covariance
determinants are different. In Data I-I, the bias of the density estimates for o,
and w2 are nearly equal near the Bayes decision boundary, and hence good
results are obtained without adjusting the threshold. However, for Data I-41
and I-A, the kNN errors are heavily biased and unusable without adjusting the
threshold.