cours1 min de lecture

Les k plus proches voisins (k-NN)

Un premier algorithme d'apprentissage — classer un point en regardant la classe majoritaire de ses k plus proches voisins.

programme

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 que vous approfondirez en Terminale et au-delà.

Le cœur du concept

Problème : on vous donne un ensemble de points dans un plan, chacun étiqueté avec une classe (par exemple « chat » ou « chien », ou « iris setosa » / « iris versicolor »). On vous présente un nouveau point sans étiquette. Quelle classe lui attribuer ?

Idée du k-NN :

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

Analogie : si vos

k

voisins de palier sont tous fans d'opéra, il est probable que vous le soyez aussi. Le k-NN parie sur cette « contagion locale » des étiquettes.

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,

d(a, b) = |a - b|.

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)$ :

d(A, B) = \sqrt{(x_A - x_B)^2 + (y_A - y_B)^2}

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

La distance euclidienne se généralise à un nombre quelconque de dimensions :

d(A, B) = \sqrt{\sum_{i=1}^{n}(x_i^A - x_i^B)^2}

L'algorithme k-NN complet

Boîte à outils Python. Le code ci-dessous s'appuie sur quelques briques vues en PC (list-comprehension) et PG (lambda, opérateurs sur itérables) :

zip(a, b) parcourt en parallèle deux listes (utile pour comparer composante par composante les coordonnées de deux points).
Counter(voisins).most_common(1) compte rapidement les occurrences et renvoie la classe majoritaire.
[expr for x in liste] est une list-comprehension : on construit une nouvelle liste en une ligne.

Pas la peine de tout maîtriser pour comprendre l'algorithme — concentrez-vous sur les quatre étapes numérotées.

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' ou 'pomme' selon les plus proches

⏵ Ctrl+↵ pour exécuter

Aucune exécution pour l'instant.

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.

En pratique, on choisit souvent

k

impair (pour éviter les égalités dans le vote majoritaire) et autour de

\sqrt{n}

où

n

est le nombre d'exemples étiquetés.

Pourquoi choisit-on souvent k impair ?

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.

Trois grandes familles d'apprentissage automatique

Supervisé : exemples étiquetés (classe connue). Le k-NN en est un cas.
Non supervisé : exemples sans étiquette, on cherche des structures (groupes, regroupements).
Par renforcement : on apprend en interagissant avec un environnement, par essais et erreurs.

Le k-NN est l'un des plus simples — pas de phase d'entraînement à proprement parler, on garde juste tous les exemples en mémoire et on calcule au moment de la prédiction.

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 on peut faire 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.

Le k-NN appartient à quelle famille d'apprentissage ?

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 : si vous avez 90 % de pommes et 10 % de mandarines, le vote majoritaire prédira presque toujours « pomme ». Il faut équilibrer ou pondérer.

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.