Algorithme des K-plus proches voisins

Cours en pdf

Dans cours, on se propose de découvrir ce qu’est le « machine learning » et en particulier un de ces algorithmes: L’algorithme des plus proches voisins.

On attend beaucoup parler d’Intelligence artificielle et d’algorithme d’apprentissage (« machine learning » en anglais) … Mais de quoi s’agit-il exactement ?

Regarder la vidéo jusqu’à la 14min30 (au moins) puis répondre aux questions posées  :

On va découvrir un algorithme d’apprentissage d’intelligence artificielle appelé « algorithmes des k plus proches voisins, en anglais « de l’anglais k-nearest neighbors »  ce qui lui vaut souvent l’abréviation de k-NN.

Pour cet algorithme d’apprentissage, on dispose d’un jeu de données d’apprentissage c’est-à-dire des données que l’on sait parfaitement classifier : Dans l’exemple de la vidéo, des fruits dont on connait le diamètre et le type orange ou clémentine.

L’objectif est de pouvoir donner le type d’un fruit en fonction de diamètre.
De ce fait, le diamètre est appelé l’entrée et son type la sortie.

Imaginons… On étudie des papillons. Ceux-ci ont une certaine largeur et une certaine longueur. Certains sont des males, d’autres des femelles.

On étudie un certain nombre de ces papillons. Cela constitue un jeu d’apprentissage dont les caractéristiques sont représentées ci-dessous.

A partir de ce jeu d’apprentissage, on cherche à prédire le sexe d’un papillon dont on connaît les dimensions.

On parle donc d’algorithme de prédiction.

L’objectif est maintenant d’identifier le sexe d’un nouveau papillon en s’appuyant sur notre expérience précédente.

Le principe est simple : On fait l’hypothèse que notre papillon a le même sexe que ces voisins.

Pour ce premier cas, on n’a pas beaucoup d’hésitation : Le papillon est « au milieu » des femelles :
On peut raisonnablement penser que c’est une femelle.
: Dans ce second cas, il est plus difficile de savoir… C’est là qu’intervient l’ »algorithme des k-plus proches voisins ».

On décide que le papillon a le même sexe que ces k-plus proches voisins

Ici, on a décidé (c’est un choix arbitraire !) de regarder les 5 plus proches voisins. Parmi eux, 3 sont des mâles, 2 sont des femelles : On fait donc l’hypothèse que notre papillon est un mâle.

Que prévoit-on si on prend k=1, k=3, k=7 ou k=6 ?

Utilisez le fichier geogebra et LearningApps pour vérifier.

L’algorithme des k plus proches voisins nécessite pour pouvoir classer un nouvel élément d’avoir conservé en mémoire l’ensemble des données du jeu d’apprentissage.

De ce fait, il nécessite des capacités de calcul importantes ou de petits jeux de données d’apprentissage.

Le choix du nombre k est, vous l’avez constaté auparavant crucial.

Un autre paramètre important est celui de la métrique, c’est-à-dire de la distance, utilisée.


STOP : fin de la partie à avoir travaillée pour le cours du 25 mars
Maintenant, vas sur l’ENT et fais le travail demandé.


Etudions un nouvel exemple : La carte scolaire. En fonction de leur lieu d’habitation, les enfants sont scolarisés dans l’école 1 (en bleue) ou dans l’école 2 (en vert).

Une nouvelle maison est construite (Aclasser ci-contre)

En utilisant l’algorithme des k plus proches voisins et la distance habituelle, déterminer :

  • Pour k=5, dans quelle école iront les enfants ?
  • Quelle est la plus petite valeur de k pour laquelle les enfants iront à l’école verte ?

Une nouvelle métrique : Le quadrillage correspond à des routes que l’on doit emprunter obligatoirement. La distance est donc le nombre de segments. Par exemple, la « Maison1 »  est à une distance de 4 de la maison à classer. 

Quel est alors l’école pour cette métrique et pour k=7 ?


Conclusion : L’algorithme des k plus proche voisin est un des plus simples algorithmes d’apprentissage.
Malgré sa simplicité, pour qu’il puisse contribuer à des prévisions correctes, il faut avoir un jeu de données important (d’où l’enjeu des données personnelles dont les GAFAM sont si gourmandes).
Le principe étant de disposer d’un jeu d’apprentissage et d’un jeu de test (un ensemble de données sur lesquelles ont connait la réponse et on évalue la fiabilité de la prédiction). Le travail de mise au point (choix de k ici est fondamental).


L’algorithme

Maintenant que nous avons compris le principe de cet algorithme, reste à l’écrire, d’abord en langage naturel.

Algorithme_KNN(Inconnu, k, jeu d’apprentissage) :
Pour chaque donnée D du jeu d’apprentissage :

  • Calculer la distance (Inconnu, D)
  • La mémoriser dans une liste ListeD

Trier la ListeD dans l’ordre croissant
Choisir les k premières valeurs de cette liste
Renvoyer la valeur majoritaire parmi ces k valeurs.

Et la complexité ?

Ce qui est « coûteux » dans cet algorithme, c’est la mémorisation du jeu d’apprentissage.
Dès que l’on veut s’appuyer sur un nombre conséquent de données d’apprentissage, on doit mémoriser toutes ces données dans des tableaux. Ensuite, ces données sont utilisées pour chaque prédiction. D’autres algorithmes exploitent les données une fois pour toutes.
L’algorithme K-NN est donc lent dès que le jeu d’apprentissage est important.

Remarques sur la complexité (hors programme) :
Imaginons que le jeu d’apprentissage a n données.
Dans l’algorithme ci-dessus :

  • on parcourt le jeu de données pour calculer les distances O(n)
  • on trie la liste O(n²)

Ce qui nous donnerait une complexité en O(n²). Or, si vous allez chercher des informations sur la complexité de cet algorithme, vous verrez que sa complexité est en O(n) seulement.
Pourquoi ?
Inutile en fait de stocker et de trier la liste des distances : Il suffit de la parcourir le jeu de données et de conserver au fur et à mesure la liste des k-voisins les plus proches. Si on rencontre une donnée plus proche, on la conserve et on supprime celle qui était moins bonne – exactement comme quand on cherche le maximum.

Bilan :

  • (+) L’algorithme est simple et facile à mettre en œuvre.
  • (-) Le choix de la distance et du nombre de voisins peut ne pas être évident.

L’algorithme kN-voisin (KNN) est un algorithme d’apprentissage simple à mettre en œuvre et à comprendre, mais présente l’inconvénient majeur de ralentir considérablement à mesure que la taille des données utilisées augmente.

En résumé, KNN recherche les distances entre une « inconnu » et toutes les données de la base d’apprentissage, sélectionne le nombre spécifié exemples (K) les plus proches de la requête, puis vote pour l’étiquette la plus fréquente.

Ajoutons que cet algorithme peut aussi être utilisé sur des données dont la sortie est un nombre réel. Dans ce cas, l’algorithme renvoie la moyenne des étiquettes à la place de l’étiquette la plus fréquente. On parle alors d’algorithme de régression.

TP :

On va utiliser l’algorithme K-NN pour reconnaître la langue d’une phrase.
Principe : On va choisir comme entrées les fréquences de deux lettres. On choisit le « u » et le « h ».
Le jeu d’apprentissage sera constitué de phrases

  • en français : un extrait de « la Princesse de Clèves ») et
  • en anglais : un extrait de « Pride and Prejudice ».

Pour chaque phrase, on calcule la fréquence des « u » et des « h » dans cette phrase.
On mémorise [freqU, freqH] dans une liste.
Ainsi, si on a trois phrases en français, on obtient une liste qui ressemble à :
[[0.02,0.12],[0.04,0.16],[0.03,0.10]] dans laquelle 0.02 est la fréquence des U dans la première phrase.
On rappelle fréquence des U = nombre de U dans la phrase / nombre total de caractères.

Une fois le jeu d’apprentissage réalisé, on l’utilise pour déterminer la langue d’une phrase inconnue en utilisant :

  • la distance usuelle
  • k = 5

Piste verte :

Télécharge le programme « clé en main.

Je te conseille de télécharger tous les fichiers dans le même dossier de ton ordinateur.

Analyse le programme et détermine la ligne à modifier pour changer la phrase à analyser ou la valeur de k.

« Amuse » toi avec plusieurs phrases et plusieurs valeurs de k.

Piste Bleue :

Voir le TP

Piste Noire :

Voir le TP

Tu peux bien sûr « tricher » en jetant un coup d’oeil à la piste bleue…

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Créez votre site Web avec WordPress.com
Commencer
%d blogueurs aiment cette page :