What is k-Nearest Neighbors (kNN)?
Definition
The k-nearest neighbors (kNN) algorithm is a supervised learning method that classifies a point by the majority class of its k closest stored points.
kNN has no explicit training step. It stores the labelled examples and does its computation when a query arrives. Scikit-learn calls this instance-based, non-generalizing learning.
How it works
- Choose k and a distance measure. Euclidean distance is the most common choice.
- Find the k stored points that are closest to the query point.
- Give the query point the class that most of those k points have.
By default every neighbor has one vote. In weighted kNN, nearer neighbors count more, for example with a weight of 1/d, where d is the distance to the neighbor.
Choosing k
The best value of k depends on the data. A larger k suppresses noise but makes the class boundaries less distinct. Cross-validation finds a good value of k from the data. For two classes, an odd k avoids tied votes.
Limits
- If the features have different units or scales, normalizing each feature can greatly improve accuracy.
- A brute-force search compares the query with every stored point. This becomes infeasible when the number of points grows.
- Tree-based search, such as a KD tree, is fast only in low dimensions (below about 20). In high dimensions, Euclidean distance is also less useful, because all vectors are almost equally far from the query.
- Libraries such as Faiss search large sets of vectors. They offer exact search and compressed indexes. Compressed indexes give a less precise search.
History
Evelyn Fix and Joseph Hodges first developed the method in 1951 in a report for the USAF School of Aviation Medicine. Thomas Cover and Hart published “Nearest neighbor pattern classification” in 1967. With unlimited training data, the error rate of the 1-nearest-neighbor rule is no worse than twice the Bayes error rate.
Frequently Asked Questions
- How do you choose k in kNN?
- Test several values of k with cross-validation and keep the one that gives the best result on held-out data. The best k depends on the data. A larger k suppresses noise but makes the class boundaries less distinct. For a two-class problem, an odd k avoids tied votes.
- Does kNN need training?
- No, kNN has no explicit training step. It stores the labelled examples and does all of its computation when a query arrives. Scikit-learn calls this instance-based, non-generalizing learning.
- What is weighted kNN?
- Weighted kNN lets nearer neighbors count more than farther ones in the vote. A common choice is a weight of 1/d, where d is the distance to the neighbor. In scikit-learn the default is uniform weights, and weights = 'distance' gives weights proportional to the inverse of the distance.
References
- sklearn-neighbors
- scikit-learn User Guide, 1.6 Nearest Neighbors scikit-learn
- wikipedia-knn
- k-nearest neighbors algorithm Wikipedia
- faiss-readme
- Faiss: a library for efficient similarity search and clustering of dense vectors Meta Research (facebookresearch/faiss on GitHub)
- faiss-getting-started
- Faiss wiki: Getting started Meta Research (facebookresearch/faiss on GitHub)
This is a reference entry. TarmacView provides drone inspection services and doesn't sell the equipment or materials described in this glossary.