Chap3 KNN

MÉTHODE K-NN
(K-NEAREST NEIGHBORS
K-PLUS PROCHES VOISINS)
Azzeddine Mazroui
Master d’Ingénierie Informatique
2022-2023
Introduction
■ La classification se déroule en quatre étapes :
– Etape 1 : Construction du modèle
– Etape 2 : Validation du modèle
– Etape 3 : Test du modèle
– Etape 4 : Application du modèle
■ La classification supervisée consiste à construire le modèle à partir

d’un échantillon fini d’objets étiquetés (c.à.d. classés).
■ Elle définit donc une fonction capable de classer (étiqueter) au mieux

de nouveaux objets (ne faisant pas partie de l’échantillon initial).
Cours Data Mining 2022-2023 A. Mazroui 2
Introduction
■ L’algorithme des k plus proches voisins (k-NN) est l’un des
algorithmes les plus simples de la classification supervisée.
■ L’algorithme k-NN permet d’obtenir de bons résultats de
classification lorsqu’une base d’apprentissage correctement étiquetée
(un échantillon fini d’objets classés) est disponible.

Définition
■ L’algorithme k-NN est une méthode de raisonnement à partir de cas :

il s’agit de prendre des décisions en recherchant un ou des cas
similaires dans l’ensemble d’apprentissage :
“Dis moi qui sont tes amis, et je te dirais qui tu es”.
■ Le principe de l’algorithme k-NN est basé sur le choix de la classe à

partir des classes des voisins les plus proches.

Algorithme
L’exécution de l’algorithme k-NN nécessite la connaissance de :
– Un ensemble de classes prédéfinies.
– Un échantillon de m exemples dont les classes sont connues
(c’est l’ensemble d’apprentissage) :
o Chacun de ces exemples est présenté sous forme d’un
vecteur de dimension n.
o Chacun de ces exemples est accompagné de sa classe
d’appartenance.
– Un paramètre k désignant le nombre de voisins.
– Une fonction distance permettant de mesurer la distance entre
les exemples.

Algorithme
C2
C1
C3
■ Si on choisit k=3, alors les 3 plus proches voisins du point en gris

sont deux points de la classe C3 et un point de la classe C2.
■ Par suite, ce point sera considéré selon le vote majoritaire comme

étant un point de la classe C3.
Algorithme : Distance
■ Le choix de la distance est primordial au bon fonctionnement de la

méthode.
■ Une distance doit vérifier les propriétés suivantes :
– d(A,A)=0
– d(A,B)= d(B,A)
– d(A,B) ≤ d(A,C) + d(B,C)

Algorithme : Distance
■ Les distances les plus utilisées dans l’espace ℝ𝑛 pour deux vecteurs
𝐴 = 𝑎𝑖 1≤𝑖≤𝑛 et 𝐵 = 𝑏𝑖 1≤𝑖≤𝑛 sont :
𝑛
Distance de Manhattan : 𝑑1 𝐴, 𝐵 = 𝑎𝑖 −𝑏𝑖

𝑖=1
Distance Euclidienne ∶ 𝑑2 𝐴, 𝐵 = 𝑎𝑖 −𝑏𝑖 2
𝑖=1
Distance de Minkowski ∶ 𝑑∞ 𝐴, 𝐵 = max 𝑎𝑖 −𝑏𝑖

1≤𝑖≤𝑛

Algorithme : Nombre de voisins
■ Si le nombre de classes est égal à 2 alors il faux choisir k impair.
■ Si k est petit alors l’algorithme est sensible aux petites variations

"aléatoires" et par suite aux bruits.
■ Si k est grand alors l’algorithme est moins sensible aux bruits mais le
coût de calcul est plus élevé.
■ Il faut donc choisir un k non sensible aux bruits et dont le coût de

calcul est raisonnable.

Nous disposons de plusieurs données qui appartiennent à deux classes :
la classe des points rouges et celle des points bleus.

■ Si k=1 alors le système donnera à un point l’étiquette du plus proche
voisin.
■ Les points des zones bleues seront donc classés dans la classe des
points rouges et ceux des zones jaunes seront classés dans la classe
des points bleus.

■ Si k=3 alors le système donnera à un point l’étiquette majoritaire de
ces trois plus proches voisins.
■ La frontière de décision est plus lisse (la séparation entre les zones
bleu et jaune est meilleure).

■ Si k=21 alors on obtient une bonne frontière de décision (elle se
présente sous forme d’une seule courbe).

■ Si par contre k est égale au nombre total des points (bleus+rouges),
alors comme il y’a plus de points bleus que de points rouges dans
l’ensemble d’apprentissage, tous les points seront classés dans la
classe des points bleus.

■ Si la taille de la base d’apprentissage est petite, alors il faut choisir k
petit.
■ Si la taille de la base d’apprentissage est grande, alors il faut choisir

k grand. Dans ce cas on peut :
– Faire un choix heuristique : k = nombre d’attributs + 1.
– Tester plusieurs valeurs de k et choisir celui dans les

performances sont les meilleurs (en général on démarre avec
𝑘 = 𝑛 où n est égal à la taille de la base d’apprentissage).

Principe
■ On dispose de :
– Un ensemble de données d’apprentissage D
– Une distance d
– Un entier k
■ Pour tout nouveau point de test X, pour lequel on doit prendre une
décision, l’algorithme recherche dans D les k points les plus proches
de X au sens de la distance d, et attribue à X la classe qui est la plus
fréquente parmi ces k voisins.

Exemple
■ Fidélité des clients d’une banque : c’est une variable à deux valeurs
qui sont ’’fidèle’’ et ’’non fidèle’’.
■ Nous disposons des données suivantes :
Client(e) Age Revenu Nombre de Fidélité
(en milliers de Dh) cartes de crédit
Ali 35 5 3 Non
Hassan 22 20 2 Oui
Sanae 63 15 1 Non
Samir 59 17 1 Non
Fadoua 25 25 3 Oui
Fouad 37 16 2 ?
■ Nous cherchons à identifier la classe de Fouad (fidèle ou pas).
Exemple
Nombre
Client(e) Age Revenu
de cartes
Fidélité Distance entre Fouad et les autres
Ali 35 5 3 Non (35−37)2+(5−16)2+(3−2)2 = 126 = 11.2
Hassan 22 20 2 Oui (22−37)2+(20−16)2+(2−2)2 = 241 = 15.5
Sanae 63 15 1 Non (63−37)2+(15−16)2+(1−2)2 = 678 = 26.1
Samir 59 17 1 Non (59−37)2+(17−16)2+(1−2)2 = 486 = 22.1
Fadoua 25 25 3 Oui (25−37)2+(25−16)2+(3−2)2 = 226 = 15.1
Fouad 37 16 2 ?
■ Si on choisit k=1, alors Ali est le voisin le plus proche de Fouad, et par
suite Fouad sera classé ’’non fidèle’’.
■ Si on choisit k=3, alors Ali, Hassan et Fadoua sont les voisins les plus
proches de Fouad, et par suite comme Hassan et Fadoua sont classés
’’fidèle’’ alors Fouad sera également classé ’’ fidèle’’. 18
Avantages de l’algorithme k-NN
■ Méthode facile à comprendre et à implémenter.
■ Pas de construction de modèle : cette méthode ne nécessite pas
une phase d’apprentissage et l’introduction de nouvelles données
permet d'améliorer la qualité de la méthode.
■ Clarté des résultats : la classe attribuée à un exemple est expliquée
en exhibant les plus proches voisins qui ont amené à ce choix.
■ Tout type de données : la méthode s'applique dès qu'il est possible
de définir une distance sur les enregistrements. Or, il est possible
de définir des distances sur des champs complexes tels que des
données vectorielles numériques, des informations géographiques,
des textes, des images, du son.
■ Nombre d’attributs : la méthode permet de traiter des problèmes
avec un grand nombre d'attributs. Mais, plus le nombre d'attributs
est important, plus le nombre d'exemples de l’ensemble
d’apprentissage doit être grand. 19
Inconvénients de l’algorithme k-NN
■ Temps de classification : la classification est lente car il faut

revoir tous les exemples à chaque fois. Ceci est la contrepartie à
payer par rapport aux méthodes qui nécessite un apprentissage.
■ Méthode gourmande en place mémoire : il faut stocker tout

l’ensemble d’apprentissage.
■ Distance et nombre de voisins : les performances de la méthode

dépendent du choix de la distance et du nombre k de voisins.

Chap3 KNN

Transféré par

Droits d'auteur :

Formats disponibles

Chap3 KNN

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Chap3 KNN

Transféré par

Droits d'auteur :

Formats disponibles

MÉTHODE K-NN

– Etape 1 : Construction du modèle

– Etape 2 : Validation du modèle

– Etape 3 : Test du modèle

– Etape 4 : Application du modèle

■ La classification supervisée consiste à construire le modèle à partir

■ Elle définit donc une fonction capable de classer (étiqueter) au mieux

■ L’algorithme des k plus proches voisins (k-NN) est l’un des

algorithmes les plus simples de la classification supervisée.

■ L’algorithme k-NN permet d’obtenir de bons résultats de

classification lorsqu’une base d’apprentissage correctement étiquetée

(un échantillon fini d’objets classés) est disponible.

Cours Data Mining 2022-2023 A. Mazroui 3

■ L’algorithme k-NN est une méthode de raisonnement à partir de cas :

“Dis moi qui sont tes amis, et je te dirais qui tu es”.

■ Le principe de l’algorithme k-NN est basé sur le choix de la classe à

Cours Data Mining 2022-2023 A. Mazroui 4

Cours Data Mining 2022-2023 A. Mazroui 5

■ Si on choisit k=3, alors les 3 plus proches voisins du point en gris

■ Par suite, ce point sera considéré selon le vote majoritaire comme

■ Le choix de la distance est primordial au bon fonctionnement de la

■ Une distance doit vérifier les propriétés suivantes :

– d(A,B) ≤ d(A,C) + d(B,C)

Cours Data Mining 2022-2023 A. Mazroui 7

Distance de Manhattan : 𝑑1 𝐴, 𝐵 = 𝑎𝑖 −𝑏𝑖

Distance Euclidienne ∶ 𝑑2 𝐴, 𝐵 = 𝑎𝑖 −𝑏𝑖 2

Distance de Minkowski ∶ 𝑑∞ 𝐴, 𝐵 = max 𝑎𝑖 −𝑏𝑖

Cours Data Mining 2022-2023 A. Mazroui 8

■ Si le nombre de classes est égal à 2 alors il faux choisir k impair.

■ Si k est petit alors l’algorithme est sensible aux petites variations

■ Il faut donc choisir un k non sensible aux bruits et dont le coût de

Cours Data Mining 2022-2023 A. Mazroui 9

Cours Data Mining 2022-2023 A. Mazroui 10

Cours Data Mining 2022-2023 A. Mazroui 11

Cours Data Mining 2022-2023 A. Mazroui 12

Cours Data Mining 2022-2023 A. Mazroui 13

Cours Data Mining 2022-2023 A. Mazroui 14

■ Si la taille de la base d’apprentissage est grande, alors il faut choisir

– Faire un choix heuristique : k = nombre d’attributs + 1.

– Tester plusieurs valeurs de k et choisir celui dans les

Cours Data Mining 2022-2023 A. Mazroui 15

– Un ensemble de données d’apprentissage D

Cours Data Mining 2022-2023 A. Mazroui 16

Ali 35 5 3 Non (35−37)2+(5−16)2+(3−2)2 = 126 = 11.2

Hassan 22 20 2 Oui (22−37)2+(20−16)2+(2−2)2 = 241 = 15.5

Sanae 63 15 1 Non (63−37)2+(15−16)2+(1−2)2 = 678 = 26.1

Samir 59 17 1 Non (59−37)2+(17−16)2+(1−2)2 = 486 = 22.1

Fadoua 25 25 3 Oui (25−37)2+(25−16)2+(3−2)2 = 226 = 15.1

■ Temps de classification : la classification est lente car il faut

■ Méthode gourmande en place mémoire : il faut stocker tout

■ Distance et nombre de voisins : les performances de la méthode

Cours Data Mining 2022-2023 A. Mazroui 20

Vous aimerez peut-être aussi