Exercice 86 / 100

ML — KNN

Implémente le K-Nearest Neighbors

K-Nearest Neighbors (knn) prédit la classe d'un point en regardant les K points d'entraînement les plus proches et en faisant un vote majoritaire.

C'est l'un des algos les plus simples : pas d'"entraînement" au sens classique, juste un stockage des données.

Fonctionnement

Pour prédire la classe d'un nouveau point :

1. calculer la distance vers TOUS les points d'entraînement
2. garder les K plus proches
3. vote majoritaire → classe prédite

KNN ne construit aucun modèle : pour classer un point, il regarde ses K voisins les plus proches et leur fait voter, la classe majoritaire l'emporte

Workflow sklearn

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train, y_train)
y_pred = knn.predict(X_test)

Choix du K

K petit (1, 3)   →  modèle complexe, sensible au bruit (overfitting possible)
K grand (15+)    →  modèle lisse, sous-apprentissage si trop grand

Règle empirique : K ≈ √n (n = taille du train), souvent impair pour éviter les égalités.

Méthodologie : tester plusieurs K en cross-validation et choisir le meilleur.

⚠ Sensible à l'échelle des features

Les distances dominent les variables d'amplitude élevée. SI tes features ont des unités différentes (âge en années, salaire en €) :

from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)
knn.fit(X_train_s, y_train)

Sans ça, knn devient inutile en pratique.

Exemple complet

for k in [3, 5, 7, 11]:
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    acc = accuracy_score(y_test, knn.predict(X_test))
    print(f'K={k}: accuracy={acc:.2%}')

Paramètres avancés

weights='distance'    plus proches votent plus fort
metric='euclidean'    'manhattan', 'cosine', etc.
p=2                    paramètre pour la métrique de Minkowski

Limites

- lent à la prédiction sur de gros datasets (calcul de toutes les distances)
- mauvais en haute dimension ("curse of dimensionality")
- stockage = tout le dataset d'entraînement

knn est aussi disponible pour la régression (KNeighborsRegressor) : moyenne des K voisins au lieu d'un vote.

exercise.py