K-nearest neighbors: classifying data by its closest known examples
K-nearest neighbors (KNN) is a non-parametric supervised learning method that assigns a label to a new point by voting among its k closest training examples. It is a lazy learner that stores the training data and computes distances at prediction time. Choosing the right distance metric and k value is essential for accuracy.
How KNN classifies data
K-nearest neighbors (KNN) is a non-parametric, supervised learning classifier that uses proximity to make classifications. The Cornell lecture notes state that the k-NN algorithm assumes similar inputs have similar outputs, so a new point receives the label most common among its nearest training neighbors.
For classification tasks, the algorithm performs a majority vote among the k nearest points; for regression, it averages their values. KNN is a lazy learning method because it only stores the training set and defers all computation until a prediction is requested, as described in the IBM overview.
The choice of k affects the bias-variance tradeoff. A small k may overfit and follow noise, while a large k can oversmooth the decision boundary. Using an odd k helps avoid ties when there are two classes.
Distance metrics and choosing k
The distance metric defines which points are considered neighbors. The most common choice is Euclidean distance, which measures straight-line distance between real-valued vectors. Other options include Manhattan distance (the sum of absolute differences) and Minkowski distance as a generalization. The scikit-learn user guide notes that Euclidean distance is the standard and supports arbitrary Minkowski metrics.
The value of k determines how many neighbors influence the classification. Lower k gives higher variance and lower bias, while higher k reduces variance but increases bias. The optimal k depends on the data; noisy data often benefits from a larger k. A rule of thumb is to choose an odd k to avoid ties.
KNN in image classification
Image classification is a classic application of nearest-neighbor methods. The Stanford course notes describe a dataset such as CIFAR-10, which contains 60,000 tiny images labeled with one of 10 classes. The training set holds 50,000 images and the test set 10,000, as explained in the Stanford CS231n notes.
In a direct nearest-neighbor approach, each test image is compared pixel by pixel to all training images using a distance metric. The label of the closest training image (or the majority among k neighbors) is assigned. This simple method highlights the data-driven nature of the algorithm, though it is rarely used for large-scale image recognition due to its computational cost and sensitivity to variations like lighting and occlusion.
Evaluating a KNN model
Accuracy is a common metric for classification models, defined as the number of correct predictions divided by the total number of predictions. However, accuracy can be misleading for imbalanced datasets, as the Google Machine Learning Glossary points out. For example, a model that always predicts the majority class can have high accuracy but no predictive power.
When evaluating KNN, it is also important to consider the computational cost. Because KNN stores all training data, prediction time grows with the dataset size. Using fast indexing structures such as KD-trees or ball trees can speed up neighbor searches, while brute-force comparisons remain straightforward for small datasets.
| Metric | p value | Description |
|---|---|---|
| Euclidean | 2 | Straight-line distance between points in real-valued vector space. |
| Manhattan | 1 | Sum of absolute differences along each dimension, also called city block distance. |
| Minkowski | >=1 | Generalization that reduces to Euclidean when p=2 and Manhattan when p=1. |
| Hamming | N/A | Number of positions where two Boolean or string vectors differ. |
Frequently asked questions
What does 'k' mean in KNN?
The k value sets how many nearest neighbors are examined before a label is assigned.
Why is KNN called a lazy learner?
Because it stores the entire training dataset and does no computation until a prediction is requested.
How should the distance metric be chosen?
The metric should reflect the notion of similarity for the data; Euclidean is common for continuous features, while Hamming works for binary or string data.
What happens if k equals the number of training points?
The classifier always predicts the most frequent class in the training set, yielding a constant predictor.