enseignements informatiques
s'identifier
portail personnel ETNA
espace pédagogique > disciplines du second degré > enseignements informatiques > enseignement > nsi
algorithme des k plus proches voisins
mis à jour le 07/02/2023
Un algorithme utilisé en I.A. ça vous tente ?
mots clés : algorithme, IA
Dans un précédent article, David Landry proposait un mini-projet de modélisation numérique du célèbre Choixpeau en utilisant l'algorithme des k plus proches voisins. Dans le présent article, il nous propose un cours (et ses activités associées ) sur ce même algorithme en prenant appui sur le tournoi de rugby des VI nations : comment trouver la place de Caliméro dans l'équipe en connaissant son gabarit ?
Ce cours s'appuie sur les données officielles des joueurs des équipes présentes au tournoi.
L'ensemble des documents est disponible sur le dépôt gitlab de l'auteur : https://gitlab.com/david_landry/nsi
Algorithme des k plus proches voisins
Un algorithme pour l'intelligence artificielle
L’algorithme des k plus proches voisins (abrégé par kPPV) est l’un des algorithmes utilisés dans le domaine de l’intelligence artificielle (IA). Il intervient dans de nombreux domaines de l’apprentissage automatique.
Cet algorithme est, par exemple, utilisé par des entreprises d'Internet comme Amazon, netflix, Spotify ou iTunes afin de prévoir si vous seriez ou non intéressés par un produit en utilisant vos données et en les comparant à celles des clients ayant acheté ce produit particulier.
Son principe peut être résumé par cette phrase : Dis-moi qui sont tes amis (ou les personnes ayant les mêmes goûts) et je te dévoilerai tes désirs.
Quel joueur de rugby seriez-vous ?
Nous allons voir comment l'algorithme des kPPV peut nous aider à prévoir quel poste pourrait être proposé à un nouveau joueur de rugby, uniquement d'après sa stature (masse et taille).
Avant toute chose, il peut-être important d'énumérer les différents postes existants au rugby. Cette illustration peut y contribuer :
Le site officiel de la fédération internationale propose une page associant les numéros aux noms des positions: https://www.world.rugby/the-game/beginners-guide/positions
Cet algorithme nécessite un jeu de données, le plus large possible. Nous utiliserons les données mises à disposition par l'organisation "Six Nations Rugby Limited". Ces données concernent les équipes des hommes sur la saison 2020-2021, et sont compilées dans le fichier "Joueurs_rugby_6_nations.csv".
Si on simplifie la variété des postes en 3 catégories (Avants, Charnière, Arrières) et que l'on traite ces données graphiquement (avec un tableur ou le module matplotlib de Python), on obtient cela :
On constate à l'oeil nu que certaines caractéristiques se détachent :
On peut donc déjà se convaincre que, dans le cas d'un gabarit extrême, il est assez évident qu'on pourra définir naturellement un poste : il paraîtrait très risqué de proposer un poste d'avant à un homme de 70 kg par exemple.
Pour des gabarits plus "intermédiaires", le choix est plus complexe , surtout si on prend en compte la diversité des postes du rugby :
Si on excepte les très lourds piliers (que l'on appelle d'ailleurs traditionnellement "les gros"), les très grands 2ème ligne et les très petits et legers demi- de mêlée (oui, tout est relatif au rugby...), les autres postes sont plus difficiles à cerner.
Si on ne devait s'en tenir qu'à la stature (ce qui serait stupide...), l'algorithme des kPPV pourrait alors nous être utile.
Ce cours s'appuie sur les données officielles des joueurs des équipes présentes au tournoi.
L'ensemble des documents est disponible sur le dépôt gitlab de l'auteur : https://gitlab.com/david_landry/nsi
L’algorithme des k plus proches voisins (abrégé par kPPV) est l’un des algorithmes utilisés dans le domaine de l’intelligence artificielle (IA). Il intervient dans de nombreux domaines de l’apprentissage automatique.
Remarques
- IA veut dire Intelligence Artificielle en français. En réalité, il s'agit de la traduction de Artificial Intelligence. Or Intelligence en Anglais ne veut pas vraiment dire intelligence en Français !
- Par exemple, Intelligence Service veut dire Service de Renseignements, les services secrets en gros.
- Et c'est ainsi qu'il faut comprendre IA: c'est un ensemble de programmes qui ont pour but d'analyser un ensemble de données pour en tirer une conclusion. Il s'agit donc bien d'un travail d'analyse de données.
Cet algorithme est, par exemple, utilisé par des entreprises d'Internet comme Amazon, netflix, Spotify ou iTunes afin de prévoir si vous seriez ou non intéressés par un produit en utilisant vos données et en les comparant à celles des clients ayant acheté ce produit particulier.
Son principe peut être résumé par cette phrase : Dis-moi qui sont tes amis (ou les personnes ayant les mêmes goûts) et je te dévoilerai tes désirs.
Remarques
- Cet algorithme a été introduit en 1951 par Fix et Hodges dans un rapport de la faculté de médecine aéronautique de la US Air Force.
- En anglais, on parle de l'algorithme "k Nearest Neighbors", que l'on abrège par kNN.
Nous allons voir comment l'algorithme des kPPV peut nous aider à prévoir quel poste pourrait être proposé à un nouveau joueur de rugby, uniquement d'après sa stature (masse et taille).
Avant toute chose, il peut-être important d'énumérer les différents postes existants au rugby. Cette illustration peut y contribuer :
Le site officiel de la fédération internationale propose une page associant les numéros aux noms des positions: https://www.world.rugby/the-game/beginners-guide/positions
Cet algorithme nécessite un jeu de données, le plus large possible. Nous utiliserons les données mises à disposition par l'organisation "Six Nations Rugby Limited". Ces données concernent les équipes des hommes sur la saison 2020-2021, et sont compilées dans le fichier "Joueurs_rugby_6_nations.csv".
Si on simplifie la variété des postes en 3 catégories (Avants, Charnière, Arrières) et que l'on traite ces données graphiquement (avec un tableur ou le module matplotlib de Python), on obtient cela :
On constate à l'oeil nu que certaines caractéristiques se détachent :
- Les avants sont plutôt grands et massiques.
- La charnière (demi de mêlée et demi-d'ouverture) sont des joueurs plus petits et légers.
- Les arrières se situent "à cheval" sur les caractéristiques des deux postes précédents.
On peut donc déjà se convaincre que, dans le cas d'un gabarit extrême, il est assez évident qu'on pourra définir naturellement un poste : il paraîtrait très risqué de proposer un poste d'avant à un homme de 70 kg par exemple.
Pour des gabarits plus "intermédiaires", le choix est plus complexe , surtout si on prend en compte la diversité des postes du rugby :
Remarque : les plus observateurs d'entre-vous auront remarqué un changement d'échelle sur ce second graphique. En effet, le premier graphe avait comme défaut de conserver un certain déséquilibre entre les deux grandeurs (masse et taille). Ce déséquilibre aurait pu entraîner des erreurs lors des calculs de distances dont nous auront besoin plus tard. Les deux grandeurs ont donc été "ré-équilibrées" par une méthode de normalisation, expliquée brièvement dans le notebook d'approfondissement 4_13.
Si on excepte les très lourds piliers (que l'on appelle d'ailleurs traditionnellement "les gros"), les très grands 2ème ligne et les très petits et legers demi- de mêlée (oui, tout est relatif au rugby...), les autres postes sont plus difficiles à cerner.
Si on ne devait s'en tenir qu'à la stature (ce qui serait stupide...), l'algorithme des kPPV pourrait alors nous être utile.
Un nouveau joueur, Caliméro, vient intégrer l'équipe et l'entraîneur ne le connait pas. Il faut lui trouver un poste : quelles sont ses options ?
Caliméro mesure 1m89 et pèse 102 kg.
Voici sa position (croix noire) sur un zoom du précédent graphique :
Nous allons chercher ses plus proches voisins et lui proposer un poste en fonction de ses k plus proches voisins.
Le plus proche voisin de Caliméro est symbolisé par un point orange, c'est donc un ailier.
On pourrait simplement en déduire que Caliméro a la stature d'un ailier ?
Remarques :
nous n'étudierons pas toutes les valeurs de k mais uniquement les plus caractéristiques.
nous privilégierons les k impairs pour éviter autant que possible les cas d'égalité.
nous n'étudierons pas toutes les valeurs de k mais uniquement les plus caractéristiques.
nous privilégierons les k impairs pour éviter autant que possible les cas d'égalité.
Parmi les 3 plus proches voisins de Caliméro, on trouve :
- 1 ailier
- 2 3ème lignes
On pourrait maintenant en déduire que Caliméro a la stature d'un 3ème ligne ?
Parmi les 9 plus proches voisins de Caliméro, on trouve :
- 2 ailiers
- 3 3ème lignes
- 4 centres
On pourrait maintenant en déduire que Caliméro a la stature d'un centre ?
Inutile de consulter le graphique dans ce cas, il suffit de trouver quel poste est le plus présent dans la base de donnée et on pourrait alors en déduire que Caliméro sera parfaitement à sa place au poste de... Pilier !?
En effet, nos données contiennent les informations sur des postes inégalement répartis :
Si on prend une valeur de k maximale, n'importe quel profil de joueur aura donc une majorité de voisins piliers !
On comprend facilement l'absurdité de ce dernier exemple extrême.
On comprend facilement l'absurdité de ce dernier exemple extrême.
On a vu que la détermination d'une catégorie à l'aide de l'algorithme des kNN dépend pour beaucoup du choix de k, le nombre de voisins.
Pour être pertinent, le choix de k est déterminant. Il peut être fait :
- par tatonnement, en fonction de l'expérience que l'on a sur un jeu de données et des résultats obtenus. Cette méthode est par essence risquée,
- par validation croisée, une procédure plus rigoureuse qui sera expliqué dans le notebook d'approfondissement 4_13A.
Pour la suite de notre étude, nous considérerons arbitrairement que la valeur k = 3 est acceptable.
Comme on l'a vu de façon extrême lorsque que k prend une valeur maximale, le résultat dépend du nombre d'éléments présents dans chaque catégorie (chaque poste). Si une catégorie est majoritaire, il est évident qu'elle pourra être statistiquement plus souvent voisine de notre cible que tout autre catégorie.
Ce problème peut être partiellement résolu en équilibrant notre base de donnée, ce qui sera expliqué dans le notebook d'approfondissement 4_13A.
Dans notre exemple, ce rééquilibre pouvant se révéler complexe, on gardera notre effectif de joueurs intact pour notre activité.
Pour connaître les plus proches voisins, il y a une notion de proximité, donc de distance.
Sur les graphiques précédents, on a symbolisé cette distance par un cercle. Sur le suivant, on symbolise chaque distance par un segment noir.
On a donc utilisé ce que l'on appelle une distance euclidienne.
Remarque : il existe d'autres méthodes pour calculer des distances. Vous pourrez les découvrir dans le notebook d'approfondissement 4_13A.
La distance euclidienne est calculée ainsi :
On considère deux points M1 et M2 dans un plan.
- Les coordonnées de M1 sont
.
- Les coordonnées de M2 sont
.
La distance euclidienne de M1 à M2 correspond à la valeur obtenue en réalisant le calcul suivant :
Remarques :
- même si dans notre cas on mesure une distance dans un repère à deux dimensions, rien d'empêche d'utiliser la distance euclidienne pour un nombre de dimension supérieure. Ce pourrait être utile si on souhaite ajouter des caractéristiques aux profils des éléments à comparer (ex: vitesse de course, age,...).
- avec Python, on peut utiliser la racine carré en...
- élevant à la puissance 1/2 (ex : 45 ** 0.5)
- utilisant la méthode sqrt() du module math (ex : math.sqrt(45))
Pour connaître les plus proches voisins de Caliméro, il faut donc calculer les distances qui le séparent de chacun des autres joueurs.
Ces distances peuvent être conservées dans une structure de données adaptée.
Une fois les distances calculées et conservées, il suffit d'en sortir les k plus petites distances pour connaître les k plus proches voisins.
Le plus simple pour cela est de trier les distances par ordre croissant.
Connaissant ses k plus proches voisins, il suffit maintenant d'affecter Caliméro au poste majoritaire parmi ses k plus proches voisins.
Remarque : pour limiter les cas d'égalité, on rappelle qu'il est intéressant de choisir une valeur de k impaire, surtout dans les situations où l'on a que deux catégories à différencier.
La pertinence des données est déterminante pour espérer une bonne prédiction.
Le fait que les caractéristiques permettent de bien différencier les différentes catégories est primordial.
Voici un graphique basé sur les mêmes critères que précédemment, appliqué aux joueurs de football ayant participé à la dernière coupe d'Europe.
Commentaires !
Appliquer cet algorithme des k plus proches voisins au mini-projet de Choixpeau magique (lien vers le mini-projet).
- Pour prédire la catégorie d’un nouvel élément à l'aide de l'algorithme des k plus proches voisins, il faut :
- Un échantillon de données suffisamment large et varié.
- Un nouvel élément dont on connaît les caractéristiques et dont on veut prédire la catégorie.
- La valeur de k, le nombre de voisins à conserver.
- L'algorithme des kPPV se modélise ensuite ainsi :
- Calculer les distances entre le nouvel élément et tous les éléments de l'échantillon.
- Trouver, dans l’échantillon, les k plus proches voisins de l'élément à catégoriser.
- Parmi ces proches voisins, trouver la catégorie majoritaire.
- Le choix de k est déterminant pour obtenir des résultats pertinents :
- avec un trop petit k, l'effet loupe est trop important, ce qui laisse une trop grande part à l'aléatoire de la répartition des éléments
- avec un trop grand k, on perd l'intérêt d'avoir un bon profil de cible et le résultat tendra vers la catégorie globalement majoritaire.
Auteur : David Landry, Lycée Clemenceau - Nantes
D'après des documents partagés par...
JC. Gérard, T. Lourdet, J. Monteillet, P. Thérèse, sur le site monlyceenumerique.fr
Infoforall
Les données des rugbymen ont été trouvées sur le site officiel sixnationsrugby.com
David Cobac, enseignant au lycée Jean Moulin, Angers
D'après des documents partagés par...
JC. Gérard, T. Lourdet, J. Monteillet, P. Thérèse, sur le site monlyceenumerique.fr
Infoforall
Les données des rugbymen ont été trouvées sur le site officiel sixnationsrugby.com
David Cobac, enseignant au lycée Jean Moulin, Angers
David Landry, enseignant au Lycée Clemenceau - Nantes (44)
information(s) pédagogique(s)
niveau : tous niveaux
type pédagogique :
public visé : non précisé
contexte d'usage :
référence aux programmes :
enseignements informatiques - Rectorat de l'Académie de Nantes