Algorithme des k plus proches voisins : cours de NSI Première

Imagine que tu aies mesuré la longueur et la largeur des pétales de plusieurs fleurs, et que tu connaisses l'espèce de chacune. Un jour, tu trouves une fleur nouvelle : tu mesures ses pétales, mais tu ne connais pas son espèce. Comment deviner ? Une idée naturelle consiste à chercher, parmi les fleurs déjà connues, celles qui ressemblent le plus à la nouvelle, puis à copier leur espèce. C'est exactement ce que fait l'algorithme des k plus proches voisins, que l'on abrège souvent en k-NN (de l'anglais k-nearest neighbors). ³

Cet algorithme appartient à la famille des algorithmes d'apprentissage automatique (en anglais machine learning). ² Au programme de Première, il figure dans la partie « Algorithmique » : il permet à un programme de prendre une décision à partir d'exemples plutôt qu'à partir de règles écrites à la main. ¹

Dans ce cours, tu vas voir :

• ce que veut dire « apprentissage supervisé » et pourquoi il faut des données labellisées ;
• comment mesurer la proximité entre deux données grâce à une distance ;
• le déroulement précis de l'algorithme ;
• un exemple entièrement calculé à la main ;
• l'influence du paramètre k ;
• une écriture en Python et ses limites.

Pour comprendre l'algorithme, il faut d'abord comprendre le vocabulaire de l'apprentissage automatique.

Les k plus proches voisins relèvent de l'apprentissage supervisé : on doit posséder des exemples labellisés. ² Une donnée labellisée est une donnée dont on connaît déjà la réponse attendue, appelée label ou classe. Concrètement, on dispose d'un jeu d'apprentissage composé de couples « entrée-sortie ». ³

Prenons un exemple concret :

Le travail de l'algorithme consiste alors à prédire la sortie pour une entrée dont on ne connaît pas la sortie.

Une démonstration classique de l'algorithme utilise trois espèces d'iris (Iris setosa, Iris virginica et Iris versicolor). Quand on représente les mesures de ces fleurs sur un graphique, les trois classes apparaissent relativement bien séparées. ² C'est une bonne situation pour les k plus proches voisins : si les classes forment des groupes assez distincts, les voisins d'une nouvelle fleur ont de grandes chances d'appartenir à la même classe qu'elle.

Pour parler de « plus proches voisins », il faut savoir mesurer la proximité entre deux données. La méthode s'appuie donc sur une distance à définir selon le problème. ³ Comme l'algorithme est basé sur la distance, une normalisation des données peut améliorer sa précision. ³

Le choix usuel pour des variables continues, c'est-à-dire des mesures qui peuvent prendre n'importe quelle valeur dans un intervalle, est la distance euclidienne. ³ C'est la distance « à vol d'oiseau » que tu connais depuis le collège.

Quand une donnée est décrite par plus de deux nombres, on ajoute simplement un terme de plus sous la racine par mesure supplémentaire. Pour deux données à trois mesures, la distance vaut $\sqrt{(a_1-b_1)^2+(a_2-b_2)^2+(a_3-b_3)^2}$. Il est même possible de représenter un objet décrit par $m$ paramètres chiffrés comme un point d'un espace à $m$ dimensions. ⁴

La distance euclidienne n'est pas la seule possible. Pour des variables discrètes, comme en classification de texte, on peut utiliser une autre distance, par exemple la distance de Hamming. ³ Au programme de Première, tu travailleras presque toujours avec la distance euclidienne.

On dispose d'un jeu de données de $n$ éléments, chacun avec sa classe, et d'une nouvelle donnée $x$ à classer. On se donne aussi un entier $k$ inférieur ou égal à $n$. ²

Il n'y a pas d'étape d'apprentissage au sens strict : on se contente de conserver le jeu de données. ² Tout le travail a lieu au moment où l'on veut classer une nouvelle donnée.

Pour trouver les $k$ plus proches voisins, une méthode directe consiste à parcourir tous les points du jeu de données. Pour chaque point, on regarde s'il est plus proche que l'un des voisins déjà retenus ; si oui, on l'insère dans la liste des voisins et on supprime le plus éloigné pour garder exactement $k$ points. ⁴ Tu reconnais là un parcours séquentiel, comme tu en as déjà écrit pour chercher un minimum dans un tableau.

Plaçons-nous dans le plan. Notre jeu de données contient sept points, répartis en deux classes, A et B :

• classe A : $A_1(1 ; 2)$, $A_2(2 ; 1)$, $A_3(1 ; 3)$ ;
• classe B : $B_1(3 ; 3)$, $B_2(5 ; 4)$, $B_3(6 ; 5)$, $B_4(5 ; 6)$.

On veut classer le point nouveau $P(3 ; 2)$.

Cet exemple montre une chose capitale : le résultat dépend de k. Pour le même point $P$ et les mêmes données, on obtient B avec $k=1$, A avec $k=3$ et $k=5$, puis B de nouveau avec $k=7$. Le dernier cas est extrême : avec $k = n$, la prédiction ne dépend plus du tout de la position de $P$, on obtient toujours la classe la plus fréquente du jeu de données. Cela n'a plus aucun intérêt.

L'algorithme a besoin de connaître le nombre $k$ de voisins à considérer. ³ Il n'existe pas de valeur universelle. Une méthode classique pour la choisir est la validation croisée. ³ Elle consiste, en gros, à essayer plusieurs valeurs de $k$ sur des données dont on connaît déjà les classes et à garder celle qui se trompe le moins. Elle dépasse le programme de Première, mais l'idée est utile pour comprendre qu'on teste k plutôt que de le deviner.

Que faire en cas d'égalité ? Le principe de base ne le précise pas : c'est un choix à faire dans le programme. On peut par exemple choisir la classe du voisin le plus proche parmi les classes à égalité, ou augmenter ou diminuer $k$ d'une unité. L'essentiel est de décider une règle claire, de la documenter et de l'appliquer toujours de la même façon.

Pondérer les voisins. Dans la version de base, les $k$ voisins comptent à égalité. Il existe une technique efficace qui donne plus de poids aux voisins proches qu'aux voisins éloignés. Un schéma courant donne à chaque voisin le poids $1/d$, où $d$ est sa distance à la donnée à classer. ³ Dans notre exemple, $B_1$ (à distance 1) compterait alors deux fois plus que $A_1$ (à distance 2).

On représente le jeu de données par une liste de couples (point, classe), où point est un tuple de coordonnées. Pour la donnée à classer, on utilise aussi un tuple.

from math import sqrt

def distance(p, q):
    return sqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2)

def k_plus_proches(donnees, x, k):
    couples = [(distance(p, x), classe) for (p, classe) in donnees]
    couples.sort()
    return couples[:k]

def classe_majoritaire(voisins):
    effectifs = {}
    for (d, classe) in voisins:
        effectifs[classe] = effectifs.get(classe, 0) + 1
    meilleure = None
    for classe in effectifs:
        if meilleure is None or effectifs[classe] > effectifs[meilleure]:
            meilleure = classe
    return meilleure

def knn(donnees, x, k):
    return classe_majoritaire(k_plus_proches(donnees, x, k))

Avec notre exemple, knn(donnees, (3, 2), 3) renvoie 'A', comme dans le calcul à la main.

Analysons ce code :

• distance applique la formule de la distance euclidienne ;
• k_plus_proches associe à chaque point du jeu de données sa distance à x, trie les couples par distance croissante, puis garde les k premiers ;
• classe_majoritaire compte les classes avec un dictionnaire et renvoie celle dont l'effectif est le plus grand. En cas d'égalité, elle garde la première rencontrée, ce qui constitue une règle de départage parmi d'autres ;
• knn assemble les deux fonctions précédentes.

Le tri complet n'est pas indispensable : le parcours séquentiel avec une liste de $k$ voisins, évoqué plus haut, suffit. ⁴ Le tri a l'avantage d'être court à écrire, ce qui est pratique pour s'entraîner.

Un avantage : pas d'entraînement. Puisqu'il suffit de conserver le jeu de données, on peut ajouter de nouveaux exemples à tout moment sans « réapprendre » quoi que ce soit. ²

Un coût au moment de la prédiction. Chaque nouvelle prédiction oblige à comparer la donnée à classer avec les $n$ éléments du jeu de données. La recherche séquentielle, qui parcourt tous les points, a un temps de calcul linéaire en la taille de l'ensemble, noté $O(n)$, tant que $k$ reste très petit devant $n$. ⁴ Si ton jeu de données double de taille, la recherche prend environ deux fois plus de temps. Tu as déjà rencontré cette notion de coût d'un algorithme en étudiant les tris.

Des limites à connaître.

• Le résultat dépend de la distance et de la valeur de $k$, deux choix qui ne sont pas imposés par les données. ³
• Sans normalisation, une mesure à grande échelle peut dominer les autres. ³
• La qualité de la prédiction dépend de la qualité des données labellisées : si les classes se mélangent beaucoup dans l'espace des mesures, les voisins ne suffisent pas à trancher.
• On peut améliorer la précision en apprenant la distance avec des algorithmes spécialisés, ce qui dépasse le niveau de la classe de Première. ³