Mis à jour le 14/05/2018
  • 10 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

Ce cours est en vidéo.

Vous pouvez obtenir un certificat de réussite à l'issue de ce cours.

J'ai tout compris !

TP : Entraînez le modèle des k plus proches voisins (k-NN)

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Dans ce chapitre, nous allons utiliser un algorithme aussi répandu que la régression linéaire, qui s'appelle le K-NN. On va s'en servir pour illustrer ce qu'on a vu au chapitre précédent,

Le k-NN est le diminutif de k Nearest Neighbors. C’est un algorithme qui peut servir autant pour la classification que la régression. Il est surnommé « nearest neighbors » (plus proches voisins en français) car le principe de ce modèle consiste en effet à choisir les k données les plus proches du point étudié afin d’en prédire sa valeur.

Comment fonctionne le modèle k-NN ?

Avant d'utiliser un vrai jeu de données, on va prendre un petit exemple visuel afin de comprendre le fonctionnement de l'algorithme.

Ci-dessous j'ai représenté un jeu de données d’entraînement, avec deux classes, rouge et bleu. L'input est donc bidimensionnel ici, et la target est la couleur à classer.

Notre nuage de points de test
Notre nuage de points de test

Si on a une nouvelle entrée dont on veut prédire la classe, comment pourrait-on faire ?

le point blanc est une nouvelle entrée
le point blanc est une nouvelle entrée

Et bien on va simplement regarder les k voisins les plus proches de ce point et regarder quelle classe constitue la majorité de ces points afin d'en en déduire la classe du nouveau point. Par exemple ici, si on utilise le 5-NN, on peut prédire que la nouvelle donnée appartient à la classe rouge puisqu'elle a 3 rouges et 2 bleus dans son entourage. 

les 5 points les plus proches du point que l'on cherche à classer
les 5 points les plus proches du point que l'on cherche à classer

On peut facilement en déduire les zones rouge et zone bleu, où les points qui se situeront dans la zone seront respectivement classés comme rouge ou bleu.

Les deux zones qui séparent l'espace pour la décision à prendre sur la classification de nouvelles entrées
Les deux zones qui séparent l'espace pour la décision à prendre sur la classification de nouvelles entrées avec le modèle 5-NN

Voilà ce n’est pas plus compliqué que ça !

Tu parlais dans les chapitres précédents de modèles statistiques auquel on voudrait faire correspondre les données, c’est quoi le modèle ici ? 

En fait, le k-NN est un type spécial d’algorithme qui n’utilise pas de modèle statistique. Il est "non paramétrique", et il se base uniquement sur les données d’entraînement. Ce type d’algorithme est appelé memory-based. A contrario, la régression linéaire est paramétrique, de paramètre $\(\theta\)$ et ne va donc pas avoir besoin de conserver toutes les données pour effectuer des prédictions mais seulement $\(\theta\)$

Il va s'agir maintenant de choisir le bon nombre de voisins k, en fonction de l’erreur de généralisation du modèle.

Utilisez k-NN sur un vrai jeu de données

Ok, on peut maintenant passer aux choses sérieuses !

Les données et la problématique

D'abord, parlons du jeu de données que nous allons utiliser. C'est un dataset très célèbre appelé MNIST. Il est constitué d'un ensemble de 70000 images 28x28 pixels en noir et blanc annoté du chiffre correspondant (entre 0 et 9). L'objectif de ce jeu de données était de permettre à un ordinateur d'apprendre à reconnaître des nombre manuscrits automatiquement (pour lire des chèques par exemple). Ce dataset utilise des données réelles qui ont déjà été pré-traitées pour être plus facilement utilisables par un algorithme.

un extrait du type d'images que l'on trouve dans le dataset NIST
Un extrait du type d'images que l'on trouve dans le dataset MNIST

Notre objectif sera donc d'entraîner un modèle qui sera capable de reconnaître les chiffres écrits sur ce type d'images. Par chance, ce jeu de données est téléchargeable directement à partir d'une fonction scikit-learn. 😇  On peut donc directement obtenir ce dataset via un appel de fonction :

from sklearn.datasets import fetch_mldata
mnist = fetch_mldata('MNIST original')

Le dataset peut prendre un certain temps à se charger, soyez patients.

L'objet  mnist contient deux entrées principales,  data  et  target , on peut les afficher

# Le dataset principal qui contient toutes les images
print mnist.data.shape

# Le vecteur d'annotations associé au dataset (nombre entre 0 et 9)
print mnist.target.shape
(70000, 784)
(70000,)
  •  data contient les images sous forme de tableaux de 28 x 28 = 784 couleurs de pixel en niveau de gris, c'est à dire que la couleur de chaque pixel est représentée par un nombre entre 0 et 16 qui représente si c'est proche du noir ou pas (0 = blanc, 16 = noir). 

  •  target qui contient les annotations (de 1 à 9) correspondant à la valeur "lue" du chiffre

Echantillonner pour faciliter le travail

Le dataset est relativement petit mais pour le modèle K-nn, il est déjà trop gros pour obtenir rapidement des résultats. On va donc effectuer un sampling et travailler sur seulement 5000 données :

sample = np.random.randint(70000, size=5000)
data = mnist.data[sample]
target = mnist.target[sample]

Séparer training / testing set

Une fois notre dataset chargé, comme nous l'avons vu dans le chapitre précédent, nous allons séparer le jeu de données en training set et testing set.

J'ai ici appelé les images d'exemple "X" et les annotations cibles "y" :

from sklearn.model_selection import train_test_split

xtrain, xtest, ytrain, ytest = train_test_split(data, target, train_size=0.8)

Je le rappelle, on va utiliser uniquement le training set pour entraîner notre modèle et on garde le testing set pour plus tard. J'ai mis la répartition classique 80/20 entre training et testing set.

Le k-NN

On peut créer un premier classifieur 3-NN, c'est à dire qui prend en compte les 3 plus proches voisins pour la classification. Pour cela on va utiliser l'implémentation de l'algorithme qui existe dans la librairie sklearn :

from sklearn import neighbors

knn = neighbors.KNeighborsClassifier(n_neighbors=3)
knn.fit(xtrain, ytrain)

Comme je l'ai dit plus haut pour le k-NN, l'algorithme ici n'effectue aucune optimisation, mais va juste sauvegarder toutes les données en mémoire. C'est sa manière d'apprendre en quelque sorte.

Testons à présent l’erreur de notre classifieur. La méthode  score  effectue exactement ça : tester les performances de prédiction d'un classifieur dans lequel on passe un jeu de données annoté - dans notre cas le jeu de données de test. Il renvoie ainsi le pourcentage de prédiction véridique trouvée par le classifieur.

error = 1 - knn.score(xtest, ytest)
print('Erreur: %f' % error)

Qui nous donne en sortie :

Erreur: 0.050499999999999989

Pas mal déjà !

Comme je l'ai dit, le k (nombre de voisins) est l'hyper-paramètre que l’on va chercher à optimiser pour minimiser l’erreur sur les données test.

Optimisation du score sur les données test

Pour trouver le k optimal, on va simplement tester le modèle pour tous les k de 2 à 15, mesurer l’erreur test et afficher la performance en fonction de k :

errors = []
for k in range(2,15):
    knn = neighbors.KNeighborsClassifier(k)
    errors.append(100*(1 - knn.fit(xtrain, ytrain).score(xtest, ytest)))
plt.plot(range(2,15), errors, 'o-')
plt.show()
L'erreur en pourcentage pour les différents classifieurs
L'erreur en pourcentage pour les différents classifieurs

Comme on peut le voir, le k-NN le plus performant est celui pour lequel k = 7. On connait donc notre classifieur final optimal : 7-nn. Ce qui veut dire que c'est celui qui classifie le mieux les données, et qui donc dans ce cas précis reconnait au mieux les nombres écrits à la main.

A titre d'exemple, vous pouvez afficher les prédictions du classifieur sur quelques données.

# On récupère le classifieur le plus performant
knn = neighbors.KNeighborsClassifier(7)
knn.fit(xtrain, ytrain)

# On récupère les prédictions sur les données test
predicted = knn.predict(xtest)

# On redimensionne les données sous forme d'images
images = xtest.reshape((-1, 28, 28))

# On selectionne un echantillon de 12 images au hasard
select = np.random.randint(images.shape[0], size=12)

# On affiche les images avec la prédiction associée
for index, value in enumerate(select):
    plt.subplot(3,4,index+1)
    plt.axis('off')
    plt.imshow(images[value],cmap=plt.cm.gray_r,interpolation="nearest")
    plt.title('Predicted: %i' % predicted[value])

plt.show()
Les prédictions du classifieur associées au images
Les prédictions du classifieur associées aux images

Pour pouvoir un peu mieux comprendre les erreurs effectuées par le classifieur, on peut aussi afficher un extrait des prédictions erronées :

# on récupère les données mal prédites 
misclass = (ytest != predicted)
misclass_images = images[misclass,:,:]
misclass_predicted = predicted[misclass]

# on sélectionne un échantillon de ces images
select = np.random.randint(misclass_images.shape[0], size=12)

# on affiche les images et les prédictions (erronées) associées à ces images
for index, value in enumerate(select):
    plt.subplot(3,4,index+1)
    plt.axis('off')
    plt.imshow(misclass_images[value],cmap=plt.cm.gray_r,interpolation="nearest")
    plt.title('Predicted: %i' % misclass_predicted[value])

plt.show()
Quelques exemples d'images mal classées
Quelques exemples d'images mal classées

Conclusion

On vient de voir sur un algorithme simple comment simplement l'entraîner sur des données pour ensuite pouvoir optimiser les paramètres de cet algorithme à l’aide d’un jeu de données test.

N’hésitez pas à entraîner ce modèle à votre tour sur d’autres jeux de données !

Exemple de certificat de réussite
Exemple de certificat de réussite