On veut « deviner » la couleur du point représenté en vert ci-dessous. Ses coordonnées sont (330,225) et il ne peut être que rouge ou bleu.
On pourrait dire qu'il est rouge parce qu'il est situé près d'un point qui, lui, est rouge :
Mais ce résultat semble contraire à l'intuition.
En élargissant le cercle autour du point vert, on constate que parmi les trois plus proches voisins, il y a une majorité de points bleus :
Cela se confirme si on élargit le cercle avec par exemple la méthode des 5 plus proches voisins :
Cet algorithme n'est pas fiable à 100%. Son coût est principalement celui du tri.
On utilise le théorème de Pythagore : la distance entre deux points est l'hypoténuse d'un triangle rectangle dont les côtés sont les différences entre les coordonnées des points (vu en maths en 2nde).
from math import hypot def distance(L1,L2): return hypot(L1[0]-L2[0],L1[1]-L2[1])
On utilise le module csv
qui permet d'ouvrir
le fichier contenant les points rouges et bleus (données
d'apprentissage). On crée une liste appelée
table
, initialement vide, puis on y ajoute, pour
chaque ligne du fichier csv, la distance et la couleur de
cette ligne.
from csv import * point_mystère = (330,225) table = [] with open('prairie.csv','r') as fichier: lignes = reader(fichier,delimiter=' ') for ligne in lignes: (x,y) = (int(ligne[0]),int(ligne[1])) couleur = ligne[2] table.append((distance(point_mystère,(x,y)),couleur))
On a obtenu une liste de couples (tuple
s à
2 éléments), et pour trier ces tuples il faut définir une
relation d'ordre : un algorithme permettant de savoir quel
est le plus petit de 2 tuples. Cette relation (« critère de
tri ») va s'appeler neighbours
et on ne va en
fait regarder que le premier élément du couple (la distance)
comme critère de tri (on ne trie pas selon les couleurs
mais selon les distances).
def neighbours(couple): return couple[0] table.sort(key=neighbours)
Comme la (nouvelle) table est maintenant triée par distances croissantes, pour appliquer l'algorithme des 3 plus proches voisins, on n'a plus qu'à en extraire les 3 premiers éléments, et ne lire que leur couleur :
print([table[k][1] for k in range(3)])
La réponse ['rouge', 'bleu', 'bleu']
montre
que la couleur bleue est majoritaire parmi les 3 plus
proches voisins : cela incite à attribuer cette couleur au
point mystère.