Understanding and Implementing K-Nearest Neighbors (KNN)

1. L'intuition du K-Nearest Neighbors

L'idée fondamentale de KNN est simple et intuitive : "Dis-moi qui sont tes voisins, et je te dirai qui tu es". Pour classifier un nouveau point de données, l'algorithme regarde les K points les plus proches de lui dans les données d'entraînement et effectue un "vote" majoritaire. La classe la plus représentée parmi ces K voisins est assignée au nouveau point.

La vidéo suivante de StatQuest explique ce concept de manière exceptionnellement claire et visuelle.

Pour visualiser ce processus, imaginez que nous avons des points de données de deux classes (A et B) et un nouveau point inconnu (le carré jaune). Si nous choisissons K=3, nous identifions les trois voisins les plus proches.

Lorsque ce processus est appliqué à tout l'espace des caractéristiques, il crée des "frontières de décision" qui séparent les différentes classes. Contrairement aux frontières linéaires que nous avons vues avec la régression logistique, celles de KNN peuvent être très complexes et non linéaires.

2. Les composants clés de KNN

Le fonctionnement de KNN repose sur deux éléments que nous devons définir : le nombre de voisins K et la manière de mesurer la "proximité" (la distance).

L'article suivant d'IBM explore ces concepts en détail.

Voici un résumé des points les plus importants :

• Le choix de K (un hyperparamètre) :

  • Un petit K (ex: 1 ou 2) rend le modèle très sensible au bruit et aux points de données aberrants. La frontière de décision sera très fluctuante. On parle de faible biais mais de variance élevée.
  • Un grand K lisse les frontières de décision, rendant le modèle plus robuste au bruit mais potentiellement moins capable de capturer les détails fins entre les classes. On parle de biais élevé mais de faible variance.
  • Le choix de K est donc un compromis (le fameux compromis biais-variance que nous avons vu au module 7). Nous verrons plus tard comment choisir une bonne valeur pour K.

• La mesure de distance :

  • La plus utilisée est la distance euclidienne, qui est simplement la distance en ligne droite entre deux points dans l'espace des caractéristiques. Pour deux points $p$ et $q$ dans un espace à $n$ dimensions, elle est calculée comme suit : $$d(p,q)=\sqrt{(q_1-p_1{)}^2+(q_2-p_2{)}^2+\cdots +(q_n-p_n{)}^2}=\sqrt{\sum _{i=1}^n(q_i-p_i{)}^2}$$
  • Étant donné que KNN est basé sur cette notion de distance, il est extrêmement important que toutes les caractéristiques (features) soient sur la même échelle. Si une caractéristique varie de 0 à 1000 (par exemple, un salaire) et une autre de 0 à 10 (par exemple, une note), la première dominera complètement le calcul de la distance. C'est pourquoi la mise à l'échelle des caractéristiques (feature scaling) est une étape de prétraitement obligatoire pour KNN.

3. Entraîner un classificateur KNN avec Scikit-learn

Passons maintenant à la pratique. Nous allons entraîner un classificateur KNN sur le jeu de données "Iris", un classique de l'apprentissage automatique qui consiste à classifier des fleurs d'iris en trois espèces différentes en fonction de la longueur et de la largeur de leurs sépales et pétales.

Le tutoriel suivant de DataCamp montre la procédure complète, de la préparation des données à l'évaluation du modèle.

Voici le code complet qui applique ces étapes. Notez bien la séquence : split -> scale -> fit.

# 1. Importer les bibliothèques nécessaires
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 classification_report, confusion_matrix
import seaborn as sns
import matplotlib.pyplot as plt




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




# 3. Séparer 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.3, random_state=42)




# 4. Mettre à l'échelle les caractéristiques
scaler = StandardScaler()



# On 'fit' et 'transform' sur les données d'entraînement
X_train_scaled = scaler.fit_transform(X_train)



# On 'transform' seulement sur les données de test
X_test_scaled = scaler.transform(X_test)




# 5. Entraîner le modèle KNN
# Nous choisissons K=5 pour commencer
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_scaled, y_train)




# 6. Faire des prédictions
y_pred = knn.predict(X_test_scaled)




# 7. Évaluer le modèle
print("Rapport de classification :")
print(classification_report(y_test, y_pred, target_names=target_names))

print("Matrice de confusion :")
cm = confusion_matrix(y_test, y_pred)
sns.heatmap(cm, annot=True, fmt='g', xticklabels=target_names, yticklabels=target_names)
plt.xlabel('Valeurs Prédites')
plt.ylabel('Valeurs Réelles')
plt.title('Matrice de Confusion pour KNN (K=5)')
plt.show()

En exécutant ce code, vous verrez un rapport de classification (avec la précision, le rappel, etc.) et une matrice de confusion. C'est une excellente façon de réutiliser les compétences que vous avez acquises dans les leçons précédentes pour évaluer notre nouveau modèle !

4. Comment choisir la meilleure valeur pour K ?

Nous avons choisi K=5 arbitrairement. Mais comment trouver la valeur optimale ? La méthode la plus courante consiste à tester plusieurs valeurs de K et à choisir celle qui donne la meilleure performance sur un jeu de données de validation.

La vidéo de codebasics illustre l'impact du choix de K et la recherche d'une valeur optimale.

Pour trouver le K optimal de manière systématique, nous pouvons entraîner et évaluer le modèle pour une série de valeurs de K et tracer les résultats. La section suivante du tutoriel DataCamp que nous avons vu plus tôt explique comment faire cela proprement en utilisant la validation croisée (cross-validation).

Conclusion

Aujourd'hui, nous avons ajouté un outil puissant et intuitif à notre boîte à outils d'apprentissage automatique. KNN se distingue des modèles précédents par son approche "paresseuse" et basée sur la similarité.

Points clés à retenir :

• KNN est un algorithme de classification (et de régression) qui prédit l'étiquette d'un nouveau point en se basant sur un vote majoritaire de ses K plus proches voisins.
• C'est un algorithme "paresseux" car il ne construit pas de modèle pendant l'entraînement ; il stocke simplement les données et effectue tous les calculs au moment de la prédiction.
• Le choix de l'hyperparamètre K est crucial et représente un compromis biais-variance.
• La mise à l'échelle des caractéristiques (par exemple, avec StandardScaler) est obligatoire pour KNN car il est basé sur des mesures de distance.
• L'implémentation avec Scikit-learn est simple en utilisant la classe KNeighborsClassifier.

Dans notre prochaine leçon, nous allons explorer une autre famille de modèles très populaires et interprétables : les arbres de décision (Decision Trees). Alors que KNN se base sur la "proximité", les arbres de décision apprennent une série de règles "si-alors-sinon" pour prendre leurs décisions, offrant une perspective complètement différente sur la manière de modéliser les données.