Unit 2: Ask the Neighbours

Two numbers make a dot on a grid

A fruit with weight 150 and bumpiness 2 is the dot at across 150, up 2. Every example in your table is a dot somewhere.

And once things are dots, similar means close together. That is the whole trick of this unit.

Distance is Pythagoras

Go across, go up, and the straight line between is the long side of a right-angled triangle. Square both steps, add them, take the square root.

Python

import math

def distance(a, b):
    across = a[0] - b[0]
    up = a[1] - b[1]
    return math.sqrt(across * across + up * up)

print(distance([0, 0], [3, 4]))
print(round(distance([150, 2], [155, 3]), 2))

It prints

5.0
5.1

Why square, then unsquare?

Squaring throws away the minus signs, so going left counts the same as going right. The square root at the end brings the answer back to normal-sized numbers.

This works with any number of features. With three, you square three gaps and add them up.

The entire algorithm, in one sentence

To label something new: find the training example nearest to it, and copy that example's label.

That is nearest neighbour. There is nothing else to it, and it works surprisingly often.

Six known fruits, one mystery

The mystery fruit weighs 185g with bumpiness 7. The loop measures the distance to every fruit we know and keeps the smallest.

Python

import math

fruits = [
    [150, 2, "apple"],
    [170, 3, "apple"],
    [140, 1, "apple"],
    [180, 7, "orange"],
    [165, 8, "orange"],
    [190, 9, "orange"],
]

def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

mystery = [185, 7]
best = fruits[0]
for fruit in fruits:
    if distance(mystery, fruit) < distance(mystery, best):
        best = fruit

print("nearest:", best)
print("guess:", best[2])

It prints

nearest: [180, 7, 'orange']
guess: orange

This model does no work until you ask it

Training a nearest-neighbour model takes no time at all, because there is nothing to train — you just keep the table. All the effort moves to guessing time, where every single example has to be measured again.

So it is instant to learn and slow to use, which is the exact opposite of everything else in this track.

A fruit that gets it wrong

This one weighs 172g and has bumpiness 8. Bumpiness 8 is exactly what the oranges look like — but watch what nearest neighbour says.

Python

import math

fruits = [
    [150, 2, "apple"],
    [170, 3, "apple"],
    [140, 1, "apple"],
    [180, 7, "orange"],
    [165, 8, "orange"],
    [190, 9, "orange"],
]

def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

mystery = [172, 8]
for fruit in fruits:
    print(fruit[2], round(distance(mystery, fruit), 1))

It prints

apple 22.8
apple 5.4
apple 32.8
orange 8.1
orange 7.0
orange 18.0

Grams are shouting over bumpiness

The nearest fruit is an apple, 5.4 away. Look at where that 5.4 comes from: 2 grams and 5 bumps. Weights differ by tens, bumpiness differs by ones — so the distance is basically the weight difference, and the feature that actually tells apples from oranges barely counts.

The maths is not wrong. The units are.

Squash every feature to between 0 and 1

Take each column, subtract the smallest value in it, and divide by the range. Now every feature runs from 0 to 1 and none of them can shout over another. This is called scaling, and forgetting it is one of the commonest mistakes in real machine learning.

Python

def scale(fruit):
    weight = (fruit[0] - 140) / 50
    bumpiness = (fruit[1] - 1) / 8
    return [round(weight, 2), round(bumpiness, 2)]

print(scale([140, 1]))
print(scale([190, 9]))
print(scale([172, 8]))

It prints

[0.0, 0.0]
[1.0, 1.0]
[0.64, 0.88]

Same fruit, same code, different answer

Nothing changed except the numbers being on the same footing — and now the mystery fruit is an orange, which is what the fruit seller said all along.

Python

import math

fruits = [
    [150, 2, "apple"],
    [170, 3, "apple"],
    [140, 1, "apple"],
    [180, 7, "orange"],
    [165, 8, "orange"],
    [190, 9, "orange"],
]

def scale(f):
    return [(f[0] - 140) / 50, (f[1] - 1) / 8]

def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

mystery = scale([172, 8])
best = fruits[0]
for fruit in fruits:
    if distance(mystery, scale(fruit)) < distance(mystery, scale(best)):
        best = fruit

print(best[2])

It prints

orange

One neighbour can be unlucky

If the single closest example happens to be a mistake in the data, you copy the mistake. So ask the nearest k examples and let them vote. With k = 3, two oranges outvote one apple.

Python

import math

fruits = [
    [150, 2, "apple"],
    [170, 3, "apple"],
    [140, 1, "apple"],
    [180, 7, "orange"],
    [165, 8, "orange"],
    [190, 9, "orange"],
]

def scale(f):
    return [(f[0] - 140) / 50, (f[1] - 1) / 8]

def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

mystery = scale([172, 8])
ranked = sorted(fruits, key=lambda f: distance(mystery, scale(f)))

for fruit in ranked[0:3]:
    print(fruit[2])

It prints

orange
orange
orange

Keep k odd

With two labels and an even k you can get a tie — two votes each, and the program has to break it with something arbitrary. An odd k can never tie.

A bigger k is steadier but blurrier: at k = 6 here, every fruit votes, so the answer is just whichever label is commonest overall.

Now for the trap

Let us score the model on the six fruits we trained it on. It gets every one right. Perfect!

It is not perfect. Each fruit's nearest neighbour is itself, distance zero, so it copies its own label. A model that memorised the answers would score 100% too.

Python

import math

fruits = [
    [150, 2, "apple"],
    [170, 3, "apple"],
    [140, 1, "apple"],
    [180, 7, "orange"],
    [165, 8, "orange"],
    [190, 9, "orange"],
]

def scale(f):
    return [(f[0] - 140) / 50, (f[1] - 1) / 8]

def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

right = 0
for fruit in fruits:
    best = fruits[0]
    for other in fruits:
        if distance(scale(fruit), scale(other)) < distance(scale(fruit), scale(best)):
            best = other
    if best[2] == fruit[2]:
        right = right + 1

print(right, "out of", len(fruits))

It prints

6 out of 6

Hide some examples before you start

Split the data in two. The model may look at the training set only. The test set is locked away and used once, at the end, to ask the only question that matters: how does it do on fruit it has never seen?

Every honest number you will ever read about an AI comes from a test set.

Python

import math

train = [
    [150, 2, "apple"],
    [170, 3, "apple"],
    [180, 7, "orange"],
    [190, 9, "orange"],
]
test = [
    [140, 1, "apple"],
    [165, 8, "orange"],
]

def scale(f):
    return [(f[0] - 140) / 50, (f[1] - 1) / 8]

def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

right = 0
for fruit in test:
    best = train[0]
    for other in train:
        if distance(scale(fruit), scale(other)) < distance(scale(fruit), scale(best)):
            best = other
    print(fruit[2], "->", best[2])
    if best[2] == fruit[2]:
        right = right + 1

print(right / len(test))

It prints

apple -> apple
orange -> orange
1.0