K-Nearest Neighbors
K-Nearest Neighbors (KNN) is a simple, non-parametric supervised learning algorithm that classifies or predicts a new data point based on the majority label or average value of its K closest points in the training data.
Definition
K-Nearest Neighbors (KNN) is a simple, non-parametric supervised learning algorithm that classifies or predicts a new data point based on the majority label or average value of its K closest points in the training data.
Overview
KNN is often called a 'lazy learning' algorithm because it performs no explicit training phase in the usual sense — it simply stores the entire training dataset and defers all computation to prediction time. To classify a new point, it computes the distance (commonly Euclidean, though Manhattan or other metrics can be used) between that point and every point in the training set, identifies the K closest neighbors, and assigns the majority class among them (for classification) or averages their target values (for regression). The choice of K is a critical hyperparameter: a small K makes the model sensitive to noise and prone to overfitting, following the idiosyncrasies of individual nearby points, while a large K smooths the decision boundary but can wash out meaningful local structure and blur distinctions between classes, potentially underfitting. K is usually chosen via cross-validation, and it's common practice to pick an odd number for binary classification to avoid tied votes. Because predictions rely entirely on distance calculations, feature scaling is essential — unscaled features with large numeric ranges would otherwise dominate the distance metric. KNN's simplicity and lack of a training phase come at the cost of prediction speed: it must scan (or, with spatial indexing structures like KD-trees or ball trees, at least partially compare against) the full training dataset for every single prediction, making inference scale poorly with dataset size and dimensionality — a challenge known as the curse of dimensionality, where distances between points become less meaningful in very high-dimensional spaces. Despite these scalability limits, KNN remains a valuable teaching tool and a reasonable baseline for smaller datasets, and its core distance-based nearest-neighbor idea underlies related techniques used in recommendation systems and, notably, retrieval components of modern RAG pipelines that search vector embeddings for similar content.
Key Concepts
- Non-parametric — makes no assumption about the underlying data distribution
- 'Lazy learning' — stores training data and defers computation to prediction time
- Classifies via majority vote or predicts via averaging among K nearest neighbors
- K is a key hyperparameter, typically chosen via cross-validation
- Requires feature scaling since it relies directly on distance metrics
- Supports different distance metrics (Euclidean, Manhattan, cosine, etc.)
- Prediction cost scales with dataset size unless spatial indexing (KD-tree, ball tree) is used
- Conceptually related to vector similarity search used in retrieval systems