k plus proches voisins (K-NN)

Le cours qui suit est issu de : https://www.numerique-sciences-informatiques.fr/

Machine learning et histoire

L'idée d'apprentissage automatique (machine learning) est réellement née en 1936 avec le concept de machine universelle d'Alan Turing et de son article de 1950 sur le test de turing. En 1943 deux chercheurs représentent le fonctionnement des neurones avec des circuits électriques, c'est le début de la théorie sur les réseaux neuronaux. En 1952 Arthur Samuel écrit un programme capable de s'améliorer en jouant aux dames. Depuis les progrès ne font que continuer et le machine learning est probablement le secteur de l'informatique le plus en expansion (reconnaissance faciale, conduite automatique, création de vaccins, aide à la prise de décision (data scientist),...).

Il existe dans ce domaine, différentes approches qu'il est intéressant de connaitre:

• Apprentissage supervisé: on a des exemples que l'on sait classer et qui sont déjà classées. L'ordinateur apprend avec les exemples et leur réponse, puis teste. Par exemple pour distinguer si l'on a une photo de chat ou de chien, l'ordinateur va analyser des centaines de photos dont il a la réponse.
• Apprentissage non supervisé: l'ordinateur a des exemples mais ne connait pas la réponse.
• Apprentissage par renforcememnt: l'algorithme apprend en observant ce qu'il essaye. Un système de récompense/punition lui permet d'améliorer ses choix. L'ordinateur joue au hasard au début et plus il apprend moins il joue au hasard et utilise ce qu'il a trouvé comme 'bonne méthode'. C'est avec ce genre de méthode que l'ordinateur peut apprendre à jouer à differents jeux. Le plus difficile est de choisir ce qui va être une récompense et ce qui sera une sanction. Un exemple des années 1990: les ascenseurs. Optimiser le programme de plusieurs ascenseurs pour une même tour.
• Apprentissage par transfert: utiliser des comptétences déjà apprises sur des nouvelles taches qui ont des points communs.

Description du problème

Notre problème est assez simple: on relève sur des objets de différentes classes des paramètres. On sait donc que pour tel objet de telle classe, on a tels paramètres. L'objectif est de pouvoir prévoir à quelle classe appartient un nouvel objet uniquement à l'aide de ses paramètres. il s'agit clairement d'un apprentissage supervisé.

Le terme de k-means (k plus proches voisins) a été utilisé par James MacQueen en 1967 mais la méthode utilisée dès 1957 par Bell Labs.

L'idée des k plus proches voisins est assez simple. Puisque l'on connait la classe et les paramètres de plusieurs objets on va dire que notre nouvel objet appartient à la classe dont il a le plus de voisins parmi les k plus proches

Par exemple, si je prends les 3-means d'un nouvel objet, je cherche les 3 voisins les plus proches de cet objet et je regarde à quelle classe ils appartiennent. Cela va déterminer à quelle classe on va attribuer le nouvel objet.

Voici un dessin. En bleu les chats, en rouge les chiens. On admet que x et y sont deux données mesurées sur les animaux qui permettent la discrimination (ces données sont bien sûr fictives, mais pour illustrer disons le poids et la taille). En bleu les chats, en rouge les chiens et en vert l'animal à prédire. On utilise la distance Euclidienne mais ce n'est pas une obligation.

Ci-dessus, avec les k plus proches voisins et k=7 on prédit que le vert est un chat.

Ci-dessus, la réponse change en fonction de k! Avec k=3 on répond un chat, avec k=5..un chien !

L'algorithme des k plus proches voisins

Tout réside dans le calcul de la distance entre le nouvel objet et les objets connus. Dans un repère orthogonal, avec donc 2 paramètres, c'est simple. Pour rester très général et donc multidimensionnel, nous allons imaginer qu'il existe une fonction distance(objet1,objet2).

Voici un algorithme simplifié qui suffit dans le cas de 2 couleurs comme dans le cours. Il est facilement adaptable à 3 couleurs mais à partir d'un nombre d'étiquettes (ici les couleurs) important mieux vaux regarder le second algorithme.

# fonction qui va retourner la liste des k plus proches voisins

# les plus proches d'un élément du plus proche au plus lointain.

➦ fonction k_plus_proches_voisins,

paramètres: liste des objets connus

            nouvel objet

            k: nombre de voisins

➦   Pour tous les objets connus

➦    calculer la distance entre objet connu et nouvel objet

➦    ajouter dans une liste 'liste_distance': cette distance et la couleur de l'objet

➦   ranger liste_distance dans l'ordre croissant des distances

➦   retourner la liste de 0 à k-1

## predire à quel groupe (étiquette) appartient nouvel objet

➦ fonction predire,

  paramètres: liste des objets connus

             nouvel objet

             k: nombre de voisins

➦  kppv = k_plus_proches_voisins(liste objets connus,nouvel objet, k)

➦  couleur={"bleu":0,"rouge":0}

➦   pour tous les éléments de kppv

➦    si étiquette de l'élément= "bleu"

➦        ajouter 1 à couleur["bleu"]

➦    sinon

➦        ajouter 1 à couleur["rouge"]

➦  si couleur["bleu"]>couleur["rouge"]

➦      renvoyer "bleu"

➦  sinon

➦      renvoyer "rouge"  

A noter que la première fonction peut être codée autrement. Si l'on veut k voisins. On prends les éléments un à un et au fur et à mesure on mémorise la plus grande distance. Dès que l'on a k valeurs dans la liste, on remplace l'élément max si on rencontre un élément plus près. Attention il faut alors retrouver le nouveau max. Cela peut paraître plus compliqué. Nous disposons de la commande sorted pour ranger nos listes et cette dernière est rapide et simple à mettre en oeuvre si le critère de tri est compris par python; du coup dans notre cas nous préférons l'algorithme proposé en premier. Mais si l'on veut ranger une liste selon un critère non numérique ou alphabétique, sorted sera inutilisable. Ranger dans l'ordre sera probablement plus couteux que la méthode que je viens jsute de décrire.

Voici un algorithme plus général:

# fonction qui va retourner la liste des k kvoisins

# les plus proches d'un élément du plus proche au plus lointain.

➦ fonction k_plus_proches_voisins,

  paramètres: liste des objets connus

              nouvel objet

              k: nombre de voisins

➦   Pour tous les objets connus

➦    calculer la distance entre objet connu et nouvel objet

➦    ajouter dans une liste 'liste_distance': la distance et le type de l'objet(son étiquette)

➦   ranger liste_distance dans l'ordre croissant des distances

➦   retourner la liste de 0 à k-1

## predire à quel groupe (étiquette) appartient nouvel objet

➦ fonction predire,

  paramètres: liste des objets connus

               nouvel objet

               k: nombre de voisins

➦  kppv = k_plus_proches_voisins(liste objets connus,nouvel objet, k)

➦  initialiser compteur_etiquette à [0] * nombre d'étiquettes différentes (liste donc de 0)

➦   pour tous les éléments de kppv

➦    pour i de 0 au nombre d'étiquettes-1

➦      si étiquette de l'élément égal à  étiquette[i]

➦        ajouter 1 à compteur_etiquette[i]

➦  renvoyer (etiquette[index_maxi(compteur_etiquette)])

Le cours qui suit est issu de : https://mrmint.fr/introduction-k-nearest-neighbors

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

By Younes Benzaki | 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.

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 Learning. Pour 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 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 régression, c’est la moyenne (ou la médiane) des variables des plus proches observations qui servira pour la prédiction.
• Si K-NN est utilisé pour la classification, c’est le mode des variables des plus proches observations qui servira pour la prédiction.

Écriture 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.
• une fonction de définition distance.
• Un nombre entier.

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

1. Calculer toutes les distances de cette observation avec les autres observations du jeu de données.
2. Retenir les observations du jeu de données les proches de en utilisation la fonction de calcul de distance.
3. Prendre les valeurs des observations retenues :
   1. Si on effectue une régression, calculer la moyenne (ou la médiane) de retenues.
   2. Si on effectue une classification, calculer le mode de 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.

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 électronique 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 :

Distance Manhattan :

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

Distance Hamming :

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

avec

• x = y => D = 0
• x ≠ y => 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 à 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 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 nombre de voisins avec et é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.

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.

Également, le choix de la méthode de calcul de la distance ainsi que le nombre de voisins 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.