from math import sqrt
def distance_euclidienne(a, b):
"""
a -- tuple, les composantes sont des nombres
b -- tuple, même longueur que a, les composantes sont des nombres
renvoie la distance euclidienne entre a et b.
"""
assert len(a) == len(b), "Attention, a et b doivent être de même longueur."
somme_des_carrés = sum([(a[i]-b[i])**2 for i in range(len(a))])
return sqrt(somme_des_carrés)
def distance_Manhattan(a, b):
"""
a -- tuple, les composantes sont des nombres
b -- tuple, même longueur que a, les composantes sont des nombres
renvoie la distance Manhattan entre a et b.
"""
assert len(a) == len(b), "Attention, a et b doivent être de même longueur."
somme = sum([abs(a[i]-b[i]) for i in range(len(a))])
return somme
def distances_et_indices(liste_tuples, a, distance):
"""
liste_tuples -- liste de tuples, les composantes sont des nombres
a -- tuple de même longueur et composantes de même nature que ceux de la liste
distance -- fonction calculant la distance entre deux tuples
renvoie la liste
[(distance(a, liste_tuples[0]),0) , (distance(a, liste_tuples[1]), 1), ...]
"""
# la liste des distances
L = [distance(a, element) for element in liste_tuples]
# la liste des couples (distance, indice):
M = [(L[i], i) for i in range(len(L))]
return M
def kppv(liste_tuples, a, distance, k):
"""
liste_tuples -- liste de tuples, les composantes sont des nombres
a -- tuple de même longueur et composantes de même nature que ceux de la liste
distance -- fonction calculant la distance entre deux tuples
k -- entier entre 1 et len(liste_tuple)
renvoie la liste des k plus proches voisins de a, les voisins étant pris dans
liste_tuple.
"""
# on calcule la liste des distances en ajoutant l'info "indice":
les_distances = distances_et_indices(liste_tuples, a, distance)
# on trie le résultat suivant l'ordre croissant des distances:
les_distances.sort(key = lambda x: x[0])
# on ne garde que les k premiers:
les_distances = [ les_distances[j] for j in range(k)]
# on crée la liste des indices associés:
indices = [ dist[1] for dist in les_distances]
# on renvoie la liste des tuples correspondant:
return [ liste_tuples[j] for j in indices]
points = [(12, 1, 3), (0,0,0), (1,2,3), (3,1,1), (5,8,9)]
kppv(points, (0,1,0), distance_Manhattan, 3)