L'algorithme des K voisins les plus proches aussi appelé algorithme KNN

Lors de cette séquence, on découvrira l’algorithme des K voisins les plus proches en anglais, 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 !

Découverte de l’algorithme K Nearest Neighbors

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

Pour effectuer une prédiction, l’algorithme K-NN ne va pas calculer un modèle prédictif. 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 l'apprentissage paresseux. Pour pouvoir effectuer une prédiction, K-NN se base sur le jeu de données pour produire un résultat.

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 K instances du jeu de données les plus proches de notre observation. Ensuite pour ces voisins, l’algorithme se basera sur leurs variables de sortie (output variable) pour calculer la valeur de la variable de l’observation qu’on souhaite prédire.

Par ailleurs :

• Si K-NN est utilisé pour la classification, c’est le mode (la valeur dominante) des valeurs des K plus proches observations qui servira pour la prédiction
• Si K-NN est utilisé pour la régression, c’est la moyenne (ou la médiane) des valeurs 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 
Un nombre entier K

Pour une nouvelle observation dont on veut prédire sa variable de sortie  Faire :

Calculer toutes les distances de cette observation avec les valeurs de l'ensemble des données
Retenir les K valeurs du jeu de données les plus proches de cette obesvation
Choisir la valeur dominante parmi les K valeurs précédentes
Retourner la valeur calculée dans l’étape 3 comme étant la valeur qui a été prédite par K-NN pour l’observation .

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 rappel, 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 :

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 proche de l'effectif total, 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.

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.

Un exemple

Une population contient deux classes, les rouges et les verts. Elle est répartie de la façon suivante :

A partir d'un échantillon de cette population, on va essayer de retrouver la répatition théorique de cette population avec un algorithme KNN.

l'algorithme KNN