knn
**K-Nearest Neighbors (KNN)** is a **"lazy learning" algorithm that makes predictions by finding the K most similar training examples to a new data point and using their labels to vote on the prediction** — requiring no training phase at all (the entire dataset IS the model), making it the simplest conceptual algorithm in machine learning but also one of the slowest at inference time because every prediction requires computing distances to every stored example.
**What Is KNN?**
- **Definition**: A non-parametric, instance-based algorithm that stores the entire training dataset and classifies new points by majority vote of their K nearest neighbors in feature space — no model is learned, no parameters are optimized, and all computation happens at prediction time.
- **"Lazy" Learning**: Unlike neural networks or decision trees that learn during training and predict quickly, KNN does zero work during training (just stores the data) and all work during prediction (compute distances to every point).
- **Intuition**: "Tell me who your neighbors are, and I'll tell you who you are" — if the 5 nearest houses to yours sold for $400K-$450K, your house is probably worth about $425K.
**How KNN Works**
| Step | Process | Example |
|------|---------|---------|
| 1. **Store** | Save all training data | 10,000 labeled examples in memory |
| 2. **New point arrives** | Calculate distance to ALL stored points | Compare against every example |
| 3. **Find K nearest** | Sort by distance, take top K | K=5: find 5 closest neighbors |
| 4. **Vote (Classification)** | Majority label wins | 3 "Cat" + 2 "Dog" → predict "Cat" |
| 4. **Average (Regression)** | Mean of K neighbor values | ($400K + $420K + $450K) / 3 = $423K |
**Distance Metrics**
| Metric | Formula | Best For | Intuition |
|--------|---------|----------|-----------|
| **Euclidean** | $sqrt{sum(x_i - y_i)^2}$ | General numeric data | Straight-line distance |
| **Manhattan** | $sum|x_i - y_i|$ | Grid-like data, sparse features | "Taxi cab" distance |
| **Cosine** | $1 - frac{A cdot B}{|A||B|}$ | Text / embeddings | Angle between vectors |
| **Minkowski** | $(sum|x_i - y_i|^p)^{1/p}$ | Generalizes Euclidean/Manhattan | Parameterized by p |
**Choosing K**
| K Value | Behavior | Risk |
|---------|----------|------|
| **K = 1** | Nearest single point decides | High variance — sensitive to noise and outliers |
| **K = 3-7** | Good balance for most datasets | Sweet spot for many practical problems |
| **K = large** | Over-smoothed decision boundaries | High bias — ignores local patterns |
| **K = N** | Predicts the majority class always | Useless (just predicts the most common label) |
**Scaling is Critical**: KNN uses distance — if Age (0-100) and Salary (0-100,000) are both features, Salary dominates all distances. Always standardize features before using KNN.
**Limitations and Solutions**
| Limitation | Impact | Solution |
|-----------|--------|----------|
| **Slow inference O(N×D)** | Every prediction scans all data | Approximate Nearest Neighbor (HNSW, Annoy, FAISS) |
| **Curse of dimensionality** | Distances become meaningless in 100+ dims | Dimensionality reduction (PCA, UMAP) first |
| **Memory-intensive** | Must store entire training set | KD-Trees or Ball Trees for efficient indexing |
| **Feature scaling required** | Unscaled features bias distances | StandardScaler before KNN |
**K-Nearest Neighbors is the conceptually simplest algorithm in machine learning** — requiring no training, no parameter optimization, and no mathematical complexity, making it the perfect teaching algorithm and a surprisingly effective baseline, with its inference speed limitation solved by approximate nearest neighbor libraries like FAISS and HNSW that power production search and recommendation systems.