0x50Lesson 6 of 12

Teaching a machine to classify

Classify new examples by asking their nearest neighbors, choose k, and see decision boundaries form.

20 min 6-question quiz 2 code exercises

By the end of this lesson you can

Measure the distance between two examples
Classify with a majority vote of the k nearest neighbors
Explain how the choice of k changes the result

Regression predicts a number. Classification predicts a category: spam or not, which digit, which species. One of the simplest and most intuitive classifiers is k-nearest neighbors (k-NN), and it works the way you’d judge a new restaurant: ask the people most like you.

To classify a new example:

Measure its distance to every training example.
Take the k closest ones.
Let them vote: the most common label wins.

With two features, distance is the straight-line (Euclidean) distance you know from geometry:

$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$

Try it

Ask the neighbors

Click anywhere on the grid to drop a new point; lines connect it to its k nearest neighbors, and the vote decides its class. Try a point right between the two groups, then change k from 1 to 9 and watch whether the verdict flips.

Class A Class B

Click the grid to try it out.

knn.py

1import math
2from collections import Counter
3
4training = [((1, 2), "apple"), ((2, 3), "apple"), ((3, 1), "apple"),
5            ((7, 7), "orange"), ((8, 6), "orange"), ((6, 8), "orange")]
6
7def classify(point, k):
8    by_distance = sorted(training, key=lambda example: math.dist(point, example[0]))
9    votes = Counter(label for _, label in by_distance[:k])
10    return votes.most_common(1)[0][0]
11
12print(classify((2, 2), k=3))
13print(classify((7, 6), k=3))
14print(classify((4.5, 4.5), k=5))

Output

apple
orange
orange

Choosing k and seeing the boundary

If you colored every spot on the grid by what k-NN would predict there, you’d see regions separated by a decision boundary. The value of k shapes that boundary:

Small k (like 1) - every point follows its single closest neighbor. The boundary is jagged and one mislabeled example creates an island around itself: overfitting.
Large k - many neighbors vote, so the boundary is smooth. Too large and the biggest class wins everywhere: underfitting.

In practice you try several values and keep the one that scores best on held-out data. An odd k avoids ties when there are two classes.

Key takeaways

k-NN classifies a new example by a majority vote of its k nearest training examples.
Distance is usually Euclidean: $\sqrt{\sum (a_i - b_i)^2}$ . Features need comparable scales.
Small k gives jagged boundaries (overfitting); large k gives over-smooth ones (underfitting).

Lesson quiz

6 questions · pass with 5 correct · up to 50 XP

Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.

Practice: write Python

Write Python in the editor and run it against sample inputs. Python runs locally in your browser using a WebAssembly runtime.

Exercise 1

Build a k-NN classifier

+25 XP

The first line has k and a query point x y. Every other line is a training example x y label. Print the labels of the k nearest neighbors (closest first, one line, space-separated), then prediction: LABEL by majority vote. Break vote ties by choosing the label of the nearer neighbor.

Fruit
Close call
Tie

main.py

Loading editor…

Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.

Exercise 2

Choose k with held-out data

+25 XP

Lines starting with train are training examples train x y label; lines starting with test are held-out examples in the same format. For k = 1, 3 and 5, classify every test example with k-NN (ties go to the nearer neighbor’s label) and print k=K accuracy=A% (whole percent). Then print best k: K - the smallest k with the highest accuracy.

A noisy point

main.py

Loading editor…

Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.

Questions about this lesson

Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.

Loading posts…