Overview
K-Nearest Neighbors (KNN) is a simple, instance-based learning algorithm that makes predictions based on the k closest training examples in the feature space. It’s a lazy learning algorithm because it doesn’t build an explicit model during training.
How It Works
- Store all training data (no explicit training phase)
- For a new data point:
- Calculate distance to all training points
- Find the k nearest neighbors
- Classification: Majority vote among k neighbors
- Regression: Average of k neighbors’ values
Distance Metrics
KNN relies entirely on distance calculations. Common choices:
- Euclidean Distance (most common): Straight-line distance
- Manhattan Distance: Sum of absolute differences
- Minkowski Distance: Generalization of Euclidean and Manhattan
- Cosine Similarity: For high-dimensional sparse data
The K Parameter
Choosing k:
| k Value | Effect | Best For |
|---|---|---|
| k = 1 | High variance, low bias | When data is noise-free |
| k = 3-5 | Balanced | Small datasets |
| k = √n | Common heuristic | General purpose |
| k = large | Low variance, high bias | Noisy data, smooth boundaries |
Finding optimal k:
- Use cross-validation
- Try odd values for binary classification (avoids ties)
- Plot accuracy vs k (elbow method)
Classification
Prediction: Majority vote among k nearest neighbors
Example (k=5):
New point: ?
5 Nearest neighbors:
- Class A: 3 votes
- Class B: 2 votes
Prediction: Class A
Weighted voting: Weight votes by inverse distance (closer neighbors have more influence)
Regression
Prediction: Average (or weighted average) of k nearest neighbors
Example (k=3):
3 Nearest neighbors with values: [10, 12, 11]
Prediction: 11.0 (mean)
With distance weighting:
- Neighbor 1: value=10, distance=0.5, weight=2.0
- Neighbor 2: value=12, distance=1.0, weight=1.0
- Neighbor 3: value=11, distance=2.0, weight=0.5
Weighted prediction: (10×2 + 12×1 + 11×0.5) / (2 + 1 + 0.5) = 10.86
Advantages
- Simple and Intuitive: Easy to understand and implement
- No Training Phase: Just stores data (lazy learning)
- Naturally Multi-class: Handles multiple classes without modification
- Non-parametric: Makes no assumptions about data distribution
- Versatile: Works for classification and regression
- Adapts to New Data: Just add new points to training set
Disadvantages
- Computationally Expensive at Prediction: Must compute distance to all training points
- Memory Intensive: Stores entire training dataset
- Sensitive to Feature Scaling: Features with larger scales dominate
- Curse of Dimensionality: Performance degrades in high dimensions
- Sensitive to Irrelevant Features: All features used equally by default
- Poor with Imbalanced Data: Majority class can dominate
- No Interpretability: Doesn’t learn an explicit model
Preprocessing Requirements
See K Nearest Neigbour - Preprocessing.
Hyperparameters
See K Nearest Neigbour - Hyperparameters.
Weighted KNN
See K Nearest Neigbour - Weighted KNN And Outlier Detection.
Practical Considerations
See K Nearest Neigbour - Practical Use.
Variants
See K Nearest Neigbour - Variants.
Implementation Example
See K Nearest Neigbour - Implementation Example.
References
- Scikit-learn documentation
- Introduction to Statistical Learning (ISLR)
- Pattern Recognition and Machine Learning (Bishop)