Python nearest-neighbor classifier

A nearest-neighbor classifier makes a prediction by finding the training examples closest to a new point and voting on their labels. It has no learned weights, but it still teaches the core questions: how to measure distance, how many neighbors to use, and why feature scale matters. You will also compare distance metrics and choose k with leave-one-out validation.

Measure distance between points

Euclidean distance is the square root of the sum of squared differences. zip pairs the coordinates, and the expression works for any number of dimensions. Keep the function small so the distance rule is easy to inspect and replace.

def distance(a, b):
    return sum((x - y) ** 2 for x, y in zip(a, b)) ** 0.5

print(distance((1, 1), (4, 5)))

Two dimensions, one formula

Rank the training points

Compute a distance for every training point, then sort by that distance. Sorting pairs of (distance, label) keeps the label attached. For a small dataset this is enough; production libraries use faster indexes for large collections.

def distance(a, b):
    return sum((x - y) ** 2 for x, y in zip(a, b)) ** 0.5

points = [((1, 1), "a"), ((4, 4), "b"), ((1, 2), "a")]
target = (1, 1.5)
ranked = sorted(points, key=lambda item: distance(target, item[0]))
print([label for _, label in ranked])

Nearest labels first

Take a majority vote

For k neighbors, count their labels and choose the most common. A Counter makes the vote readable. Ties need a documented rule, such as the label of the nearest tied neighbor, so the classifier does not change answer depending on dictionary order.

from collections import Counter

labels = ["a", "a", "b"]
winner = Counter(labels).most_common(1)[0][0]
print(winner)

The most common label

Scale features before measuring

A feature measured in thousands can dominate one measured in single digits. Standardize or normalize each feature before computing distance. Fit the scaling parameters on training data only, then apply the same transformation to new points.

def distance(a, b):
    return sum((x - y) ** 2 for x, y in zip(a, b)) ** 0.5

print(round(distance((30, 30000), (31, 30000)), 1))
print(round(distance((30, 30000), (30, 31000)), 1))

Raw units are not comparable

The distance metric changes the ranking

Euclidean distance squares coordinate differences; Manhattan distance adds absolute differences. They encode different ideas of closeness, so the same points can produce a different neighbor order. Choose a metric that matches the data and validate it rather than assuming one is universal.

def euclidean(a, b):
    return sum((x - y) ** 2 for x, y in zip(a, b)) ** 0.5

def manhattan(a, b):
    return sum(abs(x - y) for x, y in zip(a, b))

points = [((0, 0), "a"), ((3, 3), "b"), ((1, 4), "a")]
target = (0, 2)
for name, metric in [("euclidean", euclidean), ("manhattan", manhattan)]:
    ranked = sorted((metric(point, target), label) for point, label in points)
    print(name, [(round(d, 2), label) for d, label in ranked])

Same points, different neighbors

Choose k with leave-one-out validation

A small k can follow noise; a large k can wash out local structure. Leave-one-out removes one training point, predicts it from the rest, and repeats. Compare k values on that signal before touching the final test set.

def distance(a, b):
    return sum((x - y) ** 2 for x, y in zip(a, b)) ** 0.5

points = [((0, 0), "a"), ((1, 1), "a"), ((5, 5), "b"), ((6, 5), "b")]

def predict(train, target, k):
    ranked = sorted((distance(point, target), label) for point, label in train)
    labels = [label for _, label in ranked[:k]]
    return max(sorted(set(labels)), key=labels.count)

for k in [1, 3]:
    correct = 0
    for i, (point, label) in enumerate(points):
        train = points[:i] + points[i + 1:]
        correct += predict(train, point, k) == label
    print(k, correct, "/", len(points))

Validate k before the final test

Try it yourself

Change the values, predict the output, then run the code. The Python runtime is downloaded the first time you press Run, so the first run can take a few seconds.