C22.1 : Première approche

Présentation du problème

Pouvez-vous dire quelle est la couleur du point blanc ?

Les algorithmes des k plus proches voisins (k nearest neighbors)

Une façon de résoudre le problème posé consiste à :

• - choisir un nombre entier k,
• - faire la liste des k plus proches voisins du point inconnu,
• - compter le nombre de rouge et de bleu parmi ces voisins,
• - attribuer la couleur en fonction du plus grand résultat trouvé.

Vocabulaire

Travail à faire

On donne ci-dessous un implémentation des données connues (coordonnées x et y, et couleurs de 20 points).

datas = [[-1, -0.2, 'r'],
         [-0.7, 0.2, 'r'],
         [-0.6, 0.4, 'r'],
         [-0.5, -1, 'r'],
         [-0.2, 1, 'r'],
         [0.2, 1.2, 'r'],
         [0.4, 0.8, 'r'],
         [-0.45, 1.15, 'r'],
         [0.8, 0.1, 'r'],
         [1.25, 0, 'r'],
         [-0.05, 0.5, 'b'],
         [0, 0.2, 'b'],
         [0.15, -0.05, 'b'],
         [0.6, -0.75, 'b'],
         [1, -0.5, 'b'],
         [1.3, -0.4, 'b'],
         [1.6, -0.3, 'b'],
         [1.7, 0.3, 'b'],
         [1.6, 0.55, 'b'],
         [1.9, 0.7, 'b']]

1) Écrire une fonction distance(xa, ya, xb, yb) qui prend les coordonnées de deux points en paramètres et renvoie la distance entre ces deux point.

2) Proposer un programme qui permet de déterminer la couleur du point blanc de coordonnées (0,0) suivant la méthode des knn, en prenant k = 3 voisins.

3) Améliorer le programme de façon à ce que l'utilisateur puisse saisir :

• - les coordonnées du point dont on souhaite déterminer la couleur,
• - le nombre de voisins sur lequel s'appuyer.