Specialty · AILesson 4 of 6Free to read

k-nearest neighbours · AI Foundations

How can a program label something new by looking at similar examples?

Why you need it

k-nearest neighbours (kNN) is a classifier with no training at all: to label a new point, look at the k most similar examples you already have and take a vote. It's easy to reason about, it's a solid baseline, and the same "find the nearest" idea powers recommendation and search, which you'll see again in the last lesson.

The intuition

Put every example on a grid by its features, coloured by its label. A new point arrives:

measure the distance from it to every example: math.dist(a, b) gives the straight-line distance
take the k closest
the most common label among them wins

Choosing k:

k = 1 copies the label of the single nearest example, so one mislabelled example changes the answer around it
a larger k smooths out noise, but too large and the biggest class wins everywhere
with two classes, an odd k avoids ties

Distances add up the features directly, so scale them first (lesson 1). Otherwise "salary in dollars" swamps "age in years".

Definition

Classification

Predicting a category, such as spam or not spam, instead of a number.

k-nearest neighbours

Labelling a point by a vote among the k closest training examples.

Distance

How far apart two points are. math.dist gives the straight-line (Euclidean) distance.

Examples

Distance

Try it yourself

Pythagoras: a 3-by-4 step is 5 long.

import math

print(math.dist((1, 2), (4, 6)))
print(math.dist((0, 0, 0), (1, 2, 2)))

Output

5.0
3.0

Step by step

L3Differences 3 and 4: √(9 + 16) = 5.5.0
L4It works for any number of features: √(1 + 4 + 4) = 3.3.0

Vote among neighbours

Try it yourself

Points near the red corner come out red, near the blue corner blue.

import math
from collections import Counter

train = [
    ((1, 1), "red"), ((2, 1), "red"), ((1, 2), "red"),
    ((6, 5), "blue"), ((7, 7), "blue"), ((6, 6), "blue"),
]

def knn(point, k):
    nearest = sorted(train, key=lambda item: math.dist(item[0], point))[:k]
    votes = Counter(label for xy, label in nearest)
    return votes.most_common(1)[0][0]

print(knn((2, 2), 3))
print(knn((5, 5), 3))
print(knn((4, 5), 5))

Output

red
blue
blue

Step by step

L10Order the examples from nearest to farthest, keep k.
L11Count the labels among the neighbours.
L12The label with the most votes. On a tie, the one seen first (the nearer one) wins.
L16Between the two groups, 5 neighbours: 3 blue and 2 red.blue

Common mistakes

Unscaled features

The feature with the biggest numbers decides every distance on its own. Scale each feature to 0…1 first.

An even k with two classes

Two red and two blue is a tie, and the tie rule, not the data, decides. Use an odd k.

Slow on big data

Every prediction measures the distance to every example. With millions of rows you need an index for nearest-neighbour search.

Quick quiz

1. What does this print?

import math

points = {"A": (0, 0), "B": (3, 4), "C": (1, 1)}
target = (2, 2)
print(sorted(points, key=lambda n: math.dist(points[n], target)))

A
```
['C', 'B', 'A']
```
B
```
['A', 'C', 'B']
```
C
```
['C', 'A', 'B']
```

Show the answer

Answer: A

Distances from (2, 2): C ≈ 1.41, B ≈ 2.24, A ≈ 2.83.

2. One training example has the wrong label. Which k is most affected?

Ak = 1
Bk = 7
CAll k equally

Show the answer

Answer: A

With k = 1 the wrong example decides alone for every point near it; with k = 7 it's outvoted.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictCount the votes
Type exactly what this prints.
ModifyOnly looking sideways
nearest should return the label of the closest example, but it only compares the x coordinate. Use the full distance between the two points (math.dist).
Writek-nearest neighbours
Write knn(train, point, k). train is a list of ((x, y), label) pairs. Return the most common label among the k examples nearest to point.
Ties: count the labels from nearest to farthest; on a tie, the label that appeared first wins. Counter(...).most_common(1) already works this way. If k is larger than train, use all of it.

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
Classification	分类	Predicting a category instead of a number.
k-nearest neighbours	k 近邻	Voting among the k closest examples.
Euclidean distance	欧几里得距离	Straight-line distance between two points.