# Nearest neighbor classification

K nearest neighbors in a two-dimensional point set with k = 1 (dark blue) and k = 5 (light blue). The radius of the circles is not fixed.

The closest neighbor classification is a nonparametric method for estimating probability density functions . The resulting k-Nearest-Neighbor-Algorithm ( KNN , in English "k-nearest-neighbor algorithm") is a classification method in which a class is assigned taking its closest neighbors into account . The part of the learning consists of simply saving the training examples, which is also known as lazy learning ("sluggish learning"). Data normalization can increase the accuracy of this algorithm. ${\ displaystyle k}$

## k nearest neighbor algorithm

The classification of an object (often described by a feature vector ) takes place in the simplest case by majority decision. The k next already classified objects of participate in the majority decision . Many distance measures are conceivable ( Euclidean distance , Manhattan metric , etc.). is assigned to the class that has the greatest number of objects of these neighbors. For two classes a tie in the majority decision can be prevented by an odd one. ${\ displaystyle x \ in \ mathbb {R} ^ {n}}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle k}$${\ displaystyle k}$

Voronoi diagram with seven support points

For a small one, there is a risk that noise in the training data will worsen the classification results. A Voronoi diagram results for . If the choice is too large, there is a risk of including points with a large margin in the classification decision. This risk is particularly great if the training data are not evenly distributed or if only a few examples are available. If the training data is not evenly distributed, a weighted distance function can be used, which assigns a higher weight to closer points than to points further away. A practical problem is also the storage and computation effort of the algorithm in the case of high-dimensional spaces and a lot of training data. ${\ displaystyle k}$${\ displaystyle k = 1}$${\ displaystyle k}$${\ displaystyle x}$