Chapter 04 · Section II · 14 min read
The nearest neighbor method
The simplest learning algorithm in existence — and why it still works.
The nearest-neighbour classifier does almost no work. To predict the label of a new point, it looks up the closest example it has seen before, and copies that label. That is the entire algorithm. No training. No optimisation. No parameters.
And it works, in many cases, very well — well enough that it is a sensible first thing to try on any classification problem before reaching for anything fancier. We will see why, where it breaks, and how a small twist (k-nearest neighbours) makes it more reliable.
The intuition
Suppose you want to predict whether a new Newari restaurant in Patan is going to be reviewed positively or negatively. You have 5,000 historical reviews, each tagged “positive” or “negative” by the customer’s star rating. Each review is described by a handful of features: the restaurant’s neighbourhood, its average price, the time of day the customer visited, and (perhaps) the cuisine style.
Nearest-neighbour says: find the historical review whose features are closest to the new one, and predict the same sentiment.
If the new restaurant is in Patan Durbar Square, priced at Rs. 500 per person, visited at lunchtime — and the closest historical review is from a Patan restaurant at Rs. 480, visited at lunchtime, with a positive review — predict positive. If the closest review is negative, predict negative.
That’s it. No training. The algorithm just stores the data and looks up neighbours at prediction time.
What “closest” means
Everything in nearest-neighbour rests on the definition of closest. We need a distance function that says how similar two examples are.
For numerical features (price, distance, hour), the obvious distance is Euclidean: the square root of the sum of squared differences. A restaurant at Rs. 500 priced is “closer” to one at Rs. 480 than to one at Rs. 2,000.
For categorical features (neighbourhood, cuisine), one common trick is to count how many categorical features match. Same neighbourhood and same cuisine = closer than different.
For text (the actual review content), you might convert each review to a vector of word counts and compute Euclidean or cosine distance on those vectors.
The choice of distance function is the algorithm. Two engineers using “nearest neighbour” with different distance functions are using different classifiers.
k-nearest neighbours: a useful twist
Looking at the single closest example is risky. What if that one example was mislabelled, or genuinely weird? The fix is to look at the k closest examples (say, k=5) and let them vote.
If among the 5 nearest historical reviews, 4 are positive and 1 is negative, predict positive. The k=1 prediction would have been a coin-flip if the single nearest happened to be the lone negative; k=5 absorbs that noise.
How to pick k?
- k = 1 memorises noise. Very sensitive to mislabelled training examples.
- k = a large fraction of your data averages everything together. Loses local detail.
- k = √n (where n is the number of training examples) is a common starting guess.
In practice, you try several values of k, evaluate on held-out data, and pick the best.
A worked example
Imagine 6 historical Newari restaurant reviews, with two features (price in Rs., quality-of-décor on 0-10) and a sentiment label:
| Review | Price | Décor | Sentiment |
|---|---|---|---|
| A | 200 | 3 | negative |
| B | 250 | 4 | negative |
| C | 450 | 7 | positive |
| D | 500 | 8 | positive |
| E | 800 | 6 | negative |
| F | 600 | 9 | positive |
A new restaurant: Price Rs. 480, Décor 7. Compute Euclidean distance to each:
- to A: √((480-200)² + (7-3)²) ≈ 280
- to B: √((480-250)² + (7-4)²) ≈ 230
- to C: √((480-450)² + (7-7)²) ≈ 30
- to D: √((480-500)² + (7-8)²) ≈ 22
- to E: √((480-800)² + (7-6)²) ≈ 320
- to F: √((480-600)² + (7-9)²) ≈ 120
Nearest is D (distance ~22), labelled positive. With k=1, we predict positive.
With k=3 (D, C, F), all three nearest are positive — strongly positive prediction. With k=5 (D, C, F, B, A), still 3 positive and 2 negative, so positive wins. The new restaurant is predicted positive.
This is the entire process. Compute distances. Sort. Vote.
Where nearest-neighbour shines
Three properties make kNN attractive:
- No training cost. Add new data, and the model immediately reflects it. There is no retraining step.
- Easy to explain. “We predicted positive because this restaurant is most similar to these five others, which were positive.” A regulator or a customer can understand that.
- Works on any data type as long as you can define a distance. Text, images, time-series — all kNN-able if you have a distance function.
Where nearest-neighbour breaks
Three honest limits:
- Slow at prediction time. To predict one new label, you must compute distance to every training example. With a million examples, this is slow. (Specialised data structures like KD-trees and approximate nearest-neighbour libraries help.)
- Bad with many features. As you add features, the notion of “nearest” becomes unstable. This is called the curse of dimensionality, and it is the reason kNN does not power image recognition the way it powers our worked example.
- Sensitive to scaling. Without normalisation, large-numeric features dominate the distance. With one categorical feature mixed in, you have to be careful how it contributes.
But for small-to-medium datasets with a handful of features — exactly the situation a Nepali NGO, municipality, or small business is most likely to be in — kNN is hard to beat as a first model. Start there. If it isn’t enough, move on.
Check your understanding
Quick check
—In k-nearest neighbours, what role does k play?
What comes next
We have seen a classifier that predicts a category. The next section moves to the other side of supervised learning: predicting a number. Welcome to regression — the workhorse of applied AI in industry.