La Classification par k-Plus Proches Voisins (k-NN) : Décider par Similarité

1 Introduction : Apprendre sans Modèle

Dans les posts précédents, le classifieur estimé repose sur l’estimation d’un paramètre: ces modèles sont dit paramétriques.

Dans ce post, nous allons explorer une approche complètement différente : la classification par k-plus proches voisins (k-NN). C’est un modèle non-paramétrique et basé sur les instances (instance-based). On l’appelle parfois un “apprenant paresseux” (lazy learner), car il ne construit pas de modèle explicite pendant la phase d’entraînement. En fait, la phase d’entraînement consiste simplement à mémoriser toutes les données !

La prédiction se fait au dernier moment, en se basant sur un principe d’une simplicité et d’une intuition redoutables : la similarité.

2 L’Intuition : Le Vote du Voisinage

L’algorithme k-NN est basé sur l’adage “Dis-moi qui sont tes amis, je te dirai qui tu es”.

Pour classifier une nouvelle observation x_new dont on ne connaît pas l’étiquette :

1. Le modèle mesure la distance entre x_new et toutes les autres observations du jeu de données d’entraînement.
2. Il identifie les k observations les plus proches (ses “k plus proches voisins”).
3. Il organise un vote à la majorité : la classe la plus représentée parmi ces k voisins est assignée comme prédiction pour x_new.

3 La Mécanique du k-NN

3.1 La Mesure de Distance

La “proximité” est le plus souvent calculée à l’aide de la distance euclidienne, que vous connaissez bien : \[ d(a, b) = \sqrt{\sum_{i=1}^{p} (a_i - b_i)^2} \] Où \(p\) est le nombre de variables explicatives.

3.2 Prérequis Crucial : La Mise à l’Échelle des Variables

Puisque le k-NN est entièrement basé sur les distances, il est extrêmement sensible à l’échelle de vos variables. Une variable avec une grande échelle (ex: un salaire en dizaines de milliers) pèsera beaucoup plus lourd dans le calcul de la distance qu’une variable avec une petite échelle (ex: un âge en dizaines), même si cette dernière est plus importante.

Règle d’Or

Avant d’utiliser le k-NN, vous devez impérativement mettre vos variables numériques à la même échelle, par exemple en utilisant la standardisation (StandardScaler).

3.3 Le Choix de k : Le Compromis Biais-Variance

Comme pour la régression k-NN, le choix de l’hyperparamètre k est fondamental et contrôle le compromis biais-variance.

• Si k est petit (ex: k=1) : Le modèle est très sensible au bruit. La frontière de décision sera très complexe et s’adaptera aux particularités locales des données d’entraînement. C’est le cas d’une variance élevée et d’un biais faible (surapprentissage).
• Si k est grand : Le modèle devient plus lisse et moins sensible aux variations locales. La frontière de décision sera beaucoup plus simple. C’est le cas d’un biais élevé et d’une variance faible (sous-apprentissage).

Notre objectif est donc de trouver le k optimal qui équilibre ce compromis, généralement via une recherche sur grille avec validation croisée.

4 Atelier Pratique : Classifier les Fleurs d’Iris

Utilisons le jeu de données classique iris pour classifier les fleurs en trois espèces (setosa, versicolor, virginica) en fonction de la longueur et de la largeur de leurs sépales et pétales.

import pandas as pd
import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import Pipeline
from sklearn.metrics import classification_report, confusion_matrix, ConfusionMatrixDisplay
import matplotlib.pyplot as plt

# 1. Charger les données
iris = load_iris()
X, y = iris.data, iris.target
feature_names = iris.feature_names
target_names = iris.target_names

# 2. Diviser les données
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42, stratify=y)

# 3. Créer un Pipeline pour le pré-traitement et le modèle
# C'est la meilleure pratique : le pipeline s'assure que la mise à l'échelle
# est ajustée sur le train set et appliquée au test set, évitant les fuites de données.
pipeline = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier())
])

# 4. Mettre en place la recherche sur grille pour trouver le meilleur k
print("--- Lancement de la recherche du meilleur k via GridSearchCV ---")
# Définir la grille des valeurs de k à tester
# On préfixe le nom du paramètre par le nom de l'étape dans le pipeline ('knn__')
param_grid = {'knn__n_neighbors': np.arange(1, 26)}

# Configurer GridSearchCV avec 5-fold cross-validation
# Le score par défaut pour la classification est l'accuracy
grid_search = GridSearchCV(pipeline, param_grid, cv=5, scoring='accuracy')

# 5. Lancer la recherche sur les données d'entraînement
grid_search.fit(X_train, y_train)

# 6. Afficher les meilleurs résultats
print("\n--- Résultats de la Recherche ---")
print(f"Meilleur paramètre k trouvé : {grid_search.best_params_}")
print(f"Meilleur score d'accuracy en validation croisée : {grid_search.best_score_:.4f}")

# 7. Évaluer le modèle final sur le jeu de test
print("\n--- Évaluation du Modèle Final sur le Jeu de Test ---")
best_model = grid_search.best_estimator_
y_pred = best_model.predict(X_test)

print("--- Matrice de Confusion ---")
cm = confusion_matrix(y_test, y_pred)
disp = ConfusionMatrixDisplay(confusion_matrix=cm, display_labels=target_names)
disp.plot(cmap=plt.cm.Blues)
plt.show()

print("\n--- Rapport de Classification ---")
print(classification_report(y_test, y_pred, target_names=target_names))

--- Lancement de la recherche du meilleur k via GridSearchCV ---

--- Résultats de la Recherche ---
Meilleur paramètre k trouvé : {'knn__n_neighbors': 14}
Meilleur score d'accuracy en validation croisée : 0.9714

--- Évaluation du Modèle Final sur le Jeu de Test ---
--- Matrice de Confusion ---

--- Rapport de Classification ---
              precision    recall  f1-score   support

      setosa       1.00      1.00      1.00        15
  versicolor       0.88      1.00      0.94        15
   virginica       1.00      0.87      0.93        15

    accuracy                           0.96        45
   macro avg       0.96      0.96      0.96        45
weighted avg       0.96      0.96      0.96        45

5 Conclusion et Limites

La classification k-NN est un excellent outil de base, facile à comprendre et souvent étonnamment efficace, surtout pour des problèmes avec des frontières de décision complexes et non-linéaires.

Avantages :

• Très simple à implémenter et à interpréter.
• Aucune phase d’entraînement (apprentissage “paresseux”).
• Naturellement non-paramétrique, il peut s’adapter à n’importe quelle forme de distribution.

Inconvénients :

• Coût de prédiction élevé : Il doit calculer les distances avec toutes les données d’entraînement pour chaque nouvelle prédiction, ce qui est très lent sur de grands jeux de données.
• Sensible aux variables non pertinentes : Si vous avez de nombreuses variables inutiles, elles vont “polluer” le calcul de distance et dégrader la performance.
• “Malédiction de la dimensionnalité” : Dans un espace à très haute dimension, la notion de “proximité” perd son sens, et les performances du k-NN s’effondrent.

Et maintenant ?

Nous avons vu un modèle qui apprend une équation (Régression Logistique) et un modèle qui apprend par similarité (k-NN). Dans notre prochain article, nous allons explorer une troisième voie, peut-être la plus intuitive de toutes : la classification par arbre de décision, qui apprend en posant une série de questions.

---

6 Exercices

Exercise 1  

Question 1 : Principe Fondamental du k-NN

Comment l’algorithme k-NN classifie-t-il une nouvelle observation ?

1. En construisant un arbre de décision basé sur les k variables les plus importantes.
2. En calculant une équation linéaire à partir des k observations les plus proches.
3. En organisant un vote à la majorité parmi ses k plus proches voisins.
4. En trouvant le centroïde du cluster auquel le point appartient.

Question 2 : Nature du Modèle

Pourquoi le k-NN est-il souvent qualifié d’"apprenant paresseux" (lazy learner) ?

1. Parce qu’il est très lent à faire des prédictions.
2. Parce qu’il ne construit pas de modèle explicite pendant la phase d’entraînement, il mémorise simplement les données.
3. Parce qu’il est moins performant que les autres algorithmes.
4. Parce qu’il ignore la plupart des données d’entraînement.

Question 3 : Prérequis Essentiel

Quelle est l’étape de pré-traitement la plus cruciale avant d’utiliser un classifieur k-NN ?

1. La suppression des valeurs aberrantes.
2. L’encodage des variables catégorielles en utilisant le Label Encoding.
3. La mise à l’échelle des variables numériques (ex: Standardisation).
4. La sélection des k variables les plus importantes.

Question 4 : Impact d’un k faible

Un choix de k très petit (ex: k=1) dans un modèle k-NN conduit généralement à :

1. Un modèle avec un biais élevé et une faible variance (sous-apprentissage).
2. Un modèle avec une variance élevée et un biais faible (surapprentissage).
3. Un modèle parfaitement équilibré.
4. Une frontière de décision toujours linéaire.

Question 5 : Impact d’un k élevé

Que se passe-t-il si vous choisissez une valeur de k très grande ?

1. La frontière de décision devient très complexe et s’adapte au bruit.
2. Le modèle devient plus simple, plus lisse, et risque le sous-apprentissage.
3. Le temps de prédiction diminue considérablement.
4. Le modèle devient non-paramétrique.

Question 6 : Méthode de Recherche pour k

Quelle est la méthode standard et robuste pour trouver la valeur optimale de k ?

1. Choisir k comme la racine carrée du nombre d’observations.
2. Tester le modèle sur le jeu de test avec plusieurs valeurs de k et choisir la meilleure.
3. Utiliser une recherche sur grille avec validation croisée (GridSearchCV) sur le jeu d’entraînement.
4. k est toujours égal à 5 par défaut.

Question 7 : Principal Inconvénient

Quel est l’un des inconvénients majeurs de l’algorithme k-NN ?

1. Il est très difficile à interpréter.
2. Il ne peut pas gérer les problèmes multi-classes.
3. Il est très rapide à l’entraînement mais peut être très lent à la prédiction sur de grands jeux de données.
4. Il nécessite que les données suivent une distribution normale.

Question 8 : Rôle du Pipeline

Dans l’atelier pratique, pourquoi est-il recommandé d’utiliser un Pipeline Scikit-learn ?

1. Pour visualiser la frontière de décision.
2. Pour garantir que le StandardScaler est ajusté sur les données d’entraînement et appliqué correctement aux données de test, évitant les fuites de données.
3. Pour accélérer la recherche du meilleur k.
4. Pour choisir automatiquement entre la distance euclidienne et la distance de Manhattan.

Question 9 : La Malédiction de la Dimensionnalité

Comment la “malédiction de la dimensionnalité” affecte-t-elle le k-NN ?

1. Elle rend le modèle plus rapide en haute dimension.
2. Elle n’a aucun effet sur le k-NN.
3. En haute dimension, la notion de distance perd son sens et les performances du k-NN se dégradent.
4. Elle oblige à utiliser une valeur de k très petite.

Question 10 : k-NN pour la Régression

Si on utilisait k-NN pour un problème de régression (prédire une valeur numérique), comment la prédiction finale serait-elle calculée ?

1. Par un vote à la majorité parmi les k voisins.
2. En prenant la médiane des valeurs cibles des k voisins.
3. En prenant la moyenne des valeurs cibles des k voisins.
4. En construisant un arbre de décision à partir des k voisins.

Question 11 : Distance Euclidienne

Quelle est la formule de la distance euclidienne entre deux points \(a = (a_1, a_2, ..., a_p)\) et \(b = (b_1, b_2, ..., b_p)\) ?

1. \(d(a, b) = \sum_{i=1}^{p} |a_i - b_i|\)
2. \(d(a, b) = \max_{i=1}^{p} |a_i - b_i|\)
3. \(d(a, b) = \sqrt{\sum_{i=1}^{p} (a_i - b_i)^2}\)
4. \(d(a, b) = \sum_{i=1}^{p} (a_i - b_i)^2\)

Question 12 : Standardisation

Pourquoi la standardisation (par exemple avec StandardScaler) est-elle particulièrement importante pour k-NN ?

1. Elle rend les données plus faciles à visualiser.
2. Elle convertit les variables catégorielles en numériques.
3. Elle assure que toutes les variables contribuent également au calcul de la distance, évitant qu’une variable avec une grande échelle ne domine.
4. Elle réduit le nombre de dimensions.

Question 13 : Compromis Biais-Variance

Comment le choix de k influence-t-il le compromis biais-variance dans k-NN ?

1. Un petit k augmente le biais et réduit la variance.
2. Un grand k augmente la variance et réduit le biais.
3. Un petit k réduit le biais et augmente la variance.
4. Le choix de k n’a pas d’impact sur le compromis biais-variance.

Question 14 : Apprentissage Supervisé

Le k-NN est un algorithme d’apprentissage supervisé. Qu’est-ce que cela signifie ?

1. Il apprend à partir de données non étiquetées.
2. Il nécessite une intervention humaine constante pendant l’entraînement.
3. Il apprend à partir de données où les étiquettes de sortie sont connues.
4. Il est utilisé uniquement pour la régression.

Question 15 : Frontière de Décision

Comment décririez-vous la frontière de décision d’un classifieur k-NN ?

1. Toujours linéaire.
2. Toujours non-linéaire et potentiellement très complexe.
3. Toujours une ligne droite.
4. Une série de cercles concentriques.

Question 16 : Données d’Entraînement

Que fait le k-NN pendant la phase d’entraînement ?

1. Il calcule les poids pour chaque caractéristique.
2. Il ajuste un modèle mathématique complexe.
3. Il mémorise simplement toutes les données d’entraînement.
4. Il supprime les observations aberrantes.

Question 17 : Sensibilité au Bruit

Un modèle k-NN avec un k très petit est-il sensible au bruit dans les données ?

1. Non, il est très robuste au bruit.
2. Oui, car il se base sur très peu de voisins, rendant la prédiction vulnérable aux points aberrants.
3. Seulement si les données sont linéaires.
4. Le bruit n’affecte que les modèles paramétriques.

Question 18 : Utilisation de stratify dans train_test_split

Dans l’exemple de code, pourquoi utilise-t-on stratify=y lors de la division des données avec train_test_split ?

1. Pour s’assurer que les données sont mélangées aléatoirement.
2. Pour garantir que la distribution des classes est la même dans les ensembles d’entraînement et de test.
3. Pour réduire la dimensionnalité des données.
4. Pour appliquer la standardisation avant la division.

Question 19 : scoring='accuracy' dans GridSearchCV

Que signifie scoring='accuracy' dans la configuration de GridSearchCV ?

1. Que le modèle sera entraîné pour maximiser la précision (precision).
2. Que le modèle sera évalué et le meilleur k choisi en fonction du score d’exactitude (accuracy).
3. Que le modèle utilisera la métrique d’exactitude pour la prédiction finale.
4. Que le modèle ne peut être utilisé que pour des problèmes de classification binaire.

Question 20 : Cas d’Utilisation Idéal

Dans quel type de situation le k-NN est-il particulièrement bien adapté ?

1. Quand le jeu de données est très grand (millions d’observations).
2. Quand le nombre de dimensions est très élevé.
3. Quand les frontières de décision sont complexes et non-linéaires, et que le jeu de données est de taille modérée.
4. Quand on a besoin d’un modèle très rapide à la prédiction.