Classifying sensor data with k-NN

Regression predicts a number. Many robot decisions are not numbers but categories: is the line to my left, under me, or to my right? Is that sound a motor or a voice? Is this IMU window a wave or a fall? That job is called classification, and the friendliest algorithm to start with has no training phase at all. It is called k-nearest neighbours (k-NN), and its whole idea is: to label a new reading, find the most similar readings you already know and let them vote.

Features and labels

A line-following robot has two downward-facing reflectance sensors, one on the left and one on the right. A dark line reflects less infrared light, so it gives a lower reading. Each moment gives a pair (left, right) in the range 0 to 1000. The pair is the feature vector, and the answer we want is the label.

If the readings were always exactly those numbers you would write three if statements and be done. Real readings wobble with floor colour, lighting, height and battery voltage, so the clusters smear into each other. A learned classifier handles that smear without you hand-picking thresholds.

k-NN from scratch

Similarity needs a distance. For two readings p = (l1, r1) and q = (l2, r2) we use the straight-line (Euclidean) distance:

d(p, q) = sqrt((l1 - l2)^2 + (r1 - r2)^2)

The algorithm has three steps. Compute the distance from the new reading to every stored example. Sort and keep the k closest. Return the label that most of those k carry. Nothing is "trained": the stored examples are the model. Here is the whole thing on a nine-point dataset, printing the neighbours so you can see the vote.

knn_vote.py

ResetRun

import math # (left sensor, right sensor) -> where the line is train = [ ((250, 720), "left"), ((300, 650), "left"), ((220, 600), "left"), ((450, 430), "straight"), ((500, 480), "straight"), ((420, 520), "straight"), ((700, 260), "right"), ((650, 310), "right"), ((730, 350), "right"), ] def distance(p, q): return math.sqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) def classify(point, k): ranked = sorted(train, key=lambda row: distance(point, row[0])) for features, label in ranked[:k]: print(" neighbour", features, label, "dist=%.1f" % distance(point, features)) votes = [label for _, label in ranked[:k]] return max(votes, key=votes.count) new_reading = (580, 380) print("new reading:", new_reading) print("answer:", classify(new_reading, 3))

The new reading (580, 380) sits between the straight and right groups. Its three nearest neighbours are (650, 310) labelled right at distance 99.0, then (500, 480) and (450, 430) labelled straight at 128.1 and 139.3. Check the second by hand: the differences are 80 and -100, and sqrt(6400 + 10000) = sqrt(16400), about 128.1. The vote is two for straight and one for right, so the answer is straight. With k = 1 the answer would have been right, since the single closest point says so. That flip is the whole story of choosing k, and we will measure it next.

Train and test

How good is the classifier? Not the accuracy on the examples it stores, because those are trivially easy for it (more on that below). Hold some data back. Split the labelled data into a training set, which k-NN stores, and a test set, which it never sees until grading. Accuracy is correct predictions divided by total predictions.

The snippet generates 120 noisy readings around the three centres, using a fixed seed so the result is repeatable. The clusters overlap on purpose, like a real floor with a worn patch. Every fourth reading goes into the test set, giving 90 training and 30 test examples. Then it scores several values of k on both sets.

knn_accuracy.py

ResetRun

import random import math random.seed(2) CENTRES = {"left": (250, 700), "straight": (450, 450), "right": (700, 250)} NAMES = ["left", "straight", "right"] data = [] for i in range(120): label = NAMES[i % 3] cx, cy = CENTRES[label] point = (cx + random.uniform(-250, 250), cy + random.uniform(-250, 250)) data.append((point, label)) train = [d for i, d in enumerate(data) if i % 4 != 3] test = [d for i, d in enumerate(data) if i % 4 == 3] print("train:", len(train), "test:", len(test)) def distance(p, q): return math.sqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) def knn_predict(point, k): ranked = sorted(train, key=lambda d: distance(point, d[0])) votes = [label for _, label in ranked[:k]] return max(votes, key=votes.count) def accuracy(rows, k): hits = sum(1 for p, label in rows if knn_predict(p, k) == label) return hits / len(rows) for k in [1, 3, 5, 9, 15]: print("k=%2d train acc=%.2f test acc=%.2f" % (k, accuracy(train, k), accuracy(test, k)))

You should see 90 training and 30 test examples, and then:

Overfitting, with numbers

Look at the k = 1 row. Training accuracy is a perfect 1.00 and test accuracy is only 0.77, which is 23 of 30. The reason is mechanical: when you classify a point that is itself in the training set, its nearest neighbour is itself at distance 0, so it always gets its own label back. A perfect score on training data therefore tells you nothing. With k = 1 the model has memorised every noisy, mislabelled-looking point and draws a ragged decision boundary around each one. This is overfitting: excellent on what it has seen, worse on what it has not.

Raising k smooths the boundary, because one odd point is outvoted by its neighbours. Training accuracy falls (the model can no longer memorise) while test accuracy rises, to 0.90 by k = 5. Push k too far and the opposite failure appears, underfitting: with k equal to the whole training set, every reading would receive the majority label, and the model ignores the sensors. The best k lives in between, and the test set is how you find the region.

An honest caveat about these numbers. A test set of 30 means one reading is worth 3.3 percentage points, so the gap between 0.83 and 0.90 is only two readings. The big effect, 0.77 versus the rest, is believable. The small ones are not proof. In practice you would collect more test data before trusting a small difference.

Why k-NN fits robots, and where it stops

k-NN is easy to debug, needs no training time and handles odd-shaped classes, which is why it is the right first classifier. It also has costs that matter on a microcontroller. It must keep every training example in memory, and each prediction computes a distance to all of them, so the work grows with the dataset. With 90 stored points that is nothing. With 90,000 it will not fit in an Arduino, and the loop might miss its deadline. Later lessons turn to models that compress what they learned into a small, fixed set of parameters.