k-nearest neighbours explained

How the k-nearest neighbours algorithm classifies: distance to labelled examples, a vote among the k closest, and how k, scaling, wrong labels and unbalanced data change the answer, shown on a robot that tells open space, a wall and a gap apart with its depth sensor.

Guidefree, runs in your browser

k-nearest neighbours (KNN) sorts new things into groups by comparing them with examples it has already been told the answers to. Keep every labelled example. When something new comes along, find the k examples most like it and let them vote. There is no training step and no formula to fit, which makes it one of the first methods people try on a new problem. Evelyn Fix and Joseph Hodges first wrote the idea down in 1951, and finding the stored items nearest to a new one is still how many search and recommendation systems find "more like this". On this page a small robot looks ahead with its depth sensor and says what is in front of it: open space, a wall, or the gap at the wall's left or right end. Each demo below is a real program you can change and run.

Every demo uses the same 1 metre mat. A wall 72 cm long lies across it 60 cm in front of where the robot starts, with a 14 cm gap at each end. In the overhead view the robot leaves a trail of dots coloured by the answer it gave at each point: green for open, red for wall-ahead, blue for gap-left and orange for gap-right. The chart has one line for each label. In the first two demos a line shows how far the robot's view is from the nearest example with that label; in the last two it shows how many of the k votes that label won. Positions are in cm from where the robot started: y forwards, x to the right.

The idea in one loop

keep a list of examples: (numbers, label)

to classify something new:
    turn it into the same kind of numbers
    work out its distance to every example
    take the k examples with the smallest distance
    each one votes for its own label
    the label with the most votes is the answer

Two choices decide how well it works: which numbers you compare (the features), and how many neighbours get a vote (k). The rest of this page is about those two, and about the examples themselves, because KNN is only ever as good as the examples it keeps.

Features: turning a view into numbers

A classifier never sees a wall. It sees numbers. The robot's depth sensor measures 64 distances in a grid of 8 rows by 8 columns, spread 45 degrees across. Rows 2 and 3 look straight ahead, so the robot uses those 16 readings, in cm, and ignores the rest. Those 16 numbers are the features. The lesson See as numbers prints them and shows how much they change when the robot turns a little.

An example is a view plus a label: 16 numbers and a word for what they mean, recorded by driving the robot to a place where you know the answer. In Collecting data the robot drives to four spots and records one example of each of the four labels:

([54, 52, 51, 51, 51, 51, 52, 54, 54, 52, 51, 51, 51, 51, 52, 54], "open"),
([16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16], "wall-ahead"),
([36, 47, 46, 46, 46, 16, 16, 16, 36, 47, 46, 46, 46, 16, 16, 16], "gap-left"),
([16, 16, 16, 46, 46, 46, 47, 36, 16, 16, 16, 46, 46, 46, 47, 36], "gap-right"),

Read along the gap-left example. The first five columns see about 46 cm, past the end of the wall; the last three see the wall 16 cm away. The label is your judgement. If it is wrong, the classifier learns your mistake.

Distance: how alike are two views

Take two lists of 16 numbers. Subtract them column by column, square each difference so that minus signs do not cancel out plus signs, add the squares up and take the square root:

distance = √( (a1 − b1)² + (a2 − b2)² + ... + (a16 − b16)² )

This is the Euclidean distance, the straight-line distance you know from Pythagoras, with 16 numbers instead of 2. A small distance means the two views are alike. The open and wall-ahead examples above differ by between 35 and 38 cm in every column; the squares add up to 20,760 and the distance is 144.1.

The lesson Nearest neighbour leaves out the square root and compares the sums of squares. That gives the same answer every time, because the smaller sum always has the smaller square root. The demos keep the square root so that the numbers on the chart are a sensible size. Another common choice is the Manhattan distance, which adds up the differences without squaring them, so one big difference counts for less.

One example of each, k = 1

The simplest version gives the vote to the single nearest example: k = 1, often called nearest neighbour. Here it uses only the four examples above while the robot drives slowly towards the wall.

from bugbot import *
import math
connect()

# one labelled example of each situation: the 16
# level depth readings in cm, and what they mean
DATA = [
    ([54, 52, 51, 51, 51, 51, 52, 54, 54, 52, 51, 51, 51, 51, 52, 54], "open"),
    ([16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16], "wall-ahead"),
    ([36, 47, 46, 46, 46, 16, 16, 16, 36, 47, 46, 46, 46, 16, 16, 16], "gap-left"),
    ([16, 16, 16, 46, 46, 46, 47, 36, 16, 16, 16, 46, 46, 46, 47, 36], "gap-right"),
]
COLOUR = {"open": "green", "wall-ahead": "red",
          "gap-left": "blue", "gap-right": "orange"}

def distance(a, b):
    # the straight-line distance between two views
    return math.sqrt(sum((p - q) ** 2 for p, q in zip(a, b)))

def nearest(view):
    # the label of the example most like this view
    best_label, best_d = None, 1e18
    for feats, label in DATA:
        d = distance(feats, view)
        if d < best_d:
            best_label, best_d = label, d
    return best_label

trail = {label: [] for label in COLOUR}
forward(30)
wait(1)       # see "Readings of 400" below
while position()[1] < 50:
    view = tof_grid()[16:32]        # the 16 level readings
    for feats, label in DATA:
        plot(label, distance(feats, view))
    answer = nearest(view)
    x, y = position()
    trail[answer].append((50 + x, 10 + y))
    for label in COLOUR:
        draw(label, trail[label], COLOUR[label])
    print("y =", round(y), answer)
    wait(0.2)
stop()

The lowest line on the chart is the answer. The open line comes down to 2.4 at y = 10, where that example was recorded, and the wall-ahead line comes down to 3.0 at about y = 45, where that one was recorded. The two gap lines lie almost on top of each other, because the two gap examples are mirror images of each other.

In between, it goes wrong. At y = 27, 33 cm from the wall, the view is 57.0 from the gap-left example, 58.7 from gap-right, 70.8 from open and 73.3 from wall-ahead. There is no example of a wall 30 to 35 cm away, so the answer is whichever label happens to be least unlike it, and that is a gap that is not there. Nearest neighbour can only answer with a label it has seen, from somewhere near a place it has seen it.

More examples fix it

Cleverer code does not fix this. More data does. The lesson A tiny network adds 30 more examples, recorded all over the mat: open space at three distances, the wall at three distances, and six more views of each gap. Same program, same k = 1, 34 examples:

from bugbot import *
import math
connect()

# 34 labelled examples, recorded all over the mat:
# the 4 from before and 30 more (lesson 8.4)
DATA = [
    ([54, 52, 51, 51, 51, 51, 52, 54, 54, 52, 51, 51, 51, 51, 52, 54], "open"),
    ([16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16], "wall-ahead"),
    ([36, 47, 46, 46, 46, 16, 16, 16, 36, 47, 46, 46, 46, 16, 16, 16], "gap-left"),
    ([16, 16, 16, 46, 46, 46, 47, 36, 16, 16, 16, 46, 46, 46, 47, 36], "gap-right"),
    ([400, 400, 61, 61, 61, 61, 400, 400, 96, 62, 61, 61, 61, 61, 62, 64], "open"),
    ([52, 50, 49, 49, 49, 49, 50, 52, 51, 50, 49, 49, 49, 49, 50, 51], "open"),
    ([39, 38, 37, 37, 37, 37, 38, 39, 39, 38, 37, 37, 37, 37, 38, 39], "open"),
    ([400, 400, 61, 61, 61, 61, 400, 400, 64, 62, 61, 61, 61, 61, 62, 64], "open"),
    ([52, 50, 49, 49, 49, 49, 50, 52, 51, 50, 49, 49, 49, 49, 50, 51], "open"),
    ([39, 38, 37, 37, 37, 37, 38, 39, 39, 38, 37, 37, 37, 37, 38, 39], "open"),
    ([400, 400, 61, 61, 61, 61, 400, 400, 64, 62, 61, 61, 61, 61, 62, 96], "open"),
    ([52, 50, 49, 49, 49, 49, 50, 52, 51, 50, 49, 49, 49, 49, 50, 51], "open"),
    ([39, 38, 37, 37, 37, 37, 38, 39, 39, 38, 37, 37, 37, 37, 38, 39], "open"),
    ([26, 25, 25, 25, 25, 25, 25, 26, 26, 25, 25, 25, 25, 25, 25, 26], "wall-ahead"),
    ([18, 17, 17, 17, 17, 17, 17, 18, 17, 17, 17, 17, 17, 17, 17, 17], "wall-ahead"),
    ([9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9], "wall-ahead"),
    ([26, 25, 25, 25, 25, 25, 25, 26, 26, 25, 25, 25, 25, 25, 25, 26], "wall-ahead"),
    ([18, 17, 17, 17, 17, 17, 17, 18, 17, 17, 17, 17, 17, 17, 17, 17], "wall-ahead"),
    ([9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9], "wall-ahead"),
    ([26, 25, 25, 25, 25, 25, 25, 26, 26, 25, 25, 25, 25, 25, 25, 26], "wall-ahead"),
    ([18, 17, 17, 17, 17, 17, 17, 18, 17, 17, 17, 17, 17, 17, 17, 17], "wall-ahead"),
    ([9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9], "wall-ahead"),
    ([24, 34, 55, 59, 59, 59, 29, 30, 24, 33, 55, 59, 59, 59, 29, 30], "gap-left"),
    ([24, 34, 51, 51, 51, 51, 25, 22, 24, 33, 51, 51, 51, 51, 25, 22], "gap-left"),
    ([24, 34, 43, 43, 43, 43, 44, 18, 24, 33, 43, 43, 43, 43, 44, 18], "gap-left"),
    ([42, 58, 59, 59, 29, 29, 29, 30, 42, 58, 59, 59, 29, 29, 29, 30], "gap-left"),
    ([42, 52, 51, 51, 21, 21, 21, 22, 42, 52, 51, 51, 21, 21, 21, 22], "gap-left"),
    ([42, 44, 43, 43, 13, 13, 13, 13, 42, 44, 43, 43, 13, 13, 13, 13], "gap-left"),
    ([30, 29, 29, 29, 59, 59, 58, 42, 30, 29, 29, 29, 59, 59, 58, 42], "gap-right"),
    ([22, 21, 21, 21, 51, 51, 52, 42, 22, 21, 21, 21, 51, 51, 52, 42], "gap-right"),
    ([13, 13, 13, 13, 43, 43, 44, 42, 13, 13, 13, 13, 43, 43, 44, 42], "gap-right"),
    ([30, 29, 59, 59, 59, 55, 34, 24, 30, 29, 59, 59, 59, 55, 33, 24], "gap-right"),
    ([22, 25, 51, 51, 51, 51, 34, 24, 22, 25, 51, 51, 51, 51, 33, 24], "gap-right"),
    ([18, 44, 43, 43, 43, 43, 34, 24, 18, 44, 43, 43, 43, 43, 33, 24], "gap-right"),
]
COLOUR = {"open": "green", "wall-ahead": "red",
          "gap-left": "blue", "gap-right": "orange"}

def distance(a, b):
    # the straight-line distance between two views
    return math.sqrt(sum((p - q) ** 2 for p, q in zip(a, b)))

def nearest(view):
    # the label of the example most like this view
    best_label, best_d = None, 1e18
    for feats, label in DATA:
        d = distance(feats, view)
        if d < best_d:
            best_label, best_d = label, d
    return best_label

trail = {label: [] for label in COLOUR}
forward(30)
wait(1)       # see "Readings of 400" below
while position()[1] < 50:
    view = tof_grid()[16:32]        # the 16 level readings
    # how far to the nearest example of each label
    for label in COLOUR:
        plot(label, min(distance(f, view)
                        for f, l in DATA if l == label))
    answer = nearest(view)
    x, y = position()
    trail[answer].append((50 + x, 10 + y))
    for label in COLOUR:
        draw(label, trail[label], COLOUR[label])
    print("y =", round(y), answer)
    wait(0.2)
stop()

Now the chart has a line for the nearest example of each label, and the dips are the places where an example was recorded: the open line touches zero at y = 24, where one of the new examples is exactly the robot's view. The robot says open until y = 29 and wall-ahead from y = 30, 30 cm from the wall, with nothing wrong in between.

A vote among the k nearest

With k = 1, one example decides every answer, so one odd example can flip it. With a bigger k, several of the nearest examples vote and the label with the most votes wins. If two labels tie, this program gives it to the label of the nearer example.

Here the robot drives to the left end of the wall and then slides sideways along it to the right end, with its centre about 20 cm from the wall, and k = 3.

from bugbot import *
import math
connect()

K = 3        # how many neighbours get a vote

DATA = [
    ([54, 52, 51, 51, 51, 51, 52, 54, 54, 52, 51, 51, 51, 51, 52, 54], "open"),
    ([16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16], "wall-ahead"),
    ([36, 47, 46, 46, 46, 16, 16, 16, 36, 47, 46, 46, 46, 16, 16, 16], "gap-left"),
    ([16, 16, 16, 46, 46, 46, 47, 36, 16, 16, 16, 46, 46, 46, 47, 36], "gap-right"),
    ([400, 400, 61, 61, 61, 61, 400, 400, 96, 62, 61, 61, 61, 61, 62, 64], "open"),
    ([52, 50, 49, 49, 49, 49, 50, 52, 51, 50, 49, 49, 49, 49, 50, 51], "open"),
    ([39, 38, 37, 37, 37, 37, 38, 39, 39, 38, 37, 37, 37, 37, 38, 39], "open"),
    ([400, 400, 61, 61, 61, 61, 400, 400, 64, 62, 61, 61, 61, 61, 62, 64], "open"),
    ([52, 50, 49, 49, 49, 49, 50, 52, 51, 50, 49, 49, 49, 49, 50, 51], "open"),
    ([39, 38, 37, 37, 37, 37, 38, 39, 39, 38, 37, 37, 37, 37, 38, 39], "open"),
    ([400, 400, 61, 61, 61, 61, 400, 400, 64, 62, 61, 61, 61, 61, 62, 96], "open"),
    ([52, 50, 49, 49, 49, 49, 50, 52, 51, 50, 49, 49, 49, 49, 50, 51], "open"),
    ([39, 38, 37, 37, 37, 37, 38, 39, 39, 38, 37, 37, 37, 37, 38, 39], "open"),
    ([26, 25, 25, 25, 25, 25, 25, 26, 26, 25, 25, 25, 25, 25, 25, 26], "wall-ahead"),
    ([18, 17, 17, 17, 17, 17, 17, 18, 17, 17, 17, 17, 17, 17, 17, 17], "wall-ahead"),
    ([9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9], "wall-ahead"),
    ([26, 25, 25, 25, 25, 25, 25, 26, 26, 25, 25, 25, 25, 25, 25, 26], "wall-ahead"),
    ([18, 17, 17, 17, 17, 17, 17, 18, 17, 17, 17, 17, 17, 17, 17, 17], "wall-ahead"),
    ([9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9], "wall-ahead"),
    ([26, 25, 25, 25, 25, 25, 25, 26, 26, 25, 25, 25, 25, 25, 25, 26], "wall-ahead"),
    ([18, 17, 17, 17, 17, 17, 17, 18, 17, 17, 17, 17, 17, 17, 17, 17], "wall-ahead"),
    ([9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9], "wall-ahead"),
    ([24, 34, 55, 59, 59, 59, 29, 30, 24, 33, 55, 59, 59, 59, 29, 30], "gap-left"),
    ([24, 34, 51, 51, 51, 51, 25, 22, 24, 33, 51, 51, 51, 51, 25, 22], "gap-left"),
    ([24, 34, 43, 43, 43, 43, 44, 18, 24, 33, 43, 43, 43, 43, 44, 18], "gap-left"),
    ([42, 58, 59, 59, 29, 29, 29, 30, 42, 58, 59, 59, 29, 29, 29, 30], "gap-left"),
    ([42, 52, 51, 51, 21, 21, 21, 22, 42, 52, 51, 51, 21, 21, 21, 22], "gap-left"),
    ([42, 44, 43, 43, 13, 13, 13, 13, 42, 44, 43, 43, 13, 13, 13, 13], "gap-left"),
    ([30, 29, 29, 29, 59, 59, 58, 42, 30, 29, 29, 29, 59, 59, 58, 42], "gap-right"),
    ([22, 21, 21, 21, 51, 51, 52, 42, 22, 21, 21, 21, 51, 51, 52, 42], "gap-right"),
    ([13, 13, 13, 13, 43, 43, 44, 42, 13, 13, 13, 13, 43, 43, 44, 42], "gap-right"),
    ([30, 29, 59, 59, 59, 55, 34, 24, 30, 29, 59, 59, 59, 55, 33, 24], "gap-right"),
    ([22, 25, 51, 51, 51, 51, 34, 24, 22, 25, 51, 51, 51, 51, 33, 24], "gap-right"),
    ([18, 44, 43, 43, 43, 43, 34, 24, 18, 44, 43, 43, 43, 43, 33, 24], "gap-right"),
]
COLOUR = {"open": "green", "wall-ahead": "red",
          "gap-left": "blue", "gap-right": "orange"}

def distance(a, b):
    # the straight-line distance between two views
    return math.sqrt(sum((p - q) ** 2 for p, q in zip(a, b)))

def vote(view, k):
    # the k nearest examples each vote for their label
    ranked = sorted(DATA, key=lambda ex: distance(ex[0], view))
    votes = {label: 0 for label in COLOUR}
    for feats, label in ranked[:k]:
        votes[label] += 1
    most = max(votes.values())
    for feats, label in ranked:     # a tie goes to the nearer
        if votes[label] == most:
            return label, votes

def wrapped(h):
    return (h + 180) % 360 - 180

def go_to(x, y, speed):
    # slide towards (x, y), holding the heading at 0
    px, py = position()
    a = math.radians(wrapped(math.degrees(
        math.atan2(x - px, y - py)) - heading()))
    drive(speed * math.cos(a), speed * math.sin(a),
          wrapped(0 - heading()) * 3)

# get to the left end of the wall
while math.dist(position(), (-38, 40)) > 2:
    go_to(-38, 40, 60)
    wait(0.1)
stop()
wait(0.4)

# slide along the wall to the right end, and classify
trail = {label: [] for label in COLOUR}
while position()[0] < 38:
    go_to(38, 40, 30)
    view = tof_grid()[16:32]        # the 16 level readings
    answer, votes = vote(view, K)
    for label in COLOUR:
        plot(label, votes[label])
    x, y = position()
    trail[answer].append((50 + x, 10 + y))
    for label in COLOUR:
        draw(label, trail[label], COLOUR[label])
    print("x =", round(x), answer, votes)
    wait(0.2)
stop()

The robot says gap-left until x = -32.6, wall-ahead from x = -31.6 to 33.1, and gap-right from x = 34.0. The wall's ends are at x = -36 and x = 36, so the robot says it is at a gap while its centre is past the end of the wall or within 2 to 4 cm of it. Almost every answer is 3 votes to 0, so the three nearest examples agree.

Choosing k

Change K in the demo above and run it again.

• K = 1 gives one wrong answer. At x = -30.6, just after the wall-ahead stretch has begun, it says gap-left. The nearest example there is a gap-left one, 53.2 away, but the next two are wall-ahead examples 54.8 away. With K = 3 those two outvote it. A small k follows every odd example.
• K = 21 shrinks both gaps. gap-left lasts only until x = -34.6, and gap-right starts at x = 35.6. At x = -38 the vote is 7 for gap-left, 7 for open, 4 for gap-right and 3 for wall-ahead, and gap-left only wins the tie because its nearest example is nearer. There are only 7 gap-left examples, so 7 votes is as many as it can ever get. The other 14 votes come from examples that are not much like the view at all.
• K = 34 lets every example vote every time: 10 for open, 10 for wall-ahead, 7 for each gap. A gap can never win. The robot says open at both ends of the wall.

So k trades one kind of mistake for another. Too small, and the answer follows every odd example. Too big, and the vote reaches examples from other situations, and the labels with the most examples win. K = 3, 5 and 7 all give clean answers on this slide.

Three ways to choose it:

1. Make it odd. With two labels, an odd k can never tie.
2. Start near the square root of the number of examples, a common rule of thumb. For 34 examples that is about 6, so try 5 or 7.
3. Test it. Keep some examples back, classify them with each k you are thinking of, and take the k that gets the most right. The examples you test with must not be in the list you compare against; the lesson Generalisation explains why.

Bad data: one wrong label

This time the first example in the list, the view of open space the robot recorded 50 cm from the wall, has been labelled wall-ahead by mistake. Everything else is the same as the 34 examples above, and K = 1.

from bugbot import *
import math
connect()

K = 1        # how many neighbours get a vote

# the 34 examples, with one mistake: the first view
# was open space, but it was labelled wall-ahead
DATA = [
    ([54, 52, 51, 51, 51, 51, 52, 54, 54, 52, 51, 51, 51, 51, 52, 54], "wall-ahead"),   # WRONG: this is open space
    ([16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16], "wall-ahead"),
    ([36, 47, 46, 46, 46, 16, 16, 16, 36, 47, 46, 46, 46, 16, 16, 16], "gap-left"),
    ([16, 16, 16, 46, 46, 46, 47, 36, 16, 16, 16, 46, 46, 46, 47, 36], "gap-right"),
    ([400, 400, 61, 61, 61, 61, 400, 400, 96, 62, 61, 61, 61, 61, 62, 64], "open"),
    ([52, 50, 49, 49, 49, 49, 50, 52, 51, 50, 49, 49, 49, 49, 50, 51], "open"),
    ([39, 38, 37, 37, 37, 37, 38, 39, 39, 38, 37, 37, 37, 37, 38, 39], "open"),
    ([400, 400, 61, 61, 61, 61, 400, 400, 64, 62, 61, 61, 61, 61, 62, 64], "open"),
    ([52, 50, 49, 49, 49, 49, 50, 52, 51, 50, 49, 49, 49, 49, 50, 51], "open"),
    ([39, 38, 37, 37, 37, 37, 38, 39, 39, 38, 37, 37, 37, 37, 38, 39], "open"),
    ([400, 400, 61, 61, 61, 61, 400, 400, 64, 62, 61, 61, 61, 61, 62, 96], "open"),
    ([52, 50, 49, 49, 49, 49, 50, 52, 51, 50, 49, 49, 49, 49, 50, 51], "open"),
    ([39, 38, 37, 37, 37, 37, 38, 39, 39, 38, 37, 37, 37, 37, 38, 39], "open"),
    ([26, 25, 25, 25, 25, 25, 25, 26, 26, 25, 25, 25, 25, 25, 25, 26], "wall-ahead"),
    ([18, 17, 17, 17, 17, 17, 17, 18, 17, 17, 17, 17, 17, 17, 17, 17], "wall-ahead"),
    ([9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9], "wall-ahead"),
    ([26, 25, 25, 25, 25, 25, 25, 26, 26, 25, 25, 25, 25, 25, 25, 26], "wall-ahead"),
    ([18, 17, 17, 17, 17, 17, 17, 18, 17, 17, 17, 17, 17, 17, 17, 17], "wall-ahead"),
    ([9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9], "wall-ahead"),
    ([26, 25, 25, 25, 25, 25, 25, 26, 26, 25, 25, 25, 25, 25, 25, 26], "wall-ahead"),
    ([18, 17, 17, 17, 17, 17, 17, 18, 17, 17, 17, 17, 17, 17, 17, 17], "wall-ahead"),
    ([9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9], "wall-ahead"),
    ([24, 34, 55, 59, 59, 59, 29, 30, 24, 33, 55, 59, 59, 59, 29, 30], "gap-left"),
    ([24, 34, 51, 51, 51, 51, 25, 22, 24, 33, 51, 51, 51, 51, 25, 22], "gap-left"),
    ([24, 34, 43, 43, 43, 43, 44, 18, 24, 33, 43, 43, 43, 43, 44, 18], "gap-left"),
    ([42, 58, 59, 59, 29, 29, 29, 30, 42, 58, 59, 59, 29, 29, 29, 30], "gap-left"),
    ([42, 52, 51, 51, 21, 21, 21, 22, 42, 52, 51, 51, 21, 21, 21, 22], "gap-left"),
    ([42, 44, 43, 43, 13, 13, 13, 13, 42, 44, 43, 43, 13, 13, 13, 13], "gap-left"),
    ([30, 29, 29, 29, 59, 59, 58, 42, 30, 29, 29, 29, 59, 59, 58, 42], "gap-right"),
    ([22, 21, 21, 21, 51, 51, 52, 42, 22, 21, 21, 21, 51, 51, 52, 42], "gap-right"),
    ([13, 13, 13, 13, 43, 43, 44, 42, 13, 13, 13, 13, 43, 43, 44, 42], "gap-right"),
    ([30, 29, 59, 59, 59, 55, 34, 24, 30, 29, 59, 59, 59, 55, 33, 24], "gap-right"),
    ([22, 25, 51, 51, 51, 51, 34, 24, 22, 25, 51, 51, 51, 51, 33, 24], "gap-right"),
    ([18, 44, 43, 43, 43, 43, 34, 24, 18, 44, 43, 43, 43, 43, 33, 24], "gap-right"),
]
COLOUR = {"open": "green", "wall-ahead": "red",
          "gap-left": "blue", "gap-right": "orange"}

def distance(a, b):
    # the straight-line distance between two views
    return math.sqrt(sum((p - q) ** 2 for p, q in zip(a, b)))

def vote(view, k):
    # the k nearest examples each vote for their label
    ranked = sorted(DATA, key=lambda ex: distance(ex[0], view))
    votes = {label: 0 for label in COLOUR}
    for feats, label in ranked[:k]:
        votes[label] += 1
    most = max(votes.values())
    for feats, label in ranked:     # a tie goes to the nearer
        if votes[label] == most:
            return label, votes

trail = {label: [] for label in COLOUR}
forward(30)
wait(1)       # see "Readings of 400" below
while position()[1] < 50:
    view = tof_grid()[16:32]        # the 16 level readings
    answer, votes = vote(view, K)
    for label in COLOUR:
        plot(label, votes[label])
    x, y = position()
    trail[answer].append((50 + x, 10 + y))
    for label in COLOUR:
        draw(label, trail[label], COLOUR[label])
    print("y =", round(y), answer, votes)
    wait(0.2)
stop()

The robot calls open space a wall from the first reading at y = 4 until y = 11, 49 cm or more from the wall: a stretch of red dots in the open. That stretch is the area round the mislabelled example where it is the nearest one. A robot that stopped for wall-ahead would stop there and never reach the wall.

Set K = 3. On that stretch the vote is 2 for open and 1 for wall-ahead, because two correctly labelled examples are nearly as near. The answers come out the same as with the clean examples: open until y = 29, wall-ahead from y = 30. One wrong label is outvoted. If a whole spot had been labelled wrong, every example near it would be wrong too, and a vote among them would only repeat the mistake.

Other bad data to look for:

• Missing situations. The first demo had no example of a wall 30 to 35 cm away, so it made up an answer. KNN has no way to say "I have never seen this". One fix is to also report the distance to the nearest example, and answer unsure when it is large.
• Copies. The 34 examples hold only 24 different views: five of them appear three times each, with exactly the same 16 numbers. At x = -31.6 on the slide, the three nearest examples are all copies of one view, 52.2 away, so a vote of 3 is one example counted three times. At x = -30.6, the two wall-ahead votes that beat gap-left with K = 3 are two copies of one view too. Copies also make a test look better than it is, when a copy of a test view is still in the list.
• Labels that mean where instead of what. A label must describe what the robot sees from where it is. gap-left means "the wall ends to my left", wherever the robot is when it sees that.

Unbalanced data

The 34 examples are 10 open, 10 wall-ahead, 7 gap-left and 7 gap-right. That is not far from even, and with K = 3 it does no harm. The slide along the wall showed what happens when k grows: the labels with more examples take over, and at K = 34 the gaps can never win.

Real data is often much less even. Record examples as a robot drives about and most of them will be open, because that is where a robot spends most of its time, while the situations that matter most, like the gap you are looking for, are rare. Ways to deal with it:

• Record more of the rare situations on purpose, or keep the same number of examples for each label.
• Keep k small, so the vote stays among examples that are like the view.
• Weight each vote by how near the example is, for example by 1 / distance, so a few near examples outweigh many far ones.
• Measure how often each label is right, one label at a time. A classifier that always says open can be right most of the time and still be useless.

Readings of 400

The demos that drive towards the wall wait one second before they start comparing. At the start, 60 cm from the wall, four of the 16 readings are 400: the sensor's way of saying it found nothing in range. The difference between 400 and the 52 to 54 cm in the open example is 346 to 348 in each of those four columns. Squared and added up, those four columns come to 481,640 of the 482,840 total between the start view and the open example, so the other 12 readings hardly count.

A value that means "nothing" is not a distance, and KNN treats it as one. Replace it before you compare, for example by counting anything above 100 cm as 100, or leave those readings out of the features.

Scaling the features

Distance adds up differences, so a feature measured in big numbers counts for more than one measured in small numbers. All 16 features here are distances in cm over the same range, which is why the lessons never scale them. Mix units and it matters.

Suppose you shrink a view to two features, both worked out from row 2. ahead is the mean of the middle two readings, in cm. side compares the two halves of the view: the mean of the left four readings minus the mean of the right four, divided by their sum. It is positive when the left side sees further, and it runs from -0.30 to 0.30 on the four examples. As the robot passes the left end of the wall in the slide above, row 2 of its view reads [36, 47, 51, 50, 50, 20, 20, 21]: ahead = 50, side = 0.25. The left side sees further, so this is gap-left.

As they are, a difference of 1 cm in ahead counts for more than the whole range of side, so the nearest example is open: the classifier has thrown away the only feature that tells the gaps apart. Scaled, each feature is turned into a number from 0 to 1 first:

scaled = (value − smallest) / (largest − smallest)

using the smallest and largest value of that feature in the four examples. Now both features count, and the nearest example is gap-left. Work out the smallest and largest from the examples once, and scale every new view with those same numbers. Another common way is to subtract the mean and divide by the standard deviation.

Putting it to work

A classifier on its own only names what it sees. In Project: situations the robot acts on the label: drive on for open, slide along the wall for wall-ahead, and go through the gap when it finds one. It also has to cope with an answer that flickers between two labels near the end of the wall, which it does by making its decision once and sticking to it.

Questions

What is the k-nearest neighbours algorithm in simple terms?

It answers a question about something new by looking at the examples most like it. You keep a list of examples, each one a set of numbers and a label. To classify something new you find the k examples nearest to it and take the label most of them have. On this page the numbers are 16 depth readings and the labels are what is in front of the robot.

How does KNN work, step by step?

Turn the new thing into the same features as the examples. Work out its distance to every example, usually the Euclidean distance. Sort the examples by distance and take the first k. Count the labels among them, and answer with the label that has the most votes, breaking a tie with the nearest example.

How do you choose k in KNN?

Try a few values and test each one on examples kept back from the list. On this page K = 1 let a single odd example flip one answer, K = 3, 5 and 7 gave clean answers, K = 21 shrank the gaps and K = 34 lost them altogether. An odd k near the square root of the number of examples is a common place to start.

Why is k usually an odd number?

With two labels, an odd k can never produce a tie. With three or more labels ties can still happen, so a program also needs a rule for them, such as taking the label of the nearest example.

Why do you need to scale features for KNN?

Because distance adds up the differences in every feature, and a feature measured in big numbers swamps one measured in small numbers. On this page a view at the end of the wall came out nearest to open when a feature in cm was mixed with one that runs from -0.3 to 0.3, and nearest to gap-left once both were scaled to run from 0 to 1.

What distance does KNN use?

Usually the Euclidean distance: the square root of the sum of the squared differences. Leaving out the square root gives the same order, so it gives the same answers. The Manhattan distance, the sum of the differences without squaring, counts one big difference for less. Any measure works if a smaller number means more alike for your data.

Is KNN supervised or unsupervised learning?

Supervised. It needs examples that already have the right label, and it answers with one of those labels. It is sometimes called a lazy learner, because it does no work until it is asked a question: there is no training step, just a list of examples.

What is the difference between KNN and k-means?

KNN classifies: it uses labelled examples, and k is the number of neighbours that vote. k-means clusters: it starts with unlabelled data and splits it into groups, and k is the number of groups. Both measure distances between points and both have a number called k, which is why they get mixed up.

What are the advantages and disadvantages of KNN?

It is short to write, needs no training, handles any number of labels, and you can explain every answer by pointing at the examples that voted for it. To add an example, you add it to the list. Against that, it compares with every example on every question, so it slows down as the list grows; it needs the features scaled; it cannot tell you when a view is unlike anything it has seen unless you check the distance yourself; and with a great many features, most examples end up at similar distances and nearness means less.

How does KNN handle unbalanced data?

Badly, if k is large. The labels with the most examples win more votes, and on this page, with every example voting, the gaps could never win. Keep k small, record more examples of the rare labels, keep the same number of each, or weight each vote by how near the example is.

How do you write KNN in Python?

Keep the examples as a list of (features, label) pairs. Write a distance function that zips two lists together and returns the square root of the sum of squared differences. To classify a view, sort the examples by their distance to it with sorted(DATA, key=...), count the labels in the first k with a dictionary, and return the label with the most votes. The vote function in the demos above is ten lines.

Is k-nearest neighbours on the GCSE or A level specification?

It is not named in the GCSE or A level Computer Science specifications (AQA, OCR, Edexcel, Eduqas). The programming it needs is on them all: lists, loops, functions, sorting and dictionaries, and the maths is Pythagoras. It makes a good A level Computer Science programming project, because you can collect your own data, test the classifier on examples you held back, and show how k and the data change the results.

Learn it step by step

These lessons build the same ideas one at a time, each with tasks the simulator marks.

1. 8.1 See as numbers Learning, Robot club
2. 8.2 Collecting data Learning, Robot club
3. 8.3 Nearest neighbour Learning, Robot club
4. 8.8 Project: situations Learning, Robot club
5. U12.3 Generalisation Learning, and the capstone, University