K-Nearest Neighbors (KNN)

K plus proches voisins (KNN) est un algorithme d’apprentissage supervisé qui prédit l’étiquette d’un nouvel exemple à partir des k exemples étiquetés les plus proches : il utilise le vote majoritaire de ces voisins pour la classification, ou leur moyenne pour la régression. KNN est non paramétrique et « paresseux » : il n’apprend aucun poids, stocke simplement les données d’entraînement et n’effectue son travail qu’au moment où une prédiction est demandée. Evelyn Fix et Joseph Hodges ont présenté cette méthode en 1951 et, en 1967, Thomas Cover et Peter Hart ont démontré qu’avec une quantité illimitée de données, la règle du plus proche voisin a un taux d’erreur au plus deux fois supérieur à celui du meilleur classifieur possible. Cette même recherche des plus proches voisins fonctionne aujourd’hui à grande échelle dans les bases de données vectorielles et les systèmes de recherche d’images qui comparent les plongements issus de réseaux neuronaux.

Comment KNN effectue une prédiction#

Pour chaque point à interroger, KNN exécute trois étapes :

1. Mesurer la distance : L’algorithme calcule la distance entre le point à interroger et chaque exemple stocké. La distance euclidienne est celle utilisée par défaut ; les distances de Manhattan et de Minkowski sont des solutions de rechange courantes, et la similarité cosinus est standard pour les plongements, où la direction d’un vecteur porte son sens.
2. Sélectionner les voisins : L’algorithme conserve les k exemples dont les distances sont les plus faibles.
3. Combiner leurs étiquettes : Pour la classification, l’algorithme choisit la classe la plus fréquente parmi les voisins ; pour la régression, il calcule la moyenne de leurs valeurs. Avec une pondération par distance (weights="distance" dans scikit-learn), les voisins les plus proches comptent davantage.

Chaque caractéristique contribue à la distance. Les caractéristiques dont l’échelle est grande dominent donc : le revenu en dollars éclipserait l’âge en années. Les pipelines KNN standardisent donc d’abord les caractéristiques ou comparent les plongements issus d’un modèle d’extraction de caractéristiques, afin que chaque dimension contribue à une échelle comparable.

Choisir k#

La valeur de k détermine l’équilibre entre le surapprentissage et le sous-apprentissage. Avec k = 1, chaque point d’entraînement, y compris les points bruités ou mal étiquetés, s’approprie sa propre région et la frontière de décision devient irrégulière. Avec un k très élevé, chaque vote porte loin du point à interroger et brouille les véritables frontières entre les classes. Pour deux classes, un k impair évite les égalités de vote, et la validation croisée est la méthode standard pour choisir k. Sur le jeu de données bruité des deux lunes de scikit-learn, le compromis apparaît dans trois valeurs :

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

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

Avec k = 1, le classifieur mémorise ses points d’entraînement et obtient un score de 1.00 sur ces derniers et de 0.83 sur les points mis de côté. Avec k = 15, il obtient respectivement 0.90 et 0.89, le meilleur résultat de test des trois valeurs. Avec k = 300, soit près de la moitié des 700 points d’entraînement, la frontière s’adoucit jusqu’à faire baisser les deux scores à 0.84 et 0.81.

Accélérer la recherche des voisins#

Une recherche par force brute compare le point à interroger aux n points stockés dans d dimensions : chaque prédiction demande un nombre d’opérations de l’ordre de n × d, et la mémoire utilisée augmente avec la taille du jeu de données. Les structures de partitionnement de l’espace, telles que les arbres k-d et les arbres ball, évitent la plupart des comparaisons dans les espaces de faible dimension ; le algorithm="auto" de scikit-learn choisit entre la force brute, l’arbre k-d et l’arbre ball. Dans les espaces de grande dimension, la malédiction de la dimensionnalité rend les distances entre les points presque égales, l’élagage des arbres cesse d’être avantageux et les grands systèmes passent à des index approximatifs des plus proches voisins (ANN), tels que les graphes HNSW et les index de fichiers inversés (IVF) avec quantification de produit, implémentés dans des bibliothèques comme FAISS. Ces index renvoient la plupart des véritables plus proches voisins tout en comparant le point à interroger à une petite fraction des vecteurs stockés :

KNN et méthodes apparentées#

• Regroupement k-means : Un algorithme non supervisé qui regroupe les points non étiquetés en k groupes autour de centroïdes appris. La lettre commune aux noms est une coïncidence : dans k-means, k compte les groupes.
• Recherche vectorielle : La forme de récupération de la même opération : elle renvoie les éléments stockés les plus proches d’un plongement de requête, généralement au moyen d’un index approximatif, et l’application utilise directement ces éléments.
• Machines à vecteurs de support et régression logistique : Des modèles paramétriques qui apprennent une frontière de décision pendant l’entraînement ; le coût de la prédiction reste donc constant à mesure que le jeu de données d’entraînement grandit.

Applications concrètes#

• Systèmes de recommandation : Le filtrage collaboratif fondé sur les éléments recommande les produits dont les vecteurs d’évaluation ou d’achat sont les plus proches de ceux des éléments qu’un utilisateur a déjà appréciés.
• Détection des anomalies : La distance entre un point et son k-ième plus proche voisin sert de score d’anomalie. Les transactions ou les relevés de capteurs éloignés de tous les exemples normaux ressortent donc du lot.
• Imputation des valeurs manquantes : Le KNNImputer de scikit-learn remplace chaque valeur manquante par la moyenne de cette caractéristique dans les k lignes les plus similaires.
• Recherche d’images et réidentification : Les systèmes comparent le plongement d’une image à une galerie pour retrouver le même produit, visage ou personne observé par une autre caméra. La solution de recherche par similarité d’Ultralytics représente un dossier d’images avec CLIP d’OpenAI, calcule par similarité cosinus un score pour chaque image indexée par rapport à une requête textuelle telle que « voiture rouge » lors d’une recherche exacte par force brute, puis renvoie les images les plus proches, jusqu’à 30 par défaut.