La méthode des K plus proches voisins (KNN) est une technique d'apprentissage supervisé utilisée tant pour la classification que pour la régression. Son principe fondamental repose sur l'idée qu'un point de données inconnu peut être classé ou prédit en fonction de la majorité des classes ou de la moyenne des valeurs de ses K voisins les plus proches dans l'espace des caractéristiques.

Principes Fondamentaux du KNN

L'essence du KNN réside dans la mesure de la "proximité" ou "similarité" entre les points de données. Cette similarité est généralement quantifiée par une métrique de distance. Plus la distance entre deux points est faible, plus ils sont considérés comme similaires.

Comment déterminer la similarité ? Dans le contexte du KNN, la similarité est évaluée en calculant la distance entre un point de données inconnu et tous les points de données présents dans l'ensemble d'entraînement. Les points les plus proches sont alors sélectionnés comme voisins.

Fonctionnement de l'Algorithme KNN

L'algorithme KNN est polyvalent et peut être appliqué à la fois aux problèmes de classification et de régression.

Classification avec KNN Dans un scénario de classification, lorsqu'on rencontre un nouveau point de données, l'algorithme identifie les K points d'entraînement les plus proches. La classe attribuée au nouveau point est celle qui est la plus fréquemment représentée parmi ces K voisins. Par exemple, si K=5 et que parmi les 5 voisins les plus proches, 3 appartiennent à la classe "Comédie" et 2 à la classe "Drame", le nouveau point sera classé comme "Comédie".

Importance du choix de K Le paramètre K est crucial et influence significativement les performances du modèle :

• K trop petit : Un K faible rend le modèle sensible aux valeurs aberrantes et au bruit. Il peut entraîner une complexité accrue du modèle et un risque de surapprentissage (overfitting). À l'extrême, si K est égal au nombre total d'échantillons d'entraînement, la prédiction sera toujours la classe majoritaire de l'ensemble d'entraînement, ignorant ainsi les caractéristiques spécifiques du nouveau point.
• K trop grand : Un K élevé augmente la généralisation du modèle, mais peut conduire à un sous-apprentissage (underfitting) si les voisins inclus ne sont pas pertinents. Il peut également accentuer le biais du modèle en raison de la prise en compte d'une plus grande proportion d'échantillons, potentiellement moins représentatifs pour des points spécifiques. Pour déterminer la valeur optimale de K, des techniques telles que la validation croisée et la recherche par grille (grid search) sont couramment employées.

Régression avec KNN Pour les problèmes de régression, le processus est similaire. Après avoir identifié les K plus proches voisins, la prédiction pour le nouveau point est la moyenne des valeurs cibles de ces K voisins.

Processus de Classification :

1. Calculer la distance entre l'échantillon inconnu et chaque échantillon d'entraînement.
2. Trier les échantillons d'entraînement par distance croissante par rapport à l'échantillon inconnu.
3. Sélectionner les K échantillons les plus proches.
4. Appliquer un vote majoritaire : compter la fréquence de chaque classe parmi les K voisins.
5. Attribuer l'échantillon inconnu à la classe ayant le plus grand nombre de votes.

Processus de Régression :

1. Calculer la distance entre l'échantillon inconnu et chaque échantillon d'entraînement.
2. Trier les échantillons d'entraînement par distance croissante.
3. Sélectionner les K échantillons les plus proches.
4. Calculer la moyenne des valeurs cibles de ces K voisins.
5. Utiliser cette moyenne comme valeur prédite pour l'échantillon inconnu.

APIs KNN

La bibliothèque Scikit-learn offre des implémentations efficaces pour les algorithmes KNN.

API de Classification

from sklearn.neighbors import KNeighborsClassifier

# n_neighbors: Le nombre de voisins à considérer (valeur par défaut: 5)
knn_classifier = KNeighborsClassifier(n_neighbors=5)

API de Régression

from sklearn.neighbors import KNeighborsRegressor

# n_neighbors: Le nombre de voisins à considérer (valeur par défaut: 5)
knn_regressor = KNeighborsRegressor(n_neighbors=5)

Exemple d'utilisation (Régression)

from sklearn.neighbors import KNeighborsRegressor

# Données d'exemple (caractéristiques et cibles)
X_train = [[0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, 5]]
y_train = [0.1, 0.2, 0.3, 0.4]

# Instanciation et entraînement du modèle
model = KNeighborsRegressor(n_neighbors=3)
model.fit(X_train, y_train)

# Prédiction pour un nouveau point
prediction = model.predict([[4, 4, 5]])
print(prediction) # Sortie attendue: [0.35] (moyenne des voisins les plus proches)

Métriques de Distance

Le choix de la métrique de distance est fondamental pour le KNN. Les plus courantes incluent :

• Distance Euclidienne : La distance en ligne droite entre deux points.
• Distance de Manhattan : La somme des différences absolues des coordonnées (chemin de "bloc").
• Distance de Chebyshev : La différence maximale entre les coordonnées des deux points.
• Distance de Minkowski : Une généralisation des distances euclidienne et de Manhattan.

Prétraitement des Caractéristiques

Il est souvent nécessaire de prétraiter les données avant d'appliquer le KNN, notamment pour gérer les différences d'échelles antre les caractéristiques.

Pourquoi Normaliser ou Standardiser ? Lorsque les caractéristiques ont des échelles ou des unités très différentes, celles avec des plages de valeurs plus larges peuvent dominer le calcul de la distance, faussant ainsi les résultats. La normalisation et la standardisation permettent de ramener les caractéristiques à une échelle comparable.

Normalisation (Min-Max Scaling) Transforme les données pour qu'elles se situent dans une plage spécifiée, généralement [0, 1].

from sklearn.preprocessing import MinMaxScaler

scaler = MinMaxScaler(feature_range=(0, 1))
scaled_data = scaler.fit_transform(X)

Cette méthode est sensible aux valeurs aberrantes.

Standardisation (Z-score Normalization) Transforme les données pour avoir une moyenne de 0 et un écart-type de 1.

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
standardized_data = scaler.fit_transform(X)

La standardisation est généralement plus robuste aux valeurs aberrantes que la normalisation.

Exemple : Classification des Iris avec KNN et Standardisation

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

# Charger le jeu de données Iris
iris = load_iris()
X, y = iris.data, iris.target

# Diviser les données en ensembles d'entraînement et de test
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Standardiser les caractéristiques
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# Initialiser et entraîner le modèle KNN
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_scaled, y_train)

# Faire des prédictions sur l'ensemble de test
y_pred = knn.predict(X_test_scaled)

# Évaluer la précision du modèle
accuracy = accuracy_score(y_test, y_pred)
print(f"Précision du modèle KNN sur le jeu de données Iris : {accuracy:.4f}")

# Prédire une nouvelle observation
new_observation = [[5.1, 3.5, 1.4, 0.2]]
new_observation_scaled = scaler.transform(new_observation)
prediction = knn.predict(new_observation_scaled)
print(f"Prédiction pour une nouvelle observation : {iris.target_names[prediction][0]}")

Optimisation des Hyperparamètres : Validation Croisée et Recherche par Grille

Pour trouver la meilleure configuration pour les hyperparamètres (comme K), on utilise des techniques avancées.

Validation Croisée La validation croisée divise l'ensemble d'entraînement en plusieurs sous-ensembles (plis). Le modèle est entraîné sur une combinaison de ces plis et validé sur le pli restant. Ce processus est répété plusieurs fois, chaque pli servant de jeu de validation une fois. La performance finale est la moyenne des performances obtenues sur chaque pli. Cela permet d'obtenir une estimation plus fiable de la performance du modèle et de réduire le risque de surapprentissage.

Recherche par Grille (Grid Search) La recherche par grille explore systématiquement un ensemble prédéfini de valeurs d'hyperparamètres. Pour chaque combinaison d'hyperparamètres, elle effectue une validation croisée pour évaluer sa performance. La combinaison qui donne le meilleur score moyen est sélectionnée comme optimale.

API : GridSearchCV

from sklearn.model_selection import GridSearchCV
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split

# Charger et préparer les données (comme dans l'exemple précédent)
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)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
# Note: X_test_scaled sera utilisé pour l'évaluation finale après avoir trouvé le meilleur modèle

# Définir l'estimateur et la grille de paramètres
knn = KNeighborsClassifier()
param_grid = {'n_neighbors': range(1, 15)} # Tester K de 1 à 14

# Initialiser GridSearchCV
grid_search = GridSearchCV(knn, param_grid, cv=5, scoring='accuracy') # cv=5 signifie 5-fold cross-validation

# Effectuer la recherche par grille sur les données d'entraînement
grid_search.fit(X_train_scaled, y_train)

# Afficher les meilleurs résultats
print(f"Meilleur score de validation croisée : {grid_search.best_score_:.4f}")
print(f"Meilleur nombre de voisins (K) : {grid_search.best_params_['n_neighbors']}")

# Obtenir le meilleur modèle trouvé
best_knn_model = grid_search.best_estimator_

# Évaluer le meilleur modèle sur l'ensemble de test final
X_test_scaled = scaler.transform(X_test) # Assurez-vous que le test set est aussi standardisé
final_accuracy = best_knn_model.score(X_test_scaled, y_test)
print(f"Précision finale sur l'ensemble de test : {final_accuracy:.4f}")

Application : Reconnaissance d'Écritures Manuscrits avec MNIST

Le jeu de données MNIST, contenant des images de chiffres manuscrits, est un banc d'essai classique pour les algorithmes de classification. Chaque image est représentée par 784 pixels (28x28), où chaque pixel a une valeur entre 0 (blanc) et 255 (noir).

Préparation des Données MNIST Les images doivent être chargées, et les valeurs des pixels normalisées (généralement divisées par 255) pour être comprises entre 0 et 1. Ensuite, les données sont divisées en ensembles d'entraînement et de test, et prétraitées (par exemple, standardisées).

Exemple de Code pour MNIST

import pandas as pd
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
import joblib # Pour sauvegarder/charger le modèle

# Charger les données (supposant que 'train.csv' contient les données d'entraînement)
# Assurez-vous que le chemin vers le fichier est correct
try:
    df_train = pd.read_csv('train.csv')
except FileNotFoundError:
    print("Erreur: Le fichier 'train.csv' n'a pas été trouvé. Veuillez télécharger le dataset MNIST.")
    # Vous pouvez télécharger le dataset depuis : http://yann.lecun.com/exdb/mnist/
    exit()

# Séparer les étiquettes (label) des caractéristiques (pixels)
X = df_train.iloc[:, 1:] # Pixels
y = df_train.iloc[:, 0]  # Labels

# Normalisation des pixels : valeurs de [0, 255] à [0, 1]
X = X / 255.0

# Division des données en ensembles d'entraînement et de test
# stratify=y assure que la proportion des classes est conservée dans les deux ensembles
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42, stratify=y)

# Standardisation des caractéristiques
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# Entraînement du modèle KNN
# Un K plus élevé peut être nécessaire pour ce grand jeu de données
knn_mnist = KNeighborsClassifier(n_neighbors=7) # Exemple avec K=7
knn_mnist.fit(X_train_scaled, y_train)

# Évaluation du modèle
y_pred = knn_mnist.predict(X_test_scaled)
accuracy = accuracy_score(y_test, y_pred)
print(f"Précision du KNN sur le dataset MNIST : {accuracy:.4f}")

# Sauvegarder le modèle entraîné et le scaler pour une utilisation ultérieure
joblib.dump(knn_mnist, 'knn_mnist_model.pkl')
joblib.dump(scaler, 'scaler_mnist.pkl')
print("Modèle et scaler KNN sauvegardés.")

# Fonction pour afficher une image MNIST
def display_digit(index):
    img_array = X.iloc[index].values.reshape(28, 28)
    plt.imshow(img_array, cmap='gray')
    plt.title(f"Label: {y.iloc[index]}")
    plt.axis('off')
    plt.show()

# Afficher un exemple d'image
print("\nAffichage d'un exemple d'image du dataset:")
display_digit(0) # Affiche la première image du dataset chargé

# Exemple de prédiction sur une nouvelle image (nécessite une image au format numpy array 1x784)
# Pour tester, vous devriez charger une nouvelle image, la prétraiter comme X_test_scaled, puis prédire.