KNN classification : Guide complet — Classification par Proximité

Résumé — KNN (K-Nearest Neighbors) est l’algorithme de classification le plus intuitif qui soit : pour classer un nouveau point, on regarde les k points les plus proches dans le jeu d’entraînement et on leur demande leur avis par vote majoritaire. C’est un lazy learner : il n’apprend rien pendant l’entraînement, il se contente de mémoriser les données. Toute l’analyse se fait au moment de la prédiction. Cette simplicité en fait un outil puissant pour les données tabulaires et un outil pédagogique fondamental.

Principe mathématique

1. Principe fondamental

KNN repose sur l’hypothèse suivante : des points proches dans l’espace des features ont tendance à appartenir à la même classe.

Pour classer un nouveau point x, on procède en trois étapes :
1. Calculer la distance entre x et tous les points d’entraînement.
2. Identifier les k plus proches voisins (ceux avec les distances les plus petites).
3. Voter : la classe prédite est la classe majoritaire parmi ces k voisins.

2. Métriques de distance

Le choix de la distance est crucial dans KNN. Voici les métriques principales :

Distance Euclidienne (L2) :
$$d(x, y) = \sqrt{\sum_{i=1}^{p} (x_i – y_i)^2}$$

C’est la distance “en ligne droite” dans l’espace. C’est la plus intuitive et la plus utilisée par défaut.

Distance de Manhattan (L1) :
$$d(x, y) = \sum_{i=1}^{p} |x_i – y_i|$$

C’est la distance en grille urbaine (comme les blocs de Manhattan). Elle est plus robuste aux outliers que l’euclidienne.

Distance de Minkowski (généralisation) :
$$d(x, y) = \left(\sum_{i=1}^{p} |x_i – y_i|^q\right)^{1/q}$$

Avec q=1 c’est Manhattan, avec q=2 c’est Euclidienne. q=3 ou q=4 offrent un compromis.

Similarité cosinus (pour textes et features creuses) :
$$\text{sim}(x, y) = \frac{x \cdot y}{||x|| \cdot ||y||} = \frac{\sum x_i y_i}{\sqrt{\sum x_i^2} \sqrt{\sum y_i^2}}$$

Le cosinus mesure l’angle entre deux vecteurs plutôt que leur distance. Il est idéal pour la classification de textes (TF-IDF).

Distance de Mahalanobis (prend en compte les corrélations) :
$$d_M(x, y) = \sqrt{(x – y)^T \Sigma^{-1} (x – y)}$$

où Σ est la matrice de covariance. Cette distance normalise automatiquement les features et corrige les corrélations.

3. Formule de prédiction

La classe prédite est la classe la plus fréquente parmi les k voisins :

$$\hat{y} = \arg\max_{v} \sum_{i \in N_k(x)} I(y_i = v)$$

où N_k(x) est l’ensemble des k plus proches voisins de x, et I est la fonction indicatrice.

4. Pondération par distance

Au lieu d’un vote simple (1 vote par voisin), on peut pondérer chaque voisin par son inverse de distance :

$$\hat{y} = \arg\max_{v} \sum_{i \in N_k(x)} w_i \cdot I(y_i = v)$$

où w_i = 1/d(x, x_i). Cette variante donne plus de poids aux voisins très proches et moins aux voisins plus lointains, ce qui améliore généralement la performance.

Intuition

“Dis-moi qui sont tes voisins, je te dirai qui tu es.”

Imaginez que vous arrivez dans une nouvelle ville et que vous cherchez à deviner si un quartier est résidentiel ou commercial. Vous regardez les bâtiments les plus proches : si la plupart sont des boutiques, c’est probablement commercial. Si ce sont des maisons, c’est résidentiel. Plus vous regardez de bâtiments proches (grand k), plus la décision est stable mais peut-être plus floue. Plus vous en regardez peu (petit k), plus la décision est précise mais volatile.

L’analogie du vote de quartier : KNN c’est comme un scrutin de voisinage. Chaque point d’entraînement est un électeur qui crie “je suis de la classe A !” ou “je suis de la classe B !”. Le nouveau point écoute les k électeurs les plus proches et adopte la classe la plus bruyante.

Implémentation Python

Exemple 1 : KNN from scratch avec recherche brute

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

class KNNClassifier:
    """K-Nearest Neighbors Classifier."""

    def __init__(self, n_neighbors=5, weights='uniform', metric='euclidean'):
        self.n_neighbors = n_neighbors
        self.weights = weights  # 'uniform' ou 'distance'
        self.metric = metric

    def fit(self, X, y):
        self.X_train = X
        self.y_train = y
        return self

    def _compute_distances(self, X):
        if self.metric == 'euclidean':
            # Astuce vectorisée : ||x-y||^2 = ||x||^2 + ||y||^2 - 2xy
            X2 = np.sum(X ** 2, axis=1, keepdims=True)
            T2 = np.sum(self.X_train ** 2, axis=1, keepdims=True).T
            dists = np.sqrt(np.maximum(X2 + T2 - 2 * X @ self.X_train.T, 0))
        elif self.metric == 'manhattan':
            dists = np.zeros((X.shape[0], self.X_train.shape[0]))
            for i in range(X.shape[0]):
                dists[i] = np.sum(np.abs(X[i] - self.X_train), axis=1)
        return dists

    def predict(self, X):
        dists = self._compute_distances(X)
        predictions = []
        for i in range(X.shape[0]):
            # Indices des k plus proches
            nn_idx = np.argsort(dists[i])[:self.n_neighbors]
            nn_labels = self.y_train[nn_idx]
            nn_dists = dists[i, nn_idx]

            if self.weights == 'distance':
                # Pondération par 1/distance
                unique_classes = np.unique(self.y_train)
                scores = np.zeros(len(unique_classes))
                for c in unique_classes:
                    mask = nn_labels == c
                    scores[np.where(unique_classes == c)[0][0]] = np.sum(1 / (nn_dists[mask] + 1e-8))
                predictions.append(unique_classes[np.argmax(scores)])
            else:
                # Vote majoritaire simple
                counts = np.bincount(nn_labels)
                predictions.append(np.argmax(counts))

        return np.array(predictions)

# Chargement des données Iris
iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, test_size=0.3, random_state=42
)

# Standardisation (cruciale pour KNN !)
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
X_train_sc = scaler.fit_transform(X_train)
X_test_sc = scaler.transform(X_test)

# Notre KNN
for k in [1, 3, 5, 7, 11]:
    knn = KNNClassifier(n_neighbors=k, weights='distance')
    knn.fit(X_train_sc, y_train)
    acc = accuracy_score(y_test, knn.predict(X_test_sc))
    print(f"k={k:2d} | Acc: {acc:.3f}")

Exemple 2 : KNeighborsClassifier de scikit-learn

from sklearn.neighbors import KNeighborsClassifier

# Comparaison des métriques
metrics_to_test = ['euclidean', 'manhattan', 'cosine']
for metric in metrics_to_test:
    knn_sk = KNeighborsClassifier(n_neighbors=5, metric=metric)
    knn_sk.fit(X_train_sc, y_train)
    acc = accuracy_score(y_test, knn_sk.predict(X_test_sc))
    print(f"Métrique: {metric:12s} | Acc: {acc:.3f}")

# Optimisation de k par validation croisée
import matplotlib.pyplot as plt
k_range = range(1, 31)
train_scores = []
test_scores = []

for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train_sc, y_train)
    train_scores.append(accuracy_score(y_train, knn.predict(X_train_sc)))
    test_scores.append(accuracy_score(y_test, knn.predict(X_test_sc)))

plt.figure(figsize=(8, 5))
plt.plot(k_range, train_scores, 'b-o', label='Train', markersize=4)
plt.plot(k_range, test_scores, 'r-o', label='Test', markersize=4)
plt.axvline(x=k_range[np.argmax(test_scores)], color='green', linestyle='--',
    label=f'Optimal k={k_range[np.argmax(test_scores)]}')
plt.title('Impact de k sur la performance KNN')
plt.xlabel('Nombre de voisins (k)')
plt.ylabel('Accuracy')
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('knn_k_impact.png', dpi=150)

Exemple 3 : Impact de la standardisation

# KNN sans standardisation
knn_raw = KNeighborsClassifier(n_neighbors=5)
knn_raw.fit(X_train, y_train)
raw_acc = accuracy_score(y_test, knn_raw.predict(X_test))

# KNN avec standardisation
knn_sc = KNeighborsClassifier(n_neighbors=5)
knn_sc.fit(X_train_sc, y_train)
sc_acc = accuracy_score(y_test, knn_sc.predict(X_test_sc))

print(f"\nKNN sans standardisation : {raw_acc:.3f}")
print(f"KNN avec standardisation  : {sc_acc:.3f}")
print("Note: KNN est extrêmement sensible à l'échelle des features.")

Hyperparamètres

Avantages de KNN

1. Simplicité conceptuelle : Pas besoin de formation du modèle, pas de maths complexes, pas d’optimisation. L’algorithme tient en quelques lignes.
2. Adaptabilité aux nouvelles classes : Ajouter une nouvelle classe ne nécessite aucun réentraînement — il suffit d’ajouter des exemples au dataset.
3. Frontières non linéaires naturelles : KNN capture automatiquement des relations non linéaires entre features, sans besoin de transformations manuelles.
4. Pas d’hypothèse sur la distribution : Contrairement à Naive Bayes (distribution gaussienne) ou LDA (covariance égale), KNN ne fait aucune hypothèse sur la forme des données.
5. Bonnes performances en pratique : Pour les données tabulaires de taille moderate, KNN est souvent compétitif avec des modèles plus sophistiqués.

Limites de KNN

1. Coût de prédiction élevé : Chaque prédiction nécessite de calculer la distance avec tous les points d’entraînement (O(n)). Sur des gros datasets, c’est prohibitif.
2. Malédiction de la dimensionnalité : En haute dimension, toutes les distances deviennent similaires, rendant la notion de “plus proche voisin” peu informative. Performances qui chutent après ~50-100 features.
3. Sensibilité aux outliers et au bruit : Un point aberrant peut attirer des voisins lointains et fausser les prédictions locales.
4. Nécessité de standardisation : Les features à grande échelle dominent la distance. Toutes les features doivent être normalisées. C’est une étape incontournable.
5. Stockage important : KNN doit garder tous les données d’entraînement en mémoire. Impossible de supprimer le dataset après l’entraînement comme avec un modèle paramétrique.

4 cas d’usage concrets

1. Système de recommandation de produits

Les systèmes de recommandation par “filtrage collaboratif” sont essentiellement du KNN : “Les utilisateurs qui ont aimé les mêmes produits que vous (vos voisins) ont aussi aimé X, donc on vous recommande X.” Amazon, Netflix et Spotify utilisent des variantes de ce principe.

2. Classification de documents par similarité

En traitement du langage naturel, KNN avec similarité cosinus est utilisé pour classer des documents : chaque texte est représenté en TF-IDF, et la similarité cosinus entre vecteurs mesure la similarité thématique. C’est simple mais efficace pour des catégorisations rapides de corpus.

3. Détection d’anomalies (KNN inversé)

En calculant la distance moyenne aux k plus proches voisins pour chaque point, on peut identifier les anomalies : les points avec une distance moyenne élevée sont isolés dans l’espace des features et donc potentiellement anormaux. C’est une approche alternative à l’Isolation Forest.

4. Reconnaissance d’écriture manuscrite

Historiquement, le KNN a été l’une des premières méthodes utilisées pour la reconnaissance de chiffres manuscrits (MNIST). Un nouveau chiffre est comparé à tous les exemples d’entraînement, et les k plus similaires votent pour la classe. Avec une bonne standardisation et k=3-5, le KNN atteint déjà 96-97% sur MNIST — compétitif sans réseau de neurones.

Conclusion

KNN est l’algorithme qui incarne le principe “keep it simple”. Il ne fait aucun apprentissage explicite, ne calcule aucun gradient, ne minimise aucune fonction de coût. Il se contente de mémoriser et de comparer. Et pourtant, il reste compétitif sur de nombreux problèmes, surtout pour les données tabulaires.

Le coût de prédiction et la malédiction de la dimensionnalité limitent son usage aux datasets de taille moderate et de dimension raisonnable. Mais dans ce domaine, KNN demeure un outil de référence à toujours inclure dans sa boîte à outils.

Voir aussi

• Maîtriser la Manipulation des Chiffres dans les Carrés avec Python : Guide Complet et Astuces
• Python & expressions régulières : un duo gagnant pour traiter les données