K plus proches voisins

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

Proverbe librement adapté

L’algorithme des K plus proches voisins (K-Nearest Neighbors, KNN) est l’un des algorithmes les plus intuitifs de l’apprentissage automatique. Son principe est d’une simplicité désarmante : pour prédire la classe ou la valeur d’une nouvelle observation, on regarde les \(k\) observations du jeu d’entraînement qui lui ressemblent le plus, et on agrège leurs étiquettes. Malgré cette simplicité, KNN est un algorithme puissant qui peut capturer des frontières de décision arbitrairement complexes.

Apprentissage par instances

KNN appartient à la famille des méthodes d”apprentissage par instances (instance-based learning), aussi appelées méthodes à mémoire (memory-based). Contrairement aux algorithmes paramétriques (régression linéaire, régression logistique), qui apprennent un ensemble fini de paramètres à partir des données d’entraînement puis oublient les données elles-mêmes, KNN conserve l’intégralité du jeu d’entraînement en mémoire et s’en sert directement au moment de la prédiction.

Remarque 74

On qualifie souvent KNN d’algorithme paresseux (lazy learner), par opposition aux algorithmes avides (eager learners) comme les réseaux de neurones ou les SVM. Un eager learner investit du temps dans la phase d’entraînement pour construire un modèle compact. Un lazy learner reporte tout le calcul à la phase de prédiction. Concrètement, la phase d’entraînement de KNN est quasi-instantanée (il suffit de stocker les données), mais chaque prédiction peut être coûteuse car elle nécessite de parcourir toutes les observations.

Cette caractéristique a des conséquences pratiques importantes :

• Pas de phase d’entraînement (au sens classique) : le modèle est le jeu de données lui-même.

• Prédictions coûteuses : chaque nouvelle observation requiert le calcul de la distance à tous les points d’entraînement, soit \(\mathcal{O}(n \cdot d)\) opérations pour \(n\) observations en dimension \(d\).

• Sensibilité au bruit : les points aberrants dans le voisinage peuvent perturber les prédictions.

• Pas d’interprétabilité globale : il n’y a pas de modèle explicite (pas de coefficients, pas de règles), seulement des décisions locales.

Algorithme KNN

Formalisation

Définition 82 (Algorithme des K plus proches voisins)

Soit un jeu d’entraînement \(\mathcal{D} = \{(\mathbf{x}_1, y_1), \ldots, (\mathbf{x}_n, y_n)\}\) où \(\mathbf{x}_i \in \mathbb{R}^d\) et \(y_i\) est l’étiquette (classe ou valeur) associée. Soit \(d(\cdot, \cdot)\) une fonction de distance sur \(\mathbb{R}^d\) et \(k \in \mathbb{N}^*\) un entier fixé.

Pour une nouvelle observation \(\mathbf{x}\), l’algorithme KNN :

1. Calcule les distances \(d(\mathbf{x}, \mathbf{x}_i)\) pour tout \(i \in \{1, \ldots, n\}\).

2. Sélectionne les \(k\) observations \(\mathbf{x}_{(1)}, \ldots, \mathbf{x}_{(k)}\) les plus proches de \(\mathbf{x}\) (les \(k\) plus proches voisins).

3. Agrège les étiquettes \(y_{(1)}, \ldots, y_{(k)}\) pour produire la prédiction \(\hat{y}\).

La méthode d’agrégation au point 3 dépend du type de problème : classification ou régression.

Classification par vote majoritaire

Définition 83 (KNN en classification)

En classification, la prédiction est la classe la plus fréquente parmi les \(k\) plus proches voisins :

\[\hat{y} = \arg\max_{c \in \mathcal{C}} \sum_{j=1}^{k} \mathbb{1}(y_{(j)} = c)\]

où \(\mathcal{C}\) est l’ensemble des classes et \(\mathbb{1}(\cdot)\) est la fonction indicatrice.

Remarque 75

En cas d’égalité (par exemple, 2 voisins de classe A et 2 de classe B pour \(k=4\)), différentes stratégies existent : choisir la classe du voisin le plus proche parmi les ex-aequo, tirer au hasard, ou utiliser un \(k\) impair pour les problèmes binaires. Dans scikit-learn, l’implémentation retourne la classe qui apparaît en premier dans l’ordre de parcours en cas d’égalité.

Régression par moyenne

Définition 84 (KNN en régression)

En régression, la prédiction est la moyenne des valeurs cibles des \(k\) plus proches voisins :

\[\hat{y} = \frac{1}{k} \sum_{j=1}^{k} y_{(j)}\]

Remarque 76

Une variante courante consiste à pondérer les contributions par l’inverse de la distance, accordant ainsi plus d’influence aux voisins les plus proches :

\[\hat{y} = \frac{\sum_{j=1}^{k} w_j \, y_{(j)}}{\sum_{j=1}^{k} w_j} \quad \text{avec} \quad w_j = \frac{1}{d(\mathbf{x}, \mathbf{x}_{(j)})}\]

Cette pondération atténue l’influence de voisins éloignés qui se trouvent à la limite du voisinage, ce qui produit généralement des prédictions plus lisses.

Illustrons le fonctionnement de KNN sur un exemple simple en deux dimensions.

Show code cell source

Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from matplotlib.colors import ListedColormap

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)

Show code cell source

Hide code cell source

from sklearn.datasets import make_blobs

# Génération de données synthétiques
X_demo, y_demo = make_blobs(n_samples=30, centers=3, cluster_std=1.5,
                            random_state=42)

# Point de requête
x_query = np.array([[0, 2]])
k = 5

# Calcul des distances
distances = np.linalg.norm(X_demo - x_query, axis=1)
nearest_idx = np.argsort(distances)[:k]

fig, ax = plt.subplots(figsize=(8, 6))
couleurs = ['#e74c3c', '#3498db', '#2ecc71']
for c in range(3):
    mask = y_demo == c
    ax.scatter(X_demo[mask, 0], X_demo[mask, 1], c=couleurs[c],
               label=f"Classe {c}", s=60, edgecolors='k', linewidth=0.5)

# Mise en évidence des k voisins
ax.scatter(X_demo[nearest_idx, 0], X_demo[nearest_idx, 1],
           s=200, facecolors='none', edgecolors='orange', linewidth=2.5,
           label=f'{k} plus proches voisins')

# Point de requête
ax.scatter(*x_query.flatten(), marker='*', s=300, c='black',
           zorder=5, label='Point de requête')

# Cercle englobant
radius = distances[nearest_idx[-1]]
circle = plt.Circle(x_query.flatten(), radius, fill=False,
                    linestyle='--', color='orange', linewidth=1.5)
ax.add_patch(circle)

ax.set_xlabel("$x_1$")
ax.set_ylabel("$x_2$")
ax.set_title(f"Illustration de KNN avec $k={k}$")
ax.legend(loc='upper left')
ax.set_aspect('equal')
plt.tight_layout()
plt.show()

# Vote majoritaire
classes_voisins = y_demo[nearest_idx]
print(f"Classes des {k} voisins : {classes_voisins}")
print(f"Prédiction (vote majoritaire) : classe {np.bincount(classes_voisins).argmax()}")

Classes des 5 voisins : [1 1 1 1 1]
Prédiction (vote majoritaire) : classe 1

Distances

Le choix de la fonction de distance est un paramètre fondamental de KNN. La distance détermine la notion de « proximité » entre observations, et donc quels voisins seront sélectionnés.

Distance euclidienne

Définition 85 (Distance euclidienne)

La distance euclidienne (ou norme \(L^2\)) entre deux vecteurs \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^d\) est

\[d_2(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|_2 = \sqrt{\sum_{i=1}^{d} (x_i - y_i)^2}\]

C’est la distance « en ligne droite » dans l’espace euclidien, généralisation du théorème de Pythagore.

La distance euclidienne est le choix par défaut dans la plupart des implémentations de KNN. Elle est appropriée lorsque les features sont de même nature et de même échelle.

Distance de Manhattan

Définition 86 (Distance de Manhattan)

La distance de Manhattan (ou norme \(L^1\), ou distance du taxi) est

\[d_1(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|_1 = \sum_{i=1}^{d} |x_i - y_i|\]

Elle correspond au chemin le plus court en se déplaçant uniquement le long des axes, comme dans un réseau de rues à angle droit.

Remarque 77

La distance de Manhattan est plus robuste aux valeurs aberrantes que la distance euclidienne, car elle ne met pas au carré les écarts. Un écart important sur une seule dimension aura un impact linéaire (et non quadratique) sur la distance totale.

Distance de Minkowski

Définition 87 (Distance de Minkowski)

La distance de Minkowski d’ordre \(p\) (avec \(p \geq 1\)) généralise les distances précédentes :

\[d_p(\mathbf{x}, \mathbf{y}) = \|\mathbf{x} - \mathbf{y}\|_p = \left(\sum_{i=1}^{d} |x_i - y_i|^p\right)^{1/p}\]

On retrouve :

• \(p = 1\) : distance de Manhattan

• \(p = 2\) : distance euclidienne

• \(p \to \infty\) : distance de Tchebychev \(d_\infty(\mathbf{x}, \mathbf{y}) = \max_{i} |x_i - y_i|\)

Proposition 16 (Propriétés d’une distance)

Toute distance \(d\) sur un espace \(E\) vérifie les quatre axiomes suivants pour tout \(\mathbf{x}, \mathbf{y}, \mathbf{z} \in E\) :

1. Non-négativité : \(d(\mathbf{x}, \mathbf{y}) \geq 0\)

2. Identité : \(d(\mathbf{x}, \mathbf{y}) = 0 \iff \mathbf{x} = \mathbf{y}\)

3. Symétrie : \(d(\mathbf{x}, \mathbf{y}) = d(\mathbf{y}, \mathbf{x})\)

4. Inégalité triangulaire : \(d(\mathbf{x}, \mathbf{z}) \leq d(\mathbf{x}, \mathbf{y}) + d(\mathbf{y}, \mathbf{z})\)

Les distances de Minkowski (pour \(p \geq 1\)) satisfont ces quatre propriétés et sont donc des distances au sens métrique.

Visualisons les « cercles unités » (ensembles de points à distance 1 de l’origine) pour différentes valeurs de \(p\).

Show code cell source

Hide code cell source

fig, axes = plt.subplots(4, 1, figsize=(8, 14))
ps = [1, 1.5, 2, 10]
theta = np.linspace(0, 2 * np.pi, 1000)

for ax, p in zip(axes, ps):
    # Points à distance Lp = 1 de l'origine
    t = np.linspace(0, 2 * np.pi, 1000)
    x = np.sign(np.cos(t)) * np.abs(np.cos(t)) ** (2 / p)
    y = np.sign(np.sin(t)) * np.abs(np.sin(t)) ** (2 / p)
    ax.plot(x, y, linewidth=2)
    ax.set_xlim(-1.5, 1.5)
    ax.set_ylim(-1.5, 1.5)
    ax.set_aspect('equal')
    ax.axhline(0, color='gray', linewidth=0.5)
    ax.axvline(0, color='gray', linewidth=0.5)
    ax.set_title(f"$p = {p}$" if p != 10 else r"$p = 10 \approx \infty$")
    ax.grid(True, alpha=0.3)

fig.suptitle("Boules unité pour la distance de Minkowski", fontsize=14, y=1.02)
plt.tight_layout()
plt.show()

Choix de k

Le choix de l’hyperparamètre \(k\) est crucial : il contrôle le compromis entre biais et variance du modèle.

Définition 88 (Compromis biais-variance pour KNN)

• \(k\) petit (ex. \(k=1\)) : le modèle est très flexible. La frontière de décision est irrégulière, épousant les particularités locales des données. Le biais est faible (le modèle peut capturer des structures complexes), mais la variance est élevée (le modèle est très sensible au bruit et aux fluctuations d’échantillonnage).

• \(k\) grand (ex. \(k=n\)) : le modèle est très rigide. La frontière de décision est lisse, moyennant les informations d’un grand voisinage. Le biais est élevé (le modèle peut manquer des structures locales), mais la variance est faible (les prédictions sont stables).

Remarque 78

Pour un problème de classification binaire, on choisit typiquement \(k\) impair afin d’éviter les situations d’égalité dans le vote majoritaire.

Illustrons l’effet de \(k\) sur la frontière de décision.

Show code cell source

Hide code cell source

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import make_moons

# Données en forme de lunes
X_moons, y_moons = make_moons(n_samples=200, noise=0.25, random_state=42)

fig, axes = plt.subplots(3, 1, figsize=(9, 14))

for ax, k in zip(axes, [1, 7, 50]):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_moons, y_moons)

    # Grille pour la frontière de décision
    h = 0.02
    x_min, x_max = X_moons[:, 0].min() - 0.5, X_moons[:, 0].max() + 0.5
    y_min, y_max = X_moons[:, 1].min() - 0.5, X_moons[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    Z = knn.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)

    cmap_light = ListedColormap(['#FFAAAA', '#AAAAFF'])
    cmap_bold = ListedColormap(['#FF0000', '#0000FF'])

    ax.contourf(xx, yy, Z, cmap=cmap_light, alpha=0.6)
    ax.scatter(X_moons[:, 0], X_moons[:, 1], c=y_moons, cmap=cmap_bold,
               edgecolors='k', s=30, linewidth=0.5)
    ax.set_title(f"$k = {k}$", fontsize=14)
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")

fig.suptitle("Effet de $k$ sur la frontière de décision", fontsize=15, y=1.02)
plt.tight_layout()
plt.show()

Méthode du coude

Pour choisir \(k\) de manière systématique, on peut tracer l’erreur de validation en fonction de \(k\) et chercher un « coude » : la valeur de \(k\) à partir de laquelle l’erreur cesse de diminuer significativement.

Show code cell source

Hide code cell source

from sklearn.model_selection import cross_val_score

k_values = range(1, 31)
cv_scores = []

for k in k_values:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X_moons, y_moons, cv=5, scoring='accuracy')
    cv_scores.append(scores.mean())

fig, ax = plt.subplots(figsize=(10, 5))
ax.plot(k_values, cv_scores, 'o-', linewidth=2, markersize=5)
best_k = k_values[np.argmax(cv_scores)]
ax.axvline(best_k, color='red', linestyle='--', alpha=0.7,
           label=f'Meilleur $k = {best_k}$')
ax.set_xlabel("$k$ (nombre de voisins)")
ax.set_ylabel("Accuracy (validation croisée 5-fold)")
ax.set_title("Choix de $k$ par validation croisée")
ax.legend()
ax.set_xticks(range(1, 31, 2))
plt.tight_layout()
plt.show()

print(f"Meilleure accuracy : {max(cv_scores):.4f} pour k = {best_k}")

Meilleure accuracy : 0.9500 pour k = 7

Proposition 17 (Règles pratiques pour le choix de k)

• Commencer par \(k = \sqrt{n}\) (où \(n\) est le nombre d’observations d’entraînement) comme point de départ.

• Utiliser la validation croisée pour comparer plusieurs valeurs de \(k\).

• Pour la classification binaire, préférer un \(k\) impair.

• Un \(k\) trop petit conduit au surapprentissage ; un \(k\) trop grand conduit au sous-apprentissage.

Malédiction de la dimensionnalité

La malédiction de la dimensionnalité (curse of dimensionality) est un phénomène fondamental qui affecte particulièrement les méthodes basées sur la distance, dont KNN.

Définition 89 (Malédiction de la dimensionnalité)

La malédiction de la dimensionnalité désigne l’ensemble des phénomènes contre-intuitifs qui apparaissent lorsque la dimension \(d\) de l’espace des features augmente. En particulier, dans un espace de grande dimension, les notions de distance et de voisinage deviennent progressivement dénuées de sens.

Volume de l’hypersphère

Pour comprendre pourquoi, examinons le volume d’une hypersphère.

Proposition 18 (Volume de l’hypersphère)

Le volume d’une hypersphère de rayon \(r\) en dimension \(d\) est

\[V_d(r) = \frac{\pi^{d/2}}{\Gamma\!\left(\frac{d}{2} + 1\right)} \, r^d\]

où \(\Gamma\) est la fonction gamma d’Euler. Pour les premières dimensions : \(V_1(r) = 2r\), \(V_2(r) = \pi r^2\), \(V_3(r) = \frac{4}{3}\pi r^3\).

Un résultat remarquable est que le rapport entre le volume de l’hypersphère et celui de l’hypercube qui la contient tend vers zéro quand \(d\) augmente :

\[\frac{V_{\text{sphère}}}{V_{\text{cube}}} = \frac{\pi^{d/2}}{\Gamma(d/2 + 1) \cdot 2^d} \xrightarrow{d \to \infty} 0\]

Cela signifie que la quasi-totalité du volume de l’espace se concentre dans les « coins », loin du centre.

Show code cell source

Hide code cell source

from scipy.special import gamma

dimensions = np.arange(1, 51)
ratio = np.array([
    np.pi ** (d / 2) / (gamma(d / 2 + 1) * 2 ** d)
    for d in dimensions
])

fig, ax = plt.subplots(figsize=(10, 5))
ax.plot(dimensions, ratio, 'o-', markersize=4, linewidth=2)
ax.set_xlabel("Dimension $d$")
ax.set_ylabel("$V_{\\mathrm{sphère}} \\,/\\, V_{\\mathrm{cube}}$")
ax.set_title("Rapport du volume de l'hypersphère au volume de l'hypercube englobant")
ax.set_yscale('log')
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

Conséquences pour KNN

Remarque 79

En haute dimension, les conséquences pour KNN sont dramatiques :

1. Les distances se concentrent : la différence relative entre le point le plus proche et le plus éloigné diminue. Formellement, si \(d_{\min}\) et \(d_{\max}\) sont les distances minimale et maximale à un point de requête :

\[\frac{d_{\max} - d_{\min}}{d_{\min}} \to 0 \quad \text{quand } d \to \infty\]

Les « plus proches voisins » ne sont plus significativement plus proches que les autres points.

2. Les données deviennent éparses : pour maintenir une densité locale constante, le nombre d’observations nécessaire croît exponentiellement avec \(d\). Si \(n = 100\) observations suffisent en 2D, il en faut \(100^{d/2}\) en dimension \(d\).

3. Les frontières de décision deviennent instables : comme les voisins ne sont plus réellement « proches », les prédictions deviennent quasi-aléatoires.

Illustrons la concentration des distances en augmentant la dimension.

Show code cell source

Hide code cell source

np.random.seed(42)
n_points = 500
dims = [2, 10, 50, 200]

fig, axes = plt.subplots(4, 1, figsize=(8, 14))

for ax, d in zip(axes, dims):
    # Points uniformément distribués dans [0,1]^d
    data = np.random.uniform(0, 1, size=(n_points, d))
    query = np.random.uniform(0, 1, size=(1, d))

    dists = np.linalg.norm(data - query, axis=1)

    ax.hist(dists, bins=30, edgecolor='black', alpha=0.7, density=True)
    ax.set_title(f"$d = {d}$")
    ax.set_xlabel("Distance au point de requête")

    # Rapport (max - min) / min
    ratio_dist = (dists.max() - dists.min()) / dists.min()
    ax.text(0.95, 0.95, f"$(d_{{max}}-d_{{min}})/d_{{min}}$\n$= {ratio_dist:.2f}$",
            transform=ax.transAxes, ha='right', va='top',
            fontsize=10, bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.8))

fig.suptitle("Concentration des distances en haute dimension",
             fontsize=14, y=1.02)
plt.tight_layout()
plt.show()

Proposition 19 (Atténuation de la malédiction)

Pour contrer la malédiction de la dimensionnalité dans le cadre de KNN :

• Réduction de dimension : appliquer PCA, t-SNE, UMAP, ou une sélection de features avant d’utiliser KNN.

• Sélection de features : ne conserver que les variables pertinentes (tests statistiques, importance par forêt aléatoire, etc.).

• Distances adaptées : utiliser des métriques qui pondèrent les dimensions par leur pertinence.

• Augmenter le jeu de données : si possible, collecter davantage d’observations.

Normalisation des features

KNN repose entièrement sur le calcul de distances. Or, si les features ne sont pas à la même échelle, celles dont les valeurs sont numériquement plus grandes domineront le calcul de distance.

Exemple 8

Considérons deux features : l”âge (entre 20 et 70) et le revenu annuel (entre 20 000 et 100 000 euros). La différence de revenu entre deux individus sera systématiquement plus grande que la différence d’âge, même si l’âge est une variable plus discriminante. Sans normalisation, KNN ignorera quasiment l’âge.

Show code cell source

Hide code cell source

from sklearn.preprocessing import StandardScaler

# Données non normalisées : âge et revenu
np.random.seed(42)
age = np.random.randint(20, 70, size=20).astype(float)
revenu = np.random.randint(20000, 100000, size=20).astype(float)
X_raw = np.column_stack([age, revenu])

# Point de requête
query_raw = np.array([[35, 45000]])

# Distances sans normalisation
dists_raw = np.linalg.norm(X_raw - query_raw, axis=1)

# Distances avec normalisation
scaler = StandardScaler()
X_norm = scaler.fit_transform(X_raw)
query_norm = scaler.transform(query_raw)
dists_norm = np.linalg.norm(X_norm - query_norm, axis=1)

fig, axes = plt.subplots(2, 1, figsize=(9, 9))

# Contribution relative de chaque feature à la distance
contrib_raw = np.abs(X_raw - query_raw)
contrib_norm = np.abs(X_norm - query_norm)

axes[0].bar(['Âge', 'Revenu'], contrib_raw.mean(axis=0), color=['#3498db', '#e74c3c'])
axes[0].set_title("Contribution moyenne sans normalisation")
axes[0].set_ylabel("Écart moyen absolu")

axes[1].bar(['Âge', 'Revenu'], contrib_norm.mean(axis=0), color=['#3498db', '#e74c3c'])
axes[1].set_title("Contribution moyenne avec normalisation")
axes[1].set_ylabel("Écart moyen absolu (standardisé)")

plt.tight_layout()
plt.show()

print(f"Sans normalisation — contribution de l'âge : {contrib_raw.mean(axis=0)[0]:.0f}, "
      f"du revenu : {contrib_raw.mean(axis=0)[1]:.0f}")
print(f"Le revenu domine la distance par un facteur "
      f"{contrib_raw.mean(axis=0)[1] / contrib_raw.mean(axis=0)[0]:.0f}")

Sans normalisation — contribution de l'âge : 12, du revenu : 25757
Le revenu domine la distance par un facteur 2069

Remarque 80

La normalisation est indispensable pour KNN (et pour tout algorithme basé sur la distance : SVM, k-means, etc.). Les deux approches les plus courantes sont :

• Standardisation (z-score) : \(x' = (x - \mu) / \sigma\). Chaque feature a une moyenne nulle et un écart-type unitaire.

• Normalisation Min-Max : \(x' = (x - x_{\min}) / (x_{\max} - x_{\min})\). Chaque feature est projetée dans \([0, 1]\).

Comme toujours, la normalisation doit être ajustée (fit) sur les données d’entraînement uniquement et appliquée (transform) aux données de test pour éviter la fuite de données.

Exemple complet avec scikit-learn

Mettons en pratique l’ensemble des concepts sur un problème complet : classification du jeu de données Iris avec KNN, incluant normalisation, recherche d’hyperparamètre et visualisation de la frontière de décision.

Show code cell source

Hide code cell source

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report, confusion_matrix, ConfusionMatrixDisplay
from sklearn.pipeline import Pipeline
import warnings
warnings.filterwarnings('ignore')

# Chargement des données
iris = load_iris()
X, y = iris.data, iris.target
feature_names = iris.feature_names
target_names = iris.target_names

print(f"Dimensions : {X.shape}")
print(f"Classes : {list(target_names)}")
print(f"Distribution : {np.bincount(y)}")

Dimensions : (150, 4)
Classes : [np.str_('setosa'), np.str_('versicolor'), np.str_('virginica')]
Distribution : [50 50 50]

Show code cell source

Hide code cell source

# Séparation entraînement / test
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42, stratify=y
)

print(f"Entraînement : {X_train.shape[0]} observations")
print(f"Test : {X_test.shape[0]} observations")

Entraînement : 105 observations
Test : 45 observations

Show code cell source

Hide code cell source

# Pipeline : normalisation + KNN
pipe = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier())
])

# Grille d'hyperparamètres
param_grid = {
    'knn__n_neighbors': range(1, 31),
    'knn__weights': ['uniform', 'distance'],
    'knn__metric': ['euclidean', 'manhattan', 'minkowski']
}

# Recherche par validation croisée
grid = GridSearchCV(pipe, param_grid, cv=5, scoring='accuracy', n_jobs=-1)
grid.fit(X_train, y_train)

print(f"Meilleurs hyperparamètres : {grid.best_params_}")
print(f"Meilleure accuracy (CV) : {grid.best_score_:.4f}")

Meilleurs hyperparamètres : {'knn__metric': 'euclidean', 'knn__n_neighbors': 14, 'knn__weights': 'uniform'}
Meilleure accuracy (CV) : 0.9714

Show code cell source

Hide code cell source

# Évaluation sur le jeu de test
y_pred = grid.predict(X_test)

print("Rapport de classification :")
print(classification_report(y_test, y_pred, target_names=target_names))

Rapport de classification :
              precision    recall  f1-score   support

      setosa       1.00      1.00      1.00        15
  versicolor       0.88      1.00      0.94        15
   virginica       1.00      0.87      0.93        15

    accuracy                           0.96        45
   macro avg       0.96      0.96      0.96        45
weighted avg       0.96      0.96      0.96        45

Show code cell source

Hide code cell source

# Matrice de confusion
fig, ax = plt.subplots(figsize=(7, 6))
cm = confusion_matrix(y_test, y_pred)
disp = ConfusionMatrixDisplay(confusion_matrix=cm, display_labels=target_names)
disp.plot(cmap='Blues', ax=ax)
ax.set_title("Matrice de confusion — KNN sur Iris")
plt.tight_layout()
plt.show()

Frontière de décision (2D)

Pour visualiser la frontière de décision, nous projetons les données sur les deux features les plus discriminantes.

Show code cell source

Hide code cell source

# Sélection des deux meilleures features (petal length et petal width)
X_2d = X[:, 2:4]
X_train_2d, X_test_2d, y_train_2d, y_test_2d = train_test_split(
    X_2d, y, test_size=0.3, random_state=42, stratify=y
)

# Normalisation
scaler_2d = StandardScaler()
X_train_2d_s = scaler_2d.fit_transform(X_train_2d)
X_test_2d_s = scaler_2d.transform(X_test_2d)

# Entraînement avec le meilleur k trouvé
best_k = grid.best_params_['knn__n_neighbors']
best_weights = grid.best_params_['knn__weights']
best_metric = grid.best_params_['knn__metric']

knn_2d = KNeighborsClassifier(n_neighbors=best_k, weights=best_weights,
                               metric=best_metric)
knn_2d.fit(X_train_2d_s, y_train_2d)

# Grille de décision
h = 0.02
x_min, x_max = X_train_2d_s[:, 0].min() - 1, X_train_2d_s[:, 0].max() + 1
y_min, y_max = X_train_2d_s[:, 1].min() - 1, X_train_2d_s[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                     np.arange(y_min, y_max, h))
Z = knn_2d.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)

# Visualisation
fig, ax = plt.subplots(figsize=(10, 7))

cmap_light = ListedColormap(['#FFCCCC', '#CCCCFF', '#CCFFCC'])
cmap_bold = ListedColormap(['#FF4444', '#4444FF', '#44BB44'])

ax.contourf(xx, yy, Z, cmap=cmap_light, alpha=0.6)

for i, name in enumerate(target_names):
    mask_train = y_train_2d == i
    mask_test = y_test_2d == i
    ax.scatter(X_train_2d_s[mask_train, 0], X_train_2d_s[mask_train, 1],
               c=[cmap_bold.colors[i]], label=f'{name} (train)',
               edgecolors='k', s=50, linewidth=0.5)
    ax.scatter(X_test_2d_s[mask_test, 0], X_test_2d_s[mask_test, 1],
               c=[cmap_bold.colors[i]], label=f'{name} (test)',
               edgecolors='k', s=50, linewidth=0.5, marker='s')

ax.set_xlabel("Petal length (standardisé)")
ax.set_ylabel("Petal width (standardisé)")
ax.set_title(f"Frontière de décision — KNN ($k={best_k}$, {best_weights}, {best_metric})")
ax.legend(loc='upper left', fontsize=9)
plt.tight_layout()
plt.show()

accuracy_2d = knn_2d.score(X_test_2d_s, y_test_2d)
print(f"Accuracy sur le test (2 features) : {accuracy_2d:.4f}")

Accuracy sur le test (2 features) : 0.9111

Comparaison des valeurs de k

Show code cell source

Hide code cell source

fig, axes = plt.subplots(2, 3, figsize=(18, 12))

for ax, k in zip(axes.ravel(), [1, 3, 5, 9, 15, 25]):
    knn_tmp = KNeighborsClassifier(n_neighbors=k, weights='distance')
    knn_tmp.fit(X_train_2d_s, y_train_2d)

    Z_tmp = knn_tmp.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)

    ax.contourf(xx, yy, Z_tmp, cmap=cmap_light, alpha=0.6)
    ax.scatter(X_train_2d_s[:, 0], X_train_2d_s[:, 1], c=y_train_2d,
               cmap=cmap_bold, edgecolors='k', s=30, linewidth=0.5)
    acc = knn_tmp.score(X_test_2d_s, y_test_2d)
    ax.set_title(f"$k = {k}$ — Accuracy = {acc:.2%}", fontsize=12)
    ax.set_xlabel("Petal length")
    ax.set_ylabel("Petal width")

fig.suptitle("Évolution de la frontière de décision selon $k$",
             fontsize=15, y=1.01)
plt.tight_layout()
plt.show()

Remarque 81

On observe clairement le compromis biais-variance :

• Pour \(k=1\), la frontière est très irrégulière et colle aux données d’entraînement (surapprentissage).

• Pour \(k\) élevé, la frontière se lisse et les zones de décision deviennent plus larges (sous-apprentissage potentiel).

• Les valeurs intermédiaires offrent généralement le meilleur compromis.

KNN en régression

Pour conclure, montrons brièvement l’utilisation de KNN en régression.

Show code cell source

Hide code cell source

from sklearn.neighbors import KNeighborsRegressor

# Fonction cible bruitée
np.random.seed(42)
X_reg = np.sort(np.random.uniform(0, 5, 100)).reshape(-1, 1)
y_reg = np.sin(X_reg.ravel()) + np.random.normal(0, 0.2, 100)

# Grille de prédiction
X_grid = np.linspace(0, 5, 500).reshape(-1, 1)

fig, ax = plt.subplots(figsize=(10, 5))
ax.scatter(X_reg, y_reg, alpha=0.5, s=20, label="Données", color='gray')

for k, color in zip([1, 5, 20], ['#e74c3c', '#3498db', '#2ecc71']):
    reg = KNeighborsRegressor(n_neighbors=k)
    reg.fit(X_reg, y_reg)
    y_pred_grid = reg.predict(X_grid)
    ax.plot(X_grid, y_pred_grid, label=f"$k = {k}$", linewidth=2, color=color)

ax.plot(X_grid, np.sin(X_grid), '--', color='black', alpha=0.5,
        label="$f(x) = \\sin(x)$", linewidth=1.5)
ax.set_xlabel("$x$")
ax.set_ylabel("$y$")
ax.set_title("KNN en régression")
ax.legend()
plt.tight_layout()
plt.show()

Remarque 82

En régression, les mêmes principes s’appliquent :

• \(k=1\) produit une courbe en escalier qui interpole exactement les données (surapprentissage).

• \(k\) élevé produit une courbe très lisse qui peut manquer les variations de la fonction cible (sous-apprentissage).

• La pondération par l’inverse de la distance (weights='distance') produit des prédictions plus lisses que le vote uniforme.