Fiche de révision : Algorithmes d'apprentissage

Méthode des plus proches voisins

Principales caractéristiques

• 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.

Classification ou régression

• 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.

Distance du voisinage

• 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.

Nombre k de voisins

• 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.

Implémentation d’un algorithme des k plus proches voisins

• 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.

Base algorithmique

• 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.

Incidence du nombre de voisins

Modalités d’emploi de l’algorithme des 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.

Enjeux techniques et sociétaux des algorithmes d’apprentissage

Test de Turing

• 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.

Abondance des données

• 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.

Biais algorithmiques

• 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.