Classifieur de \(k\) Plus Proches Voisins (\(k\)-NN)

Authors
Affiliation

Wilson Toussile1 2

ENSPY

1ENSPY, 2ESSFAR

1 Introduction à la Classification k-NN 🎯

La méthode des \(k\) plus proches voisins (\(k\)-NN) est un algorithme d’apprentissage supervisé simple mais puissant, utilisé principalement pour les problèmes de classification et de régression. Dans ce tutoriel, nous nous concentrerons sur son application à la classification.

Supposons que nous disposions d’un ensemble de données d’entraînement \(\mathcal{D}_n = \{(x_i, y_i)\}_{i=1}^n\). Ici :

  • \(x_i \in \mathbb{X}\) représente le vecteur des caractéristiques (ou variables explicatives) de la \(i\)-ème observation. \(\mathbb{X}\) est l’espace des caractéristiques, souvent \(\mathbb{R}^p\) où \(p\) est le nombre de caractéristiques.
  • \(y_i \in \mathbb{Y}\) est l’étiquette de classe (ou variable à prédire) associée à \(x_i\). \(\mathbb{Y}\) est l’ensemble des étiquettes de classe possibles, par exemple \(\mathbb{Y} = \{c_1, c_2, \ldots, c_L\}\) pour un problème à \(L\) classes.

L’objectif est d’apprendre un classifieur \(g\), qui est une fonction \(g: \mathbb{X} \to \mathbb{Y}\). Étant donné une nouvelle observation \(x_{\text{new}} \in \mathbb{X}\) dont l’étiquette est inconnue, le classifieur \(g\) doit prédire son étiquette \(\hat{y}_{\text{new}} = g(x_{\text{new}})\) de manière à ce que cette prédiction soit la plus “correcte” possible, c’est-à-dire que \(g\) ait de bonnes performances de généralisation sur de nouvelles données.

\(k\)-NN est un algorithme non paramétrique (il ne fait pas d’hypothèses fortes sur la forme de la fonction de décision) et basé sur les instances (il mémorise l’ensemble des données d’entraînement pour faire des prédictions).

2 Principe du Classifieur k-NN (pour un \(k\) fixé) 🧐

L’intuition derrière \(k\)-NN est que les points de données similaires (proches dans l’espace des caractéristiques) ont tendance à appartenir à la même classe. Pour un entier \(k\) fixé (le nombre de voisins à considérer) et une nouvelle observation \(x_{\text{new}}\) à classer, l’algorithme k-NN procède comme suit :

  1. Calcul des distances: Pour chaque point \(x_i\) dans l’ensemble d’entraînement \(\mathcal{D}_n\), calculer la distance entre \(x_{\text{new}}\) et \(x_i\). Une fonction de distance couramment utilisée est la distance Euclidienne entre deux points \(x_a = (x_{a,1}, \ldots, x_{a,p})\) et \(x_b = (x_{b,1}, \ldots, x_{b,p})\) dans \(\mathbb{R}^p\): \[ d(x_a, x_b) = \sqrt{\sum_{j=1}^p (x_{a,j} - x_{b,j})^2} \] D’autres distances comme la distance de Manhattan, Minkowski, ou Hamming (pour les données catégorielles) peuvent aussi être utilisées. Il est crucial que les caractéristiques soient à des échelles comparables, donc une normalisation (ou standardisation) des données est souvent une étape de prétraitement importante.

  2. Identification des \(k\) plus proches voisins: Sélectionner les \(k\) points de l’ensemble d’entraînement \(\mathcal{D}_n\) qui sont les plus proches de \(x_{\text{new}}\) selon la distance choisie. Notons cet ensemble de \(k\) voisins \(V_k(x_{\text{new}})\).

  3. Vote majoritaire: L’étiquette prédite \(\hat{y}_{\text{new}}\) pour \(x_{\text{new}}\) est déterminée par un vote majoritaire parmi les étiquettes des \(k\) voisins dans \(V_k(x_{\text{new}})\). La classe la plus fréquente parmi les \(k\) voisins est assignée à \(x_{\text{new}}\): \[ \hat{g}(x_{\text{new}}) = \underset{c \in \mathbb{Y}}{\text{arg max}} \sum_{(x_j, y_j) \in V_k(x_{\text{new}})} \mathbb{I}(y_j = c) \] où \(\mathbb{I}(\cdot)\) est la fonction indicatrice (qui vaut 1 si la condition est vraie, 0 sinon).

En cas d’égalité dans le vote (plusieurs classes ont le même nombre maximal de voix), plusieurs stratégies existent : choisir aléatoirement, choisir la classe du voisin le plus proche parmi celles à égalité, ou utiliser une valeur de \(k\) impaire pour éviter les égalités dans les problèmes à deux classes.

3 Le Défi de la Sélection de \(k\) 🤔

Le choix du paramètre \(k\) est critique et a un impact significatif sur les performances du classifieur k-NN.

  • Si \(k\) est trop petit (par exemple, \(k=1\)):

    • Le classifieur a un biais faible car il est très flexible et s’adapte finement aux structures locales des données.
    • Cependant, il a une variance élevée. Cela signifie que la prédiction peut être très sensible au bruit, aux points aberrants, ou à de petites variations dans les données d’entraînement. Les frontières de décision peuvent devenir excessivement complexes et irrégulières.
    • Cela peut conduire à un surapprentissage (overfitting): le modèle performe très bien sur les données d’entraînement mais mal sur de nouvelles données invisibles.

  • Si \(k\) est trop grand:

    • Le classifieur a un biais plus élevé car il tend à lisser les frontières de décision, ignorant potentiellement des structures locales fines. Les prédictions sont basées sur une région plus vaste de l’espace des caractéristiques.
    • Il a une variance plus faible, rendant le modèle plus stable et moins sensible au bruit.
    • Si \(k\) est excessivement grand (par exemple, \(k=n\), où \(n\) est la taille de l’ensemble d’entraînement), le classifieur prédira toujours la classe majoritaire de tout l’ensemble d’entraînement, ce qui peut conduire à un sous-apprentissage (underfitting).

Comment choisir \(k\) ?

Le \(k\) optimal dépend des données. Il est généralement choisi en utilisant des techniques de validation croisée (cross-validation):

  1. Diviser l’ensemble de données \(\mathcal{D}_n\) en un ensemble d’entraînement et un ensemble de validation (ou utiliser une validation croisée à \(m\) plis, “m-fold CV”).
  2. Pour une plage de valeurs de \(k\) (par exemple, de 1 à 20, ou \(k < \sqrt{n}\)), entraîner le modèle k-NN sur l’ensemble d’entraînement et évaluer ses performances (par exemple, exactitude, précision, rappel, F1-score) sur l’ensemble de validation.
  3. Choisir la valeur de \(k\) qui donne les meilleures performances sur l’ensemble de validation. Cette valeur de \(k\) est ensuite utilisée pour entraîner le modèle final sur l’ensemble des données d’entraînement \(\mathcal{D}_n\).

4 Implémentation “From Scratch” en Python ✍️

Voici une ébauche de ce à quoi pourrait ressembler une implémentation de base de k-NN en Python.

Code 
import numpy as np
from collections import Counter

def euclidean_distance(x1, x2):
    return np.sqrt(np.sum((x1 - x2)**2))

class MyKNNClassifier:
    def __init__(self, k=3):
        self.k = k
        self._X_train = None
        self._y_train = None
        return

    def fit(self, X_train, y_train):
        self._X_train = X_train
        self._y_train = y_train
        return

    def predict_single(self, x_new):
        # Calculer les distances entre x_new et tous les points de X_train
        distances = [euclidean_distance(x_new, x_train_point) for x_train_point in self._X_train]
        
        # Obtenir les indices des k plus proches voisins
        # argsort renvoie les indices qui trieraient le tableau
        k_indices = np.argsort(distances)[:self.k]
        
        # Obtenir les étiquettes des k plus proches voisins
        k_nearest_labels = [self._y_train[i] for i in k_indices]
        
        # Effectuer un vote majoritaire
        # Counter trouve l'élément le plus fréquent
        most_common = Counter(k_nearest_labels).most_common(1)
        return most_common[0][0]

    def predict(self, X_test):
        if self._X_train is None or self._y_train is None:
            raise ValueError("Le modèle doit être entraîné avec fit() avant de prédire.")
        
        predictions = [self.predict_single(x_test_point) for x_test_point in X_test]
        return np.array(predictions)

Cette implémentation simple ne gère pas les cas d’égalité de manière sophistiquée et suppose que X_train et X_test sont des listes de listes ou des tableaux NumPy où chaque ligne est une observation.

5 Utilisation de Scikit-learn pour k-NN sklearn️

La bibliothèque scikit-learn offre une implémentation optimisée et polyvalente de k-NN via la classe KNeighborsClassifier.

Code 
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.datasets import load_iris # Exemple de dataset
from sklearn.metrics import accuracy_score
import numpy as np

# Charger un exemple de dataset
iris = load_iris()
X, y = iris.data, iris.target

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

# Créer un pipeline pour la normalisation et la classification
# C'est une bonne pratique car k-NN est sensible à l'échelle des caractéristiques
pipeline_knn = Pipeline([
    ('scaler', StandardScaler()), # Étape de normalisation
    ('knn', KNeighborsClassifier(n_neighbors=5, metric='minkowski', p=2)) # p=2 pour distance Euclidienne
])

# Entraîner le modèle
pipeline_knn.fit(X_train, y_train)

# Faire des prédictions
y_pred_sklearn = pipeline_knn.predict(X_test)

# Évaluer le modèle
accuracy = accuracy_score(y_test, y_pred_sklearn)
print(f"Données Iris - Exactitude (Accuracy) avec Scikit-learn (k=5): {accuracy:.4f}")

# Exemple de sélection de k par validation croisée
k_range = range(1, 21)
k_scores = []

for k_val in k_range:
    knn_temp = KNeighborsClassifier(n_neighbors=k_val)
    # Utiliser X (non normalisé) et y (complet) car StandardScaler est dans le pipeline pour CV
    # ou appliquer la normalisation avant la CV si on n'utilise pas de pipeline dans CV
    pipeline_cv = Pipeline([('scaler', StandardScaler()), ('knn', knn_temp)])
    scores = cross_val_score(pipeline_cv, X, y, cv=5, scoring='accuracy') # 5-fold CV
    k_scores.append(scores.mean())

# Trouver le k optimal
optimal_k = k_range[np.argmax(k_scores)]
print(f"Valeur optimale de k trouvée par validation croisée (sur Iris): {optimal_k}")
print(f"Meilleur score de validation croisée: {np.max(k_scores):.4f}")

# Entraîner le modèle final avec le k optimal sur l'ensemble d'entraînement complet
pipeline_knn_optimal = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier(n_neighbors=optimal_k))
])
pipeline_knn_optimal.fit(X_train, y_train) # Entraînement sur le X_train du split initial
y_pred_optimal = pipeline_knn_optimal.predict(X_test)
accuracy_optimal = accuracy_score(y_test, y_pred_optimal)
print(f"Exactitude avec k optimal ({optimal_k}) sur l'ensemble de test Iris: {accuracy_optimal:.4f}")
Données Iris - Exactitude (Accuracy) avec Scikit-learn (k=5): 0.9111
Valeur optimale de k trouvée par validation croisée (sur Iris): 6
Meilleur score de validation croisée: 0.9667
Exactitude avec k optimal (6) sur l'ensemble de test Iris: 0.9111
Paramètres importants de KNeighborsClassifier:
  • n_neighbors: Le nombre de voisins \(k\).
  • weights: Peut être 'uniform' (tous les voisins ont le même poids) ou 'distance' (les voisins plus proches ont un poids plus important).
  • metric: La métrique de distance à utiliser (par défaut 'minkowski', qui avec p=2 est la distance Euclidienne).
  • p: Paramètre pour la métrique de Minkowski.

6 Conclusion ✨

L’algorithme k-NN est une méthode intuitive et facile à implémenter pour la classification. Bien qu’il puisse être coûteux en calcul pour de grands ensembles de données (car il doit calculer des distances à tous les points d’entraînement pour chaque nouvelle prédiction), il reste un outil précieux, surtout comme baseline ou lorsque les frontières de décision sont complexes et non linéaires. Le choix judicieux de \(k\) et une normalisation appropriée des données sont essentiels pour obtenir de bonnes performances.