Les cellules de Voronoï☘
On commence par une situation qui ne relève pas vraiment de l'algorithme k-NN, mais qui fait intervenir des notions qui nous seront utiles.
Qu'est-ce qu'une cellule de Voronoï?☘
Dans un plan, on dispose d'une série de points (en nombre fini).
Exemple:
Chaque point bleu est un abri. Vous vous baladez dans cette zone. Lorsqu'une alerte retentit, vous devez courir le plus vite possible dans un abri. Il faut donc repérer l'abri le plus proche.
Ce découpage en "zones de proximité" constitue les cellules de Voronoï.
On obtient ici la figure suivante:
Il est facile d'obtenir ces zones avec un petit nombre de points comme c'est le cas ici: tracez les médiatrices des couples de points bleus.
Rappel sur la médiatrice
La médiatrice d'un segment [AB] (ou d'un couple de points (A,B)) est la droite perpendiculaire au segment [AB] et passant par le milieu de ce segment [AB].
Ce qui rend intéressantes ces médiatrices dans notre contexte est la propriété suivante (que l'on apprend en classe de sixième):
La médiatrice du segment [AB] est constituée des points M du plan qui vérifient MA = MB (où MA et MB désignent la distance de M à A et la distance de M à B).
La médiatrice délimite le plan en deux demi-plans.
Le demi-plan qui contient A est constitué des points qui sont plus proches de A que de B,
et le demi-plan qui contient B est constitué des points qui sont plus proches de B que de A.
Lien avec kNN
On peut voir le problème comme un cas particulier de l'algorithme k-NN (avec k=1), chaque point bleu définissant sa propre classe. Etre dans la classe d'un point bleu, c'est être plus proche de ce point bleu que de n'importe quel autre point bleu.
Exercice 1☘
Générer au hasard une liste de points à coordonnées entières:
- abscisses comprises entre xmin et xmax,
- ordonnées comprises entre ymin et ymax
(où xmin, xmax, ymin, ymax sont des entiers, variables globales).
Le nombre de points de cette liste sera généré au hasard entre nbmin et nbmax (paramètres de la fonction). Vous utiliserez pour cela la fonction randint du module random.
from random import randint
xmin, xmax = -20, 20
ymin, ymax = -20, 20
def genereListePoints(nbmin, nbmax):
"""
nbmin -- entier
nbmax -- entier
précondition: nbmin < nbmax
Renvoie une liste de couples d'entiers,
le premier élément de chaque couple
est compris entre xmin et xmax (au sens large),
le second élément de chaque couple est
compris entre ymin et ymax (au sens large).
Les couples (x, y) sont générés au hasard.
Le nombre de couples est généré au hasard, entre nbmin et nbmax.
"""
Un code possible
from random import randint
xmin, xmax = -20, 20
ymin, ymax = -20, 20
def genereListePoints(nbmin, nbmax):
"""
nbmin -- entier
nbmax -- entier
précondition: nbmin < nbmax
Renvoie une liste de couples d'entiers, le premier élément du couple
est compris entre xmin et xmax (au sens large), le second élément entre
ymin et ymax (au sens large).
Les couples (x, y) sont générés au hasard.
Le nombre de couples est généré au hasard, entre nbmin et nbmax.
"""
assert nbmin < nbmax, "Attention, on doit avoir nbmin < nbmax"
nbPoints = randint(nbmin, nbmax)
return [(randint(xmin, xmax), randint(ymin, ymax)) for _ in range(nbPoints)]
Un appel:
genereListePoints(5, 15)
Exemple de résultat:
[(5, -2),
(10, 13),
(7, -4),
(18, 8),
(-16, -19),
(2, -19),
(-15, 15),
(-9, -1),
(19, 6),
(-20, 1)]
Exercice 2☘
Écrire une fonction prenant en paramètres 4 nombres x, y, a, b
et renvoyant la distance euclidienne entre les points M(x,y) et A(a,b).
Distance euclidienne
La distance euclidienne entre deux points M(x,y) et A(a,b) est la distance usuelle apprise au collège avec le théorème de Pythagore:
AM = \sqrt{(x_M-x_A)^2 + (y_M - y_A)^2\ }
Un code possible
from math import sqrt
def distance(x,y,a,b):
"""
Renvoie la distance euclidienne entre A(a,b) et M(x,y)
"""
dx, dy = x-a, y-b
return sqrt(dx**2 + dy**2)
Exemple d'appel (distance entre les points A(0,0) et B(1,1)):
distance(0,0,1,1)
Exercice 3☘
Écrire une fonction python prenant en paramètres:
- une liste de points telle que celle de l'exercice 1 ci-dessus.
- un nouveau point A de coordonnées entières (abscisse entre xmin et xmax et ordonnée entre ymin et ymax).
et renvoyant le point de la liste qui est le plus proche de A.
def plusProcheVoisin(listePoints, x, y):
"""
listePoints -- liste de points à coordonnées entières
x -- entier entre xmin et xmax
y -- entier entre ymin et ymax
Renvoie le point de la liste listePoints le plus proche de (x,y)
"""
Un code possible
from random import randint
from math import sqrt, inf
xmin, xmax = -20, 20
ymin, ymax = -20, 20
def genereListePoints(nbmin, nbmax):
"""
Renvoie une liste de couples d'entiers, le premier élément du couple
est compris entre xmin et xmax (au sens large),
le second élément entre
ymin et ymax (au sens large).
Les couples (x, y) sont générés au hasard.
Le nombre de couples est généré au hasard, entre nbmin et nbmax.
"""
nbPoints = randint(nbmin, nbmax)
return [(randint(xmin, xmax), randint(ymin, ymax)) for _ in range(nbPoints)]
def distance(x,y,a,b):
"""
Renvoie la distance euclidienne entre A(a,b) et M(x,y)
"""
dx, dy = x-a, y-b
return sqrt(dx**2 + dy**2)
def plusProcheVoisin(listePoints, x, y):
"""
listePoints -- liste de points à coordonnées entières
x -- entier entre xmin et xmax
y -- entier entre ymin et ymax
Renvoie le point de la liste listePoints le plus proche de (x,y)
"""
distance_min = inf # initialisation à +infini
for point in listePoints:
d = distance(x, y, point[0], point[1])
if d < distance_min:
distance_min = d
pointPlusProche = point
return pointPlusProche
Exemple d'appel:
L = genereListePoints(5, 15)
plusProcheVoisin(L, 0, 0) # point de la liste L le plus proche du point (0,0)
Exercice 4☘
Python propose une fonction prédéfinie (fonction "built-in") min.
On en montre ci-dessous une utilisation:
Une utilisation de min
On dispose d'une liste de couples d'entiers représentant des plages horaire:
L = [(20, 22), (14, 15), (2, 8), (1, 18), (17, 18), (20, 23), (7, 8)]
Le couple (20, 22) représente par exemple la plage horaire de 20h à 22h.
On aimerait obtenir dans cette liste L un couple dont l'heure de début est minimale:
>>> min(L, key = lambda x: x[0])
(1, 18)
On aimerait obtenir dans cette liste L un couple dont l'heure de fin est minimale:
>>> min(L, key = lambda x: x[1])
(2, 8)
On aimerait obtenir dans cette liste L un couple dont la longueur de plage (l'écart entre l'heure de fin et l'heure de début) est minimale:
>>> min(L, key = lambda x: x[1]-x[0])
(14, 15)
Utilisez cette fonction min pour une nouvelle version de la fonction plusProcheVoisin
de l'exercice précédent en utilisant le principe ci-dessous:
Principe
On dispose de la liste de points L et d'un point A.
On crée une liste qui contient les tuples (point, distance(point, A)) pour chaque point de L.
liste = [ (point, distance(point, A)) for point in L ]
Le code suivant:
min( liste, key= lambda x: x[1] )
Il reste ensuite à renvoyer la composante un du tuple réalisant le minimum (c'est à dire le couple des coordonnées du point).
Un code
Exemple de code:
from random import randint
from math import sqrt, inf
xmin, xmax = -20, 20
ymin, ymax = -20, 20
def genereListePoints(nbmin, nbmax):
"""
Renvoie une liste de couples d'entiers, le premier élément du couple
est compris entre xmin et xmax (au sens large),
le second élément entre
ymin et ymax (au sens large).
Les couples (x, y) sont générés au hasard.
Le nombre de couples est généré au hasard, entre nbmin et nbmax.
"""
nbPoints = randint(nbmin, nbmax)
return [(randint(xmin, xmax), randint(ymin, ymax)) for _ in range(nbPoints)]
def distance(x,y,a,b):
"""
Renvoie la distance euclidienne entre A(a,b) et M(x,y)
"""
dx, dy = x-a, y-b
return sqrt(dx**2 + dy**2)
def ppv(listePoints, x, y):
"""
listePoints -- liste de points à coordonnées entières
x -- entier entre xmin et xmax
y -- entier entre ymin et ymax
Renvoie le point de la liste listePoints le plus proche de (x,y)
"""
dist = [(point, distance(x, y, point[0], point[1])) for point in listePoints]
lePlusProche = min(dist, key= lambda x: x[1])
return lePlusProche[0]
Utilisation:
On dispose par exemple de la liste de points:
L = [(0, -18), (16, 2), (-3, -20), (17, 18), (-13, -1), (-5, 8), (-10, -13)]
>>> ppv(L, 0, 0)
(-5, 8)