k-nearest neighbours

k-nearest neighbours (k-NN) makes a prediction for a new point by looking at the $k$ training points closest to it. For classification it takes a vote among them; for regression it averages their values. There is no training step at all: the model is the data.

How it works

1. Choose $k$ (say 5) and a distance measure.
2. For a new point, compute its distance to every training point.
3. Keep the $k$ closest.
4. Classification: predict the majority class among them. Regression: predict their mean.

Distance

The usual choice is Euclidean distance, the straight line between two points:

Manhattan distance, $\sum |a_j - b_j|$, is sometimes better for high dimensional or grid like data.

Because distance adds up feature differences, a feature measured in thousands swamps one measured in units. Always scale features before k-NN.

From scratch

import numpy as np
from collections import Counter

X_train = np.array([[1, 1], [1.5, 2], [2, 1], [6, 5], [7, 7], [6.5, 6]])
y_train = np.array(["a", "a", "a", "b", "b", "b"])

def predict(point, k=3):
    distances = np.sqrt(((X_train - point) ** 2).sum(axis=1))
    nearest = np.argsort(distances)[:k]
    votes = Counter(y_train[nearest])
    return votes.most_common(1)[0][0], distances[nearest].round(2)

print(predict(np.array([2, 2])))
print(predict(np.array([5, 5])))

With scikit-learn

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=0, stratify=y)

knn = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=5)).fit(X_train, y_train)
print("test accuracy:", round(knn.score(X_test, y_test), 3))

Choosing k

• $k = 1$: the prediction copies the single nearest point. Very flexible, very sensitive to noise. Overfits.
• Large $k$: predictions smooth out towards the overall majority. Underfits.
• Use an odd $k$ for binary classification to avoid ties.
• Pick $k$ by cross-validation, not by guessing.

from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline

X, y = load_iris(return_X_y=True)
for k in (1, 3, 5, 9, 15, 25):
    model = make_pipeline(StandardScaler(), KNeighborsClassifier(n_neighbors=k))
    score = cross_val_score(model, X, y, cv=5).mean()
    print(f"k={k:2d}  cv accuracy={score:.3f}")

Weighted voting

weights="distance" gives closer neighbours more say, which often helps when $k$ is large.

k-NN for regression

import numpy as np
from sklearn.neighbors import KNeighborsRegressor

X = np.array([[1], [2], [3], [4], [5], [6]])
y = np.array([10, 12, 15, 21, 24, 30])
reg = KNeighborsRegressor(n_neighbors=2).fit(X, y)
print(reg.predict([[3.5]]))     # mean of the two nearest: 15 and 21

Strengths and weaknesses

Strengths:

• No assumptions about the shape of the data; it can learn very irregular boundaries.
• Nothing to train, and easy to explain ("these are the five most similar past cases").
• Works for classification and regression.

Weaknesses:

• Prediction is slow, because every query is compared with every training point. Tree and hashing structures help, but it does not scale like a linear model.
• Needs all training data kept in memory.
• Suffers in high dimensions: with hundreds of features, every point is roughly equally far from every other and "nearest" stops meaning much. This is the curse of dimensionality.
• Sensitive to irrelevant features and to scaling.

Practice

1. Change the from scratch example to use Manhattan distance and see whether either prediction changes.
2. Run the k selection loop on the iris data without the scaler. Does the best k change?
3. Use weights="distance" in the iris pipeline and compare test accuracy.