Liste des k plus proches voisins☘
Distance entre n-uplets☘
On dispose de tuples, a et b, de même longueur n. Les éléments composant ces tuples sont des nombres.
On peut définir plusieurs distances entre a = (a_1, a_2, ..., a_n) et b = (b_1, b_2, ..., b_n).
La distance euclidienne☘
On généralise la distance euclidienne comme suit:
distance(a, b) = racine carrée de la somme des carrés des différences des composantes, soit
distance(a, b) = \sqrt{(a_1 -b_1)^2 + (a_2 -b_2)^2 + ... + (a_n -b_n)^2}.
Exercice☘
Écrire une fonction python prenant en paramètres deux tuples de même longueur et renvoyant en sortie la distance euclidienne entre ces deux tuples.
Fonction sum
On a vu cette année à plusieurs reprises comment calculer la somme des éléments d'une liste, d'un tuple.
Comme les programmes commencent à être plus complexes ici, on se permettra de ne pas réécrire le détail
des programmes déterminant une telle somme.
Pour cela, on utlisera la fonction sum de python.
Exemple:
>>> sum([3,4,1])
8
>>> sum((3,4,1))
8
Un code possible
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)
Une utilisation:
>>> distance_euclidienne((0,0,0), (1,1,1))
1.7320508075688772
>>> distance_euclidienne((0,4), (3,0))
5.0
La distance de Manhattan☘
On peut également définir d'autres distances.
On peut par exemple utiliser la distance de Manhattan,
c'est à dire la somme des valeurs absolues des écarts entre composantes de même rang:
distance(a, b) = |a_1 -b_1| + |a_2 -b_2| + ... + |a_n -b_n|.
Exercice☘
Écrire une fonction python prenant en paramètres deux tuples de même longueur et renvoyant en sortie la distance Manhattan entre ces deux tuples.
Note
En python, la fonction valeur absolue est la fonction abs.
Un code possible
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."
return sum(abs(a[i]-b[i]) for i in range(len(a)))
# exemple: distance entre (0,0) et (3,4) = (3-0)+(4-0) = 7
assert distance_Manhattan((0,0), (3,4)) == 7
# exemple: distance entre (3,5) et (1,2) = (3-1)+(5-2) = 5
assert distance_Manhattan((3,5), (1,2)) == 5
Liste des distances à un tuple.☘
On dispose d'une liste de tuples de même longueur.
Par exemple:
L = [(0,0,0), (1,2,3), (4,5,6), (1,1,1), (2,8,3), (1,1,1), (3,7,4), (7,8,9)]
On veut déterminer la liste des distances liste_distances entre un autre tuple a et chacun des tuples de la liste.
On aura ainsi liste_distances[0] = distance(a, L[0]), liste_distances[1] = distance(a, L[1])...
Écrire une fonction python prenant en paramètres:
- une liste L de tuples (de même longueur),
- un autre tuple (même longueur que ceux de la liste)
- et une fonction distance
et qui renvoie la liste des distances entre ce nouveau tuple et ceux de la liste.
Les k plus proches voisins☘
On dispose d'une liste de tuples de même longueur.
Par exemple:
L = [(0,0,0), (1,2,3), (4,5,6), (1,1,1), (2,8,3), (1,1,1), (3,7,4), (7,8,9)]
On dispose par ailleurs d'un autre tuple a de même longueur que les tuples de la liste et
on aimerait déterminer la liste des k plus proches voisins de a dans la liste (où k est compris
entre 1 et la longueur de la liste).
Première proposition☘
Disposant de la liste des distances:
[distance(a, element) for element in liste_tuples]
Hugo décide de la trier en ordre croissant.
Après un tri en ordre croissant, les k premiers éléments de la liste des distances correspondront aux k plus proches voisins. Pourquoi cette proposition ne convient pas tout à fait?
Réponse
Avant le tri, on a une correspondance entre les distances et les tuples de la liste initiale:
l'élément d'indice i de la liste des distances est la distance entre le tuple a et l'élément
d'indice i de la liste de tuples.
Le tri sur la liste des distances nous fait perdre cette correspondance. On connaîtra les k plus courtes distances mais pas les voisins qui réalisent ces distances.
Rectification de l'idée☘
Pour résoudre le problème soulevé dans la question précédente, on modifie la liste des distances en ajoutant l'indice
de l'élément de la façon suivante:
Si la liste des distances est [4, 1, 7, 2, 3], on la modifie en [(4, 0), (1, 1), (7, 2), (2, 3), (3, 4)].
Un tri sur la distance donnera [(1, 1), (2, 3), (4, 0), (3, 4), (7, 2)].
On sait ainsi que les deux plus proches voisins correspondent à l'élément d'indice 1 et à l'élément d'indice 3
dans la liste de tuples initiale.
Écrire une fonction distances_et_indices qui prend en paramètres:
- une liste L de tuples (de même longueur),
- un autre tuple (même longueur que ceux de la liste)
- et une fonction distance
et renverra la liste des couples (distance, indice) telle que nous venons de la présenter.
Les k plus proches voisins☘
En déduire une fonction qui prend en entrée
- une liste de tuples L,
- un nouveau tuple
a, - une fonction distance,
- un entier k (k compris entre 1 et longueur(L))
et renvoie une liste de longueur k qui contient la liste des k tuples de L les plus proches de a.