duranton.net

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 : Distance entre deux points

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

Rappel : la distance entre deux points (x1, y1) et (x2, y2) est donnée par la formule :

√((x2 - x1)² + (y2 - y1)²)

Exemples :

distance_2d((0,0),(3,4)) renvoie 5.0
distance_2d((1,1),(4,5)) renvoie 5.0
import math def distance_2d(tuple1, tuple2): """ Calcule la distance entre deux points 2D. tuple1, tuple2 : tuples de coordonnées (x, y) Retourne un float. """ x1, y1 = tuple1 x2, y2 = tuple2 distance = ... # appliquer la formule de la distance return ... point_A = (3, 6) point_B = (12, 8) print(f"La distance entre {point_A} et {point_B} est égale à {distance_2d(point_A, point_B)}.")

Tests :

# Tests.

Affichage :

Console:


    

      >>>
      
    

  









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

    
    
        
  1. Quel est le point le plus proche de \(M\) (en dehors de lui même)?
    2. 
        
  2. Quels sont les deux points les plus proches de \(M\) (en dehors de lui même)?
    3. 
        
  3. Quels sont les trois points les plus proches de \(M\) (en dehors de lui même)?
    4. 
        
  4. Quels sont les cinq points les plus proches de \(M\) (en dehors de lui même)?
    5. 
    













  
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.

  


  
  
import math

def distance_2d(tuple1, tuple2):
    ... # recopier la fonction d'un exercice précédent

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


M = (4, 4)

liste_tuples = []
for nom_du_point in points.keys() :
    d = ... # calcul de la distance avec M
    liste_tuples.append(...)    # on ajoute le tuple ("nom du point", distance_avec_M)

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

for nom_du_point, distance_avec_M in liste_tuples:
    print(f"{nom_du_point} est à une distance de {distance_avec_M} de M.")

print(liste_tuples)

  


  
  


  
Tests :

  
# Tests




  
Affichage :

  


  
Console:

  

    


    

      >>>
      
    

  










    
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 : Distance entre deux points en 3D


  

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


    
Exemples :

    
distance_3d((0,0,0),(1,2,2)) renvoie 3.0
distance_3d((1,1,1),(4,5,1)) renvoie 5.0

  


  
  
import math
    
    
def distance_3d(tuple1, tuple2):
    """
    Calcule la distance entre deux points 3D.
    tuple1, tuple2 : tuples de coordonnées (x, y, z)
    Retourne un float.
    """
    x1, y1, z1 = tuple1
    x2, y2, z2 = tuple2
    distance = ...  # appliquer la formule de la distance en 3D
    return ...

point_A = (2, 3, 5)
point_B = (6, 7, 9)
print(f"La distance entre {point_A} et {point_B} est égale à {distance_3d(point_A, point_B)}.")



  
  

  
Tests :

  
# Vérifie plusieurs cas : diagonale, même point, négatifs, grands écarts.


  
Affichage :

  


  
Console:

  

    

    

      >>>
      
    

  











  
8. Exercice : Points les plus proches en 3D


  

    
On cherche à automatiser la recherche des points les plus proches d’un point \( M(12, 3, 9) \) dans l’espace à partir d’un ensemble de points connus.

    
On dispose d’environ 30 points repérés par leur nom et leurs coordonnées 3D. Le but est d’afficher les points triés par distance croissante par rapport à \( M \).

    
Pour cela :

    
    
      
  • Recopier la fonction distance_3d de l’exercice précédent.
    • 
      
  • Créer une liste de tuples dont chaque élément contient le nom du point et la distance à \( M \).
    • 
      
  • Trier cette liste selon la distance à l’aide de la commande :
    • 
    

    
liste_tuples.sort(key=lambda x : x[1])  # trie selon la distance

    
On affichera ensuite le nom du point et sa distance à \( M \).


    
Liste des points (coordonnées 3D) :

    
points = {
    "A": (2, 4, 7),
    "B": (14, 2, 10),
    "C": (11, 6, 8),
    "D": (15, 5, 12),
    "E": (9, 3, 10),
    "F": (18, 4, 6),
    "G": (6, 7, 4),
    "H": (13, 1, 8),
    "I": (10, 5, 3),
    "J": (4, 2, 9),
    "K": (8, 8, 10),
    "L": (11, 2, 13),
    "M1": (12, 3, 9),
    "N": (16, 7, 11),
    "O": (7, 5, 8),
    "P": (20, 0, 15),
    "Q": (13, 6, 14),
    "R": (5, 1, 7),
    "S": (17, 3, 9),
    "T": (15, 3, 8),
    "U": (2, 10, 6),
    "V": (9, 9, 12),
    "W": (10, 0, 0),
    "X": (14, 9, 11),
    "Y": (6, 6, 10),
    "Z": (8, 3, 7),
    "AA": (12, 3, 9),
    "BB": (11, 4, 5),
    "CC": (15, 2, 11),
    "DD": (4, 5, 2)
}

  


  
  
import math

def distance_3d(tuple1, tuple2):
    ...  # recopier la fonction de l'exercice précédent


points = {
    "A": (2, 4, 7),
    "B": (14, 2, 10),
    "C": (11, 6, 8),
    "D": (15, 5, 12),
    "E": (9, 3, 10),
    "F": (18, 4, 6),
    "G": (6, 7, 4),
    "H": (13, 1, 8),
    "I": (10, 5, 3),
    "J": (4, 2, 9),
    "K": (8, 8, 10),
    "L": (11, 2, 13),
    "M1": (12, 3, 9),
    "N": (16, 7, 11),
    "O": (7, 5, 8),
    "P": (20, 0, 15),
    "Q": (13, 6, 14),
    "R": (5, 1, 7),
    "S": (17, 3, 9),
    "T": (15, 3, 8),
    "U": (2, 10, 6),
    "V": (9, 9, 12),
    "W": (10, 0, 0),
    "X": (14, 9, 11),
    "Y": (6, 6, 10),
    "Z": (8, 3, 7),
    "AA": (12, 3, 9),
    "BB": (11, 4, 5),
    "CC": (15, 2, 11),
    "DD": (4, 5, 2)
}

M = (12, 3, 9)

liste_tuples = []
for nom_du_point in points.keys():
    d = ...  # calculer la distance à M
    liste_tuples.append(...)  # ajouter (nom_du_point, distance)

liste_tuples.sort(key=lambda x: x[1])  # tri selon la distance

for nom_du_point, distance in liste_tuples:
    print(f"{nom_du_point} est à une distance de {distance} de M.")

print(liste_tuples)
  


  
  

  
Tests :

  
# Vérifie : tri, types, nombre de points et cohérence des distances.


  
Affichage :

  


  
Console:

  

    

    

      >>>
      
    

  









    
9. L'Algorithme des k Plus Proches Voisins

    
    
L'algorithme des k plus proches voisins ( K-Nearest Neighbors (KNN) )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 :


    
    
        
  1. Choisir une valeur de k, qui représente le nombre de voisins les plus proches à prendre en compte.
    2. 
        
  2. Calculer la distance (euclidienne, manhattan, etc.) entre le point à classer et tous les autres points dans l'ensemble de données.
    3. 
        
  3. Sélectionner les k points les plus proches en fonction de la distance calculée.
    4. 
        
  4. 
          
      
            
    • 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.
      • 
          
    
        
    5. 
    









  
10. Exercice : k plus proches voisins sur pétales


  

    
Vous travaillez dans un jardin botanique. On dispose d’un petit jeu de données où chaque élément est de la forme [longueur_pétale, largeur_pétale, espèce], avec l’espèce parmi "Setosa", "Versicolor", "Virginica".

    
Objectif : écrire une fonction liste_des_distances(donnees, longueur_petale, largeur_petale) qui renvoie une liste de tuples (espece, distance) pour toutes les fleurs, où distance est la distance euclidienne entre le point cible (longueur_petale, largeur_petale) et les mesures de la fleur. Puis trier cette liste par distance croissante et afficher les 3 plus proches voisins.

    
Données :

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

    
Indice : pour trier une liste de tuples par leur deuxième élément (la distance), utilisez :

    
liste.sort(key=lambda x : x[1])

  


  
  
import math


def distance_2d(tuple1, tuple2):
    ... # à recopier d'un exercice précédent

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

def liste_des_distances(donnees, longueur_petale, largeur_petale):
    """
    Retourne une liste de tuples (espece, distance) pour chaque élément de donnees,
    où distance est la distance euclidienne entre (longueur_petale, largeur_petale)
    et (longueur_i, largeur_i) de la ligne.
    """
    cible = (longueur_petale, largeur_petale)
    resultat = []
    for longueur_i, largeur_i, espece in donnees:
        d = ...  # calculer la distance entre (longueur_i, largeur_i) et cible
        resultat.append((..., d))  # (espece, distance)
    return resultat

# --- Démonstration : tri et affichage des k plus proches voisins pour une cible choisie ---
longueur_cible = ...   # ex : 4.7
largeur_cible  = ...   # ex : 1.3
k = ...     # nombre de voisins

liste_tuples = liste_des_distances(donnees, longueur_cible, largeur_cible)
liste_tuples.sort(key=lambda x: x[1])

# Afficher les k plus proches voisins :
for nom_espece, dist in liste_tuples[:k]:
    print(f"{nom_espece} à distance {dist}")


  
  

  
Tests :

  


  
Affichage :

  


  
Console:

  

    

    

      >>>
      
    

  















  
11. Exercice : KNN étape par étape


  

    
On veut prédire l’espèce d’une fleur à partir de la longueur et la largeur de son pétale, en utilisant l’algorithme des k plus proches voisins (KNN). Pour faciliter, on découpe en petites fonctions.


    
    
      
  • 1) distance_2d(p1, p2) — calcule la distance euclidienne entre deux points 2D.
    
        Attendu : renvoyer un float avec la formule √((x2-x1)^2 + (y2-y1)^2).
    
        Exemples :
        
    distance_2d((0,0),(3,4)) == 5.0
distance_2d((1,2),(1,2)) == 0.0
    
      
    • 

      
  • 2) construire_liste_distances(donnees, L, l) — fabrique la liste des distances à une fleur cible (L,l).
    
        Attendu : renvoyer une liste de tuples (espece, distance) de même longueur que donnees.
    
        Exemple :
        
    construire_liste_distances([[1.4,0.2,"Setosa"],[4.7,1.3,"Versicolor"]], 1.4, 0.2)
→ [("Setosa", 0.0), ("Versicolor", 3.4785054261852175)]
    
      
    • 

      
  • 3) trier_par_distance(liste_tuples) — trie une liste de (espece, distance) par distance croissante.
    
        Attendu : renvoyer une nouvelle liste (ne pas modifier l’originale).
    
        Exemple :
        
    trier_par_distance([("A",3.0),("B",1.0),("C",2.0)])
→ [("B",1.0),("C",2.0),("A",3.0)]
    
      
    • 

      
  • 4) k_premiers(liste_tries, k) — prend les k plus proches.
    
        Attendu : renvoyer les k premiers éléments de la liste déjà triée.
    
        Exemple :
        
    k_premiers([("X",1.0),("Y",2.0),("Z",3.0)], 2)
→ [("X",1.0),("Y",2.0)]
    
      
    • 

      
  • 5) vote_majoritaire(tuples_etiquettes) — choisit l’espèce la plus fréquente.
    
        Attendu : renvoyer l’espèce (str) la plus présente ; en cas d’égalité, choisir l’espèce du plus proche (le premier de la liste).
    
        Exemples :
        
    vote_majoritaire([("Setosa",0.1),("Virginica",0.2),("Setosa",0.3)]) → "Setosa"
vote_majoritaire([("Versicolor",0.05),("Setosa",0.05)]) → "Versicolor"  # égalité → premier
    
      
    • 

      
  • 6) algo_knn(donnees, L, l, k) — orchestre le tout et renvoie l’espèce prédite.
    
        Étapes internes : construire les distances → trier → prendre les k premiers → voter.
    
        Exemples :
        
    algo_knn(donnees, 1.4, 0.2, 3) → "Setosa"
algo_knn(donnees, 4.7, 1.3, 3) → "Versicolor"
    
      
    • 
    


    
Données : chaque ligne est [longueur_pétale, largeur_pétale, espèce].

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

  


  
  
import math

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



# question 1
def distance_2d(tuple1, tuple2):
    ... # copier/coller à partir d'un exercice précédent 




# question 2
def construire_liste_distances(donnees, L, l):
    """Retourne [(espece, distance_avec(L,l))] pour chaque ligne de donnees."""
    cible = (L, l)
    resultat = []
    for longueur_i, largeur_i, espece in donnees:
        d = ...  
        resultat.append((..., d))  # (espece, distance)
    return resultat


#question 3
def trier_par_distance(liste_tuples):
    """Retourne une NOUVELLE liste triée par distance croissante, sans modifier l'originale."""
    liste_copie = liste_tuples[:]  # copie
    ...  # trier liste_copie avec sort(key=lambda t: t[1])
    return liste_copie


#question 4
def k_premiers(liste_tries, k):
    """Retourne les k premiers tuples de la liste triée."""
    return ...




#question 5
def vote_majoritaire(tuples_etiquettes):
    """tuples_etiquettes est une liste [(espece, distance), ...] triée par distance.
    Retourne l'espèce la plus fréquente; en cas d'égalité, on choisit l'espèce du plus proche (indice 0)."""
    compteur = {}
    for espece, dist in tuples_etiquettes:
        if espece in compteur.keys():
            compteur[espece] += ...
        else:
            compteur[espece] = ...
    max_occ = max(compteur.values())
    candidates = [e for e, n in compteur.items() if n == max_occ]
    if len(candidates) == 1:
        return candidates[0]
    # égalité : choisir l'espèce du plus proche (déjà premier de la liste triée)
    return ...



#question 6
def algo_knn(donnees, L, l, k):
    """Chaîne de traitement complète KNN (retourne l'espèce prédite)."""
    distances = construire_liste_distances(donnees, L, l)
    tri = trier_par_distance(distances)
    voisins = k_premiers(tri, k)
    return vote_majoritaire(voisins)

# Démo libre :
longueur = 4.7
largeur = 3
k = 3
print(f"Il est probable qu'une feuille de longueur {longueur} cm et de largeur {largeur} cm soit une {algo_knn(donnees, longueur, largeur, k)}.")


  
  

  
Tests :

  


  
Affichage :

  


  
Console:

  

    

    

      >>>
      
    

  














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

# Vérification
print(liste[:3])  # affiche les 3 premières lignes


        
On peut aussi utiliser le code suivant pour télécharger directement le fichier dans votre script Python :

            
import urllib.request
import csv

url = "https://www.duranton.net/static/premiere_nsi/algokplusproches/prix_par_coord_gps.csv"

# Télécharger le contenu du fichier CSV
with urllib.request.urlopen(url) as response:
    lignes = response.read().decode("utf-8").splitlines()

# Transformer en liste de listes
lecteur = csv.reader(lignes)
liste = [[float(a),float(b),str(c),int(float(d))] for a,b,c,d in lecteur]

# Vérification
print(liste[:3])  # affiche les 3 premières lignes


        
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 : 

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


    
Travail à faire :

    
    
        
  1. Télécharger prix_par_coord_gps.csv
    2. 
        
  2. Le placer dans un dossier adéquat.
    3. 
        
  3. Dans un éditeur de code Python, copier/coller le premier code de l'activité.
    4. 
        
  4. 
            
    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é.
    
        
    5. 
    



    
    
    
    
    
    
    

    
Survolez la carte pour voir les coordonnées



    
    

    
    
    
    
    
    

    
    
    
    
    
    
    
    







  
13. Exercice :


  

    
     Vous pouvez sauvegarder votre code Python pour le script des carburants de l'exercice précédent ci-dessous.
  


  
  


  
  


  
Tests :

  
# Tests




  
Affichage :

  


  
Console:

  

    


    

      >>>