actually performed. k-NN has some strong consistency results. As the amount of data approaches infinity, the two-class k-NN algorithm is guaranteed to yield an error rate no worse than twice the Bayes error rate (the minimum achievable error rate given the distribution of the data). Various improvements to the k-NN speed are possible by using proximity graphs. For multi-class k-NN classification, Cover and Hart (1967) prove an upper bound error rate of where is the Bayes error rate (which is the minimal error rate possible), is the k-NN error rate, and is the number of classes in the problem. For and as the Bayesian error rate approaches zero, this limit reduces to "not more than twice the Bayesian error rate". Error rates There are many results on the error rate of the nearest neighbour classifiers. The -nearest neighbour classifier is strongly (that is for any joint distribution on ) consistent provided diverges and converges to zero as . Let denote the nearest neighbour classifier based on a training set of size . Under certain regularity conditions, the excess risk yields the following asymptotic expansion for some constants and . The choice offers a trade off between the two terms in the above display, for which the -nearest neighbour error converges to the Bayes error at the optimal (minimax) rate . Metric learning The K-nearest neighbor classification performance can often be significantly improved through (supervised) metric learning. Popular algorithms are neighbourhood components analysis and large margin nearest neighbor. Supervised metric learning algorithms use the label information to learn a new metric or pseudo-metric. Feature extraction When the input data to an algorithm is too large to be processed and it is suspected to be redundant (e.g. the same measurement in both feet and meters) then the input data will be transformed into a reduced representation set of features (also named features vector). Transforming the input data into the set of features is called feature extraction. If the features extracted are carefully chosen it is expected that the features set will extract the relevant information from the input data in order to perform the desired task using this reduced representation instead of the full size input. Feature extraction is performed on raw data prior to applying k-NN algorithm on the transformed data in feature space. An example of a typical computer vision computation pipeline for face recognition using k-NN including feature extraction