K-Nearest Neighbours (KNN) is one of the simplest and most intuitive machine learning algorithms. To classify a new data point, KNN finds the k training points closest to it (using Euclidean distance, or other distance metrics), and assigns the class that appears most frequently among those k neighbours — a democratic vote. With k=1, the algorithm simply assigns the class of the single nearest neighbour; with larger k, the decision is smoother and less sensitive to individual outliers.
KNN is a non-parametric, instance-based (lazy) learning algorithm: it makes no assumptions about the underlying data distribution and stores all training examples without learning an explicit model. Prediction time scales as O(n·d) for n training points in d dimensions, which can be expensive for large datasets. Data structures like KD-trees and ball trees reduce the search cost to O(log n) for low-dimensional data, while approximate nearest neighbour algorithms handle high-dimensional data at the cost of some accuracy.
KNN is used for classification (spam detection, image recognition, medical diagnosis based on similar patient records), regression (predicting a continuous value as the average of k neighbours' values), and anomaly detection (unusual points have few or no close neighbours). Its main limitations are sensitivity to irrelevant features (which contribute equally to distance), computational cost at prediction time, and poor performance in high dimensions (the curse of dimensionality, where all points become approximately equidistant).
KNN computes the distance from the new point to every training point, identifies the k closest ones, and takes a majority vote of their labels to assign the class. For regression, it averages the k neighbours' target values. The choice of k controls the trade-off between underfitting (large k, very smooth boundary) and overfitting (small k, noisy boundary).
Choose k by cross-validation: train on a subset of data, test on a held-out validation set, and evaluate accuracy for different values of k. Typically k is odd to avoid ties, and k=√n (where n is training set size) is a common rule of thumb. The optimal k balances bias (too large k oversmoothes) and variance (too small k is noisy).
Euclidean distance (straight-line distance) is the default. Manhattan distance (sum of absolute differences) is useful when features have different units or when the data has a grid-like structure. Minkowski distance generalises both. For text or categorical data, Hamming distance or cosine similarity may be more appropriate. Feature scaling (normalisation or standardisation) is essential before computing distances.
In high-dimensional spaces, all data points become approximately equidistant from each other, making the concept of nearest neighbours meaningless. As dimensions increase, the volume of space grows exponentially while the data stays the same size, so neighbourhoods must expand enormously to include any points. KNN degrades rapidly in performance beyond roughly 10–20 dimensions without dimensionality reduction.
KNN is a supervised classification or regression algorithm: it uses labelled training data to predict labels for new points. K-means is an unsupervised clustering algorithm: it finds natural groupings in unlabelled data. Despite sharing the letter k (and both involving distances and neighbours), they solve entirely different problems with different assumptions and methods.