Lycée Blaise Pascal - Rouen
CHAPITRE
30
Algorithme des k plus proches
voisins
Il faut éviter que les biais de la société ne se reflètent dans les décisions prises par
les machines.
Yann Le Cun 1
Contenus Capacités attendues
Écrire un algorithme qui prédit la classe d’un élé- Il s’agit d’un exemple d’algorithme d’apprentissage.
ment en fonction de la classe majoritaire de ses k plus
proches voisins.
I. Un peu d’histoire
Les algorithmes d’apprentissage sont utilisés dans le domaine de l’intelligence artificielle. Par
exemple, des algorithmes permettent d’émettre une prévision sur une caractéristique d’un élé-
ment, en fonction de l’étude de ses k plus proches voisins.
Introduction de la méthode des k plus proches voisins (Evelyn Fix et Joseph Lawson
1951
Hodges - US Air Force - Université de Californie Berkeley)
1952 Arthur Samuel écrit un programme capable de s’améliorer en jouant aux dames
1959 Arthur Samuel utilise le terme de machine learning
Comme son nom l’indique, cet algorithme permet de classifier une donnée dans une catégorie ou
une autre, à partir de l’étude de ses K plus proches voisins.
On peut déduire de cet exemple, que le rond central appartient à la classe des points rouges
1. Site personnel : http://yann.lecun.com/
II. Notion de distance
II. 1. Au sens mathématique
v Activité 1
1. Dans un repère orthonormal du plan, rappelez la formule permettant de calculer la
distance entre deux points A(xA ; yA ) et B(xB ; yB ).
2. Placez les points A(2; 2), B(3; −1), C(−1; −1), D(1; 1) et E(−1; −2) sur le repère
suivant :
y
4
0
-2 -1 0 1 2 3 4 x
-1
-2
3. Calculez les distances suivantes :
AB = AC = AD = AE =
4. Parmi les points B, C, D et E, de quel point, A est-il le plus proche ?
5. Écrivez une fonction Python renvoyant la distance entre deux points A et B (rappel :
le calcul de la racine carré se fait par la fonction sqrt() du module math).
1 import maths
2
3 def distance(..............................) :
4 """fonction renvoyant la distance entre deux points
5 Entrées :
6
7
8 Sortie :
9 d : un réel, la distance entre les deux points
10 """
11 ........................................................................
12 ........................................................................
13 ........................................................................
14 ........................................................................
15 ........................................................................
16 ........................................................................
17 ........................................................................
18 ........................................................................
19
20 return d
v Correction
q
1. d = (yB − yA )2 + (xB − xA )2
2.
2 Algorithme des k plus proches voisins NSI
y
4
2 A
1 D
0
-2 -1 0 1 2 3 4 x
C -1 B
E -2
√ √
3. AB = √32 + 12 = √10 = 3, 16
AC = √32 + 32 = √18 = 4, 24
AD = √ 12 + 12 = √ 2 = 1, 41
AE = 42 + 32 = 25 = 5
4. D est le point le plus proche de A.
5. 1 import maths
2
3 def distance(coord_A, door_B) :
4 """fonction renvoyant la distance entre deux points
5 Entrées :
6 coord_A : tuple
7 Les coordonnées du point A
8 coord_B : tuple
9 Les coordonnées du point B
10
11 Sortie :
12 d : un réel, la distance entre les deux points
13 """
14 d = maths.sqrt((coord_B[1] - coord_A[1]) ** 2 + (coord_B[0] - coord_A[0]) **
,→ 2 )
15 return d
II. 2. Un exemple : le choix d’un magasin d’alimentation
v Activité 2
Cas simple : un seul critère de choix
Pour un consommateur, on peut imaginer que le premier critère de choix est la proximité
qu’il a avec un magasin d’alimentation : il choisira le magasin le plus proche.
On considère que :
▷ Le consommateur C est situé sur les coordonnées (0; 0),
▷ Le magasin A est situé sur les coordonnées (−1; 4),
▷ Le magasin B est situé sur les coordonnées (2; −2).
Quel magasin choisira le consommateur ?
NSI Algorithme des k plus proches voisins 3
v Correction
√ √
CA = √12 + 42 = √17 = 4, 12
CB = 22 + 22 = 8 = 2, 83
Le consommateur C ira vers le magasin B car il est plus proche.
v Activité 3
Cas un peu moins simple : deux critères de choix
Pour un consommateur, on peut imaginer que le premier critère de choix est la proximité
qu’il a avec un magasin d’alimentation, et que le deuxième critère concerne la proportion
de produits labellisés bio qu’il vend.
On considère que :
▷ Le consommateur C est situé sur les coordonnées(0; 0) et souhaite acheter 25 % de
produits bio,
▷ Le magasin A est situé sur les coordonnées (−1; 4) et vend 35 % de produits bio,
▷ Le magasin B est situé sur les coordonnées (2; −2) et vend 20 % de produits bio.
1. Positionnez le consommateur C et les magasins A et B sur le graphique ci-dessous :
50
40
% produits Bio
30
20
10
00 0 1 2 3 4 5
Éloignement par rapport à C
2. Comment pourrait-on calculer la « distance » sur le critère produits Bio, entre le
consommateur et chacun des magasins ?
3. Complétez le tableau suivant :
Par rapport à C Magasin A Magasin B
Distance sur le critère kilométrique
Distance sur le critère kilométrique produits Bio
4. Comment pourrait-on calculer calculer une distance qui tienne compte de l’en-
semble des deux critères ?
5. Quel magasin choisira le consommateur ?
4 Algorithme des k plus proches voisins NSI
v Correction
1.
50
40
% produits Bio
A
30
C
20 B
10
00 0 1 2 3 4 5
Éloignement par rapport à C
2. La distance peut se calculer par la relation pourcentage souhaité par C - pourcentage
de produits bio vendu.
3.
Par rapport à C Magasin A Magasin B
Distance sur le critère kilométrique 4,12 2,83
Distance sur le critère produits Bio - 0,10 + 0,05
4. On réalise la somme des deux distances.
5. dCA = 4, 12 − 0, 10 = 4, 02
dCB = 2, 83 + 0, 05 = 2, 88
Le consommateur choisira le magasin B.
III. Notion de voisin
On considère une collection d’objets définis par trois caractéristiques, que l’on nommera caracteristique_1,
caracteristique_2 dont les valeurs sont comprises entre 0 et 1, et classe dont la valeur est
soit carré, soit rond. Les objets sont les suivants :
(0.2, 0.3, carre) ; (0.1, 0.5, carre) ; (0.3, 0.6, carre) ; (0.2, 0.5, carre) ; (0.4, 0.1, carre)
(0.6, 0.4, rond) ; (0.8, 0.2, rond) ; (0.9, 0.5, rond) ; (0.7, 0.3, rond) ; (0.9, 0.8, rond)
Les deux premières caractéristiques d’un objet A sont (0.5, 0.5). On souhaite savoir quel est sa
classe : carré ou rond.
v Activité 4
1. Placez sur le repère ci-dessous, les 10 éléments de la collection, ainsi que le point
A.
NSI Algorithme des k plus proches voisins 5
0.10
0.9
0.8
0.7
caractéristique 2
0.6
0.5
0.4
0.3
0.2
0.1
0.00.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.10
cacartéristique 1
2. Déterminez la distance entre chaque objet de la collection et le point A. Complétez
la quatrième colonne du tableau ci-dessous :
Caractéristique 1 Caractéristique 2 Classe Distance à A Classement
0.2 0.3 carre
0.1 0.5 carre
0.3 0.6 carre
0.2 0.5 carre
0.4 0.1 carre
0.6 0.4 rond
0.8 0.2 rond
0.9 0.5 rond
0.7 0.3 rond
0.9 0.8 rond
6 Algorithme des k plus proches voisins NSI
3. Numérotez chacun des objets de la collection en fonction de son éloignement au
point A. Complétez la dernière colonne du tableau ci-dessus.
4. Si on considère que la classe du point A est la même que celui de l’objet le plus
proche, quel est la classe de A ?
5. Si on considère que la classe du point A est la même que la classe majoritaire des
3 objets les plus proches, quel est la classe de A ?
6. Même question si on considère les 5 puis les 7 objets les plus proches.
v Correction
1.
0.10
0.9
0.8
0.7
caractéristique 2
0.6
0.5 A
0.4
0.3
0.2
0.1
0.00.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.10
cacartéristique 1
2.
Caractéristique 1 Caractéristique 2 Classe Distance à A Classement
0.2 0.3 carre 0,36
0.1 0.5 carre 0,40
0.3 0.6 carre 0,22
0.2 0.5 carre 0,2
0.4 0.1 carre 0,41
NSI Algorithme des k plus proches voisins 7
0.6 0.4 rond 0,14
0.8 0.2 rond 0,42
0.9 0.5 rond 0,40
0.7 0.3 rond 0,28
0.9 0.8 rond 0,50
3.
Caractéristique 1 Caractéristique 2 Classe Distance à A Classement
0.2 0.3 carre 0,36 5
0.1 0.5 carre 0,40 6-7
0.3 0.6 carre 0,22 3
0.2 0.5 carre 0,2 2
0.4 0.1 carre 0,41 8
0.6 0.4 rond 0,14 1
0.8 0.2 rond 0,42 9
0.9 0.5 rond 0,40 6-7
0.7 0.3 rond 0,28 4
0.9 0.8 rond 0,50 10
4. Si on considère que la classe du point A est le même que celui de l’objet le plus
proche, A est un rond.
5. Si on considère que la classe du point A est le même que la classe majoritaire des 3
objets les plus proches, A est un carré.
6. Si on considère les 5 les plus proches, A est un carré.
Si on considère les 7 les plus proches, A est un carré.
IV. L’algorithme des k plus proches voisins
Il existe de multiples façons d’écrire l’algorithme des k plus proches voisins. Cependant, un
canevas général pourrait être celui-ci :
Les entrées sont :
▷ une collection d’objets (n caractéristiques et une classe)
▷ un objet (n caractéristiques)
1. Calculer la distance entre chaque élément de la collection et l’objet A et l’associer à la
classe de l’élément pour former une nouvelle collection ;
8 Algorithme des k plus proches voisins NSI
2. trier cette nouvelle collection par distance croissante ;
3. pour les k premiers éléments de cette nouvelle collection, compter le nombre d’éléments de
chaque classe ;
4. associer la classe de A au maximum du nombre d’éléments comptés.
Algorithme : k plus proches voisins
/* Algorithme de classification */
Entrées :
collection : une collection d’objets identifiés par n caractéristiques et une classe
A : un objet possédant n caractéristiques, dont on cherche la classe
k : le nombre de voisins que l’on prend en compte (un entier)
Sorties :
genre : la classe de A
1 début
/* Calcul de chaque distance */
2 pour chaque objet de collection faire
3 calculer la distance selon les n caractéristiques entre A et objet
4 stocker le couple (distance ; classe) (liste de dictionnaire par exemple)
5 fin pour
/* Tri de la liste */
6 Trier cette liste par ordre croissant de la clé distance
/* Calcul de nombre d’éléments de chaque classe */
7 Initialiser nombre_classe_1, nombre_classe_2, nombre_classe_3, . . . à 0
8 pour i allant de 0 à k faire
9 si ie valeur = classe1 alors
10 augmenter nombre_classe_1 de 1
11 sinon si ie valeur = classe2 alors
12 augmenter nombre_classe_2 de 1
13 sinon si ie valeur = classe3 alors
14 augmenter nombre_classe_3 de 1
15 sinon si . . . alors
16 ...
17 fin si
18 fin pour
/* Associer la classe */
19 genre ← maximum entre nombre_classe_1, nombre_classe_2, nombre_classe_3, . . .
20 renvoyer genre
21 fin
V. Références bibliographiques
▷ Numérique et Sciences Informatiques, Serge Blays, ellipses, 2019, p. 316
▷ Numérique et Sciences Informatiques, Cécile Canus, ellipses, 2019, p. 159
NSI Algorithme des k plus proches voisins 9
