kNN (k-Nearest Neighbors)

k-Nearest Neighbors (kNN) is one of the most intuitive algorithms in machine learning, operating on a deceptively simple principle: to classify or predict a value for a new data point, find the k most similar examples in the training set and let them vote. In classification tasks, the new point inherits the majority class among its k neighbors; in regression, it receives the average of their output values. The algorithm is entirely non-parametric, meaning it makes no assumptions about the underlying data distribution — the training data itself serves as the model.

The mechanics of kNN hinge on two key choices: the value of k and the distance metric used to define "nearness." Common metrics include Euclidean distance (straight-line distance in feature space), Manhattan distance (sum of absolute differences), and Hamming distance (useful for categorical data). A small k makes the model sensitive to noise and prone to overfitting, while a large k smooths decision boundaries but risks underfitting. Selecting the right k typically involves cross-validation. Because kNN stores the entire training dataset and defers all computation to query time, it is classified as a lazy learner — there is no explicit training phase, but prediction can be slow and memory-intensive for large datasets.

Despite its simplicity, kNN remains practically relevant and theoretically important. It is often used as a baseline model, for anomaly detection, and in recommendation systems. Its performance degrades in high-dimensional spaces — a phenomenon known as the curse of dimensionality — where distances between points become increasingly uniform, making "nearness" meaningless. Dimensionality reduction techniques like PCA are frequently applied as preprocessing steps to mitigate this.

kNN also serves as a conceptual anchor for understanding more sophisticated algorithms. Its decision boundaries are inherently local and non-linear, offering a useful contrast to linear models. Approximate nearest neighbor methods (e.g., KD-trees, ball trees, FAISS) have extended kNN's scalability, keeping it relevant even as dataset sizes have grown dramatically in the modern deep learning era.