Open Spotify and look at the "Fans Also Like" section on any artist. Open Pinterest and tap "More Like This" on a pin. Open the App Store and scroll to "Apps Similar to This One." Every single one of those sections is the same algorithm running underneath: find the 10 items closest to this one in some big mathematical space, show those. It is also the algorithm running inside every modern AI search engine ("find me documents similar to this question") and every RAG system that powers a chatbot's memory. By the end of this lesson, you'll understand the whole idea — there is no training step, no math to solve, just "look at your neighbors and copy their answer" — and you'll know exactly when this dirt-simple recipe wins and when it falls apart.
Learning Objectives
After this lesson, you will be able to:
Understand KNN — it just saves all the training data and makes predictions by finding the most similar examples (no actual 'training' happens!)
See how changing K (how many neighbors you ask) makes the model smoother or more jagged
Know the different ways to measure 'closeness' (Euclidean, Manhattan, cosine) and when each makes sense
Recognize KNN's trade-offs: dead simple to understand, but slow on big datasets and struggles with many features
Explain the curse of dimensionality and why KNN requires dimensionality reduction when features exceed ~20-50
Don't worry if this one feels too simple to be real — KNN is genuinely that straightforward. No training, no fancy math, just "find the closest examples and copy their answer." It is a great starting point for any problem!
Try it! Open the Python REPL and type these lines yourself. Run KNN on the Iris dataset: from sklearn.neighbors import KNeighborsClassifier; from sklearn.datasets import load_iris; X, y = load_iris(return_X_y=True); knn = KNeighborsClassifier(n_neighbors=3).fit(X, y); print(f"Accuracy: {knn.score(X, y):.0%}") — you just classified flowers by asking their neighbors!
You have 6 labeled fruits with two features — weight (grams) and sweetness (1–10):
Fruit
Weight
Sweetness
Label
1
150
7
apple
2
170
8
apple
3
130
6
apple
4
200
4
orange
5
220
3
orange
6
180
5
A new fruit shows up: weight = 160g, sweetness = 6. What is it? With K = 3, compute Euclidean distance to each training point:
Fruit
Distance
Label
1
√((160−150)² + (6−7)²) = √101 ≈ 10.05
apple
2
√(10² + 2²) = √104 ≈ 10.20
apple
3
√(30² + 0²) = 30.00
apple
4
√(40² + 2²) = √1604 ≈ 40.05
orange
5
√(60² + 3²) ≈ 60.07
orange
6
√(20² + 1²) ≈ 20.02
orange
Sort by distance, take the 3 nearest: fruit 1 (apple, 10.05), fruit 2 (apple, 10.20), fruit 6 (orange, 20.02). Majority vote: 2 apples, 1 orange → predict APPLE.
Notice the whole algorithm just executed: compute distances, sort, vote. No training. No gradient descent. No loss function. That is KNN.
But also notice a trap waiting: weight ranges 130–220 (≈90 spread) and sweetness ranges 3–8 (≈5 spread). Weight is roughly 18× larger in raw units, so it dominates every distance calculation. Sweetness is almost invisible. This is why feature scaling is mandatory — without it, KNN is really just "1-nearest-neighbor on the biggest feature."
Try it: Change K and watch the decision boundary smooth outInteractive
Loading visualization...
Try this: Observe the decision boundary. Each region is colored by the majority class of its nearest neighbors. Notice how the boundary is non-linear and closely follows the data distribution. Change K from 1 to 20 and watch the boundary smooth out. With K=1, the boundary is jagged (overfitting). With K=50, the boundary is very smooth (underfitting).
Interactive Lab
Pick KNN from the algorithm dropdown, change K with the slider, and watch the boundary go from jagged (K=1, overfits) to smooth (K=30, underfits). The sweet spot is usually somewhere between.
A Voronoi diagram divides the space into cells, one per training point, where each cell contains all points closer to that training point than any other. KNN with K=1 predicts the class of the nearest Voronoi cell. As K increases, the boundaries smooth out because majority voting among multiple neighbors averages away noise.
Quick check
You train KNN on a 2D dataset three times: K=1, K=5, K=25. Which row matches each model's TRAINING accuracy?
Compare against every training point in d dimensions
Prediction (KD-Tree)
O(d * log n) average
Fast for low dimensions (d < 20)
Prediction (Ball Tree)
O(d * log n) average
Better for moderate dimensions
Prediction (ANN/FAISS)
O(d * log n) approximate
Sub-millisecond on billions of vectors
For small datasets (n < 10,000), the naive approach is fine. For production systems with millions of points, you need acceleration structures like KD-Trees, Ball Trees, or approximate nearest neighbor libraries.
You have a KNN classifier with K=1 that gets 100% training accuracy. Is this model good?
K is the single most important hyperparameter:
K = 1: Every training point creates its own tiny decision region. Training accuracy is always 100% (each point is its own nearest neighbor). The boundary is extremely jagged and overfits to noise. High variance, low bias.
K = n (all data): Every prediction is the majority class of the entire training set. The model ignores the input entirely. This is maximum underfitting. Low variance, high bias.
K = sqrt(n): A common starting point. Tune via cross-validation.
Words don't quite convince. In high dimensions, the ratio (max pairwise distance / min pairwise distance) goes to 1 — meaning every point becomes about the same distance from every other point. Run the simulation in your browser.
The distance metric you choose can make or break your KNN model. Here is a practical decision framework:
Structured tabular data (age, income, height): Start with Euclidean after StandardScaler. If outliers are present, switch to Manhattan -- it does not square the differences, so one extreme value in one dimension cannot dominate.
Text data (TF-IDF vectors, word embeddings): Always use Cosine. A 10-page document and a 1-page document about the same topic have very different magnitudes but similar directions. Cosine ignores magnitude and compares only direction.
Mixed feature types (some continuous, some binary): Consider Manhattan. It handles binary features more naturally because the distance is simply the number of mismatched binary features plus the absolute differences in continuous features.
Very high dimensions (d > 100): The choice of metric matters less because all distances converge -- but Cosine tends to degrade more slowly than Euclidean in high dimensions.
Quick check
You have 50,000 documents represented as 768-dim sentence-transformer embeddings. You want KNN over them for semantic search. Which distance metric and acceleration choice?
Tests · Verify K=1 returns the class of the single nearest neighbor. Verify that increasing K can change predictions for ambiguous points. Implement distance weighting and compare results.
KNN has no training step. It stores the entire dataset and defers all computation to prediction time, making it a "lazy learner" with O(1) training but O(n*d) prediction cost
K controls the bias-variance tradeoff. K=1 overfits (every point is its own neighborhood), large K underfits (everything is averaged); use cross-validation to find the sweet spot, often starting at sqrt(n)
Feature scaling is critical. KNN is purely distance-based, so unscaled features with large ranges dominate the distance calculation and render small-range features invisible
The curse of dimensionality breaks KNN in high dimensions. As dimensions increase, all points become approximately equidistant, making the concept of "nearest" meaningless; use PCA or feature selection first
Vector search is KNN's most important modern application. Every RAG system, recommendation engine, and semantic search engine is built on approximate nearest neighbor search using libraries like FAISS and ScaNN
KNN classifies by looking at local neighborhoods. But what if you want to discover the neighborhoods themselves -- with no labels at all? Next up: Clustering, where algorithms discover natural groups in your data.