Machine Learning Foundations / Core / 02.21
K-nearest neighbours: ask your neighbours
The simplest model that learns from examples: to guess something new, find the k most similar things you know and let them vote.
14 min readFree
The idea: ask your neighbours
You move to a new street and want a good place for lunch. You do not read a book about food. You ask the three people living closest to you. Two say the noodle shop, one says the bakery. You go to the noodle shop.
That is the whole idea of this lesson. Regression, the lesson before, drew a rule from the data. K-nearest neighbours (people write k-NN or KNN) draws no rule at all. To guess something about a new thing, it finds the known things most like it and copies what they say.
Key words
- Feature
- One measurement about a thing, such as its height, its price or its colour.
- Label
- The answer we want to predict, such as "cat" or "dog".
- Query point
- The new thing we want to guess about. Its label is unknown.
- Neighbour
- A known example that sits close to the query point.
- Distance
- A number that says how far apart two things are. Small means similar.
- k
- How many neighbours we ask. It is a setting you choose, not something the model learns.
- Majority vote
- Each neighbour casts one vote for its label. The label with the most votes wins.
- Hyperparameter
- A setting you pick before training. k is one.
The scikit-learn guide calls this instance-based learning, or non-generalizing learning: it does not attempt to construct a general internal model, but simply stores instances of the training data.
The recipe in four steps
Wikipedia describes the training phase in one sentence: it consists only of storing the feature vectors and class labels of the training samples. (A feature vector is just the list of a thing's numbers.) All the work happens later, when you ask a question.
- 1
1. Store
Keep every training example with its label. That is all training does.
- 2
2. Measure
For a new point, work out its distance to every stored example.
- 3
3. Pick the closest k
Sort by distance and keep the k nearest. These are the neighbours.
- 4
4. Combine
Classification: take a majority vote of their labels. Regression: take the average of their numbers.
Tip
Wikipedia's own picture shows why k matters. With k = 3, a test point has 2 triangles and 1 square inside the small circle, so it becomes a triangle. With k = 5, the bigger circle holds 3 squares and 2 triangles, so the same point becomes a square. Same point, same data, different answer.
How far is far?
"Closest" needs a way to measure. The usual choice for numbers is Euclidean distance, which is the straight line between two points, the way a bird flies. Wikipedia names it as a commonly used distance metric for continuous variables.
Take two points with two features each, written (x1, y1) and (x2, y2). Subtract the x values, subtract the y values, square both, add them up and take the square root. That is Pythagoras, the school rule for the long side of a right triangle.
In words: walk the gap sideways, walk the gap up, then take the straight line that joins them. With more than two features you keep adding one squared gap per feature.
There is another way to measure, called Manhattan distance, or city-block distance. Wikipedia explains the name: it comes from Manhattan, or any planned city with a rectangular grid of streets, in which a taxicab can only travel along grid directions. You cannot cut through buildings. You add up the sideways gap and the up gap, with no squares and no root.
In words: add the size of each gap, ignoring whether it points left or right. The bars mean "drop any minus sign". Here both ways on two points, (1, 2) and (4, 6):
Take two points, (1, 2) and (4, 6). The gaps are 3 across and 4 up. The bird flies 5, because 3 squared plus 4 squared is 25. The taxi drives 3 + 4 = 7. The scikit-learn guide lists both ('euclidean' and 'manhattan') among the metrics its neighbour searches accept, so switching is one word in the code.
Classification: a majority vote
When the label is a category, the k neighbours vote. Scikit-learn puts it this way: classification is computed from a simple majority vote of the nearest neighbors of each point: a query point is assigned the data class which has the most representatives within the nearest neighbors of the point.
The program below makes two overlapping clouds of made-up points in 2D. One cloud is "cat", centred near (3, 3). The other is "dog", centred near (6, 6). Each cloud has 30 training points and 20 test points. The fixed seed means you get the same numbers every time. Then it asks three query points for their votes at k = 1, 3 and 7, and scores all 40 test points.
import math
import random
from collections import Counter
random.seed(11)
def make_points(n, cx, cy, label):
return [((random.gauss(cx, 1.3), random.gauss(cy, 1.3)), label) for _ in range(n)]
# Two overlapping clouds: "cat" around (3, 3), "dog" around (6, 6)
train = make_points(30, 3, 3, "cat") + make_points(30, 6, 6, "dog")
test = make_points(20, 3, 3, "cat") + make_points(20, 6, 6, "dog")
def distance(a, b):
return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
def predict(point, k):
nearest = sorted(train, key=lambda item: distance(point, item[0]))[:k]
votes = Counter(label for _, label in nearest)
return votes.most_common(1)[0][0], votes
for name, point in [("A", (5.0, 5.0)), ("B", (4.2, 5.0)), ("C", (3.5, 4.8))]:
for k in (1, 3, 7):
winner, votes = predict(point, k)
print(f"point {name} {point}, k={k}: {dict(votes)} -> {winner}")
print()
for k in (1, 3, 7):
right = sum(predict(p, k)[0] == label for p, label in test)
print(f"k={k}: {right} of {len(test)} test points right ({right / len(test):.1%})")Output
point A (5.0, 5.0), k=1: {'dog': 1} -> dog
point A (5.0, 5.0), k=3: {'dog': 2, 'cat': 1} -> dog
point A (5.0, 5.0), k=7: {'dog': 5, 'cat': 2} -> dog
point B (4.2, 5.0), k=1: {'dog': 1} -> dog
point B (4.2, 5.0), k=3: {'dog': 2, 'cat': 1} -> dog
point B (4.2, 5.0), k=7: {'dog': 2, 'cat': 5} -> cat
point C (3.5, 4.8), k=1: {'dog': 1} -> dog
point C (3.5, 4.8), k=3: {'dog': 1, 'cat': 2} -> cat
point C (3.5, 4.8), k=7: {'dog': 2, 'cat': 5} -> cat
k=1: 33 of 40 test points right (82.5%)
k=3: 36 of 40 test points right (90.0%)
k=7: 37 of 40 test points right (92.5%)Read the first block, point A at (5.0, 5.0). It is deep in dog land, so every k says dog. The votes at k = 7 are 5 dogs and 2 cats.
Point B at (4.2, 5.0) sits near the border. Its single nearest neighbour is a dog, and k = 3 still says dog, 2 to 1. At k = 7 the answer flips: 5 cats and 2 dogs. The larger circle has reached more of the cat cloud. Point C at (3.5, 4.8) flips one step sooner, at k = 3.
On these 40 unseen test points, k = 1 gets 33 right (82.5%), k = 3 gets 36 (90.0%) and k = 7 gets 37 (92.5%). This is one made-up dataset with few test points, so the pattern matters more than the exact numbers.
Quick check
In the output, point B is called "dog" at k = 3 but "cat" at k = 7. What is the best explanation?
Regression: an average
When the answer is a number, the neighbours do not vote. They share the answer out. Scikit-learn says the label assigned to a query point is computed based on the mean of the labels of its nearest neighbors. A mean is an average: add the numbers up and divide by how many there are.
Picture a tea stall. You have six past days, each with a temperature and the cups sold. A new day is forecast at 26 degrees. Find the days closest in temperature and average their sales.
# Same idea, new job: guess how many cups of tea a stall sells from the day's temperature
days = [(5, 130), (8, 115), (12, 95), (15, 70), (20, 55), (30, 25)] # (degrees C, cups)
def nearest(temp, k):
return sorted(days, key=lambda d: abs(d[0] - temp))[:k]
def average_cups(temp, k):
close = nearest(temp, k)
return sum(cups for _, cups in close) / k
def weighted_cups(temp, k):
close = nearest(temp, k)
weights = [1 / (abs(t - temp) + 0.001) for t, _ in close]
return sum(w * cups for w, (_, cups) in zip(weights, close)) / sum(weights)
for k in (1, 3, 5):
print(f"k={k}: plain {average_cups(26, k):.1f}, weighted {weighted_cups(26, k):.1f}")Output
k=1: plain 25.0, weighted 25.0 k=3: plain 50.0, weighted 42.9 k=5: plain 72.0, weighted 55.1
Read the plain numbers first. The weighted ones come in a later section. At k = 1 the answer is the cups sold on the closest day, 30 degrees: 25. At k = 3 the average of the three closest days is 50. At k = 5 it is 72. The cooler days, which sold more tea, are pulling the guess up. Each added neighbour is further away, and less like a 26-degree day.
Choosing k
k is a hyperparameter: you choose it before the model runs, and nothing inside will fix a poor choice. The scikit-learn guide says the optimal choice of the value k is highly data-dependent. Wikipedia agrees, and gives the rule of thumb: generally, larger values of k reduces effect of the noise on the classification, but make boundaries between classes less distinct.
Small k: jumpy
With k = 1 the answer is only the single closest example. If that one example is a mistake or a freak, the prediction copies the mistake. The line between classes zigzags around every odd dot.
Large k: blurry
With a big k you ask so many that nearby examples drown in far-away ones. Little details smooth away, and the model leans towards whatever class is most common overall.
The middle
A medium k cancels out noise and still sees real local patterns. Where that middle sits depends on your data, which is why you test, not guess.
Wikipedia names the special case: when k = 1, the algorithm is called the nearest neighbor algorithm.
How do you find a good k? You try several values and score each on data the model has not trained on. That is exactly the job of the lesson Tuning a model's settings, which uses k-NN as one of its examples. It covers grid search, random search, the validation set and keeping the test set untouched, so this lesson does not repeat them.
Why feature scaling matters
Distance adds up the gaps on every feature. So a feature with big numbers shouts louder than one with small numbers.
Say you describe houses by size in square metres (50 to 200) and by number of rooms (1 to 6). A gap of 40 square metres is nothing to a human. But as a raw number, it is 40 times bigger than a gap of one room. The distance will be decided almost completely by size, and the rooms might as well not exist.
Wikipedia warns about this directly: the accuracy of the k-NN algorithm can be severely degraded by the presence of noisy or irrelevant features, or if the feature scales are not consistent with their importance. The fix is to put the features on a similar range before measuring.
The lesson Feature scaling and normalization teaches how: min-max scaling, z-scores and the rule to fit the scaler on training data only. Come back here after it. For k-NN the habit is simple: scale first, then measure distance.
Weighted votes: closer counts more
A plain vote treats the nearest neighbour and the k-th neighbour the same. But a neighbour right next door probably tells you more than one three streets away.
So you can give nearer neighbours a bigger say. Scikit-learn offers this through its weights setting. The default, 'uniform', gives every neighbour an equal weight. The option 'distance' assigns weights proportional to the inverse of the distance from the query point, which means one divided by the distance.
In words: multiply each neighbour's value y by its weight w, add those up, and divide by the total weight. The weight is one over that neighbour's distance d. A neighbour at distance 2 counts twice as much as one at distance 4. For classification, you add up the weights behind each label and the biggest total wins.
Back at the tea stall, the weighted_cups function did exactly this. At k = 3 the plain average was 50.0 and the weighted one was 42.9. At k = 5 it was 72.0 and 55.1. The 30-degree day, only 4 degrees away, got the biggest say, so the answer stayed closer to its 25 cups. Far-away days still count, only less. That makes the guess less sensitive to the exact k you picked.
The price: it remembers everything
k-NN is quick to train, since training is just saving the data. The bill comes when you predict.
Look back at the program. To label one point, predict measured the distance to all 60 stored points and sorted them. With 60 points that is nothing. With a million stored examples and thousands of questions a second, it is a lot of work. Scikit-learn says brute-force query time grows as O[D N], where N is the number of samples and D the number of features.
Memory
The whole training set has to stay available, because the stored examples are the model. There is no small formula to keep instead.
Speed
Each prediction compares against many saved points. The guide describes smarter structures, the KD tree and the ball tree, that skip most of the checking. For small D (less than 20 or so) the KD tree cost is approximately O[D log(N)].
Upside
Nothing to fit, nothing to relearn. Add a new example to the box, and the next prediction already uses it.
The curse of dimensionality
A dimension here means one feature. Two features make a flat sheet. Three make a box. A hundred features make a space we cannot picture, and it behaves strangely.
Wikipedia says the common theme is that when the dimensionality increases, the volume of the space increases so fast that the available data becomes sparse, and the amount of data needed often grows exponentially with the dimensionality.
That hurts k-NN twice. First, with so much room, the nearest neighbours are not really near. Second, Wikipedia explains that Euclidean distance is unhelpful in high dimensions because all vectors are almost equidistant to the search query vector. If everything is about as far away as everything else, "closest" stops meaning anything.
Quick check
Your data has 300 features and k-NN works badly, even after scaling. Which is the most sensible next step?
What to remember
How it works
Store the examples. For a new point, find the k closest by distance, then take a majority vote (classification) or an average (regression).
The dials
k is yours to pick: small is jumpy, large is blurry. Scale your features first. Weight by distance if you want near neighbours to count more.
The limits
It keeps all the data, it is slow to predict on big sets, and it struggles when there are very many features.
Next: linear regression, drawing the best straight line.
Sources
Last updated on 16 November 2026
Learn with me
Every lesson is free. I add new ones as I learn. Have a question, or want help with your own work? Book a short call.