k-NN
1. Purpose & Motivation
1.1 Why k-NN exists
- Some problems are best solved by reasoning from similar past examples
- No training phase is needed, making it ideal for small or evolving datasets
- It provides a non-parametric baseline that makes no assumptions about data distribution
1.2 The core problem it solves
Classify or predict by finding the k most similar examples in the training set and aggregating their labels or values.
2. Definition & Core Idea
2.1 Formal definition
k-Nearest Neighbors is a non-parametric, instance-based algorithm that stores the entire training set and makes predictions by finding the k closest data points to a query point using a distance metric, then voting (classification) or averaging (regression).
2.2 Intuitive mental model
"To judge an unknown fruit, look at the k most similar fruits you have seen before and go with the majority label."
3. How It Works
3.1 Algorithm steps
- Store all training examples
- Given a new query point, compute distance to every training example
- Select the k nearest neighbors
- Classification: Return the majority class among the k neighbors
- Regression: Return the mean (or weighted mean) of the k neighbors' values
3.2 Distance metrics
| Metric | Formula concept | Best for |
|---|---|---|
| Euclidean | Straight-line distance | Continuous, scaled features |
| Manhattan | Sum of absolute differences | Grid-like or sparse data |
| Cosine | Angle between vectors | Text and high-dimensional |
| Minkowski | Generalized (p-norm) | Tunable via parameter p |
4. Choosing k
4.1 Effect of k
- Small k (e.g., 1-3): Low bias, high variance; sensitive to noise
- Large k: High bias, low variance; smoother decision boundaries
- k = 1: Nearest neighbor; Voronoi tessellation of feature space
4.2 How to select k
- Use cross-validation to find the k that minimizes validation error
- Odd values of k avoid ties in binary classification
- Typical range: 3 to 20, depending on dataset size
5. Practical Considerations
5.1 Feature scaling
- k-NN is distance-based, so features must be normalized or standardized
- Without scaling, features with larger ranges dominate the distance
5.2 Curse of dimensionality
- In high dimensions, distances become nearly uniform
- Performance degrades as feature count grows
- Dimensionality reduction (PCA, feature selection) helps significantly
5.3 Computational cost
- Prediction requires scanning all training points: O(n * d) per query
- KD-trees and Ball trees accelerate neighbor search for moderate dimensions
6. Strengths & Limitations
6.1 Strengths
- No training phase; adapts instantly to new data
- Non-parametric: no assumptions about data distribution
- Simple to understand and implement
6.2 Limitations
- Slow prediction for large datasets
- Sensitive to irrelevant features and feature scale
- Memory-intensive (stores entire training set)
7. One-Sentence Summary
k-NN classifies new data points by finding the k most similar training examples and taking a majority vote, requiring no explicit training phase.