Chapter 7 NONPARAMETRIC CLASSIFICATION AND ERROR ESTIMATION After studying the nonparametric density estimates in Chapter 6, we are now ready to discuss the problem of how to design nonparumetric clussifiers and estimate their classification errors. A nonparametric classifier does not rely on any assumption concerning the structure of the underlying density function. Therefore, the classifier becomes the Bayes classifier if the density estimates converge to the true den- sities when an infinite number of samples are used. The resulting error is the Bayes error, the smallest achievable error given the underlying distributions. As was pointed out in Chapter 1, the Bayes error is a very important parameter in pattern recognition, assessing the classifiability of the data and measuring the discrimination capabilities of the features even before considering what type of classifier should be designed. The selection of features always results in a loss of classifiability. The amount of this loss may be measured by com- paring the Bayes error in the feature space with the Bayes error in the original data space. The same is true for a classifier. The performance of the classifier may be compared with the Bayes error in the original data space. However, in practice, we never have an infinite number of samples, and, due to the finite sample size, the density estimates and, subsequently, the estimate of the Bayes error have large biases and variances, particularly in a high-dimensional space. 3007 Nonparametric Classification and Error Estimation 301 A similar trend was observed in the parametric cases of Chapter 5, but the trend is more severe with a nonparametric approach. These problems are addressed extensively in this chapter. Both Parzen and kNN approaches will be discussed. These two approaches offer similar algorithms for classification and error estimation, and give similar results. Also, the voting kNN procedure is included in this chapter, because the procedure is very popular, although this approach is slightly different from the kNN density estimation approach. 7.1 General Discussion Parzen Approach Classifier: As we discussed in Chapter 3, the likelihood ratio classfier is given by -InpI(X)/p2(X) ><r, where the threshold t is determined in various ways depending on the type of classifier to be designed (e.g. Bayes, Neyman- Pearson, minimax, etc.). In this chapter, the true density functions are replaced by their estimates discussed in Chapter 6. When the Parzen density estimate with a kernel function IC,(.) is used, the likelihood ratio classifier becomes where S = {X\’), . . . ,X$!,X\2), . . . ,X$! } is the given data set. Equation (7.1) classifies a test sample X into either o1 or 02, depending on whether the left- hand side is smaller or larger than a threshold t. Error estimation: In order to estimate the error of this classifier from the given data set, S, we may use the resubstitution (R) and leave-one-out (L) methods to obtain the lower and upper bounds for the Bayes error. In the R method, all available samples are used to design the classifier, and the same sample set is tested. Therefore, when a sample Xi” from o1 is tested, the fol- lowing equation is used.302 Introduction to Statistical Pattern Recognition If < is satisfied, Xi!) is correctly classified, and if > is satisfied, Xi” is misclassified. The R estimate of the q-error, cIR, is obtained by testing Xi’), . . . ,Xyl, counting the number of misclassified samples, and dividing the number by NI. Similarly, &2R is estimated by testing xi2), . . . ,x$!. On the other hand, when the L method is applied to test Xi1), Xi’) must be excluded from the design set. Therefore, the numerator of (7.2) must be replaced by Again, Xi!) (k=l, . . . ,N I) are tested and the misclassified samples are counted. Note that the amount subtracted in (7.3), K~ (0), does not depend on k. When an 02-sample is tested, the denominator of (7.2) is modified in the same way. Typical kernel functions, such as (6.3), generally satisfy ~~(0) 2 K;(Y) (and subsequently ~~(0) 2 pj(Y)). Then, That is, the L density estimate is always smaller than the R density estimate. Therefore, the left-hand side of (7.2) is larger in the L method than in the R method, and consequently Xi’) has more of a chance to be misclassified. Also, note that the L density estimate can be obtained from the R density estimate by simple scalar operations - subtracting K~ (0) and dividing by (N -1). There- fore, the computation time needed to obtain both the L and R density estimates is almost the same as that needed for the R density estimate alone.7 Nonparametric Classification and Error Estimation 303 HN Approach Classifier: Using the kNN density estimate of Chapter 6, the likelihood ratio classifier becomes dz(xk:)N~.x) (kl-l)N2 lX2 I 112 0, =-n In -In ><r, (7.5) dI(Xil,)NN,X) (k2-1)NI IC, wz where 11, =n”12r1(n/2+1)IC, l”2d:’ from (B.l), and df(Y,X) = (Y-X)TC;l(Y-X). In order to classify a test sample X, the klth NN from oI and the k2th NN from o2 are found, the distances from X to these neighbors are measured, and these distances are inserted into (7.5) to test whether the left-hand side is smaller or larger than t. In order to avoid unnecessary com- plexity, k, = k2 is assumed in this chapter. Error estimation: The classification error based on a given data set S can be estimated by using the L and R methods. When Xi1) from o1 is tested by the R method, Xi1) must be included as a member of the design set. There- fore, when the kNN’s of Xi’) are found from the wI design set, Xi’’ itself is included among these kNN’s. Figure 7-1 shows how the kNN’s are selected and how the distances to the kth NN’s are measured for k = 2. Note in Fig. 7-1 that the locus of points equidistant from Xi!) becomes ellipsoidal because the distance is normalized by E,. Also, since Cl # C2 in general, two different ellipsoids are used for o, and 02. In the R method, Xi1) and Xi,(, are the nearest and second nearest neighbors of Xi1) from o1 , while X,$, and X$& are the nearest and second nearest neighbors of Xi1) from 02. Thus, On the other hand, in the L method, Xi” is no longer considered a member of the design set. Therefore, X$h and XgN are
View Full Document
Unlocking...