K-Nearest Neighbors (KNN) : Guide complet — Classification et Régression en Python

Résumé

Les K-Nearest Neighbors (KNN), ou k plus proches voisins en français, constituent l’un des algorithmes de machine learning les plus intuitifs et les plus enseignés. Classé parmi les méthodes non paramétriques et le lazy learning, KNN ne construit aucun modèle pendant l’entraînement : il mémorise simplement l’ensemble de données et prend ses décisions au moment de la prédiction. Cette approche remarquablement simple s’avère étonnamment efficace pour la classification comme pour la régression, à condition de bien choisir ses hyperparamètres — en particulier le nombre k de voisins. Ce guide complet explore le principe mathématique, l’intuition, l’implémentation Python avec scikit-learn, les pièges à éviter et les cas d’usage concrets.

Principe mathématique de KNN

Définition formelle

L’algorithme KNN repose sur une idée centrale : pour une nouvelle observation x, on détermine sa catégorie ou sa valeur en examinant les k points d’entraînement les plus proches selon une métrique de distance choisie.

Soit un ensemble d’entraînement D = {(x₁, y₁), (x₂, y₂), …, (xₙ, yₙ)} où chaque xᵢ ∈ ℝᵈ est un vecteur de caractéristiques et yᵢ le label (classification) ou la valeur cible (régression).

Pour une nouvelle observation x :

1. Calcul des distances : On calcule la distance entre x et chaque point xᵢ de l’ensemble d’entraînement selon une métrique d(x, xᵢ).
2. Sélection des k plus proches : On trie toutes les distances et on retient les k points ayant les distances les plus faibles.
3. Agrégation :

• Classification : Le label prédit ŷ est le mode (valeur la plus fréquente) des labels des k voisins. Formellement :

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

  où N_k(x) désigne l’ensemble des k plus proches voisins de x.

• Régression : La valeur prédite ŷ est la moyenne (ou moyenne pondérée) des valeurs des k voisins. Formellement :

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

Pondération inverse de la distance

Dans la variante pondérée, chaque voisin reçoit un poids inversement proportionnel à sa distance : wᵢ = 1 / d(x, xᵢ). Ainsi, un voisin très proche influence davantage la prédiction qu’un voisin éloigné. Pour la classification pondérée, on somme les poids par classe ; pour la régression pondérée, on calcule la moyenne pondérée :

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

Métriques de distance

Le choix de la métrique est crucial et dépend de la nature des données :

• Distance euclidienne (L2) : d(x, x’) = √Σ(xⱼ – x’ⱼ)². C’est la métrique par défaut, idéale pour des données continues normalisées.
• Distance de Manhattan (L1) : d(x, x’) = Σ|xⱼ – x’ⱼ|. Plus robuste aux outliers que l’euclidienne.
• Distance de Minkowski : Généralisation paramétrique d(x, x’) = (Σ|xⱼ – x’ⱼ|ᵖ)^(1/p). Avec p=2, on retrouve l’euclidienne ; avec p=1, la Manhattan.
• Distance de Hamming : Utile pour les données catégorielles ou binaires, elle compte le nombre de positions où les vecteurs diffèrent.
• Distance cosinus : Mesure l’angle entre deux vecteurs, particulièrement adaptée aux données textuelles et de haute dimension.

Intuition : comme demander conseil à ses voisins

Imaginez que vous emménagez dans une nouvelle ville. Pour savoir si un quartier est sûr, vous n’allez pas consulter des statistiques nationales : vous demandez aux 5 maisons les plus proches ce qu’elles en pensent. Si 4 sur 5 disent que le quartier est tranquille, vous concluez qu’il l’est probablement. C’est exactement le principe de la classification KNN avec k=5.

De la même manière, pour estimer le prix de vente d’une maison, vous regardez combien ont été vendues les maisons similaires dans le voisinage. La moyenne (ou médiane) de ces prix vous donne une estimation raisonnable. C’est le principe de la régression KNN.

Cette analogie révèle aussi les forces et les faiblesses de l’algorithme :

• Si votre voisinage est homogène (tous les voisins se ressemblent), la prédiction sera fiable.
• Si votre voisinage est très diversifié ou si un voisin atypique fausse la moyenne, le résultat sera moins bon.
• La qualité de la prédiction dépend directement de la pertinence de la notion de « proximité » — d’où l’importance cruciale du choix de la métrique de distance.

Implémentation Python avec scikit-learn

Classification sur le jeu de données Iris

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

# Chargement des données
iris = load_iris()
X, y = iris.data, iris.target

# Séparation entraînement / test
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

# Normalisation des données — étape indispensable pour KNN
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# Entraînement du classifieur KNN
knn = KNeighborsClassifier(n_neighbors=5, metric='euclidean')
knn.fit(X_train_scaled, y_train)

# Prédictions et évaluation
y_pred = knn.predict(X_test_scaled)
print(f"Précision : {accuracy_score(y_test, y_pred):.4f}")
print(classification_report(y_test, y_pred, target_names=iris.target_names))

Impact du choix de k

Le paramètre k est le plus important de l’algorithme. Trop petit (k=1), le modèle est trop sensible au bruit et au surapprentissage. Trop grand (k=n), il devient trivial et sous-apprend.

# Étude de l'impact de 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))

# Visualisation
plt.figure(figsize=(10, 6))
plt.plot(k_values, train_scores, 'b-', label='Entraînement', marker='o')
plt.plot(k_values, test_scores, 'r-', label='Test', marker='s')
plt.xlabel('Valeur de k')
plt.ylabel('Précision')
plt.title('Impact de k sur les performances KNN')
plt.legend()
plt.grid(True, alpha=0.3)
plt.show()

En général, on observe que la précision sur l’ensemble d’entraînement décroît avec k, tandis que la précision sur l’ensemble de test augmente jusqu’à un optimum avant de décliner. Le k optimal se situe typiquement entre 3 et 15 selon la complexité du problème.

Comparaison des métriques de distance

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 : pourquoi la normalisation est indispensable

KNN étant un algorithme fondé sur les distances, les échelles des caractéristiques influencent directement les résultats. Imaginez une variable allant de 0 à 1 et une autre de 0 à 10 000 : la deuxième dominera entièrement le calcul de distance, rendant la première inutile. StandardScaler centre et réduit chaque caractéristique (moyenne nulle, variance unité), garantissant que toutes contribuent équitablement.

Courbes de décision

from sklearn.inspection import DecisionBoundaryDisplay

# Pour la visualisation, on ne garde que 2 caractéristiques
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('Courbes de décision KNN (k=7, 2 caractéristiques)')
plt.show()

Régression KNN avec KNeighborsRegressor

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

# Génération de données de régression
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}")

Hyperparamètres détaillés

Conseils pratiques pour le réglage

• Commencez par k=5 avec ‘uniform’ et ‘euclidean’, puis ajustez.
• Utilisez cross_val_score ou GridSearchCV pour trouver le k optimal automatiquement.
• Testez weight=’distance’ si vous soupçonnez que les k voisins n’ont pas tous la même pertinence.
• Pour les données de haute dimension (>50 features), ‘brute’ est souvent plus efficace car les structures d’arbre perdent leur avantage.
• n_jobs=-1 accélère significativement les prédictions sur les gros jeux de données.

Avantages et limites des K-Nearest Neighbors

Avantages

1. Simplicité conceptuelle : L’algorithme se comprend en cinq minutes, ce qui le rend idéal pour la communication avec des parties prenantes non techniques.
2. Aucune hypothèse sur la distribution : Contrairement à la régression logistique ou l’analyse discriminante linéaire, KNN ne suppose aucune forme particulière pour les données — il est véritablement non paramétrique.
3. Adaptabilité aux frontières complexes : Les frontières de décision peuvent être arbitrairement complexes, car KNN apprend localement.
4. Mise à jour incrémentale : Ajouter de nouvelles données ne nécessite aucun réentraînement — il suffit de les ajouter au stock existant.
5. Polyvalence : Le même algorithme fonctionne pour la classification, la régression, et même la détection d’anomalies.

Limites

1. Coût computationnel élevé : Chaque prédiction nécessite de calculer des distances avec tous les points d’entraînement — O(n·d) par prédiction, où n est le nombre d’échantillons et d la dimension.
2. Malédiction de la dimensionalité : En haute dimension, toutes les distances tendent à devenir similaires, ce qui rend la notion de « plus proche voisin » de moins en moins significative. C’est l’un des problèmes les plus redoutés en machine learning.
3. Sensibilité au bruit et aux outliers : Un exemple mal étiqueté dans les voisins directs peut fausser la prédiction, surtout avec un petit k.
4. Exigence de normalisation : Sans mise à l’échelle des caractéristiques, les résultats sont souvent médiocres.
5. Mémoire importante : L’algorithme doit stocker l’intégralité des données d’entraînement, ce qui peut poser problème pour les très gros datasets.
6. Données déséquilibrées : Si une classe est largement majoritaire, elle dominera systématiquement le vote des voisins.

4 cas d’usage concrets des K-Nearest Neighbors

1. Recommandation de films

Des plateformes comme Netflix ou Prime Video utilisent des variantes de KNN pour recommander des contenus. Chaque film est représenté par un vecteur de caractéristiques (genre, durée, réalisateur, acteurs, notes). Pour recommander un film à un utilisateur, on trouve les k films les plus proches de ceux qu’il a aimés et on lui propose ceux qu’il n’a pas encore vus. Avec distance cosinus, cette approche capture particulièrement bien la similarité de goût.

2. Diagnostic médical assisté

Un système d’aide au diagnostic peut comparer le profil d’un nouveau patient (symptômes, résultats d’analyses, antécédents) avec ceux de patients dont le diagnostic est déjà connu. Les k patients les plus similaires permettent d’estimer la probabilité de différentes pathologies. L’avantage majeur ici est la transparence : on peut expliquer la décision en montrant les cas similaires, ce qui est crucial en médecine.

3. Détection de fraude bancaire

Les transactions frauduleuses présentent souvent des profils atypiques par rapport aux transactions légitimes du même client. En utilisant KNN, on peut identifier les transactions dont les k plus proches voisins sont majoritairement étiquetées comme frauduleuses. Le vote pondéré est particulièrement utile ici : une transaction très proche d’un cas connu de fraude recevra un score d’alerte élevé.

4. Reconnaissance d’écriture manuscrite

Le célèbre jeu de données MNIST (70 000 images de chiffres manuscrits 28×28) est un benchmark classique pour KNN. Chaque image est aplatie en un vecteur de 784 pixels. Avec un prétraitement approprié (normalisation, réduction de dimension par PCA) et un k bien choisi, KNN peut atteindre plus de 97 % de précision — un résultat remarquable pour un algorithme aussi simple.

Voir aussi

• 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