En guise d'initiation au problème d'apprentissage supervisé, nous allons implanter et manipuler l'algorithme des k plus proches voisins.
On va réaliser un programme qui implante l'algorithme des k plus proches voisins. Nous allons faire cela progressivement.
Avant même d'implanter l'algorithme des k plus proches voisins, nous avons besoin d'exemples qui seront traités par l'algorithme. Aussi, commençons par lire un jeu de données.
L'un des formats les plus simples est le format csv. Dans ce format, chaque ligne contient une donnée (un exemple ici) ; chaque ligne contient la valeur des attributs de la donnée, séparés par une virgule.
Bien entendu, il faut impérativement que les attributs apparaissent dans le même ordre à chacune des lignes.
Par exemple, pour le jeu de données que l'on va manipuler pour l'instant, les deux premières lignes du fichier sont :
5.1,3.5,1.4,0.2,Iris-setosa 4.9,3.0,1.4,0.2,Iris-setosa
Il y a 4 virgules par ligne, donc 5 attribut par ligne/donnée. Les quatre premiers attributs sont des nombres, le dernier est un symbole. Par convention, le dernier attribut de la ligne est l'étiquette de la donnée.
Sauvegardez le fichier d'exemple dans votre répertoire de travail. Il est disponible là.
On va utiliser la bibliothèque csv de Python pour charger un jeu de données (n'oubliez pas de l'importer). Son utilisation est très simple. Par exemple, on peut écrire :
csvfile = open ("iris.data", "r")
lines = csv.reader(csvfile)
dataset = list (lines)
dataset contient maintenant une espère de table dont chaque ligne contient une donnée. Chaque ligne est une liste contenant les attributs d'une donnée. dataset est une liste de listes.
Par exemple, une fois que vous avez effectué les instructions précédentes, vous pouvez tapez dataset [0] pour voir la première donnée. Vous pouvez ensuite accéder individuellement à chaque attribut. dataset [0] produit l'affichage :
['5.1', '3.5', '1.4', '0.2', 'Iris-setosa']
for x in range(len(dataset)):
for y in range (4):
dataset[x][y] = float(dataset[x][y])
On peut vérifier le résultat : dataset [0] produit maintenant l'affichage :
[5.1, 3.5, 1.4, 0.2, 'Iris-setosa']Il est normal que le dernier attribut, l'étiquette, soit une chaîne de caractères.
Avant toute chose, il nous faut définir une fonction qui mesure la distance entre deux données. Pour faire les choses les plus simples possibles pour l'instant, définissons une fonction distance qui prend deux points (deux listes de nombres) en paramètre et renvoie leur distance euclidienne.
Vous pourrez tester votre fonction entre mesurant la distance entre les deux premières données : distance (dataset [0][0:4], dataset [1][0:4]) qui doit renvoyer 0.538.... Entre la première donnée et la dernière, la distance est 4.140...
Écrire une fonction lePlusProcheVoisin qui prend en paramètre une donnée (une liste de 4 nombres, pas forcément un élément de dataset) et renvoie l'indice dans dataset du plus proche voisin (situé à une distance non nulle).
Par exemple, le plus proche voisin de la première donnée est la donnée numéro 17 et le voisin le plus proche du point [5, 3, 3, 2] est la donnée numéro 98.
Écrire une fonction lesKplusProchesVoisins qui prend en paramètre une donnée (une liste de 4 nombres, pas forcément un élément de dataset) et une valeur de k et renvoie la liste des indices dans dataset des k plus proches voisins.
Quand vous prenez
Par exemple, les 3 plus proches voisins de la première donnée sont les données numérotées 17, 4 et 39. Donc, lesKplusProchesVoisins renvoit la liste [17, 4, 39].
Les 3 plus proches voisins du point [5, 3, 3, 2] sont les données numérotées 98, 64 et 59. Donc, lesKplusProchesVoisins renvoit la liste [98, 64, 59].
Écrire une fonction predire qui prend en paramètre une liste de numéro d'exemples (de dataset) et retourne l'étiquette qui est prédite.
On décide de l'étiquette en appliquant un choix à la majorité.
Par exemple, si on passe la liste [17, 4, 39] (les trois plus proches voisins de la première donnée), la fonction predire retournera la valeur Iris-setosa.
Comme on l'a vu en cours, d'une manière générale, il faut distinguer les données avec lesquelles on prédit et les données que l'on prédit si l'on veut pouvoir estimer la probabilité qu'un classeur k pluis proches voisins se trompe dans sa prédiction.
Donc, il ne faut pas chercher les k plus proches voisins d'une donnée parmi toutes les données, mais dans un sous-ensemble de celles-ci ; et il faut mesurer les erreurs de classification sur des données que l'on n'utilise pas pour prédire la classe.
Donc, il faut découper le jeu de données en deux sous-ensembles disjoints, l'un qui est l'ensemble d'entraînement, l'autre qui est l'ensemble de test.
On écrira donc une fonction decoupeJeuDeDonnees qui prendra au hasard une certaine proportion (qui lui est passée en paramètre) des exemples pour les mettre dans une liste que l'on nommera exemplesDentrainement, les autres exemples allant dans une liste exemplesDeTest.
Dans les fonctions lePlusProcheVoisin, lesKplusProchesVoisins et predire écrites précédemment, on remplacera la référence à dataset par exemplesDentrainement.
Finalement, on peut maintenant combiner les fonctions précédentes pour obtenir le programme principal qui :
Implanter une fonction de validation croisée (VC) :
une VC est une (autre) manière d'estimer la probabilité qu'à un classeur de se tromper. Plutôt que de découper une fois pour toute l'ensemble d'exemples en un sous-ensemble d'apprentissage et un sous-ensemble de test, on effectue cette découpe plusieurs fois (on appelle cela le nombre de « plis »).
Si on fait 10 plis, on effectue le traitement suivant :
E est une estimation de la probabilité d'erreur du classeur.