Most machine learning algorithms learn a model during training and then discard the training data. K-Nearest Neighbors (KNN) does something different: it keeps all the training data and makes predictions by looking at the K closest examples to a new query point. This “lazy learning” approach is very simple. There are no weights to optimize, no gradients to compute, and no loss functions to minimize. The training data is the model. Even with this simplicity, KNN can produce complex decision boundaries that adapt to any shape in the data. Let us build KNN from scratch and understand how it works.
In this guide, you will:
- Understand the three steps of KNN: store, find, and vote
- See how the choice of K controls overfitting and underfitting
- Compare distance metrics like Euclidean, Manhattan, and Chebyshev
- Use KNN for regression by averaging neighbor values
- Learn why KNN struggles in high dimensions
1. How KNN Works
The KNN algorithm has three steps:
- Store: keep all training data (that is the entire “training” phase).
- Find: locate the K nearest neighbors to the query point.
- Vote: for classification, the majority class among K neighbors wins. For regression, take the average of their values.
The distance between two points \(\mathbf{x}^{(a)}\) and \(\mathbf{x}^{(b)}\) in \(d\) dimensions is typically the Euclidean distance:
\[d(\mathbf{x}^{(a)}, \mathbf{x}^{(b)}) = \sqrt{\sum_{i=1}^{d}(x_i^{(a)} - x_i^{(b)})^2}\]For \(K\) neighbors, the predicted class is:
\[\hat{y} = \text{mode}(y^{(1)}, y^{(2)}, \ldots, y^{(K)})\]where \(y^{(1)}, \ldots, y^{(K)}\) are the labels of the K nearest neighbors. Click anywhere on the canvas below to place a query point. The K nearest neighbors are highlighted with connecting lines, and the majority vote decides the class. Use the K slider to change how many neighbors are considered.
With K=1, the prediction always matches the single closest point. With larger K, the neighborhood vote matters and predictions become more stable.
2. Decision Boundary Canvas
The decision boundary is the line (or curve) where the predicted class changes. For KNN, this boundary is determined entirely by the data points and the value of K. Left-click to add Class A points and shift+click (or right-click) to add Class B points; the boundary updates in real time with pixel-level coloring.
Try placing a few Class A points on the left and Class B points on the right, then add a single Class A point deep inside Class B territory. It creates an island in the boundary, KNN is memorizing that individual point.
3. The K Slider: Overfitting vs. Underfitting
The choice of K is the most important decision in KNN. It controls the bias-variance tradeoff:
- Small K (e.g. K=1): the boundary is jagged and follows every point, including noise. This is overfitting (low bias, high variance).
- Large K (e.g. K=30): the boundary is very smooth and may ignore meaningful patterns. This is underfitting (high bias, low variance).
Drag the K slider and watch the decision boundary transform from jagged to smooth. The leave-one-out accuracy shown below is a proxy for how well each K generalizes: it is usually highest at a moderate K, and lower at K=1 (which memorizes noise) and at very large K (which over-smooths the boundary).
With K=1, leave-one-out accuracy is often lower than with moderate K. The model fits the training data perfectly but is fragile to noise. The sweet spot is usually somewhere in the middle.
4. Distance Metrics: Euclidean vs Manhattan vs Chebyshev
The choice of distance metric changes what “close” means, and therefore changes the shape of neighborhoods and decision boundaries.
- Euclidean distance (L2): \(d = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}\). This gives circular neighborhoods.
- Manhattan distance (L1): \(d = \vert x_1-x_2 \vert + \vert y_1-y_2 \vert\). This gives diamond-shaped neighborhoods.
- Chebyshev distance (L-infinity): \(d = \max(\vert x_1-x_2 \vert, \vert y_1-y_2 \vert)\). This gives square neighborhoods.
Switch between metrics below and watch the decision boundary change shape. With Euclidean, boundaries curve smoothly. With Manhattan, they follow axis-aligned diamond patterns. With Chebyshev, they form boxy squares.
Click on the canvas to see the neighborhood shape for each metric. Euclidean treats all directions equally, Manhattan favors axis-aligned directions, and Chebyshev only cares about the maximum difference in any single dimension.
5. Weighted KNN: Closer Neighbors Matter More
Standard KNN gives every neighbor an equal vote, regardless of how close or far it is within the K neighbors. Distance-weighted KNN gives each neighbor a vote proportional to the inverse of its distance:
\[w_i = \frac{1}{d(\mathbf{x}_{query}, \mathbf{x}_i)}\]This means very close neighbors have a much stronger influence than distant ones, which often improves accuracy near decision boundaries. Toggle between uniform and distance-weighted voting in the side-by-side demo and watch how the boundary becomes smoother and more accurate near class transitions.
The difference is most visible at larger K. With uniform voting and K=15, distant neighbors can outvote a very close one. Weighted voting keeps the closest neighbor most influential.
6. KNN for Regression
KNN is not limited to classification. For regression, instead of taking a majority vote, we average the target values of the K nearest neighbors:
\[\hat{y} = \frac{1}{K}\sum_{i=1}^{K} y^{(i)} \quad \text{(uniform)}\] \[\hat{y} = \frac{\sum_{i=1}^{K} w_i \, y^{(i)}}{\sum_{i=1}^{K} w_i} \quad \text{(weighted, } w_i = 1/d_i\text{)}\]Adjust K below to see how the regression curve changes from stepped (K=1) to smooth (large K). Toggle weighting for smoother interpolation.
With K=1, the curve passes through every training point, creating a stepped prediction. As K increases, the curve smooths out. Compare the blue prediction to the gray dashed true function to see the fit vs smoothness tradeoff.
7. The Curse of Dimensionality
KNN works well in 2D, but it has a real problem in high dimensions called the curse of dimensionality. As the number of dimensions grows, three things happen. First, data becomes sparse: to keep the same density, the number of points needed grows exponentially with the number of dimensions. Second, distances become similar: all points end up roughly the same distance from each other, making “nearest” meaningless. Third, volume grows fast: the fraction of space needed to capture K neighbors grows exponentially. To capture a fixed fraction \(f\) of data in \(d\) dimensions with a hypercube, the side length must be:
\[\ell = f^{1/d}\]For example, to capture 10% of the data: in 1D you need \(\ell = 0.1\), in 2D \(\ell = 0.32\), in 10D \(\ell = 0.79\), and in 100D \(\ell = 0.977\). You need nearly the entire space. The visualization below shows how the ratio of the nearest neighbor distance to the farthest neighbor distance approaches 1 as the number of dimensions increases. When all distances are similar, KNN cannot tell neighbors apart from non-neighbors.
As dimensions increase, the ratio climbs toward 1.0, meaning all points are roughly the same distance from the query. In the red “danger zone” (ratio > 0.9), KNN is basically choosing neighbors at random. This is why feature selection and dimensionality reduction (like PCA) are critical preprocessing steps for KNN.
8. Interactive Classification Playground
Now let us put it all together. Choose a dataset, configure K, the distance metric, and weighting, and watch the full decision boundary with accuracy statistics. Select a preset dataset, tune all hyperparameters, and observe how the decision boundary changes. Try to find the best K for each dataset.
Some observations to explore:
- Blobs: linearly separable. Even K=1 works well, but K=5 to 10 gives the cleanest boundary.
- Moons: needs moderate K to capture the curved boundary without overfitting.
- Circles: KNN handles them naturally since the boundary is based on local neighborhoods.
- XOR: requires a non-linear boundary that KNN provides easily.
- Spiral: the hardest. Only small K values can trace the spiral arms, but they also overfit to noise.
9. Summary
| Concept | Key Idea | Formula / Detail |
|---|---|---|
| KNN Classification | Majority vote of K nearest neighbors | $$\hat{y} = \text{mode}(y^{(1)}, \ldots, y^{(K)})$$ |
| KNN Regression | Average of K nearest neighbors | $$\hat{y} = \frac{1}{K}\sum_{i=1}^{K} y^{(i)}$$ |
| Euclidean Distance | Straight-line distance (circular neighborhoods) | $$\sqrt{\sum(x_i - x_i')^2}$$ |
| Manhattan Distance | Axis-aligned distance (diamond neighborhoods) | $$\sum \vert x_i - x_i' \vert$$ |
| Chebyshev Distance | Maximum coordinate difference (square neighborhoods) | $$\max \vert x_i - x_i' \vert$$ |
| Weighted KNN | Closer neighbors get more vote weight | $$w_i = 1 / d_i$$ |
| K=1 (overfit) | Jagged boundary, memorizes noise | Low bias, high variance |
| K=N (underfit) | Predicts majority class everywhere | High bias, low variance |
| Curse of dimensionality | Distances become meaningless in high-D | Neighborhood side length: $$f^{1/d}$$ |
When to Use KNN
- Good for: small to medium datasets, non-linear boundaries, multi-class problems, when you want a simple baseline, recommendation systems.
- Less ideal for: large datasets (prediction is slow because it must compute distance to every training point), high-dimensional data, features on very different scales (must normalize first).
- Key hyperparameters: K (number of neighbors), distance metric, weighting scheme, feature scaling.
Computational Complexity
| Phase | Time | Space |
|---|---|---|
| Training | \(O(1)\) - just store data | \(O(nd)\) |
| Prediction | \(O(nd)\) per query | \(O(1)\) |
where \(n\) is the number of training points and \(d\) is the number of dimensions. KNN’s prediction cost is its main drawback. For large datasets, KD-trees or ball trees reduce this to \(O(d \log n)\) on average.
What is Next
In the next chapter, we will explore Naive Bayes, a probability-based classifier that uses Bayes rule with a strong independence assumption. It is fast to train, works well on small datasets, and is often used for text classification.