Aller au contenu

On cherche le plus proche voisin dans le dictionnaire (K=1)

Dans le domaine de l'apprentissage automatique dit "Machine Learning", l'algorithme des k plus proches voisins est l'un des plus utilisés.

Sommaire

Chapitre Description
Distance Calcul des distances entre points
Implémentation Code Python de l'algorithme KNN
TP KNN Travaux pratiques
Exercices Exercices d'application

Le programme

bo

Un peu d'histoire...

Même si les Large Language Models (LLM) ont démocratisé ce genre d'outil, l'apprentissage automatique ne date pas d’hier, puisque le terme de machine learning a été utilisé pour la première fois par l’informaticien américain Arthur Samuel en 1959. Puis, début 2000, l'arrivée des Big Datas va contribuer à l'explosion de ce genre de modèle.

Classification

  • Permet de prédire si un élèment est membre d'un groupe ou d'une catégorie donnée
  • Une classe permet une identification de groupes avec des profils particuliers
  • Offre une possibilité de décider de l'appartenance d'une entitié à une classe
  • Dans notre exemple, on parlera de classification supervisée c'est à dire que l'on connait déjà les différentes classes à l'avance

Parmi les modèles et méthodes de classification, on peut citer :

  • K-NN Voisins
  • Arbres de décision
  • Réseaux de neurones

Exemple de Problème de classification avec K-NN

L'algorithme des k plus proches voisins permet de résoudre certains problèmes, notamment ceux qui proposent de classer des données et élèments.

Il s'agit d'une méthode de raisonnement à partir de cas connus : ce modèle va aider à prendre des décisions en recherchant un ou des cas similaires déjà résolus.

Attention, KNN est un algorithme dit paresseux (lazy learning) : contrairement à d'autres algorithmes de classification, il n'y a pas de phase d'entraînement où un modèle est construit. L'échantillon d'apprentissage est simplement mémorisé, et tout le travail de calcul se fait au moment de la prédiction.

Qu'est ce qu'un modèle ?

Il s'agit d'une représentation simplifiée de la réalité en vue de réaliser un traitement avec un ordinateur.

Dans ce cas, notre modèle = échantillon d’apprentissage + fonction de distance + fonction de choix de la classe en fonction des classes des voisins les plus proches.

Pour quels types de variables ?

  • Qualitatives
  • Quantitatives

Exemple de l'implémentation de l'algorithme des k plus proches voisins

Le Professeur Chen, inventeur du Pokédex, utilise cet algorithme afin que son appareil puisse prédire quel pokémon se trouve devant lui.

chen

Pour simplifier, imaginons que les Pokemons ne possèdent que deux caractéristiques : leurs points de vie et leur valeur d'attaque. On peut prendre deux types pour commencer.

Nom Écayon Deoxys Éoko Groret Tarpaud
Points de vie 49 50 80 90 90
Attaque 49 95 45 75 75
Type Eau Psy Psy Psy Eau
  • Nous pouvons utiliser cet échantillon afin de prédire la classification d'un Pokémon mystère, selon ses points de vie et sa valeur d'attaque, en représentant ces données sous la forme d'un graphique.

echantillon

Prédiction

À partir des données du diagramme, on veut prédire la classe d'un pokémon ayant 65 points de vie et 40 en attaque.

echantillon_2

Il devrait donc se trouver dans cette zone. On peut alors trouver ses cinq ou six plus proches voisins.

  • Parmi ces voisins se trouvent deux Pokémons de type Eau, et trois de types Psy.
  • Le Pokémon mystère sera donc probablement de type Psy !

Formulation de l'algorithme

Pour rendre cette classification automatique, nous allons utiliser un algorithme python.

D'après vous, que faut-il pour pouvoir prédire la classe d'un Pokemon donné ?

  • Échantillon de Pokemon
  • Un pokemon mystère dont on souhaite prédire la classification
  • la valeur de k

Comment choisir k ? On choisit généralement k impair (pour éviter les égalités lors du vote majoritaire) et une valeur raisonnable comme √n (racine carrée du nombre d'échantillons) ou entre 5 et 7 pour de petits échantillons.

Une fois ces données modélisées, on peut formuler notre algorithme:

  • Trouver dans l'échantillon, les k plus proches voisins du pokemon mystère
  • Trouver la classification majoritaire parmi les voisins les plus proches
  • Renvoyer cette classification

Application concrète : Google compresse ses modèles IA avec KNN

Vous venez d'apprendre à trouver le voisin le plus proche d'un point dans un espace de coordonnées. Google utilise exactement ce principe pour réduire la mémoire nécessaire à ses modèles d'IA (comme Gemini).

Le problème : un modèle d'IA contient des milliards de paramètres — des vecteurs de nombres décimaux très précis. Les stocker tels quels nécessite des dizaines de gigaoctets de RAM.

La solution (quantification vectorielle) : 1. On construit un petit dictionnaire de vecteurs représentatifs (quelques milliers d'entrées) 2. Pour chaque vecteur du modèle, on cherche lequel dans le dictionnaire est le plus proche — en calculant une distance, exactement comme en KNN 3. On stocke uniquement l'indice de ce voisin le plus proche, au lieu du vecteur complet

C'est du KNN avec K = 1, appliqué non pas à une classification, mais à une compression. Le gain en mémoire peut atteindre un facteur 8.

import math

vecteur_du_modele = [0.83, -1.47, 0.21]

dictionnaire = [
    [1.0, -1.5, 0.0],  # indice 0
    [0.8, -1.4, 0.2],  # indice 1
    [-0.5, 0.3, 1.1],  # indice 2
]

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

# On cherche le plus proche voisin dans le dictionnaire (K=1)
plus_proche = min(range(len(dictionnaire)),
                  key=lambda i: distance(vecteur_du_modele, dictionnaire[i]))

print(f"On stocke juste l'indice {plus_proche} au lieu de {vecteur_du_modele}")
# → On stocke juste l'indice 1 au lieu de [0.83, -1.47, 0.21]

L'algorithme KNN n'est donc pas réservé à la classification : dès qu'on cherche "le plus ressemblant" dans un ensemble connu, on fait du KNN.

Pour résumer...

L'algorithme des k plus proches voisins a pour objectif d'identifier les voisins les plus proches d'un point de requête donné, afin d'attribuer une classe à ce point

Auteur : Florian Mathieu

Licence CC BY NC

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.