K-nearest neighbors algorithm

The nearest neighbor classification is a parameter-free method for estimating probability density functions. The resulting k- Nearest Neighbor algorithm (KNN to German "k - nearest -neighbor algorithm ") is a classification method, in which a class assignment is made in consideration of its nearest neighbors. The part of learning consists system of plain storing the training examples, which is also known as lazy learning ( " lazy learning").

K- Nearest Neighbor algorithm

The classification of an object ( often described by a feature vector) in the simplest case by a majority decision. The k nearest objects already classified by participating in the majority decision. Here are many distance measures are possible ( Euclidean distance, Manhattan metric, etc.). is assigned to the class that has the greatest number of objects that neighbor.

For a small selected there is a risk that noise degrades the classification results in the training data. For results in a Voronoi diagram. If too large, there is a danger points with a large distance to the classification decision to involve. This danger is particularly great when the training data is not uniformly distributed or only a few examples are available. At non-uniformly distributed training data, a weighted distance function can be used, the detailed point assigns a higher weight than more distant. A practical problem is the storage and computational complexity of the algorithm in high-dimensional spaces and many training data.