Skip to content

k-NN classification🔗

K-Nearest Neighbors (k-NN)🔗

K-Nearest Neighbors (k-NN) is a classification approach that assigns an unknown feature vector to a class based on the closest training samples in the feature space.

Unlike statistical classifiers such as GMM, which estimate class probability distributions, k-NN does not learn an explicit model of the class distributions. Instead, the labeled training samples are stored and directly used during classification.

The classification is based on the k nearest neighbors of the unknown sample. Depending on the selected classification method, the class can be determined using the frequency of the neighboring classes, a distance-weighted frequency, or the distances of the neighbors.

Figure 1: Principle of k-NN classification

The choice of k influences the behavior of the classifier. A small value allows the classifier to follow local structures in the feature space but makes it more sensitive to individual training samples and noise. Larger values generally result in a more robust classification and smoother class boundaries, but increase the classification time.

Nearest neighbors🔗

For an unknown feature vector, the k-NN classifier searches for the k training samples with the smallest distance to the unknown sample.

The selected neighbors form the basis for the classification decision. For example, a simple majority vote assigns the class that occurs most frequently among the k nearest neighbors.

A distance-weighted vote additionally takes the distances of the neighbors into account. Neighbors that are closer to the unknown sample therefore have a greater influence on the classification result.

The nearest-neighbor search can be performed approximately to achieve a fast classification. The search accuracy and runtime can be controlled using the corresponding search parameters.

Training🔗

During training, the labeled feature vectors are added to the classifier and an internal representation is prepared for an efficient nearest-neighbor search.

Unlike parametric classifiers, k-NN does not optimize a set of model parameters that describes the class distributions or decision boundaries. The training data itself remains the basis for the subsequent classification.

The quality of the classifier therefore strongly depends on the representativeness of the training data. The training samples should cover the expected variations within each class.

Feature scaling can also have a significant influence on the classification because the nearest neighbors are determined using distances in the feature space.

Further information on parameter optimization can be found in the Optimization chapter.

Typical applications🔗

k-NN classifiers can be applied to a wide range of classification tasks. Typical applications include

  • general feature classification,

  • image segmentation, and

  • optical character recognition (OCR).

Compared to parametric classifiers such as GMM or MLP, k-NN classification is particularly simple because the training samples are used directly during classification. This also makes it easy to add new training samples.

The main disadvantage is that classification can become slower as the number of training samples increases. In addition, the training data has to be stored by the classifier.