K-nearest neighbors

K-Nearest Neighbors (KNN) est l'un des algorithmes d'apprentissage automatique les plus simples et les plus intuitifs. Pour classer un nouveau point de données, il examine les K exemples d'entraînement les plus proches et effectue un vote — la classe majoritaire l'emporte. Pour la régression, il calcule la moyenne des valeurs des K voisins à la place.

Ce chapitre couvre :

• Le fonctionnement de l'algorithme KNN étape par étape
• Les métriques de distance : euclidienne, Manhattan et Minkowski
• Pourquoi la mise à l'échelle des caractéristiques est essentielle pour KNN
• Comment choisir la bonne valeur de K
• La classification et la régression avec scikit-learn
• L'évaluation d'un classificateur KNN avec une matrice de confusion
• Les points forts, les limites et quand utiliser KNN

Fonctionnement de KNN

KNN est un apprenant paresseux — il n'effectue aucun véritable « entraînement ». Il mémorise plutôt l'intégralité du jeu de données et reporte tous les calculs au moment de la prédiction.

Étant donné un nouveau point, l'algorithme :

1. Calcule la distance entre le nouveau point et chaque point d'entraînement.
2. Sélectionne les K points d'entraînement ayant les distances les plus faibles (les « voisins les plus proches »).
3. Agrège leurs étiquettes :
   • Classification — le nouveau point reçoit l'étiquette de classe la plus fréquente.
   • Régression — le nouveau point reçoit la moyenne (ou la moyenne pondérée) des valeurs cibles des voisins.

Comme il n'y a pas de modèle à entraîner, l'ajout de nouvelles données est trivial — il suffit de les ajouter au jeu de données. La contrepartie est que la prédiction est lente pour les grands jeux de données, car le calcul complet des distances s'exécute à chaque fois.

Métriques de distance

Le terme « le plus proche » dans KNN est défini par une fonction de distance. La valeur par défaut dans scikit-learn est la distance euclidienne, la distance en ligne droite dans un espace à n dimensions :

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

Deux alternatives courantes :

Vous pouvez changer la métrique dans scikit-learn avec le paramètre metric :

from sklearn.neighbors import KNeighborsClassifier

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

Pourquoi la mise à l'échelle des caractéristiques est essentielle

KNN calcule des distances brutes. Une caractéristique mesurée en milliers (comme le salaire) dominera complètement une caractéristique mesurée en unités simples (comme les années d'expérience), même si la caractéristique plus petite est plus informative.

Mettez toujours les caractéristiques à l'échelle avant d'utiliser KNN. Consultez le chapitre sur la mise à l'échelle des caractéristiques pour une explication complète ; en résumé :

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

N'appelez jamais fit_transform sur le jeu de test — cela ferait fuiter les statistiques du jeu de test dans le normaliseur.

Choisir K

K contrôle le compromis biais-variance :

• K petit (ex. K=1) — très flexible, s'adapte étroitement aux données d'entraînement, mais bruité et sujet au surapprentissage. Un seul voisin aberrant peut changer la prédiction.
• K grand — frontière de décision plus lisse, variance plus faible, mais peut sous-apprendre et brouiller les vraies frontières entre classes.

L'approche standard consiste à tester une plage de valeurs de K et à choisir celle qui donne la meilleure précision par validation croisée :

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}")

Sortie attendue :

Best K: 6, CV Accuracy: 0.9667

Pour plus de détails sur la validation croisée, consultez le chapitre validation croisée.

Règles pratiques :

• Préférez un K impair pour la classification binaire afin d'éviter les égalités.
• Un point de départ courant est K = sqrt(n) où n est le nombre d'échantillons d'entraînement.
• Validez toujours avec la validation croisée plutôt que de deviner.

Classification KNN avec scikit-learn

L'exemple suivant utilise le jeu de données Iris — un vrai problème multiclasse — et parcourt le flux de travail complet : découpage, mise à l'échelle, entraînement, prédiction, évaluation.

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))

Sortie attendue :

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 avec K=5 atteint une précision de 93 % sur ce jeu de test de 30 échantillons. La classe setosa est classifiée parfaitement car elle est linéairement séparable des deux autres ; versicolor et virginica se chevauchent quelque peu, provoquant quelques erreurs de classification.

Notez l'argument stratify=y dans train_test_split — il préserve les proportions de classes dans chaque découpage, ce qui est particulièrement important pour les jeux de données déséquilibrés. Consultez découpage entraînement/test pour plus de détails.

Évaluation avec une matrice de confusion

Une matrice de confusion montre exactement quelles classes le modèle confond entre elles :

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)

Sortie attendue :

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

Chaque ligne représente une classe réelle ; chaque colonne représente une classe prédite. Les valeurs sur la diagonale sont des prédictions correctes ; les valeurs hors diagonale sont des erreurs de classification. Ici, 2 échantillons virginica ont été mal classifiés comme versicolor. Consultez le chapitre matrice de confusion pour une explication plus approfondie.

Régression KNN avec scikit-learn

Pour la régression, KNN prédit la moyenne des valeurs cibles des K voisins les plus proches. Remplacez KNeighborsClassifier par 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}")

Sortie attendue :

RMSE: 0.4217
R²:   0.8053

Le RMSE est dans les mêmes unités que la cible (valeur médiane des maisons en centaines de milliers de dollars). Un R² de 0,81 signifie que le modèle explique environ 81 % de la variance sur ce sous-ensemble de 2 000 échantillons — un résultat solide pour une base KNN non optimisée.

KNN pondéré

Par défaut, tous les K voisins ont un poids égal indépendamment de leur proximité. Définir weights='distance' donne plus d'importance aux voisins les plus proches :

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}")

Sortie attendue :

Uniform weights accuracy:  0.93
Distance weights accuracy: 0.97

La pondération par distance améliore ici la précision de 0,93 à 0,97 — les voisins les plus proches ont plus d'influence, ce qui aide à résoudre les cas limites ambigus.

Points forts et limites

Quand utiliser KNN

• Le jeu de données est de taille petite à moyenne (des dizaines de milliers d'échantillons).
• Vous avez besoin d'une base de référence rapide et interprétable — KNN est facile à expliquer et à déboguer.
• Vous disposez de caractéristiques bien mises à l'échelle et de faible dimensionnalité.
• La frontière de décision est complexe et non linéaire.

Quand éviter KNN

• Grands jeux de données. Le temps de prédiction évolue avec le nombre d'échantillons d'entraînement (O(n·d) par requête). Pour des millions d'échantillons, envisagez des bibliothèques de voisins les plus proches approximatifs (Faiss, Annoy) ou passez à un algorithme plus rapide.
• Données de haute dimension. Dans de nombreuses dimensions, tous les points deviennent approximativement équidistants — le « fléau de la dimensionnalité ». KNN se dégrade rapidement au-delà de ~20 caractéristiques. Appliquez d'abord une réduction de dimensionnalité (PCA, sélection de caractéristiques).
• Caractéristiques non pertinentes. Chaque caractéristique participe au calcul de la distance. Les caractéristiques bruitées ou non pertinentes diluent le signal. Supprimez-les ou réduisez-les avant l'entraînement.
• Environnements à mémoire limitée. KNN stocke l'intégralité du jeu d'entraînement ; un jeu de données avec des millions de lignes occupe une quantité significative de RAM.

Résumé

Chapitres associés :

• Mise à l'échelle des caractéristiques — pourquoi et comment mettre à l'échelle avant KNN
• Découpage entraînement/test — découper les données correctement
• Validation croisée — choisir K avec la validation croisée k-fold
• Matrice de confusion — interpréter les résultats de classification
• Recherche par grille — optimisation systématique des hyperparamètres