8.3 Nearest neighbour worksheet

Questions 7 marks in all

[1 mark]What does this program print?

def difference(a, b):
    return sum((p - q) ** 2 for p, q in zip(a, b))

print(difference([10, 20, 30], [12, 20, 27]))

[1 mark]What does this program print?

def nearest(sample, data):
    best_label, best_d = None, 1e18
    for feats, label in data:
        d = sum((a - b) ** 2 for a, b in zip(feats, sample))
        if d < best_d:
            best_label, best_d = label, d
    return best_label

DATA = [([50, 50, 50], "open"), ([16, 16, 16], "wall-ahead"), ([45, 45, 16], "gap-left")]
print(nearest([40, 42, 20], DATA))

[1 mark]Why are the differences squared before adding them up?

ASo a negative difference counts as much as a positive one instead of cancelling it out
BTo make the numbers smaller
CBecause the depth grid is square
DSo that the answer is always a whole number

[1 mark]Around 30 cm from the wall, the classifier says gap-left when the truth is a wall ahead. What is the cure?

ARecord more samples, including views from in-between places
BWrite a cleverer nearest function
CDelete the gap-left sample
DUse rows 6 and 7 instead

[1 mark]The dataset has no sample labelled corner. The robot drives into a corner. What can nearest neighbour say?

AOne of the labels it has, whichever sample looks most like the corner
Bcorner
Cunsure
DNothing: it raises an error

[1 mark]A student tests nearest by classifying each sample in DATA and gets every one right. What does that show?

AVery little: each sample is at difference 0 from itself, so it always wins. Test on views it has not stored
BThe classifier is perfect and ready for the mat
CThe data has no wrong labels
DThe samples were recorded in enough places

[1 mark]Two views of 16 readings differ by exactly 1 cm in every column. What is their difference, using the sum of squared differences?

The task: nearest neighbour

Drive to (0, 15), (0, 40), (-38, 40) and (38, 40) in turn, and print spot <n>: <label> at each, using nearest against DATA.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
# maths: atan2, hypot, sin, cos, radians
import math

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

def go_to(x, y, speed=60):
    # where am I?
    px, py = position()
    a = math.radians(wrapped(math.degrees(math.atan2(x - px, y - py)) - heading()))
    # forward, sideways, rotation: -100 to 100 each, until the next command
    drive(speed * math.cos(a), speed * math.sin(a), wrapped(0 - heading()) * 3)

def near(x, y, cm=4):
    # where am I?
    px, py = position()
    return math.hypot(x - px, y - py) < cm

def drive_to(x, y):
    while not near(x, y):
        go_to(x, y)
        # pause 0.1 s (the robot keeps doing what it was told)
        wait(0.1)
    # all motors off
    stop()
    # pause 0.4 s (the robot keeps doing what it was told)
    wait(0.4)
def level_rows():
    # rows 2 and 3: the 16 readings that look straight ahead
    return tof_grid()[16:32]

def nearest(sample, data):
    # the label of the recorded sample most like this one (smallest sum of squared differences)
    best_label, best_d = None, 1e18
    for feats, label in data:
        d = sum((a - b) ** 2 for a, b in zip(feats, sample))
        if d < best_d:
            best_label, best_d = label, d
    return best_label
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'),
]
drive_to(0, 15)
print('spot 1:', nearest(level_rows(), DATA))

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/8-3-nearest-neighbour/
The simulator checks it and tells you when it passes. Nothing to install, no account.

8.3 Nearest neighbour

What this lesson is about

Questions 7 marks in all

The task: nearest neighbour

Challenges