Les k plus proches voisins (k-NN)

Introduction

Les cours précédents portaient sur des algorithmes déterministes (qui produisent toujours la même sortie pour une même entrée) : on sait exactement ce qu'ils calculent, et on peut prouver leur correction. Ce dernier cours change de registre : il introduit un algorithme d'apprentissage, le k plus proches voisins (ou k-Nearest Neighbors, k-NN). On lui fournit des exemples déjà étiquetés, et il classe un nouvel exemple par ressemblance aux exemples connus. C'est un avant-goût de l'apprentissage automatique, approfondi en Terminale et au-delà.

Le cœur du concept

Problème : un ensemble de points d'un plan est donné, chacun étiqueté avec une classe (par exemple « chat » ou « chien », ou « iris setosa » / « iris versicolor »). Un nouveau point se présente, sans étiquette. Quelle classe lui attribuer ?

Idée du k-NN :

1. Calculer la distance entre le nouveau point et chaque point étiqueté.
2. Sélectionner les $k$ plus proches.
3. Regarder leur classe majoritaire parmi ces $k$ voisins.
4. Attribuer cette classe au nouveau point.

La distance euclidienne

Pour mesurer à quel point deux points sont proches, on utilise une distance. La plus classique est la distance euclidienne, celle de la règle, en ligne droite.

En 1D, c'est tout simplement l'écart entre deux nombres : pour deux points $a$ et $b$ sur une droite,

En 2D, on applique le théorème de Pythagore au triangle rectangle formé par les deux points. Pour deux points $A = (x_A, y_A)$ et $B = (x_B, y_B)$ :

En Python :

import math

def distance(a, b):
    """Distance euclidienne entre deux points 2D."""
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

print(distance((0, 0), (3, 4)))   # 5.0

L'algorithme k-NN complet

import math
from collections import Counter

def distance(a, b):
    return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))

def knn(donnees, nouveau, k):
    """donnees : liste de tuples (point, classe).
    nouveau : un point à classer.
    k : nombre de voisins à considérer.
    Retourne la classe prédite pour nouveau."""
    # 1. Distances entre nouveau et chaque point étiqueté
    distances = [(distance(point, nouveau), classe) for point, classe in donnees]
    # 2. Tri par distance croissante
    distances.sort()
    # 3. Récupération des classes des k plus proches
    voisins = [classe for _, classe in distances[:k]]
    # 4. Vote majoritaire
    return Counter(voisins).most_common(1)[0][0]

# Exemple : classifier un fruit par son poids et son diamètre
fruits = [
    ((150, 7), "pomme"),
    ((170, 7.5), "pomme"),
    ((140, 6.8), "pomme"),
    ((120, 5.5), "mandarine"),
    ((110, 5), "mandarine"),
    ((130, 5.8), "mandarine"),
]
inconnu = (135, 6.2)
print(knn(fruits, inconnu, k=3))
# mandarine (2 voisins mandarine sur 3)

Choisir $k$

Le choix de $k$ influence fortement le résultat.

• $k = 1$ : on prend la classe du voisin le plus proche, point. Très sensible au bruit (un seul exemple aberrant peut faire basculer la classification).
• $k$ grand : on lisse, on moyenne, mais on perd la finesse locale. Si $k =$ nombre total d'exemples, on retombe sur la classe globalement majoritaire quel que soit le nouveau point.

C'est un algorithme d'apprentissage

Le k-NN apprend à partir d'exemples étiquetés : il n'a pas besoin qu'on lui donne de règle explicite (« si poids > 140 alors pomme »). Il déduit ces règles implicitement de la disposition des points. C'est ce qu'on appelle l'apprentissage supervisé : on apprend à partir d'exemples dont on connaît la classe.

Coût de l'algorithme

Pour classer un seul nouveau point :

• on calcule $n$ distances : $\mathcal{O}(n)$ ;
• on les trie : $\mathcal{O}(n \log n)$, ou moins si on ne veut que les $k$ plus petites ;
• on fait un vote : $\mathcal{O}(k)$.

Au total : $\mathcal{O}(n \log n)$ par prédiction. Acceptable pour quelques milliers d'exemples, lourd au-delà, d'où des structures de données plus malines (arbres k-d, hashage de localité) qu'on rencontre en pratique réelle.

Pièges courants

• Unités hétérogènes : si une coordonnée est en grammes (100 à 200) et l'autre en centimètres (5 à 8), le poids dominera la distance et la taille sera ignorée. On normalise souvent les coordonnées avant de calculer des distances.
• Choix de $k$ extrême : $k = 1$ surajuste, $k$ trop grand sous-ajuste.
• Base de données déséquilibrée : avec 90 % de pommes et 10 % de mandarines, le vote majoritaire prédira presque toujours « pomme ». Il faut équilibrer ou pondérer.

Le nuage ci-dessous met le premier piège en scène, avec les six fruits du programme précédent. Cliquer dans le cadre place un point à classer, le curseur règle $k$.

La frontière en pointillés, celle qui délimite les $k$ voisins retenus, est étirée en hauteur, et ce n'est pas un défaut d'affichage. Dans le calcul, un gramme et un centimètre comptent pour la même chose : le poids varie sur 60 unités quand le diamètre n'en parcourt que 2,5, si bien que la distance est décidée par le poids presque seul. C'est exactement ce que dit le premier piège, et ce qu'une normalisation des coordonnées corrigerait.

Pour aller plus loin

Le k-NN est conceptuellement très simple. C'est souvent un baseline, un algorithme de référence facile à coder, contre lequel on compare des méthodes plus sophistiquées (arbres de décision, réseaux de neurones, etc.). Sa simplicité reste sa force pédagogique : pour comprendre l'idée même d'apprentissage automatique, il est imbattable.