k-Nearest Neighbors
A simple instance-based machine learning algorithm that classifies or regresses by majority vote among the k closest training examples.
k-nearest neighbors (k-NN) is a machine learning algorithm that makes predictions by looking at the k training examples closest to a new query point. For classification, the query receives the majority class among its k nearest neighbors; for regression, it receives their average value. It belongs to the family of instance-based (lazy) learning: no model is built during training — the training data itself is the model, and all computation happens at prediction time.
The core ingredient is the distance metric, which defines what nearest means. The most common is Euclidean distance, the straight-line distance in feature space; Manhattan distance sums absolute coordinate differences, and cosine similarity is preferred for text and embeddings where direction matters more than magnitude. The choice of metric should match the geometry of the problem, and features must be normalized (scaled to comparable ranges) or the largest-magnitude feature will dominate the distance — a person's income in dollars would otherwise dwarf their age in years.
Choosing k controls the bias–variance trade-off, the same tension analyzed in overfitting and regularization: a small k (say k = 1) makes the decision boundary extremely flexible and prone to overfitting noise, while a large k smooths the boundary and can underfit. Cross-validation is the standard way to choose k. Two practical problems plague k-NN: the curse of dimensionality — in high-dimensional spaces all points become nearly equidistant, so nearest-neighbor structure degrades — and prediction cost, since every query must scan the training set (data structures such as k-d trees or approximate nearest-neighbor indexes mitigate this).
Despite its simplicity, k-NN is competitive on many problems and is a standard baseline that more complex models must beat. It is used in recommendation systems, handwriting recognition, and anomaly detection. Its non-parametric nature means it makes no strong assumptions about the shape of the data, and its predictions are easy to explain — the decision is literally visible in the neighboring points. k-NN also connects to k-means clustering: clustering is the unsupervised cousin that groups points without labels, while k-NN classifies labeled points, and both depend on the same geometry of distances.
Tags
classification distance metrics k-nn machine learning