24  Nearest Neighbors

The models of the previous chapters estimate a function with a fixed form and a set of parameters. Nearest-neighbor methods estimate the prediction at a point directly from the training cases closest to it, with no global form. They are the simplest local methods, and they make two ideas concrete that recur in later chapters: that flexibility can be controlled by the size of a neighborhood, and that the notion of closeness depends on how features are measured.

24.1 The k-nearest-neighbor rule

For a new case \(x\), let \(N_k(x)\) be the set of the \(k\) training cases whose features are closest to \(x\). The k-nearest-neighbor (kNN) prediction is the average outcome of these neighbors for regression,

\[ \hat f(x) = \frac{1}{k} \sum_{i \in N_k(x)} y_i , \tag{24.1}\]

and, for classification, the proportion of neighbors in each class, which estimates \(P(Y = c \mid X = x)\), with the most frequent class as the class prediction (Cover and Hart 1967). kNN fits no parameters; the training data are the model, and the computation occurs at prediction time.

Weighted kNN weights each neighbor by a decreasing function, a kernel, of its distance to \(x\), so that closer neighbors contribute more (Hechenbichler and Schliep 2004).

24.2 Distance

Closeness is measured by a distance between feature vectors, most commonly the Euclidean distance \(\lVert x - x' \rVert_2\), or more generally the Minkowski distance \(\left(\sum_j \lvert x_j - x'_j \rvert^q\right)^{1/q}\) (AMDS: Distance, Other norms). Every feature contributes to the distance in proportion to its scale: a feature measured in thousands dominates one measured in fractions. Features are therefore standardized before distances are computed (Section 12.3), and categorical features are one-hot encoded. The distance treats all features as equally relevant; a feature unrelated to the outcome adds noise to every distance.

24.3 The number of neighbors

\(k\) controls the bias–variance tradeoff (Chapter 16). With \(k = 1\), the prediction at a training case is its own outcome, so the training error is zero and the fit follows every fluctuation of the data: high variance. With large \(k\), each prediction averages over a large region, in which the true function may vary: high bias. At \(k = n\), every prediction is the mean outcome. Figure 24.1 shows kNN regression fits to the simulated data of Figure 4.1 for three values of \(k\).

Figure 24.1: kNN regression with \(k\) = 1, 10 and 50 on 100 simulated cases. Small \(k\) follows the noise; large \(k\) flattens the function.

The number of training cases relative to \(k\) determines the effective number of parameters, approximately \(n / k\), the number of non-overlapping neighborhoods (Hastie et al. 2009). \(k\) is chosen by resampling (Chapter 20).

24.4 The curse of dimensionality

Local methods require neighbors that are close. In high dimensions, cases are far apart: to capture a fixed fraction \(r\) of uniformly distributed cases in a hypercube of \(p\) dimensions, a neighborhood must span a fraction \(r^{1/p}\) of the range of each feature. With \(p = 10\), a neighborhood containing 1% of the cases spans \(0.01^{1/10} \approx 0.63\) of each feature’s range, and is no longer local. Distances also concentrate: as \(p\) grows, the ratio of the distance to the nearest case and the distance to the farthest approaches 1 (Figure 24.2), so that the nearest neighbors are barely nearer than any other case.

Figure 24.2: Ratio of the distance to the nearest and to the farthest of 499 uniformly distributed cases, by dimension (mean of 50 simulations).

kNN therefore performs best with few features, or when the outcome depends on few features and the others are removed or down-weighted.

24.5 Properties

  • kNN makes no assumption about the form of the function, and can represent any shape given enough data.
  • With \(k = 1\), its asymptotic error is at most twice the Bayes error (Cover and Hart 1967); when \(k\) and \(n/k\) both grow with \(n\), its error converges to the Bayes error (Stone 1977).
  • It requires standardized, informative features; it is sensitive to irrelevant features and to the curse of dimensionality.
  • It stores all training data, and the cost of a prediction grows with \(n\).
  • Its probability estimates for classification take only the values \(0, 1/k, \dots, 1\).

24.6 Summary

  • kNN predicts from the outcomes of the \(k\) closest training cases, without fitting a parametric function.
  • Features are standardized before distances are computed.
  • \(k\) controls the bias–variance tradeoff and is chosen by resampling.
  • In high dimensions neighborhoods are not local, which limits kNN to problems with few relevant features.

24.7 Further reading