K-Nearest Neighbors (KNN): Complete Guide — Classification and Regression in Python

Summary

K-Nearest Neighbors (KNN), or k nearest neighbors, is one of the most intuitive and most taught machine learning algorithms. Classified among non-parametric methods and lazy learning, KNN does not build any model during training: it simply memorizes the entire dataset and makes its decisions at prediction time. This remarkably simple approach proves surprisingly effective for both classification and regression, provided you choose your hyperparameters carefully — especially the number k of neighbors. This complete guide explores the mathematical principle, the intuition, the Python implementation with scikit-learn, the pitfalls to avoid, and concrete use cases.

Mathematical Principle of KNN

Formal Definition

The KNN algorithm relies on a core idea: for a new observation x, you determine its category or value by examining the k closest training points according to a chosen distance metric.

Let a training set D = {(x₁, y₁), (x₂, y₂), …, (xₙ, yₙ)} where each xᵢ ∈ ℝᵈ is a feature vector and yᵢ is the label (classification) or target value (regression).

For a new observation x:

1. Distance computation: Compute the distance between x and each point xᵢ in the training set according to a metric d(x, xᵢ).
2. Selection of the k nearest: Sort all distances and retain the k points with the smallest distances.
3. Aggregation:

• Classification: The predicted label ŷ is the mode (most frequent value) of the labels of the k neighbors. Formally:

  ŷ = argmax_{c} Σ_{i∈N_k(x)} 1(yᵢ = c)

  where N_k(x) denotes the set of k nearest neighbors of x.

• Regression: The predicted value ŷ is the mean (or weighted mean) of the values of the k neighbors. Formally:

  ŷ = (1/k) Σ_{i∈N_k(x)} yᵢ

Inverse Distance Weighting

In the weighted variant, each neighbor receives a weight inversely proportional to its distance: wᵢ = 1 / d(x, xᵢ). Thus, a very close neighbor influences the prediction more than a distant one. For weighted classification, the weights are summed per class; for weighted regression, the weighted average is computed:

ŷ = Σ wᵢ·yᵢ / Σ wᵢ

Distance Metrics

The choice of metric is crucial and depends on the nature of the data:

• Euclidean distance (L2): d(x, x’) = √Σ(xⱼ – x’ⱼ)². This is the default metric, ideal for normalized continuous data.
• Manhattan distance (L1): d(x, x’) = Σ|xⱼ – x’ⱼ|. More robust to outliers than Euclidean.
• Minkowski distance: Parametric generalization d(x, x’) = (Σ|xⱼ – x’ⱼ|ᵖ)^(1/p). With p=2, we get Euclidean; with p=1, Manhattan.
• Hamming distance: Useful for categorical or binary data, it counts the number of positions where vectors differ.
• Cosine distance: Measures the angle between two vectors, particularly suited to textual and high-dimensional data.

Intuition: like asking your neighbors for advice

Imagine you’re moving to a new city. To find out if a neighborhood is safe, you won’t consult national statistics: you ask the 5 nearest houses what they think. If 4 out of 5 say the neighborhood is quiet, you conclude it probably is. This is exactly the principle of KNN classification with k=5.

Similarly, to estimate the selling price of a house, you look at what similar houses in the neighborhood sold for. The average (or median) of those prices gives you a reasonable estimate. This is the principle of KNN regression.

This analogy also reveals the strengths and weaknesses of the algorithm:

• If your neighborhood is homogeneous (all neighbors are similar), the prediction will be reliable.
• If your neighborhood is very diverse or if an atypical neighbor skews the average, the result will be less good.
• The quality of the prediction directly depends on the relevance of the notion of “proximity” — hence the crucial importance of choosing the distance metric.

Python Implementation with scikit-learn

Classification on the Iris Dataset

from sklearn.datasets import load_iris
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_report, accuracy_score
import numpy as np
import matplotlib.pyplot as plt

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

# Train / test split
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

# Feature normalization — essential step for KNN
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# Train the KNN classifier
knn = KNeighborsClassifier(n_neighbors=5, metric='euclidean')
knn.fit(X_train_scaled, y_train)

# Predictions and evaluation
y_pred = knn.predict(X_test_scaled)
print(f"Accuracy: {accuracy_score(y_test, y_pred):.4f}")
print(classification_report(y_test, y_pred, target_names=iris.target_names))

Impact of the Choice of k

The parameter k is the most important in the algorithm. Too small (k=1), the model is too sensitive to noise and overfitting. Too large (k=n), it becomes trivial and underfits.

# Study of the impact of k
k_values = range(1, 31)
train_scores = []
test_scores = []

for k in k_values:
    knn = KNeighborsClassifier(n_neighbors=k, metric='euclidean')
    knn.fit(X_train_scaled, y_train)
    train_scores.append(knn.score(X_train_scaled, y_train))
    test_scores.append(knn.score(X_test_scaled, y_test))

# Visualization
plt.figure(figsize=(10, 6))
plt.plot(k_values, train_scores, 'b-', label='Training', marker='o')
plt.plot(k_values, test_scores, 'r-', label='Test', marker='s')
plt.xlabel('Value of k')
plt.ylabel('Accuracy')
plt.title('Impact of k on KNN Performance')
plt.legend()
plt.grid(True, alpha=0.3)
plt.show()

In general, we observe that accuracy on the training set decreases with k, while accuracy on the test set increases up to an optimum before declining. The optimal k typically lies between 3 and 15 depending on the complexity of the problem.

Comparison of Distance Metrics

metrics = ['euclidean', 'manhattan', 'minkowski']
results = {}

for m in metrics:
    params = {'n_neighbors': 5, 'metric': m}
    if m == 'minkowski':
        params['p'] = 3
    knn = KNeighborsClassifier(**params)
    scores = cross_val_score(knn, X_train_scaled, y_train, cv=5, scoring='accuracy')
    results[m] = scores.mean()
    print(f"{m}: {scores.mean():.4f} (+/- {scores.std():.4f})")

StandardScaler: Why Normalization is Essential

Since KNN is a distance-based algorithm, the scales of the features directly influence the results. Imagine a variable ranging from 0 to 1 and another from 0 to 10,000: the second will entirely dominate the distance computation, rendering the first useless. StandardScaler centers and scales each feature (zero mean, unit variance) to ensure they all contribute equally.

Decision Boundaries

from sklearn.inspection import DecisionBoundaryDisplay

# For visualization, we keep only 2 features
X_2d = X[:, :2]
X_train_2d, X_test_2d, y_train_2d, y_test_2d = train_test_split(
    X_2d, y, test_size=0.2, random_state=42
)
scaler_2d = StandardScaler()
X_train_2d_s = scaler_2d.fit_transform(X_train_2d)

knn_2d = KNeighborsClassifier(n_neighbors=7)
knn_2d.fit(X_train_2d_s, y_train_2d)

fig, ax = plt.subplots(figsize=(8, 6))
DecisionBoundaryDisplay.from_estimator(
    knn_2d, X_train_2d_s, alpha=0.3, ax=ax,
    response_method='predict', cmap='viridis'
)
ax.scatter(X_train_2d_s[:, 0], X_train_2d_s[:, 1], c=y_train_2d,
           edgecolor='k', s=50, cmap='viridis')
ax.set_title('KNN Decision Boundaries (k=7, 2 features)')
plt.show()

KNN Regression with KNeighborsRegressor

from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error, r2_score
from sklearn.datasets import make_regression

# Generate regression data
X_reg, y_reg = make_regression(
    n_samples=500, n_features=10, noise=20, random_state=42
)
X_reg_train, X_reg_test, y_reg_train, y_reg_test = train_test_split(
    X_reg, y_reg, test_size=0.2, random_state=42
)

scaler_reg = StandardScaler()
X_reg_train_s = scaler_reg.fit_transform(X_reg_train)
X_reg_test_s = scaler_reg.transform(X_reg_test)

knn_reg = KNeighborsRegressor(n_neighbors=7, weights='distance', metric='euclidean')
knn_reg.fit(X_reg_train_s, y_reg_train)

y_reg_pred = knn_reg.predict(X_reg_test_s)
print(f"R² : {r2_score(y_reg_test, y_reg_pred):.4f}")
print(f"RMSE : {np.sqrt(mean_squared_error(y_reg_test, y_reg_pred)):.4f}")

Detailed Hyperparameters

Practical Tuning Tips

• Start with k=5 with ‘uniform’ and ‘euclidean’, then adjust.
• Use cross_val_score or GridSearchCV to find the optimal k automatically.
• Test weight=’distance’ if you suspect the k neighbors aren’t all equally relevant.
• For high-dimensional data (>50 features), ‘brute’ is often more efficient because tree structures lose their advantage.
• n_jobs=-1 significantly speeds up predictions on large datasets.

Advantages and limitations of K-Nearest Neighbors

Advantages

1. Conceptual simplicity: The algorithm can be understood in five minutes, making it ideal for communicating with non-technical stakeholders.
2. No distribution assumptions: Unlike logistic regression or linear discriminant analysis, KNN does not assume any particular form for the data — it is truly non-parametric.
3. Adaptability to complex boundaries: Decision boundaries can be arbitrarily complex, since KNN learns locally.
4. Incremental updates: Adding new data does not require any retraining — simply add it to the existing stock.
5. Versatility: The same algorithm works for classification, regression, and even anomaly detection.

Limitations

1. High computational cost: Each prediction requires computing distances to all training data points — O(n·d) per prediction, where n is the number of samples and d the dimension.
2. Curse of dimensionality: In high dimensions, all distances tend to become similar, making the notion of “nearest neighbor” increasingly meaningless. This is one of the most dreaded problems in machine learning.
3. Sensitivity to noise and outliers: A mislabeled example in the immediate neighbors can skew the prediction, especially with a small k.
4. Normalization requirement: Without feature scaling, results are often poor.
5. Significant memory usage: The algorithm must store the entire training dataset, which can be a problem for very large datasets.
6. Imbalanced data: If one class is overwhelmingly dominant, it will systematically dominate the neighbor vote.

4 Concrete Use Cases for K-Nearest Neighbors

1. Movie Recommendation

Platforms like Netflix or Prime Video use variants of KNN to recommend content. Each movie is represented by a feature vector (genre, duration, director, actors, ratings). To recommend a movie to a user, you find the k closest movies to the ones they liked and suggest the ones they haven’t seen yet. With cosine distance, this approach captures taste similarity particularly well.

2. Assisted Medical Diagnosis

A diagnostic assistance system can compare a new patient’s profile (symptoms, test results, medical history) with patients whose diagnosis is already known. The k most similar patients help estimate the probability of different pathologies. The major advantage here is transparency: you can explain the decision by showing similar cases, which is crucial in medicine.

3. Banking Fraud Detection

Fraudulent transactions often present atypical profiles compared to legitimate transactions from the same customer. Using KNN, you can identify transactions whose k nearest neighbors are mostly labeled as fraudulent. Weighted voting is particularly useful here: a transaction very close to a known fraud case will receive a high alert score.

4. Handwriting Recognition

The famous MNIST dataset (70,000 28×28 handwritten digit images) is a classic benchmark for KNN. Each image is flattened into a vector of 784 pixels. With appropriate preprocessing (normalization, dimensionality reduction via PCA) and a well-chosen k, KNN can achieve over 97% accuracy — a remarkable result for such a simple algorithm.

See also

• C’est vrai que je peux acheter un Iphone avec seulement 1 euro ?
• Maîtrisez le Calcul des Points de Grille dans des Cubes Lattices avec Python : Guide Complet et Tutoriels