Comprendre et utiliser l'algorithme des k plus proches voisins
- Fiche de cours
- Quiz et exercices
- Vidéos et podcasts
Comprendre l'algorithme des k plus proches voisins en intelligence artificielle (IA).
- L’algorithme des k plus proches voisins permet de prédire à quelle famille une nouvelle entrée (une nouvelle donnée) va appartenir. Il calcule pour cela les distances de la nouvelle entrée au jeu de donnée, c’est-à-dire la distance entre la nouvelle donnée et toutes celles déjà présentes dans le jeu de données.
- Il s’agit d’un modèle de prédiction utilisé en intelligence artificielle pour la reconnaissance de formes mais aussi pour certains diagnostics médicaux.
- Écrire une fonction.
- Utiliser des bibliothèques.
- Utiliser la bibliothèque Matplotlib de Python pour créer un graphique.
- On définit en entrée de cet algorithme un ensemble de données déjà classifiées (appelé jeu de données), une distance d et un nombre entier k.
- L’algorithme des k plus proches voisins calcule la distance entre toutes les données déjà classifiées et la nouvelle donnée qui vient d’être entrée.
- L’algorithme extrait ensuite les k données déjà classifiées les plus « proches » de la nouvelle donnée entrée, c’est-à-dire les données déjà classifiées qui ont la distance d la plus petite avec la nouvelle donnée entrée.
- L’algorithme choisit enfin à quelle famille appartient la nouvelle donnée, en cherchant la famille majoritaire parmi les k données identifiées.
Cet algorithme se nomme k-NN, diminutif de k Nearest Neighbors : on le nomme l’algorithme des k plus proches voisins en français.
On a un jeu de données qui permet de classer des individus dans deux familles A et B. On ajoute un individu en noir. On prend k = 3.
On peut utiliser différentes distances entre les données, les plus usitées sont la distance euclidienne et la distance Manhattan.
Une donnée D1 est constituée de n éléments que l’on considère comme ses coordonnées, on note cela par D1(x1, x2, … , xn). On a de même D2(y1, y2, … , yn).
La distance euclidienne d entre les points D1 et D2 est donnée par la relation suivante.
La distance de Manhattan est nommée ainsi car elle permet de mesurer la distance parcourue entre deux points par une voiture dans une ville où les rues sont agencées selon un quadrillage.
Sur le visuel ci-dessous, le tracé violet correspond à la distance euclidienne, tandis que les tracés rose, bleu clair et bleu foncé correspondent à la distance de Manhattan.
La distance de Manhattan d entre deux données D1 et D2 est donnée par la relation suivante.
On va prioritairement utiliser la distance euclidienne.
La difficulté consiste à utiliser les données déjà classifiées car le jeu de données est généralement dans un format CSV. Pour programmer les fonctions distances, il faut ouvrir le fichier et créer une liste.
| import csv | On importe la bibliothèque CSV, |
| from math import* | pour utiliser la racine carrée qui appartient au module math. |
|
with
open(‘donnees.csv',
'rt',newline=" ") as fichier: |
On ouvre le fichier donnees.csv. rt signifie avec le droit de lecture et en mode texte. La nouvelle ligne est symbolisée par l’espace. On lui donne le nom de « fichier ». |
| lecteurCSV=csv.reader (fichier,delimiter=",") | On utilise le lecteur de données csv sur le fichier avec comme délimiteur la virgule. |
| tableau=[] | On crée un tableau vide. |
| for ligne in lecteurCSV: | Pour chaque ligne, |
| tableau.append(ligne) | on place la ligne dans le tableau. |
| fichier.close() | Il faut toujours fermer le fichier ! |
Soit un jeu de données qui a m données. Pour calculer la distance euclidienne d entre le i-ème élément du jeu de données et la nouvelle entrée, on doit taper les lignes de code Python suivantes sachant que la nouvelle entrée est un tableau de longueur m.
| d=0 | On initialise la distance d à 0. |
| for j in range(1,m): | Pour j de 1 à m, |
|
d=d+eval(tableau[i][j] -nouvelle[j])**2 |
on ajoute à d les distances respectives au carré. |
| d=sqrt(d) | Pour obtenir la distance euclidienne, on prend la racine carrée de d. |
La programmation de l’algorithme est très technique, on utilise donc une bibliothèque spécifique qui contient tous les outils nécessaires à l’intelligence artificielle.
Cette bibliothèque contient un ensemble de jeux
de données contenus dans datasets.
Elle contient également un package
sklearn.neighbors qui contient tous les outils
pour faire de l’apprentissage supervisé
avec l’algorithme k-NN, en particulier
l’outil KNeighborsClassifier qui permet de
prédire l’appartenance d’une
nouvelle donnée à une famille.
Voici les lignes de code à utiliser pour importer ces outils.
Voici l’explication ligne par ligne.
| from sklearn import datasets | On importe le jeu de données datasets du module sklearn. |
| from sklearn.neighbors import KNeighborsClassifier | On importe le module de classification KNeighborsClassifier du module sklearn.neighbors. |
En 1936, M. Fisher a étudié les iris de Gaspesie, au Québec. Ces plantes comportent trois familles : Setosa, Versicolore et Verginica. Il a étudié la longueur des sépales et pétales pour 150 iris, ce qui a donné naissance au jeu de données Iris, aussi appelé Iris de Fisher.
Coupe schématique d’une fleur
Chaque fleur comporte ainsi des attributs (longueurs et largeurs des sépales, longueurs et largeurs des pétales) ainsi qu’une classe (0 pour Setosa, 1 pour Versicolore et 2 pour Verginica), qui sont répertoriés dans le jeu de données Iris.
La bibliothèque dataset contient ce jeu de données. Pour le charger dans un programme, il faut taper la ligne de code suivante.
Pour visualiser les données, on utilise la bibliothèque Matplotlib, laquelle permet de tracer et de visualiser des données sous forme de graphiques.
Il faut pour cela taper les lignes de code suivantes.
Voici l’explication ligne par ligne.
| import matplotlib.pyplot as pl | On importe matplotlib.pyplot avec un alias pl afin d’obtenir un environnement de travail. |
| import matplotlib | On importe matplotlib, pour pouvoir réaliser les tracés. |
On va représenter la longueur et la largeur des pétales. Les points violets représentent les iris Setosa, les jaunes représentent les Versicolore et les bleus les Verginica. Voici les lignes de code Python.
Voici l’explication ligne par ligne.
| clist=['violet' , 'yellow' , 'blue'] | Création de la liste des couleurs du graphique. |
| colores=[clist[c] for c in irisData.target] | Création de la liste des couleurs des 150 iris du jeu de données. |
|
pl.scatter(irisData.data[:,2], irisData.data[:,3],c=colors) |
Création du nuage de points de coordonnées (irisData.data[:,2], irisData.data[:,3]) avec la couleur associé. |
| pl.xlabel('longueur') | Ajout de la légende « longueur » sur l’axe des abscisses. |
| pl.ylabel('largeur') | Ajout de la légende « largeur » sur l’axe des ordonnées. |
Ces lignes de code permettent de visualiser les données sur le graphique ci-dessous.
On s’intéresse à une iris ayant une longueur de pétale de 3,5 cm et une largeur de pétale de 1,7 cm. On souhaite déterminer à quelle famille d’iris cette plante appartient.
On ajoute pour cela la ligne de code ci-dessous à la fin du programme déjà existant.
Cette ligne indique qu’on ajoute au nuage de points le point de coordonnées (3.5,1.7) avec la couleur dont le code est 'k', c’est du noir.
On obtient le graphique suivant, où le point noir correspond à l’iris étudié.
Pour utiliser l’algorithme des k plus proches voisins avec k = 5, on tape les lignes de code suivantes.
Voici l’explication ligne par ligne.
| d=list(zip(irisData.data[:,2], irisData.data[:,3])) | Extraction des données. |
| model=KNeighborsClassifier (n_neighbors=5) | On applique la méthode de classification knn avec un nombre de voisins égal à 5. On lui donne le nom « model ». |
| model.fit(d,irisData.target) | On applique cet outil au jeu de données irisData. |
| prediction=model.predict ([3.5,1.7]]) | On demande alors la prédiction pour une mesure (3.5,1.7). |
| print(prediction) | On affiche ensuite cette prédiction. |
À l'exécution, on obtient le graphique suivant, où le numéro de la famille apparait en haut à gauche.
L’algorithme classe ainsi la nouvelle entrée comme faisant partie de la famille 1, c’est-à-dire Versicolore (points jaunes).
Évalue ce cours !
Des quiz et exercices pour mieux assimiler sa leçon
La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.
Des exercices variés pour ne pas s’ennuyer
Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !
Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.
Des quiz pour une évaluation en direct
Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.
myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.
Des vidéos et des podcasts pour apprendre différemment
Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.
Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !
Des podcasts pour les révisions
La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.
Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.
Des vidéos de cours pour comprendre en image
Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !
Fiches de cours les plus recherchées
NSI
L'algorithme de recherche dichotomique dans un tableau trié
NSI
Résoudre un problème avec un algorithme glouton
NSI
Écrire un entier positif dans une base donnée
NSI
Passer de la représentation d'une base à une autre
NSI
Comprendre les bases de la représentation binaire
NSI
Effectuer des opérations en binaire
NSI
Utiliser la méthode du complément à 2 en binaire
NSI
Représenter les nombres réels en binaire
NSI
Comprendre les booléens
NSI
Utiliser les opérateurs booléens élémentaires
NSI
Obtenir une table de vérité d'une expression booléenne complexe
NSI
Représenter un texte en utilisant différents encodages
Fermer
Accédez gratuitement à
