Méthode des 3 plus proches voisins

Position du problème

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.

Algorithme des 3 plus proches voisins

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 :

Algorithme

• Pour chaque point dont on connaît la couleur, calculer sa distance par rapport au point inconnu (vert pour l'instant).
• Trier les points par distances croissantes.
• Parmi les 3 voisins les plus proches (les trois plus petites distances), regarder quelle est la couleur majoritaire.
  • S'il y a plus de points rouges, décider que le point inconnu est rouge aussi.
  • S'il y a plus de points bleus, décider que le point inconnu est bleu.

Cet algorithme n'est pas fiable à 100%. Son coût est principalement celui du tri.

Programmation en Python

1) Distance

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])

2) Accès à la table

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))

3) Tri et conclusion

On a obtenu une liste de couples (tuples à 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.