k Plus Proches Voisins (Classification) : Guide Complet

Résumé — L’algorithme des k plus proches voisins (k-NN) est l’une des méthodes de classification supervisée les plus intuitives et les plus utilisées en machine learning. Ce guide explore en profondeur le principe mathématique, l’implémentation Python avec scikit-learn, le choix des hyperparamètres et les cas d’usage concrets.

Principe mathématique

L’algorithme des k plus proches voisins repose sur un principe d’une élégance remarquable : pour classer un nouveau point de donnée, on examine les k points du jeu d’entraînement qui lui sont les plus proches, et on lui attribue la classe majoritaire parmi ces voisins.

Distance euclidienne

La métrique de distance la plus couramment utilisée est la distance euclidienne. Pour deux points x et y dans un espace à n dimensions, elle se calcule ainsi :

$$d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i – y_i)^2}$$

Cette formule mesure simplement la longueur du segment reliant les deux points dans l’espace des caractéristiques. Chaque dimension correspond à une variable explicative du problème.

Autres métriques de distance

Bien que la distance euclidienne soit la plus populaire, l’algorithme des k plus proches voisins supporte d’autres métriques :

• Distance de Manhattan (L1) : $$d(x, y) = \sum_{i=1}^{n}|x_i – y_i|$$ — utile lorsque les dimensions ont des échelles très différentes ou pour des données clairsemées.
• Distance de Minkowski : généralisation paramétrique qui inclut euclidienne (p=2) et Manhattan (p=1) comme cas particuliers.
• Distance de Hamming : pour des données catégorielles ou binaires.
• Distance cosinus : pour mesurer la similarité angulaire, très utilisée en traitement du langage naturel.

Fonction de décision

Une fois les k plus proches voisins identifiés, la classe prédite (\hat{y}) est obtenue par vote majoritaire :

$$\hat{y} = \text{argmax}{c \in C} \sum(y_i = c)$$}^{k} \mathbb{I

où C est l’ensemble des classes possibles et (\mathbb{I}) est la fonction indicatrice qui vaut 1 si la condition est vraie, 0 sinon.

Dans la variante avec pondération, chaque voisin i reçoit un poids (w_i = 1/d(x, x_i)), ce qui donne plus d’influence aux voisins les plus proches.

Intuition

« Dis-moi qui sont tes voisins, je te dirai qui tu es. »

Cette maxime résume parfaitement la philosophie des k plus proches voisins. Imaginez que vous emménagez dans un nouveau quartier et que vous voulez savoir si vous êtes dans un quartier résidentiel ou commercial. La chose la plus naturelle serait de regarder les bâtiments autour de vous. Si la majorité sont des restaurants et des commerces, vous êtes probablement dans une zone commerciale. C’est exactement le raisonnement de l’algorithme.

L’algorithme paresseux (lazy learning)

Le terme lazy learner (apprentissage paresseux) qualifie parfaitement les k plus proches voisins. Pourquoi ? Parce que pendant la phase d’entraînement, l’algorithme ne fait… absolument rien. Il se contente de mémoriser l’ensemble des données d’entraînement. Tout le travail de calcul se produit au moment de la prédiction, lorsqu’il faut trouver les voisins les plus proches d’un nouveau point.

Cette approche présente un avantage certain : l’entraînement est quasi instantané, quelle que soit la taille du jeu de données. En revanche, la prédiction peut devenir coûteuse car elle nécessite de calculer les distances entre le nouveau point et tous les points d’entraînement.

Le compromis biais-variance et le choix de k

Le paramètre k est le levier principal de contrôle de l’algorithme :

• k = 1 : chaque point est son propre classifieur. La frontière de décision épouse parfaitement les données d’entraînement. Résultat : faible biais mais forte variance. On surajuste (overfitting) le bruit dans les données.
• k très grand (proche de n) : la prédiction tend vers la classe majoritaire globale. Le modèle devient trop lisse, trop rigide. Biais élevé, faible variance (sous-ajustement).
• k optimal : le juste milieu, généralement situé entre 3 et 21, souvent impair pour les problèmes binaires afin d’éviter les égalités lors du vote.

En pratique, on détermine la valeur optimale de k par validation croisée, en testant systématiquement plusieurs valeurs et en retenant celle qui maximise la performance sur un ensemble de validation.

Implémentation Python

Plongeons dans le code avec la bibliothèque scikit-learn, qui offre une implémentation robuste et optimisée des k plus proches voisins via KNeighborsClassifier.

Exemple de base avec le jeu Iris

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report, accuracy_score

# Chargement du jeu de données Iris
iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.2, random_state=42
)

# Création et entraînement du modèle
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train, y_train)

# Prédiction et évaluation
y_pred = knn.predict(X_test)
print(f"Exactitude (k=5) : {accuracy_score(y_test, y_pred):.4f}")
print(classification_report(y_test, y_pred, target_names=iris.target_names))

Comparaison de plusieurs valeurs de k

Il est essentiel de trouver la valeur optimale de k. Voici comment explorer systématiquement un éventail de valeurs :

import matplotlib.pyplot as plt
import numpy as np

from sklearn.datasets import make_classification
from sklearn.model_selection import cross_val_score

# Génération d'un jeu de données synthétique
X, y = make_classification(
    n_samples=1000, n_features=10, n_informative=5, n_redundant=2,
    n_clusters_per_class=1, random_state=42
)

# Exploration de k de 1 à 50
k_range = range(1, 51)
accuracies = []

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

# Visualisation
plt.figure(figsize=(10, 6))
plt.plot(k_range, accuracies, marker='o', linestyle='-', color='steelblue')
plt.axvline(x=k_range[np.argmax(accuracies)], color='red', linestyle='--',
            label=f"k optimal = {k_range[np.argmax(accuracies)]}")
plt.xlabel('Nombre de voisins (k)')
plt.ylabel('Exactitude moyenne (validation croisée 5 plis)')
plt.title('Exactitude en fonction de k — k plus proches voisins')
plt.legend()
plt.grid(True, alpha=0.3)
plt.show()

Visualisation des frontières de décision

Les frontières de décision illustrent visuellement comment l’algorithme sépare les classes selon la valeur de k :

from matplotlib.colors import ListedColormap
from sklearn.datasets import make_moons

X, y = make_moons(n_samples=300, noise=0.15, random_state=42)

# Création d'une grille pour la visualisation
x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
xx, yy = np.meshgrid(np.linspace(x_min, x_max, 200),
                     np.linspace(y_min, y_max, 200))

fig, axes = plt.subplots(1, 3, figsize=(18, 5))
cmap = ListedColormap(['#FF6B6B', '#4ECDC4'])

for ax, k in zip(axes, [1, 5, 15]):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X, y)

    # Prédiction sur la grille
    Z = knn.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)

    ax.contourf(xx, yy, Z, alpha=0.3, cmap=cmap)
    ax.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap, edgecolor='white', s=40)
    ax.set_title(f'Frontières de décision — k = {k}')
    ax.set_xlim(x_min, x_max)
    ax.set_ylim(y_min, y_max)

plt.suptitle('Impact de k sur les frontières de décision des k plus proches voisins', fontsize=14)
plt.tight_layout()
plt.show()

Impact du scaling (mise à l’échelle)

Les k plus proches voisins sont particulièrement sensibles à l’échelle des caractéristiques. Si une variable est mesurée en milliers et une autre en décimales, la première dominera entièrement le calcul de distance. Il est donc crucial de normaliser ou standardiser les données :

from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

# Pipeline avec standardisation intégrée
pipeline = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier(n_neighbors=5))
])

# Le pipeline applique automatiquement le scaling avant l'entraînement
pipeline.fit(X_train, y_train)
y_pred = pipeline.predict(X_test)
print(f"Exactitude avec scaling : {accuracy_score(y_test, y_pred):.4f}")

Hyperparamètres

Voici le tableau récapitulatif des hyperparamètres principaux de KNeighborsClassifier dans scikit-learn :

Recommandations pratiques

• Commencez toujours par faire varier n_neighbors entre 1 et (\sqrt{n}) (où n est la taille du jeu d’entraînement).
• Si vos données ne sont pas équilibrées, préférez weights=”distance” pour réduire l’influence de la classe majoritaire.
• Pour des jeux de données volumineux (> 10 000 échantillons), testez algorithm=”ball_tree” pour de meilleures performances.
• Si le temps de prédiction est critique, envisagez des structures d’indexation approximative comme Approximate Nearest Neighbors (ANN).

Avantages et Limites

Avantages

• Simplicité conceptuelle : l’algorithme est facile à comprendre et à expliquer, ce qui constitue un atout majeur pour des projets où la transparence est requise.
• Aucune hypothèse distributionnelle : contrairement à la régression logistique ou à l’analyse discriminante, les k plus proches voisins ne font aucune hypothèse sur la distribution sous-jacente des données. Il s’adapte naturellement à des frontières de décision non linéaires complexes.
• Multi-classes natif : gère directement les problèmes avec plus de deux classes, sans avoir recours à des stratégies de type one-vs-all.
• Entraînement instantané : la phase d’apprentissage se résume à stocker les données, ce qui est utile lorsque les données d’entraînement arrivent continuellement.
• Mise à jour aisée : ajouter de nouvelles données d’entraînement ne nécessite aucun ré-entraînement du modèle.

Limites

• Curse of dimensionality : en grande dimension, toutes les paires de points tendent à avoir des distances similaires, ce qui rend la notion de “plus proche voisin” peu discriminante. La performance se dégrade significativement au-delà de quelques dizaines de dimensions.
• Lenteur en prédiction : pour chaque nouvelle prédiction, l’algorithme doit calculer les distances avec tous les points d’entraînement. Sur un jeu de 1 million d’échantillons, cela peut prendre plusieurs secondes par requête.
• Consommation mémoire : le modèle doit conserver en mémoire l’intégralité du jeu d’entraînement, ce qui peut être prohibitif pour de très grandes bases de données.
• Sensibilité aux variables non normalisées : comme mentionné précédemment, l’absence de mise à l’échelle peut fausser complètement les résultats.
• Sensibilité au bruit et aux outliers : avec un petit k, un voisin aberrant peut changer la prédiction. C’est pourquoi le choix de k est si déterminant.

Cas d’usage

1. Système de recommandation de contenu

Les plateformes de streaming utilisent les k plus proches voisins pour suggérer des films ou des séries. Chaque utilisateur est représenté par un vecteur de préférences (genres regardés, notes attribuées, temps de visionnage). Lorsqu’il faut recommander un contenu à un utilisateur donné, on identifie les k utilisateurs les plus similaires et on suggère les titres qu’ils ont appréciés mais que notre utilisateur n’a pas encore découverts. Cette approche collaborative est particulièrement efficace pour les catalogues de grande taille.

2. Reconnaissance de caractères manuscrits

La classification de chiffres manuscrits (jeu MNIST) constitue un cas d’école historique pour les k plus proches voisins. Chaque image de 28×28 pixels est aplatie en un vecteur de 784 dimensions. En appliquant une réduction de dimensionnalité préalable (PCA) et en choisissant judicieusement la métrique de distance, on obtient des taux de reconnaissance supérieurs à 96 %. Bien que les réseaux de neurones convolutifs surpassent désormais cette approche, k-NN reste une référence pédagogique précieuse.

3. Diagnostic médical par analogie

Dans certains systèmes d’aide au diagnostic, un nouveau cas patient est comparé aux antécédents médicaux stockés dans la base de données. Les k plus proches voisins identifient les patients présentant les profils cliniques les plus similaires (symptômes, résultats d’analyses, antécédents). Le diagnostic majoritaire parmi ces voisins constitue une piste diagnostique que le médecin peut explorer. Cette approche est particulièrement utile pour les maladies rares où les cas similaires sont peu nombreux mais très informatifs.

4. Détection d’anomalies et fraudes

En inversant la logique, les k plus proches voisins peuvent servir à détecter des observations inhabituelles. Si la distance moyenne d’un point à ses k plus proches voisins est anormalement élevée, ce point est probablement une anomalie. Cette technique est utilisée dans la détection de fraudes bancaires : une transaction dont le profil s’éloigne significativement des transactions habituelles du client et de ses pairs sera signalée pour examen manuel. Des variantes comme le Local Outlier Factor (LOF) étendent cette idée fondamentale.

Bonnes pratiques récapitulatives

1. Toujours standardiser ses données avant d’appliquer k-NN (StandardScaler ou MinMaxScaler).
2. Utiliser la validation croisée pour déterminer le k optimal — ne jamais se fier à une seule valeur par défaut.
3. Réduire la dimensionnalité (PCA, t-SNE, UMAP) si le nombre de caractéristiques est élevé, pour lutter contre le curse of dimensionality.
4. Préférer weights=”distance” lorsque les classes sont déséquilibrées.
5. Limiter la taille du jeu d’entraînement si la vitesse de prédiction est critique (condensing, editing, ou échantillonnage).
6. Tester plusieurs métriques de distance : Manhattan peut surpasser l’euclidienne pour certaines distributions de données.

Voir aussi

• Multiplier des chaînes de caractères avec Python
• Maîtrisez l’Art du Reverse Engineering en Python : Guide Complet pour Débutants et Experts