K-Nearest Neighbors, the game

Ask the neighbours

k-nearest neighbours (k-NN) is a simple, non-parametric classifier. To label a new point it finds the k closest training points and takes a majority vote of their classes. With k = 3, if two neighbours are red triangles and one is a blue square, the new point becomes a red triangle.

Measuring distance

Because k-NN uses raw distances, features on large scales dominate. Normalize (for example min–max scaling) before using it, as the article’s code does.

Slide the k

Small k follows every training point (overfitting); large k blurs everything together (underfitting). Find the sweet spot.

The playground uses R’s built-in iris data (150 flowers, 3 species) with just two features, sepal length and width, so you can see the decision regions. Every third flower is held out as a test set.

Lazy learners and too many dimensions

• Lazy learner: k-NN does no work at training time; it just stores the data and does all the work when predicting. Eager learners (logistic regression, trees) build a model up front and predict quickly.
• Curse of dimensionality: with many features, points spread out and the “nearest” neighbours stop being meaningfully near. Reduce dimensions or select features first.

Code it from scratch

The article builds k-NN from scratch on the iris CSV. Here is the core, compact and runnable:

import math
from collections import Counter

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

def predict(train, row, k=3):
    """train: list of (features, label); row: features of the new point."""
    neighbours = sorted(train, key=lambda t: euclidean(t[0], row))[:k]
    return Counter(label for _, label in neighbours).most_common(1)[0][0]

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import MinMaxScaler
from sklearn.neighbors import KNeighborsClassifier

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
scaler = MinMaxScaler().fit(X_train)
knn = KNeighborsClassifier(n_neighbors=5).fit(scaler.transform(X_train), y_train)
print(knn.score(scaler.transform(X_test), y_test))

Defeat the Neighbour Boss 🐲

Six questions, three hearts.

Keep levelling up

You learned how k-NN classifies by majority vote of the nearest points, how distance is measured, how k trades overfitting for underfitting, why k-NN is a lazy learner, and why it struggles in high dimensions.