K-nearest neighbor algorithm

In pattern recognition, the k-nearest neighbors algorithm (k-NN) is a non-parametric method used for classification and regression. In both cases, the input consists of the k closest training examples in the feature space. The output depends on whether k-NN is used for classification or regression:

k-NN is a type of instance-based learning, or lazy learning, where the function is only approximated locally and all computation is deferred until classification. The k-NN algorithm is among the simplest of all machine learning algorithms.

Both for classification and regression, it can be useful to assign weight to the contributions of the neighbors, so that the nearer neighbors contribute more to the average than the more distant ones. For example, a common weighting scheme consists in giving each neighbor a weight of 1/d, where d is the distance to the neighbor.

The neighbors are taken from a set of objects for which the class (for k-NN classification) or the object property value (for k-NN regression) is known. This can be thought of as the training set for the algorithm, though no explicit training step is required.

A shortcoming of the k-NN algorithm is that it is sensitive to the local structure of the data. The algorithm is not to be confused with k-means, another popular machine learning technique.

Suppose we have pairs ${\displaystyle (X,Y),(X_{1},Y_{1}),\dots ,(X_{n},Y_{n})}$ taking values in ${\displaystyle \mathbb {R} ^{d}\times \{1,2\}}$, where Y is the class label of X, so that ${\displaystyle X|Y=r\sim P_{r}}$ for ${\displaystyle r=1,2}$ (and probability distributions ${\displaystyle P_{r}}$). Given some norm ${\displaystyle \|\cdot \|}$ on ${\displaystyle \mathbb {R} ^{d}}$ and a point ${\displaystyle x\in \mathbb {R} ^{d}}$, let ${\displaystyle (X_{(1)},Y_{(1)}),\dots ,(X_{(n)},Y_{(n)})}$ be a reordering of the training data such that ${\displaystyle \|X_{(1)}-x\|\leq \dots \leq \|X_{(n)}-x\|}$.

...
Wikipedia