Cours Machine Learning:

k-Nearest Neighbor (k-NN)

présentée par :

Equipe Machine Learning

Unité pédagogique: Génie Logiciel et Mathématiques

[Link]

Equipe Machine Learning 1 Octobre 2020 1 / 16

Introduction

Problème
Un fleuriste veut deviner l’achat N d’un client X par rapport à son achat
N − 1.

[Link]

Equipe Machine Learning 2 Octobre 2020 2 / 16

Introduction

Problème
Un fleuriste veut deviner l’achat N d’un client X par rapport à son achat
N − 1.

[Link]

Equipe Machine Learning 2 Octobre 2020 2 / 16

Introduction

Problème
Un fleuriste veut deviner l’achat N d’un client X par rapport à son achat
N − 1.

[Link]

Equipe Machine Learning 2 Octobre 2020 2 / 16

Introduction

[Link]

Equipe Machine Learning 3 Octobre 2020 3 / 16

Introduction

[Link]

Equipe Machine Learning 3 Octobre 2020 3 / 16

Introduction

[Link]

Equipe Machine Learning 3 Octobre 2020 3 / 16

Introduction

Pour répondre à ces questions il faut construire un model:

Features: propriétés des données utilisées pour la prédiction
Label: la valeur cible pour un seul point de données
Algorithme ou méthodes pour mesurer la similarité: classification.

[Link]

Equipe Machine Learning 4 Octobre 2020 4 / 16

Introduction

Pour répondre à ces questions il faut construire un model:

Features: propriétés des données utilisées pour la prédiction
Label: la valeur cible pour un seul point de données
Algorithme ou méthodes pour mesurer la similarité: classification.

k-Nearest Neighbor (k-NN)

[Link]

Equipe Machine Learning 4 Octobre 2020 4 / 16

Généralités

L’algorithme des k plus proches voisins est un algorithme

d’apprentissage supervisé, il est nécessaire d’avoir des données
labellisées.
A partir d’un ensemble E de données labellisées, il sera possible de
classer (déterminer le label ) une nouvelle donnée (donnée
n’appartenant pas à E.
Il est aussi possible d’utiliser l’algorithme des k plus proches voisins
pour la régression (on cherche à déterminer une valeur à la place
d’une classe),

[Link]

Equipe Machine Learning 5 Octobre 2020 5 / 16

Généralités

Méthode de raisonnement à partir de cas: prendre des décisions en

recherchant un ou des cas similaires déjà résolus.

[Link]

Equipe Machine Learning 6 Octobre 2020 6 / 16

Généralités

Méthode de raisonnement à partir de cas: prendre des décisions en

recherchant un ou des cas similaires déjà résolus.
Pas d’étape d’apprentissage: construction d’un modèle à partir d’un
échantillon d’apprentissage.

[Link]

Equipe Machine Learning 6 Octobre 2020 6 / 16

Généralités

Méthode de raisonnement à partir de cas: prendre des décisions en

recherchant un ou des cas similaires déjà résolus.
Pas d’étape d’apprentissage: construction d’un modèle à partir d’un
échantillon d’apprentissage.
Modèle= échantillon d’apprentissage + fonction de distance +
fonction de choix de la classe en fonction des classes des voisins les
plus proches.

[Link]

Equipe Machine Learning 6 Octobre 2020 6 / 16

Principe
Soit la base de donnée:

[Link]

Equipe Machine Learning 7 Octobre 2020 7 / 16

Principe
On veut prédire à quelle classe appartient la nouvelle donnée:

[Link]

Equipe Machine Learning 7 Octobre 2020 7 / 16

Principe
Si on prend un seul voisin:

[Link]

Equipe Machine Learning 7 Octobre 2020 7 / 16

Principe
Si on considère deux voisins:

[Link]

Equipe Machine Learning 8 Octobre 2020 8 / 16

Principe
Si on considère trois voisins:

[Link]

Equipe Machine Learning 8 Octobre 2020 8 / 16

Principe
Si on considère quatres voisins:

[Link]

Equipe Machine Learning 8 Octobre 2020 8 / 16

Algorithme de KNN

Début Algorithme
Input :
un ensemble de données D .
une fonction de définition distance d.
Un nombre entier k
une nouvelle observation X
Output:
Prédire la variable de sortie y de X:
Faire :
1 Calculer toutes les distances de cette observation X avec les autres observations du jeu de
données D.
2 Retenir les k observations du jeu de données D les proches de X en utilisation le fonction
de calcul de distance d
3 Prendre les valeurs de y des k observations retenues : et calculer le mode de y retenues.
4 Retourner la valeur calculée dans l’étape 3 comme étant la valeur qui a été prédite par
K-NN pour l’observation X.
Fin Algorithme [Link]

Equipe Machine Learning 9 Octobre 2020 9 / 16

Distance

L’algorithme, K-NN a besoin d’une fonction de calcul de distance entre

deux observations.
Définition distance
on appelle distance sur un ensemble E de Rn , une application définie de
E × E à valeurs dans R+ notée d qui à tout couple (x, y) ∈ E × E fait
correspondre un réel positif ou nul d(x, y) vérifiant:
1 d(x, y) = 0 SSi x = y.
2 d(x, y) = d(y, x), ∀(x, y) ∈ E 2 .
3 d(x, y) ≤ d(x, z) + d(z, y), ∀(x, y, z) ∈ E 3 .

[Link]

Equipe Machine Learning 10 Octobre 2020 10 / 16

Type des distance
Il existe plusieurs fonctions de calcul de distance:
La distance euclidienne.
la distance de Manhattan.
la distance de Minkowski
la distance de Jaccard.
la distance de Hamming.
Le choix de la fonction de distance en fonction des types de données qu’on
manipule.
Ainsi pour les données quantitatives (exemple : poids, salaires, taille,
montant de panier éléctronique etc...) et du même type: la distance
euclidienne est un bon candidat.
La distance de Manhattan est une bonne mesure à utiliser quand les
données (input variables) ne sont pas du même type (exemple :age,
[Link]
sexe, longueur, poids etc...).
Equipe Machine Learning 11 Octobre 2020 11 / 16
Distance euclidienne
Définition
C’est la distance qui calcule la racine carrée de la somme des différences carrées entre les
coordonnées de deux points:
Soient X = (x1 , x2 , ..., xn ) et Y = (y1 , y2 , ..., yn ) la distance euclidienne entre X et Y est:
v
u n
uX
d(X, Y ) = t (xi − yi )2 .
i=1

[Link]

Equipe Machine Learning 12 Octobre 2020 12 / 16

Distance euclidienne
Définition
C’est la distance qui calcule la racine carrée de la somme des différences carrées entre les
coordonnées de deux points:
Soient X = (x1 , x2 , ..., xn ) et Y = (y1 , y2 , ..., yn ) la distance euclidienne entre X et Y est:
v
u n
uX
d(X, Y ) = t (xi − yi )2 .
i=1

[Link]

Equipe Machine Learning 12 Octobre 2020 12 / 16

Distance Manhattan
Définition
C’est la distance qui calcule la somme des valeurs absolues des différences entre les coordonnées
de deux points:
Soient X = (x1 , x2 , ..., xn ) et Y = (y1 , y2 , ..., yn ) la distance Manhattan entre X et Y est:

n
X
dm (X, Y ) = |xi − yi |.
i=1

[Link]

Equipe Machine Learning 13 Octobre 2020 13 / 16

Distance Manhattan
Définition
C’est la distance qui calcule la somme des valeurs absolues des différences entre les coordonnées
de deux points:
Soient X = (x1 , x2 , ..., xn ) et Y = (y1 , y2 , ..., yn ) la distance Manhattan entre X et Y est:

n
X
dm (X, Y ) = |xi − yi |.
i=1

[Link]

Equipe Machine Learning 13 Octobre 2020 13 / 16

Distance de Minkowski

Définition
La distance de Minkowski ou métrique de Minkowski est une généralisation à la fois de la
distance euclidienne et de la distance de Manhattan: Soient X = (x1 , x2 , ..., xn ) et
Y = (y1 , y2 , ..., yn ) la distance Minkowski d’ordre p entre X et Y est:
v
u n
uX
p
dM (X, Y ) = t (xi − yi )p .
i=1

Remarque
Si p → +∞ alors la distance de Minkowski nous obtenons la distance de Chebyshev:
Soient X = (x1 , x2 , ..., xn ) et Y = (y1 , y2 , ..., yn ) la distance Minkowski d’ordre p entre X et Y
est:
v
u n
uX
dT (X, Y ) = lim p
t (xi − yi )p = max |xi − yi |.
p→+∞ i
i=1
[Link]

Equipe Machine Learning 14 Octobre 2020 14 / 16

Comment choisir la valeur K

Le choix de la valeur K à utiliser pour effectuer une classification

avec K-NN, varie en fonction du jeu de données.
En règle générale, moins on utilisera de voisins (un nombre K petit)
plus on sera sujette au sous apprentissage (underfitting).
Par ailleurs, plus on utilise de voisins (un nombre K grand) plus, sera
fiable dans notre classification.
Toutefois, si on utilise K nombre de voisins avec K = N et N étant
le nombre d’observations, on risque d’avoir du overfitting.

[Link]

Equipe Machine Learning 15 Octobre 2020 15 / 16

Limitations de K-NN

K-NN est un algorithme assez simple à appréhender.

Principalement, grâce au fait qu’il n’a pas besoin de modèle pour
pouvoir effectuer une prédiction.
Le contre coût est qu’il doit garder en mémoire l’ensemble des
observations pour pouvoir effectuer sa prédiction. Ainsi il faut faire
attention à la taille du jeu d’entrainement.
Le choix de la méthode de calcul de la distance ainsi que le nombre
de voisins k peut ne pas être évident. Il faut essayer plusieurs
combinaisons et faire du tuning de l’algorithme pour avoir un résultat
satisfaisant.

[Link]

Equipe Machine Learning 16 Octobre 2020 16 / 16

 MERCI POUR VOTRE ATTENTION

[Link]

Equipe Machine Learning 17 Octobre 2020 17 / 16