An Average-Case Analysis of the k-Nearest Neighbar Classifier for Noisy Domains

1 Introduction

The k-nearest neighbor classifier (k-NN) is one of the most widely applied learning algorithms. Although k­ NN is a powerful algorithm and has been studied by many researchers, it is not clear how noise affects the classification accuracy of k-NN. Moreover, it is also un­ clear which value should be chosen for k to maximize accuracy in noisy domains. These are crucial problems in k-NN applications, because there are few noise-free problems in practical domains.

Variants of k-NN have been proposed to tolerate noise (e.g., [Aha and Kibler, 1989]), and to choose an appropri­ ate value of k (e.g., [Creecy et al., 1992]). These propos­ als exhibit the high performance of k-NN by empirical evaluations. However, the noise effects on the accuracy of k-NN and on the optimal value of k still remain un­ clear. It is therefore important to understand the noise effects on k-NN and the optimal k by theoretical evalu­ ations.

There have been several theoretical analyses of k-NN. The upper bound of k-NN error rate (risk) is twice the optimal Bayes risk under the assumption of an infinite number of training instances [Cover and Hart, 1967).

Yugami Nobuhiro

Fujitsu Laboratories Ltd. 2-2-1 Momochihama, Sawara-ku Fukuoka 814, Japan yugami@fiab.fujitsu.co.jp

Moreover, k-NN risk converges to the optimal Bayes risk as k approaches infinity [Cover, 1968). For a finite set of training instances, the new bounds of 1-NN risk are ~iven using Bayes risk [Drakopoulos, 1995). Aha et al. [1991) analyze 1-NN with a similar model to PAC (Prob­ ably Approximately Correct) learning, and this analysis is generalized to k-NN [Albert and Aha, 1991). Although these theoretical results are important and give some in­ sights into the behavior of k-NN, all of these studies as­ sume noise-free instances.

An average-case an·alysis is· a useful theoretical frame­ work to understand the behavior of learning algorithm [Pazzani and Sarrett, 1992) . This framework is base on the formal computation of the expected accuracy o a learning algorithm for a certain fixed class of con­ cepts. Using the result of this computation, we can ex­ plore the predicted behavior of an algorithm. There hav been some average-case analyses of k-NN. Langley an Iba [1993) analyzed 1-NN for conjunctive concepts, and we analyzed k-NN for m-of-n concepts without irrele vant attribute [Okamoto and Satoh, 1995). However, these studies assumed noise-free instances. Recently, we presented an average-case analysis of 1-NN for m­ of-n concepts with irrelevant attribute in noisy domain [Okamoto and Yugami, 1996). This paper generalize our recent study for 1-NN to k-NN.

In this paper, we present an average-case analysis of k­ nearest neighbor classifier for noisy domains. Our analy­ sis handles m-of-n concepts with l irrelevant attributes and deals with three types of noise: relevant attribut noise, irrelevant attribute noise, and class noise. First we formally compute the expected classification accu­ racy (i.e., predictive accuracy) of k-NN after N train­ ing instances are given. This accuracy is represented as a function of the domain characteristics: k, N , m, n, l , the probabilities of occurrence for relevant and irrel­ evant attributes, and noise rates. Using the accuracy function, we explore the predicted behavior of k-NN in noisy domains. We describe the predictive accuracy o k-NN at various noise levels, and show the effects of noise on the accuracy of k-NN. We also show the relationship between the optimal value of k and the number of train­ ing instances in noisy domains. Our theoretical analysis is supported with Monte Carlo simulations.

2 Problem Description

Our analysis deals with m-of-n/l concepts defined over the threshold m, n relevant and l irrelevant Boolean at­ tributes [Murphy and Pazzani, 1991] . These concepts classify an instance as positive if and only if at least m out ofn relevant attributes occur (i .e., take the value 1) in its instance.

Our analysis handles three types of noise. Each type of noise is independently introduced by the following com­ mon definition. Relevant (irrelevant, resp.) attribute noise flips an arbitrary relevant (irrelevant, resp.) at­ tribute value in each instance with a certain probability Ur ( u;, resp.). Class noise replaces the class label for each instance with its negation with a certain probability Uc ·

We investigate a k-nearest neighbor classifier using hamming distance (i.e., the number of attributes on which two instances differ) as a distance measure. For the distribution over the instance space, our analysis as­ sumes every relevant and irrelevant attribute indepen­ dently occurs with a certain probability p and q. Each training instance is independently drawn from the in­ stance space. After the effects of each type of noise, all training instances are stored into memory to allow for duplication. When a test instance is given, k-NN classifies the test instance into a majority class (posi­ tive or negative) among its k nearest training instances. H the number of positive instances equals that of nega­ tive instances among its k nearest neighbors, then k-NN randomly determines the class of the test instance (this situation can occur only when k is an even number) .

3 Predictive Accuracy

We formally compute the predictive accuracy of k-NN for m-of-n/l target concepts after N training instances are given. The predictive accuracy is represented as a function of the domain characteristics: k, N, m, n, l, p, q, u., u;, and Uc· However, to avoid complicated nota­ tion, we will not explicitly express these characteristics as parameters of the accuracy function with the excep­ tion of k.

We compute the predictive accuracy in the case where each type of noise affects only training instances. Af­ ter this computation, we also give the accuracy function in the case where noise affects both test and training instances.

To compute the predictive accuracy, we use a set of instances in which x relevant attributes and y irrelevant attributes simultaneously occur (we denote this set with I(x,y)). Let Pocc(x,y) be the probability that an arbi­ trary noise-free instance belongs to I ( x, y). This proba­ bility is given by

Under our assumptions given in Section 2, k-NN has the same expected probability of correct classification for an arbitrary test instance in I(x,y). Hence, we can repre­ sent the predictive accuracy of k-NN after N training

where Ppos(k,x,y) represents the probability that k-NN classifies an arbitrary test instance in I(x, y) as positive.

Let t(x,y) be an arbitrary test instance in I(x,y) . To represent Ppos(x, y), we compute the appearance probability for an arbitrary training instance with dis­ tance e(O ~ e ~ n + l) from t(x,y). Let Pctp(x,y,e) (Pctn(x, y, e), resp.) be this probability for an arbitrary training instance with the positive (negative, resp.) class label. Pctp(x, y, e) and Pctn(x, y, e) were computed using Eq.(14) and Eq.(15) in our previous paper [Okamoto and Yugami, 1996]. Hence, we simply state the computation of these probabilities here.

Pctp(x, y, e) and Pctn (x, y, e) are given by

In these equations, Pp(X, Y) (Pn(X, Y), resp.) rep­ resents the probability that an arbitrary training in­ stance belongs to I(X, Y) and has the positive (nega­ tive, resp.) class label. Moreover, Pct;.(x, y, X, Y, e) de­ notes the probability that an arbitrary training instance in I(X, Y) has distance e from t(x, y).

First, we represent Pp(X, Y) and Pn(X, Y) by consid­ ering the effects of each type of noise on the training instances. These probabilities are represented as

where Pp 0 (X, Y) (Pn 0 (X, Y) , resp.) denotes the ap­ pearance probability for an arbitrary positive (negative, resp.) training instance in I(X, Y), before the effect of class noise. Pp 0 (X, Y) and Pn 0 (X, Y) are given by

where Pnr(X0 , X) (Pn;(Yo, Y), resp.) represents the probability that the number of relevant (irrelevant, resp.) attributes occurring in an arbitrary training instance is changed from X0 (Y0 , resp.) to X (Y, resp.) by the ef­ fect of relevant (irrelevant, resp.) attribute noise. These probabilities are represented as

Next, we represent Pdis(x, y, X, Y, e) . Let Zr (zi, resp.) be the number of relevant (irrelevant, resp.) attributes which occur in both t(x, y) and an arbitrary training instance in /(X, Y). Then, Pdis(x, y, X, Y, e) is given by

where S is a set of a pair of Zr and Zi, that satisfies all conditions of

We have represented Pdp(x,y,e) and Pdn(x,y,e) . Us­ ing these probabilities, we compute Ppos(k,x,y) in the accuracy function. For this computation, we consider the distance from t( x, y) to the k-th nearest neighbor. We denote this distance with d(O ~ d ~ n + l). When the k-th nearest neighbor has distance d from t( x, y), then exactly a(O ~ a ~ k - 1) out of N training in­ stances have the distance less than d from t(x, y), and exactly b training instances have distance d. Here, we have (k - a) ~ b ~ (N - a) from k ~ (a + b) ~ N. We use Pnum(x,y,d,a,b) to denote the probability that this situation occurs. We also use Psp(k, x, y, d, a, b) to designate the probability that k-NN classifies t(x,y) as positive in this situation. Combining Pnum(x,y,d,a,b) and P.p(k, x, y, d, a, b), Ppos(k, x, y) can be computed as

d=Oa=Ob=k-a We can represent Pnum(x,y,d,a,b) as Pnum(x,y,d,a,b) = (:) (N ;a)R(x,y,d)a

where R(x,y,d) and Pd(x,y,d) denotes the probability that an arbitrary training instance has the distance less than and equal to d from t(x, y), respectively. R(x, y, d) and Pd(x,y,d) are given by

Finally, we compute P.P ( k, x, y, d, a, b) by considering the following situations. When exactly a training in­ stances have the distance less than d from t( x, y), we let exactly u out of these a instances have the positive class label. We use ~Pu (a, u) to denote the probability that this situation occurs. To get k nearest neighbors for t(x,y), k-NN selects exactly (k- a) out of b train­ ing instances with distance d from t(x, y). We let w out of these (k- a) instances have the positive class la­ bel. Under these situations, if we have u + w > k/2, then k-NN always classifies t(x, y) as positive, and if u + w < k/2, then always classifies t(x,y) as negative. Moreover, if u+w = k/2, then t(x, y) is classified as posi­ tive with the probability of 1/2. Hence, we can represent P.p(k, x, y, d, a, b) as

In this equation, Pd~ (b, v) denotes the probability that exactly v out of b training instances with distance d from t(x, y) have the positive class label. Moreover, Pd; ( k, a, b, v, w) denotes the probability that exactly w out of (k -a) training instances, selected by k-NN from b instances with distanced from t(x,y), have the positive class label. Note that Pd; ( k, a, b, v, ~ - x) becomes zero, when k is an odd number.

We can represent ~Pu(a, u) as

where P1p(x, y, d) (Rn(x, y, d), resp.) is the probability that an arbitrary instance has the distance less than d from t(x, y) and has the positive (negative, resp.) class label. Rp(x, y, d) and Rn(x, y, d) are give by

In a similar manner, we can represent Pd~ ( b, v) as

When k-NN selects exactly (k -a) out of b training in­ stances with distanced from t(x, y) , these (k- a) train­ ing instances comprise exactly w out of v instances with the positive class label and exactly (k- a- w) out of (b- v) instances with the negative class labeL Hence, Pd;(k , a, b, v , w) is given by

We have computed the predictive accuracy of k-NN in the case where each type of noise affects only the training instances. \Vhen noise affects test instances , the appear­ ance probability for an arbitrary test instance with the positive (negative, resp.) class label in I(x,y) is Pp(x,y) (Pn(x, y), resp.). Hence, when noise affects both test and training instances, the predictive accuracy of k-NN after N training instances can be represented as

4 Predicted Behavior

Using the accuracy function described in Section 3, we explore the predicted behavior of k-NN. Although the accuracy function was obtained for both noise-free and noisy test instances, our exploration deals with only noise-free test instances for lack of space. Moreover, we investigate the effects of each individual noise type on k-NN.

For irrelevant attribute noise, we can formally prove the following claim from the accuracy function (the proof is omitted here due to space limitations).

Claim 1

If the probability of occurrence for irrelevant attribute is

1/2, then the predictive accuracy of k-NN for m-of-n/l concepts is entirely independent of the noise rate for ir­ relevant attributes.

From this claim, we can expect that irrelevant attribute noise does not greatly affect the classification accuracy of k-NN, nor the optimal value of k. Therefore, the follow­ ing discussions focus on the effects of relevant attribute noise and class noise. Throughout our exploration, we set the probabilities of occurrence for both relevant and irrelevant attributes to 1/2.

In addition to the theoretical results from the accuracy function , we give the results of Monte Carlo simulations to confirm our analysis. For each case, 500 training sets are randomly generated in accordance with each noise rate, then the data is collected as the classification ac­ curacy measured over the entire space of noise-free in­ stances. For each case, we report a 95% confidence in­ terval for the mean accuracy of 500 data items. In the following figures, the error bar indicates this confidence interval.

4.1 Accuracy against Value of k

First, we report the predicted behavior of k-NN against the value of k at several levels of noise, as shown in Fig­ ure 1. In this figure, the number of training instances is fixed at 32, and the target is a 3-of-5/2 concept. The lines indicate the theoretical results from the accuracy function, and the error bars represent the empirical re­ sults of Monte Carlo simulations. The theoretical results agree well with the empirical ones for both relevant at­ tribute noise and class noise.

Figure 1 shows that the predictive accuracy of k-NN markedly drops off for each noise level when k is an even number. This negative influence of an even number for k on the accuracy is caused by a random determination of class when a tie occurs . This negative influence suggests that a choice of even number for k is undesirable when applying k-NN.

In Figure 1, each circle represents the predictive ac­ curacy for the optimal value of k at the corresponding noise level. For each odd number for k, the accuracy of k-NN for a 0% noise level has two peaks. One appears at k = 1, while the other appears at the optimal value of k. In contrast, the accuracy for a 10% noise level and a 20% level have one peak at the corresponding optimal k. This is because the peak at k = 1 disappears due to the effect of noise.

4.2 Effects of Noise on the Accuracy

We further investigate the effects of noise on the pre­ dictive accuracy of k-NN, as shown in Figure 2. In this figure, the number of training instances is fixed at 32, and all curves come from the theoretical results. Each curve for k-NN represents the predictive accuracy of k­ NN with the optimal value of k at each noise level.

Figure 2(a) shows the effects of relevant attribute noise on the predictive accuracies of 1-NN and the optimal k­ NN. When the noise level is 0%, the accuracy of 1-NN is comparable to that for the optimal k-NN, for both 1-of5/2 and 3-of-5/2 concepts. However, the predictive accu­ racy of 1-NN almost linearly decreases with an increase in the noise level. For a 50% noise level, the accuracy of 1-NN equals that of a random prediction algorithm which predicts the same class as that for a randomly se­ lected training instance. These observations suggest that 1-NN is strongly sensitive to relevant attribute noise. In contrast, the predictive accuracy of the optimal k-NN exhibits slower degradation. For the disjunctive concept (1-of-5/2 concept), the accuracy of the optimal k-NN is not greatly changed as the noise level increases.

Figure 2(b) shows the effects of class noise on the pre­ dictive accuracies of 1-NN and the optimal k-NN. For the 3-of-5/2 concept, both 1-NN and the optimal k-NN exhibit similar behavior to the corresponding tests with relevant attribute noise. However, the effects of class noise on the accuracy differ entirely from ones of rel­ evant attribute noise for the disjunctive concept. The predictive accuracy of 1-NN linearly decreases to 0.5. In · contrast, the optimal k-NN's accuracy does not substantially change until about a 30% noise level, whereafter it rapidly decreases to 50%.

These observations show that the predictive accuracy of 1-NN is strongly affected by both relevant attribute noise and class noise. Also, they suggest that we can restrain the degradation in the predictive accuracy of k­ NN caused by an increase in noise level by optimizing the value of k.

4.3 Optimal Value of k

Finally, we give the relationship between the optimal value of k and the number of training instances in noisy domains, as shown in Figure 3. In this figure, the optimal value of k comes from the theoretical results, and the target is a 3-of-5/2 concept. In the following discussions, we use N to refer to the number of training instances.

For a 0% noise level, the optimal value of k remains k = 1 until N = 28. There is a rapid increase in the opti­ mal k at N = 32, and then the optimal k almost linearly increases with an increase of N. This rapid increase is caused by the change of the peak given the highest ac­ curacy from k = 1 to another (as mentioned in Section 4.1, k-NN's predictive accuracy has two peaks) .

For each level (5%, 10%, and 30%) for both relevant attribute noise and class noise, the optimal value of k is changed from k = 1 to another at small N. This observation can be explained by the strong sensitivity of the accuracy of 1-NN to both relevant attribute noise and class noise (as mentioned in Section 4.2). That is, the peak at k = 1 disappears due to the effect of noise, even though N is a small number. After changing from k = 1 to another, the optimal value of k almost linearly increases with an increase of N.

These observations from Figure 3 show that the opti­ mal value of k almost linearly increases with an increase of N after the optimal k is changed from k = 1 to an­ other, regardless of the noise level for both relevant at­ tribute noise and class noise. That is , the optimal value of k strongly depends upon the number of training in­ stances in noisy domains.

5 Conclusion

In this paper, we presented an average-case analysis of the k-nearest neighbor classifier (k-NN) for m-of-n/l tar­ get concepts in noisy domains. Our analysis dealt with three types of noise: relevant attribute noise, irrelevant attribute noise, and class noise.

We formally defined the predictive accuracy of k-NN as a function of the domain characteristics. Using the accuracy function, we explored the predicted behavior of k-NN for each type of noise. The predictive accuracy of k-NN was given at various levels of noise, then the noise effects on k-NN's accuracy were shown. We also show that the optimal value of k almost linearly increases with an increase in the number of training instances in noisy domains. Our analysis was supported with Monte Carlo simulations.

In the future, we will extend the framework of average­ case analysis to relax many restrictions such as Boolean attributes, a fixed class of target concepts, and a fixed distribution over the instance space. Using the extended framework, we would like to analyze learning algorithms to give more useful insights into their practical applica­ tions.