Wiki NSI

Outils pour utilisateurs

Outils du site

Piste:
les_programmes_a_connaitre:algorithmique_premiere:k_plus_proches

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision 		Révision précédente
les_programmes_a_connaitre:algorithmique_premiere:k_plus_proches [2022/05/14 09:44]
bs 		les_programmes_a_connaitre:algorithmique_premiere:k_plus_proches [2023/01/16 10:24] (Version actuelle)
fm
Ligne 1: Ligne 1:
-====== **Algorithme des k plus proche voisins:**======+====== Algorithme des k plus proche voisins:======
  
-====__Introduction:__====+====Introduction:====
  
 L'algorithme des k plus proches voisins appartient à la famille des algorithmes d'apprentissage automatique (machine learning). L'algorithme des k plus proches voisins appartient à la famille des algorithmes d'apprentissage automatique (machine learning).
-C'est un algorithme simple a appréhender. +C'est un algorithme simple a appréhender, il permet apprentissage supervisé qui permet de classer de nouvelles données. Les GAFAM utilisent également les données concernant les utilisateurs afin de "nourrir" des algorithmes de machine learning qui permettrons à des sociétés d'en savoir toujours plus sur nous et ainsi de mieux cerner nos "besoins" en termes de consommation. Ce type d'algorithme sont par exemple utilisé pour classer différentes espèces d'arbres par exemple.
-Les apprentissages automatique ne date pas d'hier et ont connu un fort regain d'intérêt au début des années 2000, notamment grâce à la quantité de données disponibles sur internet. +
-C'est un algorithme d'apprentissage supervisé qui permet de classer de nouvelles données mais qui permet également d'utiliser cet algorithme a des fins de régression (non abordé dans le programme). +
-Les GAFAM utilisent également les données concernant les utilisateurs afin de "nourrir" des algorithmes de machine learning qui permettrons à des sociétés d'en savoir toujours plus sur nous et ainsi de mieux cerner nos "besoins" en termes de consommation.+
  
-====__Principe de l'algorithme:__====+====Principe de l'algorithme:====
  
-L'algorithme des k plus proche voisins ne nécessite pas de phase d'apprentissage (à proprement parlé), il faut juste stocker le jeu de données d'apprentissage. 
-Soit un ensemble //E// contenant //n// données labelisées: //E//={(//yi//,__xi__)} avec //i// compris entre 1 et //n//, où //yi// correspond à la classe de la donnée //i// et où le vecteur //xi// de dimension //p//(//xi//=(//x1i//,//x2i//,...,//xpi//)) représente les variables prédictrices de la donnée //i//. 
-Soit une donnée //u// qui n'appartient pas à //E// et qui ne possède pas de label (//u// est uniquement caractérisée par un vecteur //xu// de dimension //p//). 
-Soit //d// une fonction qui renvoie la distance entre la donnée //u// et une donnée quelconque appartenant à //E//. 
-Soit un entier //k// inférieur ou égal à //n//. 
 Voici le principe de l'algorithme de //k// plus proches voisins: Voici le principe de l'algorithme de //k// plus proches voisins:
-   -On calcule les distances entre la donnée //u// et chaque donnée appartenant à //E// à l'aide de la fonction //d//. +   -On calcule les distances entre la donnée //u// et chaque donnée appartenant au graphique. 
-   -On retient les //k// données du jeu de données //E// les plus proches de //u//.+   -On retient les //k// données du jeu de données les plus proches de //u//.
    -On attribue à //u// la classe qui est la plus fréquente parmi les //k// données les plus proches.    -On attribue à //u// la classe qui est la plus fréquente parmi les //k// données les plus proches.
-Il est possible d'utiliser différents types de distance si souhaité. 
  
-====__Etude d'un exemple:__====+====Etude d'un exemple:====
  
 ===Les données:=== ===Les données:===
 +
 +Comment savoir à quelle espèce appartient une pétale ?
  
 Par exemple pour un jeu de donnée s'appelant "iris de Fisher" qui est composé de 50 entrées et pour chaque entrée nous avons: Par exemple pour un jeu de donnée s'appelant "iris de Fisher" qui est composé de 50 entrées et pour chaque entrée nous avons:
-   -La longueur des sépales (en cm) 
-   -La largeur des sépales (en cm) 
    -La longueur des pétales (en cm)    -La longueur des pétales (en cm)
    -La largeur des pétales (en cm)    -La largeur des pétales (en cm)
    -L'espèce d'Iris    -L'espèce d'Iris
-Il est possible de télécharger ces données au format csv.+Il est possible de télécharger ces données au format csv :
  
-Ensuite il faut les modifier à l'aide d'un tableur: +{{:les_programmes_a_connaitre:algorithmique_premiere:nsi_prem_knn_1.png?400|}}
-   -Nous supprimons les colones qui ne nous intéresse pas afin de garder seulement celles qui nous intéresse. +
-   -Il faut égallement encoder les espèces avec des chiffres (0,1,2,...)+
  
 ===Bibliothèques Python utilisées:=== ===Bibliothèques Python utilisées:===
Ligne 70: Ligne 59:
 ===Utilisation de l'algorithme des k plus proches voisins:=== ===Utilisation de l'algorithme des k plus proches voisins:===
  
-Le graphique ci dessus (FIGURE 1) montre que les 3 classes (Iris stetosa, Iris virginica, Iris versicolor) sont relativement bien séparées.+Le graphique ci-dessus (FIGURE 1) montre que les 3 classes (Iris stetosa, Iris virginica, Iris versicolor) sont relativement bien séparées.
 On peut ajouter une données non labellisée n'appartenant pas à l'ensemble d'origine (FIGURE 2): On peut ajouter une données non labellisée n'appartenant pas à l'ensemble d'origine (FIGURE 2):
  
Ligne 76: Ligne 65:
 FIGURE 2 - Ajout d'une donnée non labellisée FIGURE 2 - Ajout d'une donnée non labellisée
  
-Cet algorithme "__k ppv__" (en anglais "k nearest neighbors" : knn) est un algorithme d'apprentissage, qui prédit la classe d’un élément en fonction de la classe majoritaire de ses k plus proches voisins. Il permet par exemple de savoir grâce à des données, quelle fleur ça peut-être \\ +Dans l'exemple ci-dessus (FIGURE 2), nous n'aurons aucune difficultés à déterminer l'espèce d'Iris qui a été ajouté au jeu de données. 
-Il fonctionne en deux parties, tout d'abord, il calcule la distance entre nos données recueillies et chaque donnée connues, et ensuite, on sélectionne uniquement les k distancent les plus petites (les k plus proches voisins) +Dans certains cas, il est un peu plus difficile de se prononcer "au premier coup d'oeil" (FIGURE 3): 
-parmi les k plus proches voisins, on détermine quel est le groupe de données majoritaires. + 
-  +{{https://pixees.fr/informatiquelycee/n_site/img/nsi_prem_knn_4.png}} 
 +FIGURE 3 - Cas plus difficile 
 + 
 +A partir de l'exemple ci-dessus (FIGURE 3), il faut utiliser une méthode pour traiter ce genre de cas litigieux. 
 +Nous allons pour ce faire, utiliser l'algorithme des k plus proches voisins: 
 +   -On calcule la distance entre nos points et chaque points issu du jeu de données "Iris" 
 +   -On sélectionne uniquement les k distances les plus petites 
 +   -Parmi les k plus proches voisins, on détermine quelle est l'espèce majoritaire? 
 +   -On associe à notre "Iris mystère" cette espèce "majoritaire parmi les k plus proches voisins" 
 +Dans l'exemple évoqué ci-dessus, nous obtenons graphiquement: 
 + 
 +{{https://pixees.fr/informatiquelycee/n_site/img/nsi_prem_knn_5.png}} 
 +FIGURE 4 - Ici les 3 plus proches voisins 
 + 
 +Un Iris ayant une largeur de pétale égale à 0.75 cm et une longueur de pétale égale à 2.5 cm a une "forte" probabilité d'appartenir à l'espèce setosa. 
 + 
 +===Utilisation de scikit-learn:=== 
 + 
 +La bibliothèque Python scikit-learn propose un grand nombre d'algorithmes lié à l'apprentissage automatique. 
 +Parmi tout ces algorithmes, scikit-learn propose l'algorithme des k plus proches voisins. 
 +Voici un programme Python permettant de résoudre le problème évoqué ci-dessus:
  
-Exemple d'utilisation de l'algorithme k ppv en important des données sur des fleurs: 
 <code python> <code python>
 import pandas import pandas
Ligne 108: Ligne 116:
 #fin graphique #fin graphique
  
-#algo kppv+#algo knn
 d=list(zip(x,y)) d=list(zip(x,y))
 model = KNeighborsClassifier(n_neighbors=k) model = KNeighborsClassifier(n_neighbors=k)
 model.fit(d,lab) model.fit(d,lab)
 prediction= model.predict([[longueur,largeur]]) prediction= model.predict([[longueur,largeur]])
-#fin algo kppv+#fin algo knn
  
 #Affichage résultats #Affichage résultats
 txt="Résultat : " txt="Résultat : "
 if prediction[0]==0: if prediction[0]==0:
-  txt=txt+"setosa"+txt=txt+"setosa"
 if prediction[0]==1: if prediction[0]==1:
-  txt=txt+"virginica"+txt=txt+"virginica"
 if prediction[0]==2: if prediction[0]==2:
-  txt=txt+"versicolor"+txt=txt+"versicolor"
 plt.text(3,0.5, f"largeur : {largeur} cm longueur : {longueur} cm", fontsize=12) plt.text(3,0.5, f"largeur : {largeur} cm longueur : {longueur} cm", fontsize=12)
 plt.text(3,0.3, f"k : {k}", fontsize=12) plt.text(3,0.3, f"k : {k}", fontsize=12)
Ligne 130: Ligne 138:
 plt.show() plt.show()
 </code> </code>
 +
 +les éléments des tableaux x et y ayant le même indice sont regroupés dans un tuple, nous obtenons bien une liste de tuples.
 +
 +"KNeighborsClassifier" est une méthode issue de la bibliothèque scikit-learn (voir plus haut le "from sklearn.neighbors import KNeighborsClassifier"), cette méthode prend ici en paramètre le nombre de "plus proches voisins" (model = KNeighborsClassifier(n_neighbors=k))
 +
 +"model.fit(d, lab)" permet d'associer les tuples présents dans la liste "d" avec les labels (0 : "iris setosa", 1 : "iris versicolor" ou 2 : "iris virginica"). Par exemple le premier tuple de la liste "d", (1.4, 0.2) est associé au premier label de la liste lab (0), et ainsi de suite...
 +
 +La ligne "prediction= model.predict([[longueur,largeur]])" permet d'effectuer une prédiction pour un couple [longueur, largeur] (dans l'exemple ci-dessus "longueur=2.5" et "largeur=0.75"). La variable "prediction" contient alors le label trouvé par l'algorithme knn. Attention, "predection" est une liste Python qui contient un seul élément (le label), il est donc nécessaire d'écrire "predection[0]" afin d'obtenir le label.
 +
 +Nous obtenons le résultat suivant (FIGURE 5):
 +
 +{{https://pixees.fr/informatiquelycee/n_site/img/nsi_prem_knn_6.png}}
 +FIGURE 5 - A l'aide de scikit-learn
 +
 +Il est également possible de modifier le programme ci-dessus afin d'étudier les changements induits par la modification du paramètre k en gardant toujours les mêmes valeurs de largeur et de longueur ou encore de changer les valeurs de longueur et de largeur.
les_programmes_a_connaitre/algorithmique_premiere/k_plus_proches.1652514285.txt.gz · Dernière modification: 2022/05/14 09:44 de bs

Outils de la page

Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial 4.0 International
CC Attribution-Noncommercial 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki