k-nearest neighbours

k-nearest neighbours (k-NN) is the simplest classifier there is: to label a new example, find the k training examples closest to it, and let them vote.

Distance

"Closest" needs a distance. With two features, the Euclidean distance between (x₁, y₁) and (x₂, y₂) is the straight-line distance:

d = √((x₁ − x₂)² + (y₁ − y₂)²)

With more features, add more squared differences under the root. The Manhattan distance, |x₁ − x₂| + |y₁ − y₂|, measures along the grid, like walking city blocks.

# (weight in grams, diameter in cm, fruit)
training = [
    (150, 7.0, "apple"), (170, 7.5, "apple"), (140, 6.8, "apple"),
    (130, 7.2, "orange"), (120, 6.5, "orange"), (125, 7.0, "orange"),
]

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

def classify(fruit, k=3):
    ranked = sorted(training, key=lambda t: distance(fruit, t))
    nearest = ranked[:k]
    votes = {}
    for t in nearest:
        votes[t[2]] = votes.get(t[2], 0) + 1
    return max(votes, key=votes.get), [(t[2], round(distance(fruit, t), 1)) for t in nearest]

label, why = classify((135, 7.1))
print("135 g, 7.1 cm ->", label, why)

The program sorts the training fruits by their distance to the new fruit and takes a vote of the nearest 3. Step through and watch the distances fill in.

Choosing k

• k = 1 follows every training example, noise included: it overfits (it is the memorizer of the last lesson).
• A large k smooths everything out; with k = all examples, it always predicts the most common class.
• Pick k with a validation set or cross-validation. For two classes use an odd k, so votes cannot tie.

Scale first

Here weight is in grams (around 150) and size in centimetres (around 7), so a 10-gram difference counts as much as a 10-centimetre one, which is a huge difference in size. Without scaling, k-NN would judge almost only by weight. Scale every feature (min-max or z-scores) before measuring distances.

A lazy learner

k-NN does no work when training: it just stores the examples. All the work comes at prediction time, when it measures the distance to every training example. That is fine for thousands of examples and slow for millions; special structures (k-d trees, approximate nearest-neighbour indexes) speed it up. It also needs to keep all the training data around.

Mark lesson complete