Chapitre 4

k plus proches voisins

(k-ppv)

Zied Elouedi 2015/2016 169

 Plan

 Algorithme k-pvv

 Paramètres

 Exemples

 Avantages et inconvénients

Zied Elouedi 2015/2016 170

 Introduction
Apprentissage par analogie: Recherche d’un ou de plusieurs cas
similaires déjà résolus.

Dis moi quels sont tes voisins, je te dirais qui tu es.

Un nouvel objet sera affecté à la classe la plus commune parmi

les classes des k objets qui sont les plus proches de lui.

k plus proche voisins (k-ppv)

k nearest neighbors (k-nn)
 Algorithme k-pvv

Zied Elouedi 2015/2016 172

 Algorithme k-ppv
 Pour déterminer la classe d’un nouvel objet O:
 Calculer la distance entre O et tous les objets de l’ensemble
d’apprentissage.
 Choisir les k objets de l’ensemble d’apprentissage qui sont les plus
proches de O.
 Affecter O la class majoritaire parmi les classes des k plus proches
Objet à classer
voisins.
 Exemples

X X X

(a) 1-plus proche voisin (b) 2-plus proches voisins (c) 3-plus proches voisins

Zied Elouedi 2015/2016 174

 Paramètres

Zied Elouedi 2015/2016 175

 Paramètres

o L’ensemble d’apprentissage.

o La métrique de distance pour calculer la distance entre deux objets.

o La valeur de K représentant le nombre des voisins les plus proches.

o Choix de la classe de l’objet à classer.

Zied Elouedi 2015/2016 176

 Ensemble d’apprentissage

o Ensemble d’objets tel que pour chaque objet, on connaît:

 La valeur de ses attributs.

 Sa classe.

Zied Elouedi 2015/2016 177

 Distance
 Le choix de la distance est primordial au bon fonctionnement
de la méthode.

 Les distances les plus simples permettent d'obtenir des

résultats satisfaisants (lorsque c'est possible).

 Propriétés de la distance:
 Réflexivité: d(A,B)=0 SSi A = B
 Non négativité: d(A, B)  0
 Symétrie: d(A,B)= d(B,A)
 Inégalité triangulaire: d(A,B) d(A,C) + d(B,C)

Zied Elouedi 2015/2016 178

 Distance Euclidienne

 L’une des distances utilisées quand les attributs sont numériques est
la distance Euclidienne.

 La distance euclidienne entre deux objets

O1=(x1, x2, x3,…xn) et O2 =(y1,y2, y3,…yn)
est définie comme suit:

n
D(O1, O2)   i i
(x  y ) 2

i1

Zied Elouedi 2015/2016 179

 Distance Euclidienne pondérée

n
D(O1,O2)   w (x
i1
i i  yi ) 2

Remarque: il y a plusieurs distances à utiliser comme celles

utilisées en clustering (Minkowski, Manhattan, etc).

Zied Elouedi 2015/2016 180

 Distance selon les variables

 Variables nuémriques

 Variables catégoriques

 Variables binaires

 Variables ordinales

Il suffit d’utiliser la distance appropriée à chaque type de variable.

Zied Elouedi 2015/2016 181

 Choix du k
 Si k est trop petit, sensible au bruit
 Si k est trop grand, le voisinage peut conetnir des objets de
plusieurs classes.

 Choix du nombre k de voisins déterminé par utilisation d'un

ensemble test ou par validation croisée.
 Une heuristique fréquemment utilisée est de prendre k égal au
nombre d'attributs plus 1.
Zied Elouedi 2015/2016 182
 Classification

 Pour déterminer la classe à partir de la liste des k plus proches

voisins:

 Choix de la classe majoritaire.

 Choix de la classe majoritaire pondérée:

Chaque classe d'un des k voisins sélectionnés est
pondéré.
Par exemple w = 1/d2.

Zied Elouedi 2015/2016 183

 Complexité

 La complexité de l'algorithme naïf appliquant la règle des k-ppv

est de O(kdn).

o d est la dimensionnalité de l'espace (nombre d’attributs).

o n est le nombre d'échantillons.

Zied Elouedi 2015/2016 184

 Remarques

o Pas de construction de modèle

C'est l'échantillon d'apprentissage, associé à une

fonction de distance et d'une fonction de choix de la
classe en fonction des classes des voisins les plus
proches, qui constitue le modèle.

Zied Elouedi 2015/2016 185

 Exemples

Zied Elouedi 2015/2016 186

Exemple (1)
Client Age Revenu Nombre Classe
cartes (Réponse)
de crédit
Mohamed 35 350 3 Non

Ali 22 500 2 Oui

Samia 63 2000 1 Non

Sami 59 1700 1 Non

Meriem 25 400 4 Oui

Lotfi 37 500 2 ?
 Exemple (2)
Client Age Revenu Nombre cartes Classe Distance(Client, Lotfi)
de crédit (Réponse)
Mohamed 35 350 3 Non Sqrt((35-37)2+(350-
500)2+(3-2)2)=150.01
Ali 22 500 2 Oui Sqrt((22-37)2+(500-
500)2+(2-2)2)= 15
Samia 63 2000 1 Non Sqrt((63-37)2+(2000-
500)2+(1-2)2)=1500.22
Sami 59 1700 1 Non Sqrt((59-37)2+(1700-
500)2+(1-2)2)=1200.2
Meriem 25 400 4 Oui Sqrt((25-37)2+(400-
500)2+(4-2)2)=100.74
Lotfi 37 500 2 ?

Zied Elouedi 2015/2016 188

 Exemple (3)
Client Age Revenu Nombre cartes Classe Distance(Client, Lotfi)
de crédit (Réponse)
Mohamed 35 350 3 Non Sqrt((35-37)2+(350-
500)2+(3-2)2)=150.01
Ali 22 500 2 Oui Sqrt((22-37)2+(500-
500)2+(2-2)2)= 15
Samia 63 2000 1 Non Sqrt((63-37)2+(2000-
500)2+(1-2)2)=1500.22
Sami 59 1700 1 Non Sqrt((59-37)2+(1700-
500)2+(1-2)2)=1200.2
Meriem 25 400 4 Oui Sqrt((25-37)2+(400-
500)2+(4-2)2)=100.74
Lotfi 37 500 2 Oui ?
Il faut normaliser puis calculer les distances!
Zied Elouedi 2015/2016 189
 Normalisation des variables
Client Age Revenu Nombre Classe
cartes (Réponse)
de crédit
Mohamed 0.56 0.18 0.75 Non

Ali 0.35 0.25 0.5 Oui

Samia 1 1 0.25 Non

Sami 0.94 0.85 0.25 Non

Meriem 0.4 0.2 1 Oui

Lotfi 0.59 0.25 0.5 ?

Zied Elouedi 2015/2016 190

 Exemple (4)

Client Age Revenu Nombre cartes Classe Distance(Client, Lotfi)

de crédit (Réponse)
Mohamed 0.56 0.18 0.75 Non Sqrt((0.56-0.59)2+(0.18-
0.25)2+(0.75-0.5)2)=0.26
Ali 0.35 0.25 0.5 Oui Sqrt((0.35-0.59)2+(0.25-
0.25)2+(0.5-0.5)2)= 0.24
Samia 1 1 0.25 Non Sqrt((1-0.59)2+(1-
0.25)2+(0.25-0.5)2)=0.89
Sami 0.94 0.85 0.25 Non Sqrt((0.94-0.59)2+(0.85-
0.25)2+(0.25-0.5)2)=0.74
Meriem 0.4 0.2 1 Oui Sqrt((0.4-0.59)2+(0.2-
0.25)2+(1-0.5)2)=0.54
Lotfi 0.59 0.25 0.5 ?

Zied Elouedi 2015/2016 191

 Exemple (5)
k=3
Client Age Revenu Nombre cartes Classe Distance(Client, Lotfi)
de crédit (Réponse)
Mohamed 0.56 0.18 0.75 Non Sqrt((0.56-0.59)2+(0.18-
0.25)2+(0.75-0.5)2)=0.26
Ali 0.35 0.25 0.5 Oui Sqrt((0.35-0.59)2+(0.25-
0.25)2+(0.5-0.5)2)= 0.24
Samia 1 1 0.25 Non Sqrt((1-0.59)2+(1-
0.25)2+(0.25-0.5)2)=0.89
Sami 0.94 0.85 0.25 Non Sqrt((0.94-0.59)2+(0.85-
0.25)2+(0.25-0.5)2)=0.74
Meriem 0.4 0.2 1 Oui Sqrt((0.4-0.59)2+(0.2-
0.25)2+(1-0.5)2)=0.54

Lotfi 0.59 0.25 0.5 Oui

Zied Elouedi 2015/2016 192

 Avantages et
inconvénients

Zied Elouedi 2015/2016 193

 Avantages

 Simple et facile à implémenter et à utiliser.

 Compréhensible : La classification est facile à expliquer.

 Robuste aux données bruitées.

 Efficace pour des classes réparties de manière irrégulière.

 Des applications intéressantes.

Zied Elouedi 2015/2016 194

 Inconvénients

 Nécessité de capacité de stockage et de puissance de calcul.

 Pas de modèle construit.

 Prend du temps pour classer un nouvel objet:

Comparaison des distances du nouvel objet avec tous les autres
de l’ensemble d’apprentissage.

 Choix du k.

Zied Elouedi 2015/2016 195

 Travail à faire
Une usine fait une étude sur le statut de ses employés s’ils sont titulaires ou contractuels.
Chaque employé de l’ensemble d’apprentissage ci-joint est caractérisé par trois attributs à
savoir l’âge, le salaire mensuel et le genre permettant de déterminer son statut.
Employé Age Salaire mensuel Genre Statut
E1 27 190 F Contractuel
E2 51 640 M Titulaire
E3 52 1000 M Titulaire
E4 33 550 F Titulaire
E5 45 450 M Contractuel
1) Transformer l’ensemble d’apprentissage en un ensemble normalisé. Pour l’attribut Genre
remplacer F par 1 et M par 0. Cet attribut sera désormais considéré comme un attribut
numérique.
2) Soit l’ensemble test composé par les employés E6 et E7:
Employé Age Salaire mensuel Genre Statut
E6 32 310 M ?
E7 42 700 F ?
Appliquer l’algorithme standard de k plus proche voisins (k = 3) pour classer les employés E6
et E7.
Zied Elouedi 2015/2016 196
 Solution (1)
1) La normalisation donne
Employé Age Salaire mensuel Genre Statut
E1 0 0 1 Contractuel
E2 0,96 0,56 0 Titulaire
E3 1 1 0 Titulaire
E4 0,24 0,44 1 Titulaire
E5 0,72 0,32 0 Contractuel

Employé Age Salaire mensuel Genre Statut

E6 0,2 0,15 0 ?
E7 0,6 0,63 1 ?

Zied Elouedi 2015/2016 197

 Solution (2)
2) D(E6, E1) = Sqrt((0,2)*2+ (0,15)*2 +(1)*2)= 1,03
D(E6, E2) = Sqrt( (0,76)*2+ (0,41)*2 +(0)*2)= 0,86
D(E6, E3) = Sqrt((0,8)*2+ (0,85)*2 +(0)*2)= 1,17
D(E6, E4) = Sqrt((0,04)*2+ (0,31)*2 +(1)*2)= 1,05
D(E6, E5) = Sqrt((0,52)*2+ (0,17)*2 +(1)*2)= 0,55

Donc E6 contractuel

D(E7, E1) = Sqrt((0,6)*2+ (0,63)*2 +(0)*2)= 0,87

D(E7, E2) = Sqrt((0,36)*2+ (0,07)*2 +(1)*2)= 1,07
D(E7, E3) = Sqrt((0,4)*2+ (0,37)*2 +(1)*2)= 1,14
D(E7, E4) = Sqrt((0,36)*2+ (0,19)*2 +(0)*2)= 0,41
D(E7, E5) = Sqrt((0,12)*2+ (0,31)*2 +(1)*2)= 1,05

Donc E7 contractuel

Zied Elouedi 2015/2016 198

 Conclusion (1)
 K-pvv est une méthode de classification non-paramétrique puisqu'aucune
estimation de paramètres n'est nécessaire pas comme pour la régression
linéaire.

 Tous les calculs doivent être effectués lors de la classification (pas de

construction de modèle).

 Le modèle est l'échantillon: Espace mémoire important nécessaire pour

stocker les données, et méthodes d'accès rapides nécessaires pour
accélérer les calculs.

 Les performances de la méthode dépendent du choix de la distance, du

nombre de voisins et du mode de combinaison des réponses des voisins.

 La méthode permet de traiter des problèmes avec un grand nombre

d'attributs. Cependant, plus le nombre d'attributs est important, plus le
nombre d'exemples doit être grand.
 Conclusion (2)

⚫ Plusieurs extensions de K plus proches voisins:

⚫ Système de classification hybrides
⚫ Fuzzy K-NN.
⚫ Belief K-NN.
.
.
.

Zied Elouedi 2015/2016 200