Average-Case Analysis of a Nearest Neighbor Algorithm

1. Nearest Neighbor Algorithms

Most learning methods form some abstraction from experience and store this structure in memory. The field has explored a wide range of such structures, includ­ ing decision trees (Quinlan, 1986), multilayer networks (Rumelhart & McClelland, 1986), and probabilistic sum­ maries (Fisher, 1987). However, in recent years there has been growing interest in methods that store instances or cases in memory, and that apply this specific knowledge directly to new situations. This approach goes by many names, including instance-based learning and case-based reasoning, and one can apply it to many different tasks.

The simplest and most widely studied class of tech­ niques, often called nearest neighbor algorithms, origi­ nated in the field of pattern recognition (Cover & Hart, 1967; Dasarathy, 1991) and applies to classification tasks. In the basic method, learning appears almost trivial - one simply stores each training instance in memory. The power of the method comes from the retrieval process. Given a new test instance, one finds the stored training case that is nearest according to some distance measure, notes the class of the retrieved case, and predicts the new instance will have the same class.

Many variants exist on this basic algorithm. For in­ stance, Stanfill and Waltz (1986) have studied a version that retrieves the k closest instances and bases predic- WAYNE IBA AI Research Branch Mail Stop 269-2 NASA Ames Research Center Moffett Field, CA 94035 USA

tions on a weighted vote, incorporating the distance of each stored instance from the test case; such techniques are often referred to as k-nearest neighbor algorithms. Others (Cover & Hart, 1967; Aha, Kibler, & Albert, 1991) have studied an alternative approach that stores cases in memory only upon making an error, thus reduc­ ing memory load and retrieval time with little reduction in accuracy.

We would like to understand the learning behavior of this intriguing class of methods under various condi­ tions. Aha et al. present a PAC analysis of one such algorithm, but our aim is to obtain tighter bounds that we can directly relate to experimental results. To this end, we decided to pursue an average-case analysis along the lines developed by Hirschberg and Pazzani (1991) for logical induction methods and by Langley, Iba, and Thompson (1992) for probabilistic ones. For the sake of tractability, we focused our efforts on the most basic of the instance-based techniques, which stores all train­ ing cases and bases its prediction on the single nearest neighbor.

However, the simplicity of this method does not mean it lacks power. Aha et al. (1991) report the results of an experimental study that compared the algorithm (which they called IB1) to Quinlan's (1986) more so­ phisticated C4 algorithm for inducing decision trees. Ta­ ble 1 contains the results on four natural domains, two of them ("Cleveland" and "Hungarian") involving pre­ diction of heart disease from symptoms, another con­ cerning the diagnosis of primary tumors, and a fourth involving prediction of party affiliations for members of Congress from their voting records. For each domain, Aha et al. trained the algorithms on approximately 80% of the cases and tested them on the remaining instances, averaging over 50 different partitions. On the Cleveland data, the two algorithms' performance was indistinguish­ able, and IB1 's behavior on the tumor and voting records nearly reached C4's level. Although the basic nearest neighbor algorithm fared much worse on the Hungarian data set, simple modifications produce accuracy compa­ rable to that for C4 (Aha, 1990), and its performance on the other domains argues that it deserves closer inspec­ tion in any case.

In the remainder of this paper, we report the initial results of our average-case analysis of the simple near­ est neighbor method. We begin by presenting the assumptions of the analysis, followed by our derivation of the equations for predicting accuracy as a function of three variables. After this, we examine the implications of the analysis for the algorithm's behavior, comparing predicted learning curves for artificial domains of differ­ ing difficulty. Finally, we note some limitations of the analysis and suggest directions for future research.

2. An Average-Case Analysis

Recall that the algorithm under study stores all train­ ing cases in memory. Upon encountering a test instance, it retrieves the nearest observed case and predicts the same class as that for the stored instance. If a tie oc­ curs, the version we will examine selects one of the near­ est cases at random. We would like to compute An, the probability of correct classification (i .e., the predic­ tive accuracy) after n training instances as a function of characteristics of the domain.

Our analysis will assume that there exist two classes, C and C, defined over r relevant Boolean attributes Aj and i irrelevant ones. We will also assume that the prob­ ability of occurrence P(Aj) = 1/2 for each such attribute Aj, generating a uniform distribution over the instance space, and that the target concept is conjunctive, giving P(C) = P(At = 1/2r. Finally, we will measure the distance be,tween two cases as the number of attributes on which they differ. Because there are r + i attributes, there are exactly r+i+ 1 distinct distances, ranging from zero to r + i, that can occur.

We will use Id to denote an arbitrary test case that is distance d from the prototype P for the positive class. We will also refer to Je as an arbitrary training case that is distance e from test instance Id. We will often treat groups of test cases as a class based on their distance d from the prototype; similarly, we will consider groups of training instances based on their distance e from a given class of test cases.

Our strategy considers positive and negative test in­ stances separately. We will use A( C)n to refer to the probability of correct classification given that the algo­ rithm encounters a positive test case after n training cases, and we will use A( C)n for the predictive accuracy given a negative test instance. The overall accuracy of the nearest neighbor algorithm after n training cases is

where P(C) is the probability of a positive test case and P( C) = 1 - P( C) is the probability of a . negative one.

Let us deal with the accuracy on negative test cases first. We can view this term as a weighted sum of the accuracies for different types of test cases Id, where dis the distance from the prototype. 1 We must sum over all possible distances from the prototype at which a test case can occur (except ford= 0), multiplying the probability of each type d by its accuracy B( C)d,n according to the possible contents of memory after n training instances:

where the accuracy component

can be further divided into three terms, which are re­ lated to the regions shown in Figure 1. These corre­ spond, respectively, to situations in which the closest stored training case is near enough to Id to ensure cor­ rect classification, in which ties can occur because the closest case may belong to either class, and in which the closest instance is far enough from Id to ensure correct prediction.

The initial term, N(Jd-i-dn, represents the contribu­ tion to the accuracy that results from the first of these situations, when the nearest stored training case Je is closer to Id than the latter is to the nearest positive instance (i.e., 0 ~ e < d - i) . When this occurs, the algorithm will correctly classify Id as negative. To see this, consider the innermost region in Figure 1, and note that the algorithm must observe only one training case within the region for this to transpire. The probabil­ ity that any given training instance will fall within e or fewer steps of the test case is

giving the probability 1-W(Je) that this will not occur. Thus, the probability that (after n training instances) the algorithm will have seen at least one such case is

which gives the first term in the definition of B(C)d,n in equation (3).

1. When some features are irrelevant, there are multiple pos­ itive instances, any of which we can select as the proto­ type without loss of generality.

The second term from this equation, T( Jd-i,d+i):;;, is the contribution to the accuracy when the distance to the nearest stored training instance Je is between the distances to the nearest possible positive instance and the farthest one (i.e., d-i ~ e ~ d+i). This corresponds to the central region in the figure. In this situation, con­ flicts can occur during the classification process, in that the algorithm may retrieve both positive and negative training cases at distance e from the test case.

Ties are possible in this region because, given i irrele­ vant attributes, there are 2i positive instances that can be located i steps or less away from the prototype. For any given test case Id that is distance d from the pro­ totype, the nearest stored positive case may be i steps away from the prototype in the direction toward Id, i steps away from the prototype in the direction away from Id, or somewhere between these two extremes. Negative instances can also occur anywhere within this region, making the entire middle band in the figure open to the possibility of ties.

To handle all possible ties, we must sum over all dis­ tances e between d - i and d + i, then sum over the possible numbers k of nearest instances (positive or neg­ ative) that have been stored at each such distance. In each case, we must multiply the probability M(Je)n,k of that number occurring by the accuracy E(Je)/; that results from such a tie. We can state this formally as

We can further decompose the first term in the product into the probability that exactly k of the n training cases are distance e from the test case and that the remaining n- k are at some greater distance (since the k cases are the nearest ones), giving

as the formal expression. To compute the accuracy given a tie among k stored cases, we must sum over the possible numbers j of negative instances, in each case multiplying the subaccuracy by the probability of that occurrence. This gives

where j / k is the expected accuracy when one selects a training case at random from a set that contains j out of k negative instances. The term V(C); d represents the probability of a positive instance Je gi~en that the instance is e steps away from negative test case Id , which is in turn d steps away from the prototype. We can expand this term to

provided k ~ e, k ~ r, and d- k ~ i, and to zero other­ wise. This expression sums over different ways in which distanced can occur, with some steps along relevant at­ tributes and others along irrelevant ones, multiplied by the probability that an instance e steps away from the resulting test case will be positive.

The final term from equation (3), F(Jd+i+dn, spec­ ifies the contribution to the accuracy when the nearest training instance Je has distance greater than d + i from test case Id (i.e., d + i < e ~ r + i), and thus falls within the outermost region in Figure 1, which contains only negative instances. As with the N(Jd-i-dn term, the algorithm will correctly classify Id as negative whenever this occurs. The chance that this situation will arise is

which is the probability that 1ny given training case will fall at distance e or greater · ~om the test iastance, taken to power n to generate the probability that every train­ ing instance seen so far satisfies this condition.

Now we can turn to A(C)n, the accuracy on positive test cases after n training instances. The situation here is simpler than for negative test cases, but still nontrivial. The algorithm is guaranteed to classify a positive test case Id correctly only when the nearest stored training instance is itself the test case (i.e., e = 0) . Ties can occur anywhere in the range 1 ~ e ~ i, giving the expression

Because one can treat any positive instance as the pro­ totype, there is no need to sum over different distances d here. Moreover, since no positive instance can be more than i steps away from any other, we can omit the third term of equation (3), F(Ji+dn, which is always zero.

The term for handling ties is analogous to equation (6) for the negative situation, but we must revise the definition for E(Je)'k in equation (8) to

Note that here we must use the numerator k - j rather than k, in that we are dealing with positive test cases. Moreover, we must take a different approach to com­ puting V(C)~, the probability of a positive instance Je given that the instance is e steps away from positive test case Id. In this case, we have

when i ~ e, but zero in other situations. Taken together, the definitions for A(C)n, A(C)n, and their component terms let us predict the overall accuracy An for the near­ est neighbor algorithm as a function of the number of training instances n, the number of relevant attributes r, and the number of irrelevant attributes i.

3. Behavioral Implications of the Analysis

Although the equations in the previous sections pro­ vide a formal characterization of the nearest neighbor algorithm's behavior, their implications are not obvious. To better understand the effects of domain characteris­ tics, we systematically varied certain domain parameters and examined the predicted results. In addition to com­ puting theoretical predictions, we also collected experi­ mental learning curves that summarized the algorithm's actual behavior. Each datum on these curves reports the classification accuracy averaged over 100 runs on ran­ domly generated training sets, measured over the entire space of uniformly distributed noise-free instances. In each case, we bound the mean accuracy with 95% confi­ dence intervals to show the degree to which our predicted learning curves fit the observed ones. These experimen­ tal results provide an important check on our reasoning, and they identified a number of problems during devel­ opment of the analysis.

Figure 2 shows the effects of the number of relevant attributes in the conjunctive target concept. For this study, we held the number of irrelevant attributes i con­ stant at one, and we varied both the number of training instances and the number of relevant attributes r. As typical with learning curves, the accuracy starts low and gradually improves as the algorithm encounters more training instances. The effects of target complexity also make sense. Increasing the number of relevant features should increase the overall number of negative instances, giving higher accuracy early in the induction process; however, this factor also increases the total number of possible instances, requiring more training cases to reach asymptote and producing a crossover effect. The learn­ ing rate seems to degrade gracefully with increasing com­ plexity, and the theoretical and actual learning curves are in close agreement, which lends confidence to the analysis.

The sensitivity of the nearest neighbor algorithm to irrelevant attributes is more dramatic, as shown in Fig­ ure 3. This graph summarizes the results of a similar study of the interaction between the number of train­ ing instances n and the number of irrelevant attributes. Here we held the number of relevant attributes constant at two, and we examined three levels of the i parameter. As with the previous study, the degradation in learning rate is graceful, but the effect is somewhat greater. The difference between the two results appears more signifi­ cant when one realizes that increasing i does not reduce the proportion of positive instances, as does increasing the number of relevant attributes. These observations are consistent with Aha's (1990) reports on the sensitiv­ ity of nearest neighbor methods to the number of irrele­ vant attributes.

We can also compare the behavior of the nearest neigh­ bor algorithm to that of other induction methods for which average-case analyses exist. In particular, Pazzani and S;mett (1992) have studied the WHOLIST algorithm, which initializes its concept description to the conjunc­ tion of features in the first positive training instance, then removes any feature that fails to occur in later pos­ itive instances. Similarly, Langley, Iba, and Thompson (1992) have analyzed the behavior of the Bayesian clas­ sifier, a simple probabilistic method that stores observed base rates and conditional probabilities. As Pazzani and Sarrett note, WHOLIST's learning rate is unaffected by the number of relevant attributes, so their algorithm clearly scales up better on this dimension than does the nearest neighbor technique. Comparison to the Bayesian classifier on this factor is more difficult, in that Lang­ ley et al. 's study examined equal probabilities for the two classes, whereas the current analysis assumes that they differ.

In some domains, effective learning relies more on the ability to handle many irrelevant features than many rel­ evant ones. In this vein, we have shown analytically that the number of training instances required for WHOLIST to achieve a given level of accuracy increases only with the logarithm of the number of irrelevant attributes. Al­ though we have not yet derived similar analytic relations for the nearest neighbor or probabilistic methods, we can use the existing analyses to estimate ability to scale on this dimension.

Figure 4 graphs the predicted number of training in­ stances needed to achieve 90% accuracy for each algo­ rithm as a function of the number of irrelevant attributes, assuming a target concept involving only one relevant feature and a uniform distribution of instances. The analyses do not provide these quantities directly, but one can interpolate them from the theoretical learning curves. The figure reveals that the Bayesian classifier scales well to increasing numbers of irrelevant attributes, with the dependent measure growing as an approximate linear function of this factor. In contrast, the num­ ber of training instances required by the nearest neigh­ bor method grows much faster , although we cannot yet determine the precise superlinear relation. These re­ sults are also consistent with Aha's (1990) conclusions about the response of standard instance-based methods to many irrelevant features.

However, the above comparisons are not entirely fair . Neither the WHOLIST algorithm nor the Bayesian clas­ sifier are designed to handle disjunctive concepts, which present no obstacles to even the simplest nearest neigh­ bor algorithm. Our focus on conjunctive concepts in the current analysis has obscured this strength. Also, Aha (1990) has developed a variant of the nearest neighbor algorithm that retains statistics on the usefulness of each attribute, and he has shown that this approach fares bet­ ter in domains with many irrelevant terms. Nevertheless, the ability to make comparisons of the above type is one advantage of careful formal analyses, and they have pro­ vided insights about the relative strengths of the differ­ ent learning algorithms.

4. General Discussion

In this paper we presented an average-case analysis of the most basic nearest neighbor algorithm. Our treat­ ment assumes that the target concept is conjunctive, that instances are free of noise, that attributes are Bool­ ean, and that instances are uniformly distributed. Given information about the number of relevant and irrelevant attributes, our equations let us compute the expected classification accuracy after a given number of training instances.

To explore the implications of the analysis, we plotted the predicted behavior of the algorithm as a function of these three factors, finding graceful degradation as the number of relevants r and irrelevants i increased, but finding a stronger effect for the second. As a check on our analysis, we ran the algorithm on artificial domains with the same characteristics. The predicted behavior closely fit that found in the experiments, but only af­ ter correcting several errors in our reasoning that the empirical studies revealed.

These results begin to account for the wide range of performance observed for the algorithm by Aha and oth­ ers on natural domains. However, a full explanation will require several extensions to the analysis. In particular, we must incorporate the influence of both class and at­ tribute noise, as we have done in earlier analyses (Iba & Langley, 1992; Langley et al., 1992). We must also han­ dle situations in which each attribute follows a separate probability distribution, following the approach taken by Hirschberg and Pazzani (1991).

Even more important, we must extend the framework to handle broader classes of target concepts. Nearest neighbor methods are well suited for M of N concepts, in which any M of the N features in the prototype are sufficient for membership in the class. Since distance from the prototype plays a central role in the current analysis, we believe extending it to handle such concepts will be quite feasible. Similarly, because the algorithm stores many training instances in memory, it can easily acquire disjunctive concepts that require multiple pro­ totypes. Again, we hope that simple extensions to the existing framework will handle this situation. We should also generalize the analysis to include k-nearest neighbor methods, following the lead recently provided by Turney (in press).

Another direction for future work would attempt to map the extended analysis onto natural domains in which there already exist experimental results with the method. Given information about the distributions of attributes (which are available in the data), along with estimates of the noise levels and target concepts (which require informed guesses), we can compare learning curves pre­ dicted by the theory with those observed in experimen­ tal runs. This approach would extend the applicability of our average-case model beyond the artificial domains to which we have limited our tests to date.

In summary, we believe that our initial analysis has provided some useful insights about the behavior of the basic nearest neighbor algorithm. These begin to explain why the algorithm compares favorably with more com­ plex induction methods on some domains but not oth­ ers, and our results are consistent with intuitions about the algorithm's sensitivity to irrelevant attributes. We also believe the existing theoretical framework can be ex­ tended to handle more challenging target concepts and other factors that complicate the learning task, thus pro­ viding a solid base on which to carry out further studies of instance-based learning.

Acknowledgements

We would like to thank Stephanie Sage and David Aha for discussions that helped clarify our ideas, David Aha and three reviewers for useful comments, and Nils Nils­ son for his support and encouragement. The first author contributed to this work while he was at the Center for the Study of Language and Information, Stanford Uni­ versity, and the Institute for the Study of Learning and Expertise.