Cours : Algorithmes d'apprentissage

Méthode des plus proches voisins

L’algorithme des plus proches voisins est un algorithme très répandu. Il est notamment employé pour proposer des recommandations de livres, de films ou de musique. Ces recommandations sont basées sur les comportements d’autres utilisateurs ayant lu, vu ou entendu les mêmes médias. On peut aussi l’employer pour la reconnaissance d’images.

Assez simple de conception, cet algorithme se contente en effet d’analyser les éléments les plus proches d’un élément donné, pour en déduire à quelle catégorie cet élément est le plus susceptible de se rattacher.

Définition

L’algorithme des plus proches voisins est une méthode d’apprentissage automatique qui appartient au champ d’étude de l’intelligence artificielle.

Définition

Algorithme des plus proches voisins :

L’algorithme des plus proches voisins est une méthode d’apprentissage automatique capable de proposer des prédictions sur de nouvelles données, en s’appuyant sur les caractéristiques connues d’éléments proches de ceux à prédire.

Cet algorithme est parfois abrégé KNN ou k-NN, qui est la contraction de son appellation anglaise « k-nearest neighbors ». La lettre $k$ désigne de manière générique le nombre de voisins pris en compte par l’algorithme.

Découvrons maintenant les caractéristiques de cet algorithme.

Principales caractéristiques

L’algorithme des plus proches voisins s’intéresse aux voisins d’un élément inconnu, pour déterminer à quelle catégorie cet inconnu est susceptible d’appartenir.

À retenir

La méthode algorithmique des plus proches voisins est une méthode d’apprentissage supervisé. Cela signifie que l’algorithme travaille sur des données qui ont été préalablement étiquetées, appelées données d’apprentissage. L’algorithme s’appuiera sur l’apprentissage effectué à partir de ces données étiquetées, pour proposer un étiquetage pour de nouvelles données.

• L’algorithme des plus proches voisins a besoin de cet étiquetage pour effectuer ses prévisions, contrairement à certains autres algorithmes d’apprentissage qui reposent sur une méthode dite non supervisée.

La méthode algorithmique des plus proches voisins est aussi une méthode non paramétrique. Cela signifie qu’elle ne suppose pas une distribution statistique particulière des données utilisées pour l’apprentissage, contrairement à d’autres méthodes qui ont besoin de se référer à un modèle statistique.

Classification ou régression

L’algorithme des plus proches voisins est utilisable pour la classification et la 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.

La notion de distance par rapport au voisinage est centrale à cet algorithme. Nous allons maintenant la préciser.

Distance du voisinage

L’algorithme des plus proches voisins se base sur la distance entre un nouvel élément inconnu et ceux issus des données d’apprentissage.

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.

On peut calculer une distance entre deux points dans un plan, mais aussi la distance entre deux chaînes de caractères ou deux brins d’ADN. Il faut surtout retenir que l’algorithme des plus proches voisins ne repose pas sur une distance en particulier : il est applicable avec toute distance adaptée au type de données traitées.

Le nombre de voisins pris en compte par l’algorithme a également une importance.

Nombre $k$ de voisins

La lettre « k », de l’abréviation k-NN, traduit le nombre de voisins pris en compte pour effectuer la prédiction. Assez trivialement quand $k$ vaut $1$, l’élément inconnu est évalué comme son voisin le plus proche.

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, il n’existe pas de valeur unique de $k$ pour un résultat optimal, mais les valeurs donnant des bons résultats sont significativement inférieures à la taille du jeu de données tout en étant supérieures à $1$.

Nous allons maintenant implémenter un algorithme des plus proches voisins.

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.

Notre implémentation est réalisée sans faire appel à aucun module spécialisé, afin de bien comprendre dans le détail la méthode des $k$ plus proches voisins.

Base algorithmique

Notre objectif est de pouvoir classifier un nouvel élément inconnu sur la base de ses plus proches voisins. Nous lui attribuerons la classe majoritairement représentée parmi ses voisins immédiats. Notre programme pourra fonctionner pour un nombre quelconque de voisins.

À retenir

• Notre programme s’appuiera sur :
• un ensemble de données ;
• une fonction de calcul de distance ;
• 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 ;
• retenir uniquement les $k$ éléments les plus proches ;
• déterminer parmi ces $k$ éléments les plus proches, en déterminer la classe majoritaire ;
• fournir une prédiction de la classe de l’élément inconnu, sur la base de cette classe majoritaire.

Nous allons procéder étape par étape, en implémentant chaque portion de notre algorithme.

Pour le rendre concret, nous travaillerons sur un programme capable de prédire si un fruit est une pomme ou une poire.

Stockage des éléments

Notre ensemble de données est composé d’éléments individuels, chaque élément étant caractérisé par :

• ses coordonnées ;
• sa classe d’appartenance.

Les coordonnées sont définies sous forme de tuples $(x,y)$ et correspondent à deux caractéristiques arbitraires des fruits. La classe d’appartenance est une chaîne de caractères qui précise si le fruit est une pomme ou une poire.

Nous stockons l’ensemble de ces données individuelles sous forme de liste.

Développons maintenant une fonction de calcul de distance entre deux éléments quelconques.

Calcul de distance

Dans notre cas d’étude nous calculerons la distance euclidienne entre deux éléments, de coordonnées $(x_{1},y_{1})$ pour l’élément 1 et $(x_{2},y_{2})$ pour l’élément 2.

La formule mathématique de calcul de la distance euclidienne est la suivante : $$d=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}$$

• Notre fonction calcule et retourne la distance euclidienne.

Notre fonction reçoit en entrée deux tuples de coordonnées et retourne en sortie leur distance euclidienne.

• Cette fonction sera notre outil de calcul pour toutes les distances entre voisins.

Distances du voisinage

Calculons maintenant les distances d’un élément quelconque avec chacun des éléments de notre ensemble de données, et stockons les résultats dans une liste. La classe de chaque élément de comparaison est aussi stockée dans cette liste. Nos résultats sont donc des tuples de distance et de classe.

Nous trions ensuite cette liste par distance croissante et nous ne retenons que les $k$ premiers éléments.

Testons notre fonction avec un élément inconnu de coordonnées $(3,4)$ et un nombre de voisins fixé à $3$.

La fonction plus_proches_voisins() retourne une liste de longueur $k$ basée sur les voisins les plus proches de l’élément inconnu. Chaque élément de cette liste est un tuple composé de la distance euclidienne par rapport à l’élément inconnu et de la classe du fruit situé à cette distance.

Reste maintenant à déterminer quelle est la classe majoritaire parmi les plus proches voisins.

Détermination de la classe majoritaire

Comme précisé en préambule de notre implémentation, la prédiction de notre programme est basée sur la classe majoritaire. Nous devons donc déterminer quelle est la classe majoritaire dans la liste des plus proches voisins, produite par la fonction précédente.

Nous développons donc, une nouvelle fonction qui effectuera le comptage des différentes classes pour retourner la classe majoritaire.

Nous utilisons un dictionnaire pour compter les occurrences. Nous le convertissons ensuite en liste de tuples et nous trions cette liste par nombre décroissant d’occurrences. Il nous suffit ensuite, de retourner la classe du premier élément de la liste triée. Il correspond à la classe majoritaire.

Attention

Notons que nous convertissons le dictionnaire en liste de tuples car un dictionnaire ne peut pas, par définition, être ordonné (il n’est pas organisé selon un index numérique mais selon une clé, ici la classe).

Pour la composition de la liste nommée « classement », nous avons eu recours à une compréhension de liste, présentée dans le cours « Tableaux et matrices ». Nous aurions également pu composer cette liste avec une boucle de la manière suivante :

Équivalent à :

Reprenons l’exemple précédent pour vérifier que notre fonction classe_majoritaire() produit le résultat attendu.

Dans notre exemple un fruit est soit une pomme, soit une poire. On aurait donc pu simplement utiliser un branchement conditionnel et incrémenter deux compteurs nombre_pommes et nombre_poires. Mais notre fonction telle que nous l’avons implémentée, sera capable de déterminer la classe majoritaire d’un élément quels que soit le nombre de classes et le nombre d’éléments dans les données d’apprentissage.

Incidence du nombre de voisins

Nous avons testé la classification d’un élément inconnu avec $3$ voisins. Comparons avec la classification obtenue pour $5$ voisins.

Le résultat est identique. Mais ce n’est pas toujours le cas. Tout dépend des voisins, comme nous allons le voir avec un autre élément.

Exemple

Testons notre fonction avec un élément inconnu de coordonnées $(4,6)$ et le nombre de voisins fixé à $3$ :

print(classe_majoritaire(plus_proches_voisins((4, 6), fruits, 3)))

# affiche poire

Mais si nous fixons le nombre de voisin à $5$, avec les mêmes coordonnées pour l’élément inconnu :

print(classe_majoritaire(plus_proches_voisins((4, 6), fruits, 5)))

# affiche pomme

L’illustration suivante montre l’élément inconnu et ses plus proches voisins. L’inconnu est matérialisé par le triangle rouge. Les pommes sont représentées par des cercles verts et les poires par des carrés bleus. Le cercle en trait plein montre les $3$ plus proches voisins $(k = 3)$ de l’élément à évaluer. Le cercle en trait pointillé montre les $5$ plus proches voisins $(k = 5)$ de l’élément à évaluer.

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

Notre programme prédit la classe de l’élément évalué en fonction de la classe majoritaire. Dans notre exemple, le fruit inconnu de caractéristiques $(4, 6)$ est entouré par une majorité de poires si l’on considère ses $3$ voisins immédiats, mais par une majorité de pommes si l’on considère ses $5$ voisins immédiats.

Mise en perspective de notre implémentation

Nous aurions pu avoir recours à un module spécialisé pour réaliser ce comptage des classes de manière plus automatique. De même il existe des modules spécialisés qui intègrent l’algorithme des $k$ voisins les plus proches et permettent de le mobiliser en quelques lignes de code. Mais dans le cadre de notre implémentation à but pédagogique, nous avons pu constater qu’il est possible de réaliser un tel programme, uniquement avec les éléments de base du langage.

Cela nous permet de prendre conscience que les constructions avancées des langages, qui peuvent parfois paraitre « magiques », sont en réalité le résultat de l’enchainement logique d’étapes et de traitements assez simples.

Modalités d’emploi de l’algorithme des plus proches voisins

Maintenant que nous avons une compréhension concrète du fonctionnement de l’algorithme des plus proches voisins, nous allons nous intéresser à ses modalités d’emploi et à ses performances.

Classes et paramètres multiples

Notre implémentation pédagogique comportait uniquement deux classes et deux caractéristiques pour chaque élément, mais l’algorithme des plus proches voisins est applicable à des jeux de données comportant un nombre quelconque de classes ainsi qu’à un nombre potentiellement élevé de paramètres.

Pondération de la distance

Dans notre implémentation, tous les éléments retenus comme proches voisins ont la même importance et la majorité l’emporte. Notre algorithme accorde la même importance à tous les $k$ voisins retenus comme proches. Il ne fait aucune différence entre un voisin très proche de l'élément à déterminer et un autre voisin plus éloigné.

Il est cependant 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é.

Choix de la valeur de $k$

Comme nous l’avons expérimenté avec notre implémentation, la valeur choisie pour le nombre $k$ de voisins peut avoir une incidence sur le résultat produit.

Il n’existe pas de règle universelle pour choisir la valeur de $k$, son choix dépend du jeu de données.

On peut comparer les résultats produits par l’algorithme, pour différentes valeurs de $k$ en n’utilisant pas la totalité du jeu de données pour la prédiction et on en conserve une partie servant à évaluer l’algorithme.

On dispose ainsi d’un jeu de test composé de données étiquetées, ce qui nous permet de vérifier les prédictions de l’algorithme. Nous pouvons ensuite choisir une valeur de $k$ qui tend à minimiser les erreurs de classification, sans pour autant être trop parfait par rapport aux données d’apprentissage : il faut trouver un juste milieu entre la variabilité avec une valeur basse et le sur-lissage avec une valeur élevée.

En effet le but d’un algorithme d’apprentissage est d’être capable d’effectuer ensuite des prédictions fiables sur des nouvelles données inconnues. 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. On désigne ce phénomène par un sur-apprentissage (overfitting en anglais).

• Le choix du nombre de voisins n’est pas le seul paramètre influant sur la performance de notre algorithme d’apprentissage. Il faut également prendre en compte la qualité des données utilisées pour l’apprentissage.

Qualité du jeu de données

Dans la mesure où, un algorithme d’apprentissage a vocation à généraliser sa capacité à prédire la classification d’un élément inconnu à partir de ses voisins connus, il est essentiel que le jeu de données constitué pour l’apprentissage ne comporte pas de biais importants.

Même si l’algorithme des plus proches voisins n’est pas tributaire d’un modèle statistique en particulier, 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 anecdotiques, ou encore un déséquilibre important dans la représentation des différentes classes.

Exemple

On comprend aisément que si notre jeu de données expérimental qui comportait dix fruits avait comporté huit pommes, notre algorithme aurait eu tendance à voir des pommes presque partout.

Avantages et inconvénients de l’algorithme des plus proches voisins

• Au rang des avantages, cet algorithme :
• est très simple à implémenter ;
• n’est pas tributaire d’un modèle statistique ;
• permet facilement l’ajout de données au jeu d’apprentissage ;
• nécessite seulement deux paramètres (la valeur de $k$ et une fonction de calcul de distance adaptée aux données).
• Au rang des inconvénients, cet algorithme devient coûteux à exploiter quand les jeux de données sont importants :
• en espace mémoire pour stocker l’ensemble du jeu de données ;
• en temps d’exécution pour le calcul de l’ensemble des distances.

L’algorithme des plus proches voisins appartient à la famille des algorithmes d’apprentissage dont l’essor fulgurant ces dernières années n’est pas sans enjeux tant au niveau technique que sociétal.

Enjeux techniques et sociétaux des algorithmes d’apprentissage

Les algorithmes d’apprentissage sont rattachés au champ d’étude de l’intelligence artificielle. Cette expression d’intelligence artificielle s’est imposée pour désigner les simulations d’intelligence réalisées par des machines capables d’apprentissage. Elle est cependant critiquée sur l’emploi du terme intelligence, qui prête à confusion et suscite fantasmes et inquiétudes.

Test de Turing

Définir l’intelligence humaine ou animale n’est pas chose aisée et la tâche l’est tout autant sinon plus pour une machine. Il existe toutefois un test imaginé en 1950 par le mathématicien britannique Alan Turing. Ce test porte le nom de son inventeur.

• Le test de 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.

Pour réussir le test de Turing, la machine doit se faire passer pour un humain. Elle doit suffisamment bien imiter une conversation humaine par écrans interposés pour que la personne qui interagit avec elle ne parvienne pas à la distinguer du véritable humain qui converse également avec elle.

Ce test d’intelligence simulée est lui aussi critiqué car il ne mesure pas vraiment l’intelligence de la machine mais seulement sa capacité à imiter les comportements d’un humain. Il peut, toutefois, servir à illustrer l’illusion d’intelligence croissante dont sont capables les machines modernes.

Abondance des données

La quantité et la diversité des données collectées et traitées chaque année augmentent à une vitesse inédite. Les algorithmes d’apprentissage peuvent donc s’appuyer sur des volumes colossaux d’information pour bâtir leur « intelligence », ou du moins leur capacité à effectuer des prédictions ou à remarquer des corrélations parmi des données très nombreuses.

La facilité avec laquelle les données peuvent être collectées et stockées n’est pas sans poser des problèmes :

• techniques avec la nécessité de disposer d’espaces de stockage toujours plus importants ;
• économiques avec la nécessité de disposer d’une puissance de calcul suffisante pour effectuer les traitements ;
• écologiques dans la mesure où le stockage et le traitement des données consomment des ressources (en particulier de l’électricité pour l’alimentation des ordinateurs et les climatisations qui les refroidissent, de la matière pour la confection des disques et des ordinateurs) ;
• légaux et éthiques avec les potentielles atteintes à la vie privée liées à la collecte, au recoupement et à l’archivage de données personnelles.

Les enjeux ne concernent pas seulement les volumes toujours croissants de données, mais aussi la diversité de leurs contenus.

Biais algorithmiques

La composition des jeux de données est également cruciale.

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.

Exemple

• Un algorithme de reconnaissance de visages fiable à plus de $99\ \%$ pour des hommes blancs s’est révélé commettre des erreurs dans près de $35\ \%$ des cas pour des femmes noires.

• Un programme de traduction automatique depuis une langue non genrée traduisait systématiquement le métier de médecin au masculin et celui d’infirmier au féminin.

Les éditeurs de solutions basées sur des algorithmes d’apprentissage doivent avoir une vigilance particulière envers les performances de leurs produits. Ils doivent en particulier éviter que ceux-ci ne causent ou n’entretiennent des discriminations ou des biais du fait de jeux d’apprentissage insuffisamment diversifiés et représentatifs.

Les progrès réalisés ces dernières années en matière d’algorithmes d’apprentissage ont été fulgurants. Leurs apports sont indéniables dans de nombreux domaines pour le diagnostic, l’optimisation ou l’aide à la décision. Il faut néanmoins être conscient des enjeux qui accompagnent ces progrès.