Chapitre 14 : Algorithme des k plus proches voisins.

Introduction :

L'idée de l'algorithme des k plus proches voisins (k-NN) est simple : un élément ressemble souvent à ceux qui l'entourent.

Mais cela amène une question importante : est-ce que la proximité est toujours un bon indicateur ? Si les données sont très variées ou si certains voisins sont éloignés, peut-on toujours se fier à ce principe ?

1. Distance dans un repère à deux dimensions:

Dans un repère à deux dimensions, la distance $AB$ de deux points $A(x_A;y_A)$ et $B(x_B;y_B)$ est égale à :

$$ AB=\sqrt{(x_B-x_A)^2+(y_B-y_A)^2} $$

2. Exercice:

A faire dans le cahier.

Quelle est la distance qui sépare le point $C(3;8)$ et le point $D(5;4)$?

3. Exercice:

Programmer une fonction distance_2d(tuple1,tuple2) qui retourne un float correspondant à la distance entre les coordonnées de deux points stockées dans tuple1 et tuple2.

4. Exercice:

A faire dans le cahier.

On considère les points suivants :

points = {
    "A": (2, 3),
    "B": (5, 7),
    "C": (-1, 0),
    "D": (8, 2),
    "E": (0, -4),
    "F": (-3, 6)
}

On considère maintenant le point $M(4;4)$.

Quel est le point le plus proche de $M$ (en dehors de lui même)?
Quels sont les deux points les plus proches de $M$ (en dehors de lui même)?
Quels sont les trois points les plus proches de $M$ (en dehors de lui même)?
Quels sont les cinq points les plus proches de $M$ (en dehors de lui même)?

5. Exercice:

Refaire l'exercice précédent en automatisant la procédure grâce à Python.

On pourra, par exemple créer une liste composée de tuples de deux éléments : le premier élément est un string correspondant au nom du point, et le deuxième élément sera la distance entre ce point et le point $M$.

On pourra ensuite trier la liste en fonction du deuxième élément du tuple à l'aide de la commande :

liste.sort(key=lambda x : x[1])  #trie la variable liste en fonction du deuxième élément.

6. Distance dans un repère à n dimensions:

Dans un repère à $n$ dimensions, la distance $AB$ de deux points $A(a_1;a_2;...;a_n)$ et $B(b_1;b_2;....;b_n)$ est égale à :

$$ AB=\sqrt{(b_1-a_1)^2+(b_2-a_2)^2+...+(b_n-a_n)^2} $$

7. Exercice:

Programmer une fonction distance_3d(tuple1,tuple2) qui retourne un float correspondant à la distance entre les coordonnées de deux points stockées dans tuple1 et tuple2.

Bien entendu, chaque tuple contient 3 valeurs.

8. Exercice:

On considère les points suivants :

points_3d = {
    "A": (12, 13, 1),
    "B": (5, 17, 20),
    "C": (-1, 0, 4),
    "D": (8, 2, 6),
    "E": (4, 3, 1),
    "F": (-3, 6, -1)
}

On considère maintenant le point $M(4;4;2)$.

Quel est le point le plus proche de $M$ (en dehors de lui même)?
Quels sont les deux points les plus proches de $M$ (en dehors de lui même)?
Quels sont les trois points les plus proches de $M$ (en dehors de lui même)?
Quels sont les cinq points les plus proches de $M$ (en dehors de lui même)?

Vous pouvez le faire au choix : soit à la main, soit en le programmant.

9. L'Algorithme des k Plus Proches Voisins

L'algorithme des k plus proches voisins est une technique automatique simple et efficace utilisée pour la classification et la régression. Cet algorithme repose sur le principe que des données similaires ont tendance à avoir des résultats similaires.

L'algorithme des k plus proches voisins fonctionne comme suit :

Choisir une valeur de k, qui représente le nombre de voisins les plus proches à prendre en compte.
Calculer la distance (euclidienne, manhattan, etc.) entre le point à classer et tous les autres points dans l'ensemble de données.
Sélectionner les k points les plus proches en fonction de la distance calculée.
Pour une classification, attribuer la classe majoritaire parmi les k voisins à la nouvelle donnée. Pour une régression, calculer la moyenne (ou la médiane) des valeurs des k voisins.

10. Activité:

Vous travaillez dans un jardin botanique et vous avez collecté des données sur différentes espèces de fleurs.

Vous avez mesuré la longueur et la largeur des pétales de plusieurs fleurs et avez étiqueté chaque fleur avec son espèce correspondante : "Setosa", "Versicolor" ou "Virginica".

Vous voulez maintenant utiliser l'algorithme des k plus proches voisins pour classer de nouvelles fleurs en fonction de leurs mesures de pétales.

Voici les données que vous avez collectées, organisées dans une liste de listes :

donnees = [
    [1.4, 0.2, "Setosa"],
    [1.3, 0.2, "Setosa"],
    [4.7, 1.3, "Versicolor"],
    [4.6, 1.5, "Versicolor"],
    [4.6, 1.2, "Versicolor"],
    [4.8, 1.3, "Versicolor"],
    [5.9, 2.3, "Virginica"],
    [6.3, 2.5, "Virginica"],
    [5.8, 2.5, "Virginica"],
    [6.2, 2.6, "Virginica"],
    [5.1, 1.8, "Virginica"],
    [5.7, 2.8, "Virginica"],
    [1.2, 0.3, "Setosa"],
    [1.1, 0.4, "Setosa"],
    [1.4, 0.3, "Setosa"],
    [1.4, 0.2, "Setosa"],
    [5.5, 2.4, "Virginica"],
    [4.9, 2.0, "Versicolor"],
    [5.4, 2.3, "Virginica"],
    [6.2, 2.2, "Virginica"],
    [5.8, 1.9, "Virginica"],
    [4.8, 1.8, "Versicolor"],
    [4.5, 1.7, "Versicolor"],
    [5.2, 2.2, "Virginica"],
    [6.0, 1.8, "Virginica"],
    [6.4, 2.1, "Virginica"],
    [4.4, 1.3, "Versicolor"]
]

Ce qui correspond à :

Longueur du pétale	Largeur du pétale	Espèce
1.4	0.2	Setosa
1.3	0.2	Setosa
4.7	1.3	Versicolor
4.6	1.5	Versicolor
4.6	1.2	Versicolor
4.8	1.3	Versicolor
5.9	2.3	Virginica
6.3	2.5	Virginica
5.8	2.5	Virginica
6.2	2.6	Virginica
5.1	1.8	Virginica
5.7	2.8	Virginica
1.2	0.3	Setosa
1.1	0.4	Setosa
1.4	0.3	Setosa
1.4	0.2	Setosa
5.5	2.4	Virginica
4.9	2.0	Versicolor
5.4	2.3	Virginica
6.2	2.2	Virginica
5.8	1.9	Virginica
4.8	1.8	Versicolor
4.5	1.7	Versicolor
5.2	2.2	Virginica
6.0	1.8	Virginica
6.4	2.1	Virginica
4.4	1.3	Versicolor

Programmer une fonction liste_des_distances(donnees,longueur_petale,largeur_petale)qui retourne une liste de plusieurs tuples contenant chacun deux éléments :
- Il y a autant d'éléments que dans celle de donnees
- Pour chaque élément de données, notre liste retournée contiendra un tuple dont :
  - La première valeur est un string correspondant au nom de la plante.
  - La deuxième valeur est la distance entre les données de la plante et ce qui a été passé en paramètre. On pourra utiliser la fonction distance_2d programmée précédemment.
Trier les tuples dans cette liste en fonction de la deuxième valeur de chaque tuple. On pourra utiliser ce code:
```
liste.sort(key=lambda x : x[1])  #trie la variable liste en fonction du deuxième élément.
```
Afficher les 3 premiers éléments de cette liste.On parle donc ici des "3 plus proches voisins".

11. Activité:

Refaire l'exercice précédent en automatisant la procédure dans une grande fonction algo_des_k_plus_proches_fleurs(donnees,longueur_petale,largeur_petale,k) et qui retournera un string correspondant à la prévision de la catégorie de la fleur.

12. Activité : le prix du contrôle technique 🚙

Sur le site data.gouv.fr, le professeur a récupéré un fichier CSV contenant les prix des contrôles techniques automobiles.

Après un traitement, on a obtenu le prix des contrôles techniques des automobiles à essence, diesel et électrique.

Tout ceci a été mis dans un csv comportant 16 874 prix.

Le code ci-dessous permet d'importer le fichier csv et de mettre les données dans une liste de tuples.

import os
os.chdir("u:\\") # a modifier 
import csv

def import_depuis_csv(nom_fichier):
    liste = []
    with open(nom_fichier, 'r', encoding='utf-8', newline='') as fichier:
        reader = csv.reader(fichier)  
        for ligne in reader:
            a,b,c,d=ligne
            liste.append([float(a),float(b),str(c),int(float(d))])
    return liste


liste=import_depuis_csv("prix_par_coord_gps.csv")

Voici à quoi ressemble le début de la liste :

liste = [
    [48.081344084, 1.8636736312, 'Essence', 80] ,
    [48.081344084, 1.8636736312, 'Diesel', 80] ,
    [48.081344084, 1.8636736312, 'Electrique', 90] ,
    [44.939926375, 4.8600288586, 'Essence', 88] ,
    [44.939926375, 4.8600288586, 'Diesel', 88] ,
    [44.939926375, 4.8600288586, 'Electrique', 88] ,
    [44.803847824, 4.7878513582, 'Essence', 88] ,
    [44.803847824, 4.7878513582, 'Diesel', 88] ,
    [44.803847824, 4.7878513582, 'Electrique', 88] ,
    [45.493544863, 0.2732083176, 'Essence', 75] ,
    [45.493544863, 0.2732083176, 'Diesel', 75] ,
    [45.493544863, 0.2732083176, 'Electrique', 75] ,
    [44.917371745, 4.9336981199, 'Essence', 88] ,
    [44.917371745, 4.9336981199, 'Diesel', 88] ,
    [44.917371745, 4.9336981199, 'Electrique', 88] ,
    [44.962031877, 4.8834650356, 'Essence', 88] ,
    [44.962031877, 4.8834650356, 'Diesel', 88] ,
    [44.962031877, 4.8834650356, 'Electrique', 88] ,
    [43.603837202, 1.1009835826, 'Essence', 80] ,
    [43.603837202, 1.1009835826, 'Diesel', 80] ,
    [43.603837202, 1.1009835826, 'Electrique', 80] ,
    [46.185350817, 6.2748103237, 'Essence', 100] ,
    [46.185350817, 6.2748103237, 'Diesel', 100] ,
    [46.185350817, 6.2748103237, 'Electrique', 115] ,
    [45.996232976, 1.1501655149, 'Essence', 71] ,
    [45.996232976, 1.1501655149, 'Diesel', 71] ,
    [45.996232976, 1.1501655149, 'Electrique', 71] ,
    [48.773551118, 2.4892141723, 'Essence', 69] ,
    [48.773551118, 2.4892141723, 'Diesel', 79] ,
    [48.773551118, 2.4892141723, 'Electrique', 79] ,
    [46.980750529, -0.196806828, 'Essence', 78] ,
    [46.980750529, -0.196806828, 'Diesel', 78] ,
    [46.980750529, -0.196806828, 'Electrique', 78] ,
    [43.36190268, -0.579636841, 'Essence', 70] ,
    [43.36190268, -0.579636841, 'Diesel', 70] ,
    [43.36190268, -0.579636841, 'Electrique', 70] ,
    [46.007235521, 5.0367598707, 'Essence', 80] ,
    [46.007235521, 5.0367598707, 'Diesel', 80] ,
    [46.007235521, 5.0367598707, 'Electrique', 80] ,
    [46.222228767, 5.2276600825, 'Essence', 89] ,
    ...
    ...
    #encore 16834 lignes ainsi..

Il s'agit donc d'une liste de listes.

Chaque sous-liste est composée 4 éléments :

un nombre en flottant correspondant à la latitude;
un nombre en flottant correspondant à la longitude;
un string précisant la nature du moteur de la voiture;
un nombre entier correspondant au prix pratiqué à ces coordonnées géographiques pour ce type de moteur lors de la relevé d'informations.

Travail à faire :

Télécharger prix_par_coord_gps.csv
Le placer dans un dossier adéquat.
Dans un éditeur de code Python, copier/coller le premier code de l'activité.
Ecrire la fonction algo_des_k_plus_proches_prix(liste,latitude,longitude,type_moteur,k) avec
- liste qui est la liste issue du csv
- latitude qui est un flottant correspondant à la latitude à laquelle on veut connaitre le prix pratiqué aux alentours.
- longitude qui est un flottant correspondant à la longitude à laquelle on veut connaitre le prix pratiqué aux alentours.
- type_moteur qui est un string correspondant au type de moteur auquel on veut connaitre les prix pratiqués aux alentours.
- k qui est un nombre entier pour correspondant aux k plus proches voisins.
Cette fonction renverra le prix moyen pratiqué parmi les k plus proches centres de contrôle technique pour le moteur étudié.

Survolez la carte pour voir les coordonnées

Latitude : Longitude :