Pourquoi cet alogorithme ?
Cet algorithme est souvent nommé aussi KNN (de l'anglais : K Nearest Neighbors).
C'est un algorithme utilisé en machine-learning (algorithme d'apprentissage) et donc fait partie de l'univers des algorithmes dit de l'Intelligence Artificielle.
Le concept de machin-learning est apparu en 1959 par Arthur Samuel, informaticien qui était précurseur dans les jeux sur ordinateur et les programmes d'auto-apprentissages. Il est donc aux origines des concepts d'intelligence artificielle.
L'objectif de l'algorithme KNN est de déterminer pour une nouvelle donnée, à quelle classe (ou groupe) elle appartient.
L'exemple le plus connu pour expliquer l'algorithme KNN est le classement des fleurs d'iris :
Si on trouve une fleur d'iris dans la nature, l'algorithme des plus proches voisins est capable de vous dire à quelle variété elle appartient parmi toutes les variétés d'iris en utilisant une base de données des fleurs d'iris.
Comment fonctionne cet algorithme ?
Mise en évidence des classes de données
Afin de mieux comprendre le principe de fonctionnement de cet algorithme on représente les données sous forme de graphique.
Par exemple sur le graphique suivant, il est mis en évidence 2 classes de données. C'est à dire que la représentation des données permet de mettre en évidence 2 groupes distincts : ceux en vert et ceux en rouge :
En orange est représenté une nouvelle donnée et on cherche à déterminer à quelle classe elle appartient. Ce serait nos iris, on chercherait à savoir si cela appartient à telle variété ou telle autre variété d'iris.
Les k plus proches voisins
A noter l'apparition de K et de cercles (un cercle n'est qu'une représentation d'un calcul qui permet de déterminer les plus proches voisins) :
- dans le plus petit il y a 3 voisins, donc k=3,
- dans le plus grand il y a 7 voisins, donc k=7.
Mais comment savoir à quelle classe appartient notre nouvelle donnée ?
On détermine la classe à laquelle notre nouvelle donnée appartient à la majorité.
Par exemple, pour notre graphique ci-dessus :
- pour k=3, cela correspond à la classe verte (il y en a 2 contre 1 en rouge)
- pour k=7, cela correspond à la classe rouge (il y en a 4 contre 3 verte).
Exercice
On dispose d’une table de données de villes européennes.
On utilise ensuite l’algorithme des k plus proches voisins pour compléter automatiquement cette base avec de nouvelles villes.
Ci-dessous, on a extrait les 7 villes connues de la base de données les plus proches de Davos.
Mais comment choisir K ?
Il faut prendre plusieurs valeurs de K et calculer pour chacune le taux d'erreur de test : on conserve la valeur de K qui minimise ce taux d'erreur.
Passons à la pratique
Vous allez faire entièrement l'activité sur le site Pixees qui utilise l'exemple des fleurs d'iris.
Remarques complémentaires
- A noter que c'est le fichier iris.csv qui sert de base de données de départ avec 150 fleurs différentes et 3 classes (variétés).
La dernière colonne 'species' correspond à la variété d'iris, indiquée par un n° au lieu de son nom latin.
- L'installation des bibliothèques matplotlib, pandas, scikit-learn est à faire suivant l'IDE python que vous utilisez :
- Dernière version d'Edupython : rien à faire.
- Pyzo, spyder : dans la console exécuter pip install nomBibliothèque (exemple pip install pandas).
- Replit : l'installation se fait automatiquement au lancement du programme
- La bibliothèque Pandas est très intéressante pour manipuler facilement des données à analyser, par exemple :
iris=pandas.read_csv("iris.csv") : importe le fichier csv en datafram (se comporte comme un dictionnaire dont les clefs sont les noms des colonnes et les valeurs sont des séries)
x=iris.loc[:,"petal_length"] : crée un tableau d'une seule colonne avec les valeurs de la colonne petal_lenght (explication ici)
Exercice
Réaliser un programme en python avec une boucle pour faire varier k afin de construire un tableau de couples [k,prediction].
Cela permettra la visualisation de la tendance de prédiction suivant les valeurs de k.