Nearest Neighbor Pattern Classification

“Nearest Neighbor Pattern Classification” is a paper by Thomas M. Cover of Stanford University’s Department of Electrical Engineering and Peter E. Hart of the Stanford Research Institute in Menlo Park, published on pages 21–27 of IEEE Transactions on Information Theory in January 1967 (the manuscript was received in February 1966 and revised that April). It analysed the simplest nonparametric classifier, which gives a new observation the label of the closest stored example, and proved that when the number of stored examples grows without limit its probability of error $R$ satisfies

$$R^* \;\le\; R \;\le\; R^*\Big(2 - \frac{M}{M-1}\,R^*\Big)$$

for $M$ categories, where $R^*$ is the Bayes error, the lowest error any rule can reach with full knowledge of the distribution. The upper bound never exceeds $2R^*$, and the paper shows that both bounds are as tight as possible. The paper also showed that the one-neighbour rule is admissible among $k$-neighbour rules for every sample size, and extended the large-sample bounds to the $k$-neighbour vote. The method as used today, including the choice of $k$, distances, cost and its uses in vision, is the subject of the k-nearest neighbors article; this article covers the paper. Section, equation and figure numbers below are those of the printed journal version, read in the scan of the printed pages that Cover’s Stanford web page hosts.

Problem

The paper opens with two extremes of knowledge. A statistician who knows the joint distribution of an observation $x$ and its category $\theta$ can apply the Bayes rule and reach the minimum error $R^*$. One who knows only $n$ correctly classified samples $(x_1, \theta_1), \dots, (x_n, \theta_n)$, drawn independently from that distribution, faces a nonparametric problem for which, the authors note, no classification procedure is optimal against every distribution. A natural heuristic is that observations close together in some metric have the same category, or at least nearly the same posterior probabilities, so the evidence of nearby samples should weigh most; the nearest-neighbour (NN) rule is the simplest procedure of that kind.

Cover and Hart credit the first formulation of a nearest-neighbour type rule, and the main earlier analysis of one, to Evelyn Fix and J. L. Hodges Jr., in two reports for the US Air Force School of Aviation Medicine at Randolph Field, Texas: one of February 1951 and one of August 1952. Fix and Hodges studied what the paper calls the $k_n$-NN rule, which assigns a point to the class most represented among its $k_n$ nearest neighbours, and established its consistency for sequences with $k_n \to \infty$ and $k_n / n \to 0$; Cover’s 1968 follow-up adds that they did so under conditions on the underlying distributions, with the risk approaching the Bayes risk. The 1952 report studied numerically the small-sample performance of the rule under normal distributions. The first report was reprinted in 1989 in the International Statistical Review.

The paper lists other earlier uses. Johns had used the NN rule as an example of an empirical Bayes rule; Kanal, Sebestyen, who called it the proximity algorithm, and Nilsson had pointed out its intuitive appeal and suggested it for pattern recognition. Kanal’s 1963 report, the reference list notes, had first appeared in a Philco study titled “Semi-automatic imagery screening research study and experimental investigation”. Loftsgaarden and Quesenberry had shown that a modification of the $k_n$-NN rule gives a consistent density estimate. In none of these papers, Cover and Hart write, had analytical results been obtained in the nonparametric case for a finite sample size or for a finite number of neighbours. Fix and Hodges’ consistency result is analytical but lets the number of neighbours grow; whether “the above mentioned papers” is meant to include their reports is not clear from the text. The paper set out to analyse the rule that uses a single neighbour.

Contribution

• Admissibility of 1-NN (§III). For every sample size $n$ there is a distribution on which the one-neighbour rule has strictly lower error than every $k$-neighbour majority rule with $k \ne 1$, so no such rule is better than 1-NN against all distributions.
• Convergence of the nearest neighbour (§V). In any separable metric space the nearest of $n$ independent samples converges to the query with probability one, for any probability distribution.
• The two-class bound (§VI). $R^* \le R \le 2R^*(1 - R^*)$, eq. (13), under mild conditions on the class densities, with both bounds as tight as possible and an exact expression for the slack.
• The $M$-class bound (§VI). $R^* \le R \le R^*(2 - MR^*/(M - 1))$, eq. (29), again tight.
• A worked example (§VII). What the paper presents as an exact expression for the error of 1-NN at every finite $n$ in one simple problem; the printed formula is wrong for $n \ge 2$ (see the slips below).
• The $k$-NN rule (§VIII). For two classes and odd $k$, the tightest upper bound on the large-sample $k$-NN error, which decreases with $k$ toward $R^*$.

The authors read the main result as a statement about information: since any rule based on the infinite sample set can at best halve the NN error, in the abstract’s words “half the classification information in an infinite sample set” is contained in the nearest neighbour.

Method

Setting and the rule

Section II takes the $x_i$ in a metric space $X$ with metric $d$ and the categories $\theta_i$ in $\{1, 2, \dots, M\}$. A new pair $(x, \theta)$ arrives, with only $x$ observed. The sample $x_n'$ is a nearest neighbour of $x$ if $d(x_n', x) = \min_i d(x_i, x)$, eq. (1), and the NN rule assigns $x$ to the category $\theta_n'$ of $x_n'$, ignoring the other $n - 1$ labels. A footnote handles ties: the rule may decide the most popular category among tied points, and where ties occur with nonzero probability the results hold trivially. The paper’s notation differs from the subject article’s: $\eta_i$ are the prior probabilities of the categories, $f_i$ their densities with respect to a measure $\nu$, and $\hat\eta_i(x) = \eta_i f_i(x) / \sum_j \eta_j f_j(x)$, eq. (4), the posterior probabilities. With the 0–1 loss the conditional Bayes risk is $r^*(x) = 1 - \max_i \hat\eta_i(x)$ and the Bayes risk is $R^* = \mathbb{E}\, r^*(x)$, eqs. (6)–(7) and (32). The $n$-sample NN risk $R(n)$ is the expected loss of the rule, eq. (10), and the large-sample NN risk is its limit $R = \lim_{n \to \infty} R(n)$, eq. (11). All pairs are assumed independent and identically distributed.

Admissibility

Section III first gives the case for a vote over $k$ neighbours: a large $k$ lowers the chance of a non-Bayes decision while a small $k$ keeps the neighbours close, and then shows that 1-NN is nevertheless never dominated. In its example (Fig. 1) two equally likely classes are uniform on unit disks centred at $(-3, 0)$ and $(3, 0)$. A query from one disk has its nearest neighbour in the other disk only if all $n$ samples lie there, so 1-NN errs with probability $(1/2)^n$. With $k = 2k_0 + 1$ the vote errs whenever $k_0$ or fewer samples lie in the query’s disk, with probability

$$P_e(k; n) = \Big(\frac{1}{2}\Big)^n \sum_{j=0}^{k_0} \binom{n}{j},$$

eq. (2), larger than $(1/2)^n$ for every $k > 1$. The same example works for every $n$. The formula covers odd $k$ only; the paper does not discuss vote ties for even $k$.

Convergence of the nearest neighbour

The large-sample analysis rests on a lemma in Section V: if $x, x_1, x_2, \dots$ are independent and identically distributed in a separable metric space, then $x_n' \to x$ with probability one. The proof first shows convergence for any $x$ whose every surrounding ball has positive probability, then uses a countable dense subset to cover the remaining points by countably many balls of probability zero, so that such points occur with probability zero. The authors prove it in this generality, they say, to cover pathological candidates such as the Cantor distribution on the real line. They add that, because this convergence does not depend on the metric, the bounds on the NN risk do not either.

The two-class theorem

For $M = 2$ and the 0–1 loss, the theorem of Section VI assumes a separable metric space and densities $f_1, f_2$ such that, with probability one, $x$ is either a continuity point of both or a point of nonzero probability. The remarks note that any mixture of point masses and piecewise continuous densities on Euclidean space qualifies. Conditioning on $x$ and $x_n'$, the labels $\theta$ and $\theta_n'$ are independent, so the conditional risk is $\hat\eta_1(x)\hat\eta_2(x_n') + \hat\eta_2(x)\hat\eta_1(x_n')$, eq. (15). The continuity assumption, together with the lemma, makes $\hat\eta(x_n') \to \hat\eta(x)$; at an atom $x_0$ the neighbour simply equals $x_0$ from some $n$ on. The conditional risk therefore tends to $r(x) = 2\hat\eta_1(x)\hat\eta_2(x) = 2r^*(x)(1 - r^*(x))$, eq. (21), and dominated convergence carries the limit through the expectation. Writing $\mathbb{E}[r^{*2}] = R^{*2} + \operatorname{Var} r^*$ gives the exact large-sample risk

$$R = 2R^*(1 - R^*) - 2\operatorname{Var} r^*(x),$$

eq. (25). The upper bound $2R^*(1 - R^*)$, eq. (26), is reached exactly when $r^*$ is constant, which the paper turns into the condition that $\eta_1 f_1(x) / \eta_2 f_2(x)$ equal $R^*/(1 - R^*)$ or its reciprocal almost everywhere, eq. (27). Rewriting the risk as $R = R^* + \mathbb{E}[r^*(1 - 2r^*)]$, eq. (28), gives the lower bound, reached exactly when $r^*$ is 0 or $1/2$ almost everywhere. At the extremes the two rules agree: $R^* = 0$ if and only if $R = 0$, and $R^* = 1/2$ if and only if $R = 1/2$.

The M-class theorem

With more than two classes the substitution of eq. (21) no longer applies. The theorem’s assumptions are the same, with densities $f_1, \dots, f_M$ with respect to a probability measure $\nu$, and the limit of the conditional risk is

$$r(x) = \sum_{i \ne j} \hat\eta_i(x)\hat\eta_j(x) = 1 - \sum_{i=1}^{M} \hat\eta_i(x)^2,$$

eq. (31). The Cauchy–Schwarz inequality applied to the $M - 1$ non-maximal posteriors, eqs. (33)–(35), gives $r(x) \le 2r^*(x) - \frac{M}{M-1} r^*(x)^2$, eq. (36), and taking expectations gives eq. (29). The upper bound is attained by a “no-information” experiment in which all classes have the same density and the priors are $1 - R^*$ for one class and $R^*/(M-1)$ for each of the others; the lower bound is attained, for example, by equal priors and uniform densities that overlap completely on one interval and are disjoint elsewhere, eq. (39). Hastie and colleagues (2009, §13.3, eq. 13.5 and Exercise 13.3) state the same conditional inequality and the same bound.

Results

The paper’s only numerical example, in Section VII, is one-dimensional. Two equally likely classes have triangular densities on $[0, 1]$, $f_1(x) = 2x$ and $f_2(x) = 2 - 2x$ (Fig. 2), so that the mixture is uniform and the posterior of class 1 is simply $\hat\eta_1(x) = x$. The Bayes error is $R^* = \int_0^1 \min(x, 1 - x)\,dx = 1/4$, eq. (43). The paper writes the $n$-sample 1-NN risk as $R(n) = \mathbb{E}[x(1 - x_n') + (1 - x)x_n']$, eq. (40), and after what it calls a lengthy but straightforward calculation gives

$$R(n) = \frac{1}{3} + \frac{1}{(n + 1)(n + 2)},$$

eq. (41), with limit $R = 1/3$, eq. (42), so that the bounds read $1/4 \le 1/3 \le 3/8$, eq. (44). The paper observes that $R(1) = 1/2$, in agreement with simpler considerations, and that $R(n)$ approaches its limit approximately as $1/n^2$.

The example below reproduces Section VII with images: each sample is a uniform $4 \times 4$ grey patch whose brightness $x$ is drawn from the two triangular densities, a lit and a shadowed class, and the classifier compares the 16 pixel values. Because the patches are noise-free, the Euclidean distance between two of them is $4|x - x'|$, so the nearest patch is the one of closest brightness and the problem is exactly the paper’s. The block estimates the 1-NN error by simulation for several $n$ and prints it beside eq. (41) and beside an exact expression we derived for the same quantity. It then evaluates the paper’s large-sample formulas for this example: $R^*$, the 1-NN risk of eq. (24), and, applying Section VIII to Section VII (a computation the paper does not make), the large-sample 3-NN risk and its tightest bound, checked by a simulation at $n = 1{,}000$. It takes about 5 seconds; the output came from NumPy 2.3.5 and SciPy 1.16.3.

import numpy as np
from scipy.integrate import quad

# Section VII of Cover & Hart, as images: every sample is a uniform 4x4 grey patch whose
# brightness x in [0, 1] has density f1(x) = 2x for class 1 (lit) and f2(x) = 2 - 2x for
# class 2 (shadow), with equal priors, so the posterior of class 1 is eta1(x) = x.
PIX = 16

def patches(m, rng):
    """m patches, one row each; brightness drawn from the triangular class densities."""
    y = rng.integers(1, 3, m)
    u = np.sqrt(rng.uniform(size=m))
    x = np.where(y == 1, u, 1 - u)
    return np.repeat(x[:, None], PIX, axis=1), y

def knn_error(n, k, trials, rng, chunk=2000):
    """Monte Carlo error of the k-NN vote (Euclidean distance on the 16 pixel values),
    each trial with its own n training patches and one query patch."""
    errs = 0
    for _ in range(trials // chunk):
        X, y = patches(chunk * n, rng)
        X, y = X.reshape(chunk, n, PIX), y.reshape(chunk, n)
        q, yq = patches(chunk, rng)
        d = ((X - q[:, None, :]) ** 2).sum(-1)                  # chunk x n squared distances
        nn = np.argsort(d, axis=1)[:, :k]
        votes1 = (np.take_along_axis(y, nn, 1) == 1).sum(1)
        errs += np.sum(np.where(votes1 * 2 > k, 1, 2) != yq)
    return errs / trials

rng = np.random.default_rng(0)
print("   n   1-NN error, 200,000 trials   printed eq. (41)   exact (our derivation)")
for n in (1, 2, 5, 20, 100):
    printed = 1/3 + 1/((n + 1) * (n + 2))
    exact = 1/3 + (3*n + 5) / (2 * (n + 1) * (n + 2) * (n + 3))
    print(f"{n:>4}   {knn_error(n, 1, 200_000, rng):>13.4f}{printed:>27.4f}{exact:>21.4f}")

# Large-sample risks from the paper's formulas, with r*(x) = min(x, 1 - x) and x uniform.
R_star = quad(lambda x: min(x, 1 - x), 0, 1, points=[0.5])[0]               # eq. (43)
R_1 = quad(lambda x: 2 * x * (1 - x), 0, 1)[0]                               # eq. (24)
rho3 = lambda r: r + 3 * r**2 - 8 * r**3 + 4 * r**4                          # eq. (46), k = 3
R_3 = quad(lambda x: rho3(min(x, 1 - x)), 0, 1, points=[0.5])[0]
# least concave majorant of rho3 on [0, 1/2] at r = R*, from the upper hull of a fine grid
r = np.linspace(0, 0.5, 5001); v = rho3(r)
hull = [0]
for i in range(1, len(r)):
    while len(hull) > 1 and ((v[hull[-1]] - v[hull[-2]]) * (r[i] - r[hull[-2]])
                             <= (v[i] - v[hull[-2]]) * (r[hull[-1]] - r[hull[-2]])):
        hull.pop()
    hull.append(i)
rho3_tilde = np.interp(R_star, r[hull], v[hull])
print(f"\nR* = {R_star:.4f}   R (1-NN) = {R_1:.4f}   bound 2R*(1 - R*) = {2*R_star*(1-R_star):.4f}")
print(f"R_3 (3-NN) = {R_3:.4f}   bound rho3~(R*) = {rho3_tilde:.4f}")
print(f"3-NN error at n = 1,000 (40,000 trials): {knn_error(1000, 3, 40_000, rng):.4f}")

Output:

   n   1-NN error, 200,000 trials   printed eq. (41)   exact (our derivation)
   1          0.5007                     0.5000               0.5000
   2          0.4253                     0.4167               0.4250
   5          0.3645                     0.3571               0.3631
  20          0.3367                     0.3355               0.3364
 100          0.3339                     0.3334               0.3335

R* = 0.2500   R (1-NN) = 0.3333   bound 2R*(1 - R*) = 0.3750
R_3 (3-NN) = 0.3000   bound rho3~(R*) = 0.3281
3-NN error at n = 1,000 (40,000 trials): 0.2981

The simulation agrees with the paper at $n = 1$ and approaches the limit $1/3$, but it does not match the printed eq. (41) in between: at $n = 2$ and $n = 5$ the simulated error exceeds the formula by 0.009 and 0.007, many times the sampling error of 200,000 trials (a standard deviation of about 0.001, by our calculation). Our own calculation of the risk defined by eq. (40) gives

$$R(n) = \frac{1}{3} + \frac{3n + 5}{2(n + 1)(n + 2)(n + 3)},$$

which matches the simulation at every $n$ shown, agrees with eq. (41) at $n = 1$, and has the same $1/n^2$ decay, with a leading constant of $3/2$ instead of 1. The reasoning behind it, which is ours: for a query of brightness $x \le 1/2$, a neighbour closer than $x$ is equally likely to lie on either side, so it contributes no systematic error; the excess over the limit comes only from queries near the ends of the interval, whose nearest neighbour must lie on the inside when no sample is closer to the query than the edge is. This discrepancy is our finding; we know of no published correction. The large-sample numbers illustrate the paper’s chain of bounds for this example: 1-NN at $1/3$ is below the two-class bound $3/8$, and three neighbours lower the large-sample error to $0.30$, below their own tightest bound $\tilde\rho_3(1/4) \approx 0.328$ and above $R^* = 1/4$; a simulation with 1,000 patches is already close to that value.

The k-NN rule

Section VIII extends the analysis to $k$ neighbours. With $k$ fixed, the $k$-th nearest neighbour also converges to $x$ (from §V), and the $k$ neighbours cast conditionally independent votes. For two classes and odd $k$, the large-sample conditional $k$-NN risk $r_k(x)$ is a binomial expression in $\hat\eta_1(x)$, eq. (45): the probability that the majority of $k$ independent labels disagrees with $\theta$. The paper notes that $r_k(x)$ decreases monotonically in $k$ toward $\min(\hat\eta_1, 1 - \hat\eta_1)$, and that since $r_k$ is symmetric in $\hat\eta_1$ and $1 - \hat\eta_1$ it can be written as a function $\rho_k(r^*)$ of the conditional Bayes risk alone, eq. (46). With $\tilde\rho_k$ the least concave function above $\rho_k$, Jensen’s inequality gives

$$R_k = \mathbb{E}\,\rho_k(r^*) \le \mathbb{E}\,\tilde\rho_k(r^*) \le \tilde\rho_k(\mathbb{E}\, r^*) = \tilde\rho_k(R^*),$$

eqs. (47)–(48). The authors state that simple distributions attain $\tilde\rho_k(R^*)$, so that it is the least upper bound, without exhibiting them, and conclude with the chain

$$R^* \le R_k \le \tilde\rho_k(R^*) \le \tilde\rho_{k-1}(R^*) \le \dots \le \tilde\rho_1(R^*) = 2R^*(1 - R^*),$$

eq. (49), with the upper and lower bounds on $R_k$ as tight as possible. Large-sample $k$-NN error can therefore only improve on 1-NN as $k$ grows, while Section III shows that at a fixed sample size it need not: the two results together state the trade-off in the choice of $k$ that the k-nearest neighbors article treats in practice.

Impact

Hastie, Tibshirani and Friedman (2009, §13.3) describe the bound as famous and present its argument, the asymptotic error of a random rule that draws both the label and the test point’s class from the posterior, together with the $M$-class inequality. The paper itself is not about images and contains no experiments on data. The rule it analysed is the one behind descriptor matching, image retrieval, face identification against a gallery and the evaluation of learned embeddings, uses the k-nearest neighbors article describes.

Limitations

The results are asymptotic. Apart from the admissibility example and the triangular example, every bound concerns the limit $n \to \infty$. The paper gives no rate at which $R(n)$ approaches $R$ in general and no bound on the error at a finite sample size; the $1/n^2$ behaviour it reports belongs to one example. How slowly the limit is reached in high dimensions is shown by the 16-pixel experiment in the k-nearest neighbors article.

Metric independence is a large-sample statement. It follows from eq. (31) that the limit $R$ depends only on the posteriors at $x$, so any metric for which the lemma and the continuity assumption hold gives the same large-sample error. The error at finite $n$ does depend on the metric, which is why distance choice, feature scaling and metric learning matter in practice. The continuity assumption is itself tied to the metric’s topology (our observation): a metric under which the class densities are discontinuous almost everywhere would fall outside the theorems.

Scope of the assumptions. The theorems assume independent, identically distributed pairs, the 0–1 loss, and densities that are continuous at almost every point that is not an atom. The $k$-NN bounds cover two classes and odd $k$ only. The admissibility result is a statement about undominated rules among $k$-NN rules, not a claim that 1-NN is a good choice: in the same section the paper shows that on its disk example the error rises toward $1/2$ as $k$ grows for fixed $n$, and falls to zero as $n$ grows for any fixed $k$, eq. (3).

The bound concerns 1-NN against Bayes, not the best $k$. Letting $k$ grow with $n$ removes the factor of two altogether, as Fix and Hodges’ consistency result already showed under their conditions; the Cover–Hart bound describes what is lost by insisting on a single neighbour.

Slips in the printed paper

• The lemma’s proof. Below eq. (9) the proof in §V appeals to the monotone decrease in $k$ of $d(x_k, x)$, the distance of the $k$-th sample. Cover (1968, footnote 1) corrected this as a misprint for $d(x_k', x)$, the distance of the nearest of the first $k$ samples, whose monotonicity turns convergence in probability into convergence with probability one.
• Admissibility. The last sentence before Fig. 1 states that 1-NN is strictly better than other $k$-NN rules when each in-class distance is greater than any between-class distance. In the disk example the reverse holds (distances within a class are at most 2, between classes at least 4), so in our reading the sentence has the inequality inverted.
• Correct versus incorrect. After eq. (21) the text says a randomly chosen $x$ will be “correctly classified” with probability $2r^*(x)(1 - r^*(x))$; by eq. (21) that is the probability of misclassification (our reading).
• The M-class risk. Eq. (37) is printed as an equality, but it follows from the inequality (36) by taking expectations, so for $M > 2$ it holds as $R \le 2R^* - \frac{M}{M-1}(R^*)^2 - \frac{M}{M-1}\operatorname{Var} r^*$ (our reading; for $M = 2$ it is an equality and matches eq. 25). For the same reason the statement after eq. (38) that equality holds if and only if $\operatorname{Var} r^* = 0$ needs, for $M > 2$, also equality in the Cauchy–Schwarz step, that is, equal non-maximal posteriors almost everywhere; the paper’s no-information example satisfies both.
• The triangular example. As the code above shows, eq. (41) does not match the risk defined by eq. (40) for $n \ge 2$, although its value at $n = 1$, its limit and its $1/n^2$ decay are right (our finding).

In our reading, none of these affects the main theorems, eqs. (13) and (29): eq. (29) still follows from eq. (36).

What Came After

Both authors returned to the rule in the same journal the next year. Cover (1968) extended the analysis from classification to estimation, where the label is a parameter in an arbitrary space and the losses can be unbounded. Under conditions that allow limit and expectation to be exchanged, to which part of that paper is devoted, he showed that the large-sample NN risk is at most $2R^*$ for metric loss functions and equal to $2R^*$ for squared-error loss, and that a simple estimator using $k$ neighbours has risk $R^*(1 + 1/k)$ under squared error; he read these as saying that at least half the information in an infinite training set is contained in the nearest neighbour. That paper also cites, beside the 1967 paper, a May 1966 Stanford Electronics Laboratories technical report by Hart, “An asymptotic analysis of the nearest-neighbor decision rule”, for the classification bound.

Hart then turned to the practical cost of storing every sample: his condensed nearest-neighbour rule of 1968, described in the k-nearest neighbors article, keeps only a subset of the training set for the nearest-neighbour decisions (Hastie et al., 2009, §13.5).

Hastie and colleagues (2009, §13.3 and the chapter’s bibliographic notes) write that many additional results of the Cover–Hart kind have been derived, point to Chapter 6 of Ripley (1996) for a summary, and to Dasarathy (1991) for a review of the extensive literature on nearest-neighbour methods. For the large image collections of computer vision, finding the neighbours quickly is the separate subject of approximate nearest neighbor search.