L’algorithme des k plus proches voisins appartient à la famille des algorithmes d’apprentissage automatique (machine learning). L’idée d’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. Les algorithmes d’apprentissage automatique ont connu un fort regain d’intérêt au début des années 2000 notamment grâce à la quantité de données disponibles sur internet.
L’algorithme des k plus proches voisins est un algorithme d’apprentissage supervisé, il est nécessaire d’avoir des données classées. À partir d’un ensemble E de données classées, il sera possible de classer (déterminer la classe) d’une nouvelle donnée (donnée n’appartenant pas à E). L’algorithme des k plus proches voisins est une bonne introduction aux principes des algorithmes d’apprentissage automatique, il est en effet relativement simple à comprendre.
AstucePrincipe
L’algorithme des k plus proches voisins est basé sur une idée simple : si une majorité des voisins d’un point sont de la classe C, alors ce point est probablement de la classe C. Pour déterminer la classe d’un point, l’algorithme va donc chercher les k points les plus proches de ce point et déterminer la classe majoritaire parmi ces k points.
Pour cela :
On dispose d’un jeu de données d’apprentissage (ensemble E) composé de données dont on connaît la classe.
On dispose d’une nouvelle donnée dont on souhaite déterminer la classe.
On calcule la distance entre la nouvelle donnée et chaque donnée de l’ensemble E.
On sélectionne les k données de l’ensemble E les plus proches de la nouvelle donnée.
On détermine la classe majoritaire parmi ces k données.
La nouvelle donnée est classée dans la classe majoritaire.
Exemple
On cherche à classifier des iris en fonction de la taille de leurs pétales. Le jeu de données suivant (ensemble E) présente 6 fleurs pour lesquelles on connaît la classe.
Nom de la fleur
Classe
Longueur du pétale (cm)
Largeur du pétale (cm)
Iris Setosa 1
Setosa
1.4
0.2
Iris Setosa 2
Setosa
1.5
0.2
Iris Versicolor 1
Versicolor
4.7
1.4
Iris Versicolor 2
Versicolor
4.3
1.5
Iris Virginica 1
Virginica
5.5
2.1
Iris Virginica 2
Virginica
5.6
2.2
Sur la représentation ci-dessous, on a représenté les iris de la classe Setosa en vert, ceux de la classe Versicolor en bleu et ceux de la classe Virginica en rouge.
Code
import matplotlib.pyplot as pltimport numpy as np# DonnéesX = np.array([[1.4, 0.2], [1.5, 0.2], [4.7, 1.4], [4.3, 1.5], [5.5, 2.1], [5.6, 2.2]])y = np.array([1, 1, 0, 0, 2, 2])# Représentation avec les couleurs rouge, vert et bleuplt.scatter(X[y ==0, 0], X[y ==0, 1], color='red', label='Versicolor')plt.scatter(X[y ==1, 0], X[y ==1, 1], color='blue', label='Setosa')plt.scatter(X[y ==2, 0], X[y ==2, 1], color='green', label='Virginica')plt.xlabel('Longueur du pétale (cm)')plt.ylabel('Largeur du pétale (cm)')plt.legend()plt.show()
Considérons maintenant une fleur d’iris “Iris X” dont les pétales ont une longueur de 3,5 cm et une largeur de 0,75 cm. On souhaite déterminer la classe de cette fleur.
Ajoutons le point correspondant à “Iris X” sur le graphique précédent.
Pour déterminer la classe de “Iris X”, on va calculer la distance entre “Iris X” et chacune des fleurs de l’ensemble E. Nous utilisons ici la distance euclidienne définie par la formule :
\[AB=\sqrt{(x_B-x_A)^2+(y_B-y_A)^2}\]
pour deux points \(A\) et \(B\) de coordonnées respectivement \((x_A, y_A)\) et \((x_B, y_B)\) dans un repère orthonormé du plan.
On obtient les résultats suivants :
Nom de la fleur
Distance à Iris X (cm)
Iris Setosa 1
2.17
Iris Setosa 2
2.07
Iris Versicolor 1
1.36
Iris Versicolor 2
1.10
Iris Virginica 1
2.41
Iris Virginica 2
2.55
On décide de donner au paramètre \(k\) la valeur 3. Cela signifie que l’on cherche les 3 points les plus proches de “Iris X” et on détermine la classe majoritaire parmi ces 3 points.
D’après le tableau ci-dessus, les trois fleurs les plus proches de “Iris X” sont “Iris Versicolor 2”, “Iris Versicolor 1” et “Iris Setosa 2”. On détermine donc que “Iris X” est de la classe Versicolor.
Remarque : en réalité, le nombre d’élément de l’ensemble E doit être le plus grand possible pour que l’algorithme soit efficace.
Important
Deux points importants influent sur le résultat de l’algorithme :
Le choix de la distance entre les points : la distance euclidienne n’est pas toujours la meilleure distance possible. Il est parfois préférable d’utiliser d’autres distances. On utilise parfois la distance Manhattan, définie par : \[AB=|x_B-x_A|+|y_B-y_A|\]
Le choix du nombre de voisins : le nombre de voisins \(k\) doit être suffisamment grand, mais pas trop, pour que l’algorithme soit efficace. En général, on choisit une valeur impaire pour éviter les cas d’égalité.
Exercice : les pétales d’un iris ont une longueur de 2,5 cm et une largeur de 1,25 cm. Déterminer la classe de cette fleur.
