K-nearest neighbors

K-Nearest Neighbors (KNN) is one of the simplest and most intuitive machine learning algorithms. To classify a new data point, it looks at the K training examples closest to it and takes a vote — the majority class wins. For regression it averages the K neighbors' values instead.

This chapter covers:

• How the KNN algorithm works step by step
• Distance metrics: Euclidean, Manhattan, and Minkowski
• Why feature scaling is critical for KNN
• How to choose the right value for K
• Classification and regression with scikit-learn
• Evaluating a KNN classifier with a confusion matrix
• Strengths, limitations, and when to use KNN

How KNN Works

KNN is a lazy learner — it does no real "training." Instead it memorises the entire dataset and defers all computation to prediction time.

Given a new point, the algorithm:

1. Computes the distance from the new point to every training point.
2. Selects the K training points with the smallest distances (the "nearest neighbors").
3. Aggregates their labels:
   • Classification — the new point gets the most common class label.
   • Regression — the new point gets the average (or weighted average) of the neighbors' target values.

Because there is no model to train, adding new data is trivial — just append to the dataset. The trade-off is that prediction is slow for large datasets because the full distance calculation runs every time.

Distance Metrics

The "nearest" in KNN is defined by a distance function. The default in scikit-learn is Euclidean distance, the straight-line distance in n-dimensional space:

d(p, q) = sqrt( (p1-q1)² + (p2-q2)² + … + (pn-qn)² )

Two common alternatives:

You can change the metric in scikit-learn with the metric parameter:

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=5, metric='manhattan')

Why Feature Scaling Is Critical

KNN computes raw distances. A feature measured in thousands (such as salary) will completely dominate a feature measured in single digits (such as years of experience), even if the smaller feature is more informative.

Always scale features before using KNN. See the feature scaling chapter for a full explanation; the short version is:

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)   # fit on training data only
X_test_scaled  = scaler.transform(X_test)         # apply same transform to test data

Never call fit_transform on the test set — that would leak test-set statistics into the scaler.

Choosing K

K controls the bias-variance trade-off:

• Small K (e.g. K=1) — very flexible, fits the training data tightly, but noisy and prone to overfitting. A single outlier neighbor can change the prediction.
• Large K — smoother decision boundary, lower variance, but may underfit and blur real class boundaries.

The standard approach is to try a range of K values and pick the one with the best cross-validated accuracy:

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler

iris = load_iris()
X, y = iris.data, iris.target

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

k_range = range(1, 31)
cv_scores = []

for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X_scaled, y, cv=5, scoring='accuracy')
    cv_scores.append(scores.mean())

best_k = k_range[np.argmax(cv_scores)]
print(f"Best K: {best_k}, CV Accuracy: {max(cv_scores):.4f}")

Expected output:

Best K: 6, CV Accuracy: 0.9667

For more detail on cross-validation see the cross-validation chapter.

Practical rules of thumb:

• Prefer odd K for binary classification to avoid ties.
• A common starting point is K = sqrt(n) where n is the number of training samples.
• Always validate with cross-validation rather than guessing.

KNN Classification with scikit-learn

The following example uses the Iris dataset — a real multiclass problem — and walks through the complete workflow: split, scale, train, predict, evaluate.

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.metrics import accuracy_score, classification_report

# 1. Load a real dataset
iris = load_iris()
X, y = iris.data, iris.target

# 2. Split into training and test sets
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

# 3. Scale features — critical for KNN
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled  = scaler.transform(X_test)

# 4. Train the classifier
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_scaled, y_train)

# 5. Predict and evaluate
y_pred = knn.predict(X_test_scaled)
print(f"Accuracy: {accuracy_score(y_test, y_pred):.2f}")
print()
print(classification_report(y_test, y_pred, target_names=iris.target_names))

Expected output:

Accuracy: 0.93

              precision    recall  f1-score   support

      setosa       1.00      1.00      1.00        10
  versicolor       0.83      1.00      0.91        10
   virginica       1.00      0.80      0.89        10

    accuracy                           0.93        30
   macro avg       0.94      0.93      0.93        30
weighted avg       0.94      0.93      0.93        30

KNN with K=5 achieves 93% accuracy on this 30-sample test set. Setosa is classified perfectly because it is linearly separable from the other two; versicolor and virginica overlap somewhat, causing a few misclassifications.

Note the stratify=y argument in train_test_split — this preserves the class proportions in each split, which is especially important for imbalanced datasets. See train/test split for details.

Evaluating with a Confusion Matrix

A confusion matrix shows exactly which classes the model confuses with each other:

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.metrics import confusion_matrix

iris = load_iris()
X, y = iris.data, iris.target

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_s, y_train)
y_pred = knn.predict(X_test_s)

cm = confusion_matrix(y_test, y_pred)
print(cm)

Expected output:

[[10  0  0]
 [ 0 10  0]
 [ 0  2  8]]

Each row is a true class; each column is a predicted class. Diagonal values are correct predictions; off-diagonal values are misclassifications. Here, 2 virginica samples were misclassified as versicolor. See the confusion matrix chapter for a deeper explanation.

KNN Regression with scikit-learn

For regression, KNN predicts the mean of the K nearest neighbors' target values. Replace KNeighborsClassifier with KNeighborsRegressor:

from sklearn.datasets import fetch_california_housing
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error, r2_score
import numpy as np

# Load a real regression dataset (a subset for speed)
housing = fetch_california_housing()
X, y = housing.data[:2000], housing.target[:2000]

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

knn_reg = KNeighborsRegressor(n_neighbors=5)
knn_reg.fit(X_train_s, y_train)
y_pred = knn_reg.predict(X_test_s)

rmse = np.sqrt(mean_squared_error(y_test, y_pred))
r2   = r2_score(y_test, y_pred)
print(f"RMSE: {rmse:.4f}")
print(f"R²:   {r2:.4f}")

Expected output:

RMSE: 0.4217
R²:   0.8053

RMSE is in the same units as the target (median house value in $100k). R² of 0.81 means the model explains about 81% of the variance on this 2,000-sample subset — a strong result for an untuned KNN baseline.

Weighted KNN

By default, all K neighbors have equal weight regardless of how close they are. Setting weights='distance' makes closer neighbors count more:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score

iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

knn_uniform  = KNeighborsClassifier(n_neighbors=5, weights='uniform')
knn_distance = KNeighborsClassifier(n_neighbors=5, weights='distance')

knn_uniform.fit(X_train_s, y_train)
knn_distance.fit(X_train_s, y_train)

print(f"Uniform weights accuracy:  {accuracy_score(y_test, knn_uniform.predict(X_test_s)):.2f}")
print(f"Distance weights accuracy: {accuracy_score(y_test, knn_distance.predict(X_test_s)):.2f}")

Expected output:

Uniform weights accuracy:  0.93
Distance weights accuracy: 0.97

Distance weighting improves accuracy here from 0.93 to 0.97 — closer neighbors carry more influence, which helps resolve ambiguous borderline cases.

Strengths and Limitations

When to use KNN

• The dataset is small to medium-sized (tens of thousands of samples).
• You need a quick, interpretable baseline — KNN is easy to explain and debug.
• You have well-scaled, low-dimensional features.
• The decision boundary is complex and non-linear.

When to avoid KNN

• Large datasets. Prediction time scales with the number of training samples (O(n·d) per query). For millions of samples, consider approximate nearest-neighbor libraries (Faiss, Annoy) or switch to a faster algorithm.
• High-dimensional data. In many dimensions, all points become roughly equidistant — the "curse of dimensionality." KNN degrades rapidly beyond ~20 features. Apply dimensionality reduction first (PCA, feature selection).
• Irrelevant features. Every feature participates in the distance calculation. Noisy or irrelevant features dilute the signal. Remove or reduce them before training.
• Memory-constrained environments. KNN stores the entire training set; a dataset with millions of rows occupies significant RAM.

Summary

Related chapters:

• Feature scaling — why and how to scale before KNN
• Train/test split — splitting data correctly
• Cross-validation — choosing K with k-fold CV
• Confusion matrix — interpreting classification results
• Grid search — systematic hyperparameter tuning