Fiche de révision Algorithmes d'apprentissage

Méthode des plus proches voisins

L’algorithme des plus proches voisins a besoin d’être supervisée pour effectuer ses prévisions.
C’est une méthode non paramétrique.
C’est aussi une méthode d’apprentissage automatique appartenant au champ d’étude de l’intelligence artificielle.

Le résultat produit par l’algorithme est une classification, quand il est utilisé pour prédire à quelle catégorie appartient le nouvel élément inconnu, à partir des catégories des voisins ;
Le résultat produit par l’algorithme est une régression, quand il est utilisé pour prédire une valeur numérique moyenne issue des valeurs des voisins.

Il existe différentes manières de calculer les distances entre les données :
pour les variables continues on emploie généralement la distance euclidienne ;
pour les variables discrètes on pourra employer la distance de Hamming.
L’algorithme des plus proches voisins est applicable avec toute distance adaptée au type de données traitées.

Dans l’absolu, l’algorithme peut fonctionner pour toute valeur de k inférieure ou égale à la taille du jeu de données.
Dans la pratique les valeurs donnant des bons résultats sont significativement inférieures à la taille du jeu de données tout en étant supérieures à 1.

Notre algorithme sera capable de prédire la classe d’un nouvel élément, en fonction de la classe majoritaire de ses k plus proches voisins.

Notre programme s’appuiera sur : un ensemble de données, une fonction de calcul de distance et un nombre entier k représentant le nombre de voisins.
Il sera capable de calculer toutes les distances entre un élément inconnu et chacune des données de notre ensemble, afin de retenir uniquement les k éléments les plus proche, pour ensuite déterminer parmi ces k éléments les plus proches c’est-à-dire la classe majoritaire pour enfin fournir une prédiction de la classe de l’élément inconnu, sur la base de la classe majoritaire.

L’illustration suivante montre l’élément inconnu et ses plus proches voisins. L’inconnu est matérialisé par le triangle rouge.
Dans notre exemple, le fruit inconnu de caractéristiques (4, 6) est entouré par une majorité de rectangles si l’on considère ses 3 voisins immédiats, mais par une majorité de ronds si l’on considère ses 5 voisins immédiats.

K plus proches voisins L’élément inconnu et ses plus proches voisins

L’algorithme des plus proches voisins est aussi applicable à des jeux de données comportant un nombre quelconque de classes ainsi qu’à un nombre potentiellement élevé de paramètres.
Il est possible de prendre en compte l’éloignement en introduisant une pondération du vote, qui est inversement proportionnelle à la distance par rapport à l’élément évalué.
Il n’existe pas de règle universelle pour choisir la valeur de k. Son choix dépend du jeu de données.
Si notre algorithme est trop parfaitement adapté aux données d’apprentissage, il pourrait avoir du mal à se généraliser à des données jamais rencontrées auparavant, c'est un sur-apprentissage (overfitting en anglais).
Il convient d’éviter des déséquilibres majeurs dans le jeu de données, comme la sur-représentation de valeurs extrêmes ou encore un déséquilibre important dans la représentation des différentes classes.

Avantages	Inconvénients
très simple à implémenter	coûteux en espace mémoire pour stocker l’ensemble du jeu de données
pas tributaire d’un modèle statistique	coûteux en temps d’exécution pour le calcul de l’ensemble des distances
nécessite seulement deux paramètres	$$

Le test de Turing, imaginé en 1950 par Alan Turing, consiste en des conversations écrites à l’aveugle entre une personne et deux interlocuteurs et l’un des interlocuteurs est un humain et l’autre est une machine.
Ce test d’intelligence simulée mesure l’intelligence de la machine par sa capacité à imiter les comportements d’un humain.

La facilité avec laquelle les données peuvent être collectées et stockées n’est pas sans poser des problèmes techniques, économiques, écologiques ou encore légaux et éthiques.

Si les jeux de données ne sont pas représentatifs de la diversité des cas de figures possibles, la performance de l’algorithme ne sera pas homogène ou pas satisfaisante.