Introduction à l’algorithme K Nearst Neighbors (K-NN)

By | 2 octobre 2018

Lors de cet article, on découvrira l’algorithme K Nearest Neighbors (K-NN). Il s’agit d’un algorithme d’apprentissage supervisé. Il sert aussi bien pour la classification que la régression. Ainsi, nous allons voir le fonctionnement de cet algorithme, ses caractéristiques et comment il parvient à établir des prédictions.

C’est parti !

Mr Mint - k nearest neighbors

Découverte de l’algorithme K Nearest Neighbors

l’algorithme K-NN (K-nearest neighbors) est une méthode d’apprentissage supervisé. Il peut être utilisé aussi bien pour la régression que pour la classification. Son fonctionnement peut être assimilé à l’analogie suivante “dis moi qui sont tes voisins, je te dirais qui tu es…”.

Pour effectuer une prédiction, l’algorithme K-NN ne va pas calculer un modèle prédictif à partir d’un Training Set comme c’est le cas pour la régression logistique ou la régression linéaire. En effet,  K-NN n’a pas besoin de construire un modèle prédictif. Ainsi, pour K-NN il n’existe pas de phase d’apprentissage proprement dite. C’est pour cela qu’on le catégorise parfois dans le Lazy LearningPour pouvoir effectuer une prédiction, K-NN se base sur le jeu de données pour produire un résultat.

Principe de K-NN : dis moi qui sont tes voisins, je te dirais qui tu es !

Comment K-NN effectue une prédiction ?

Pour effectuer une prédiction, l’algorithme K-NN va se baser sur le jeu de données en entier. En effet, pour une observation, qui ne fait pas parti du jeu de données, qu’on souhaite prédire, l’algorithme va chercher les instances du jeu de données les plus proches de notre observation. Ensuite pour ces K voisins, l’algorithme se basera sur leurs variables de sortie (output variable) y pour calculer la valeur de la variable y de l’observation qu’on souhaite prédire. 

Par ailleurs  :

  • Si K-NN est utilisé pour la régression, c’est la moyenne (ou la médiane) des variables y des K plus proches observations qui servira pour la prédiction
  • Si K-NN est utilisé pour la classification, c’est le mode des variables y des K plus proches observations qui servira pour la prédiction

Ecriture algorithmique

On peut schématiser le fonctionnement de K-NN en l’écrivant en pseudo-code suivant :

Début Algorithme

Données en entrée :

  • un ensemble de données D .
  • une fonction de définition distance d.
  • Un nombre entier K

Pour une nouvelle observation X dont on veut prédire sa variable de sortie y 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 :
    1. Si on effectue une régression, calculer la moyenne (ou la médiane) de y retenues
    2. Si on effectue une classification , 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

 

Calcul de similarité dans l’algorithme K-NN

Comme on vient de le voir dans notre écriture algorithme, K-NN a besoin d’une fonction de calcul de distance entre deux observations. Plus deux points sont proches l’un de l’autre, plus ils sont similaires et vice versa.

Il existe plusieurs fonctions de calcul de distance, notamment, la distance euclidienne, la distance de Manhattan, la distance de Minkowski, celle de Jaccard, la distance de Hamming…etc. On choisit 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. Quant à la distance de Manhattan, elle est une bonne mesure à utiliser quand les données (input variables) ne sont pas du même type (exemple :age, sexe, longueur, poids etc…).

Il est inutile de coder, soi-même ces distances, généralement, les librairies de Machine Learning comme Scikit Learn, effectue ces calculs en interne. Il suffit juste d’indiquer la mesure de distance qu’on souhaite utiliser.

Pour les curieux, voici les définitions mathématiques des distances qu’on vient d’évoquer.

La distance euclidienne:

  • distance qui calcule la racine carrée de la somme des différences carrées entre les coordonnées de deux points :

D_e(x, y) = \sqrt{\sum_{j=1}^{n} (x_j - y_j)^2}

Distance Manhattan :

  • la distance de Manhattan: calcule la somme des valeurs absolues des différences entre les coordonnées de deux points :

D_m(x, y) = \sum_{i=1}^{k}\mid x_i - y_i \mid

Distance Hamming :

  • la distance entre deux points données est la différence maximale entre leurs coordonnées sur une dimension.

D_h(x, y) = \sum_{i=1}^{k}\mid x_i - y_i \mid

avec

  • x = y \implies D = 0
  • x \neq y \implies D = 1

Notez bien qu’il existe d’autres distances selon le cas d’utilisation de l’algorithme, mais la distance euclidienne reste la plus utilisée.

Comment choisir la valeur K ?

Le choix de la valeur K à utiliser pour effectuer une prédiction 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 prédiction. Toutefois, si on utilise K nombre de voisins avec K=N et N étant le nombre d’observations, on risque d’avoir du overfitting et par conséquent un modèle qui se généralise mal sur des observations qu’il n’a pas encore vu.

k nearest neighbors

L’image ci-dessus à gauche représente des points dans un plan 2D avec trois types d’étiquetages possibles (rouge, vert, bleu). Pour le 5-NN classifieur, les limites entre chaque région sont assez lisses et régulières.  Quant au N-NN Classifier, on remarque que les limites sont “chaotiques” et irrégulières. Cette dernière provient du fait que l’algorithme tente de faire rentrer tous les points bleus dans les régions bleues, les rouges avec les rouges etc… c’est un cas d’overfitting.

Pour cet exemple, on préférera le 5-NN classifier sur le NN-Classifier. Car le 5-NN classifier se généralise mieux que son opposant.

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. 

Egalement, 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.

Conclusion

Dans cet article, vous avez découvert l’algorithme K-NN. Vous avez appris également que :

  • K-NN stocke tout le jeu de données pour effectuer une prédiction,
  • K-NN ne calcule aucun modèle prédictif et il rentre dans le cadre du Lazy Learning,
  • K-NN effectue des prédictions juste à temps (à la volée) en calculant la similarité entre un observation en entrée et les différentes observations du jeu de données,

 

J’espère que cet article vous a plu, si vous avez des questions n’hésitez pas à me les poser en commentaire. J’y répondrai du mieux que je peux. 🙂

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.