Reconnaissance de chiffres avec KNN (algorithme des plus proches voisins) 
MNIST est un jeu de données de chiffres manuscrits, utilisée initialement pour la reconnaissance de code postal. Pour reconnaître des chiffres sur une image, nous allons utiliser un algorithme d'apprentissage automatique (machine learning), appelé k-nearest neighbor (KNN).
Ceci est un problème de classification : on veut associer chaque donnée à une classe, les classes étant connues à l'avance (ici les chiffres de $0$ à $9$).
Commençons par importer les packages nécessaires :
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd # un peu comme numpy, mais plus adapté à la manipulation de données
import plotly.express as px # affichage
import sklearn # pour importer le jeu de données
Importons la base de donnée MNIST :
from sklearn import datasets
digits = sklearn.datasets.load_digits() # charge jeu de données dans digits
digits est un dictionnaire : une structure de donnée contenant des paires clé/valeur (à chaque clé est associé une valeur). C'est similaire à une liste, sauf que les indices (appelées clés) ne sont pas forcément des entiers. On accède à la valeur associée à la clé k avec digits[k].
digits.keys() # clés
Voici leurs significations :
target: la valeur des chiffres (un entier entre $0$ et $9$)images: les images des chiffres (un tableau 2D NumPy de pixels)data: même chose queimagesmais en une dimension
Vérifions :
digits["target"] # tableau contenant en ième position le chiffre correspondant à l'image i
digits.images[0] # 1er chiffre sous forme de matrice, chaque pixel étant entre 0 (blanc) et 16 (noir)
plt.imshow(digits.images[0], cmap=plt.cm.gray_r); # affiche la matrice précédente
Affichons les 10 premiers chiffres :
_, axes = plt.subplots(nrows=1, ncols=10, figsize=(20, 3))
for ax, image, label in zip(axes, digits.images, digits.target):
ax.set_axis_off()
ax.imshow(image, cmap=plt.cm.gray_r)
ax.set_title(label)
Exercice : Combien y a t-il de chiffres dans la base de données ?
Affichons la fréquence de chaque chiffre :
fig = px.histogram(pd.DataFrame({"digit": digits.target}))
fig.update_layout(bargap=0.2)
%%html
<center><iframe src="https://editor.p5js.org/fortierq/full/CsVuWdehV" height=700 width=600></iframe></center>
Comme la plupart des algorithmes d'apprentissage, KNN sépare les données en deux ensembles : celles utilisées pour entraîner l'algorithme (train) et celles pour tester la précision de notre algorithme (test).
n_train = 1000 # on choisit de mettre 1000 images dans les données d'entrainement et le reste dans les données de test
X_train, X_test = digits["images"][:n_train], digits["images"][n_train:]
Y_train, Y_test = digits["target"][:n_train], digits["target"][n_train:]
KNN demande de définir une distance sur les données. Ici, on va utiliser la distance euclidienne entre 2 matrices (somme des différences des carrés des composantes) :
def d(p, q):
return ((p - q)**2).sum()
d(X_train[0], X_train[1]) # exemple
Exercice : Écrire une fonction plus_frequent(L) qui renvoie le plus fréquent dans la liste L.
def plus_frequent(L):
frequences = {}
maxi = None
for e in L:
if e not in frequences:
frequences[e] = 0
frequences[e] += 1
if not maxi or frequences[e] > frequences[maxi]:
maxi = e
return maxi
Voici le code principal de KNN, permettant d'assigner une classe à une nouvelle image x, en utilisant les données d'apprentissage X_train (images), Y_train (chiffres correspondants) :
import heapq
def knn(k, X_train, Y_train, x):
'''renvoie le chiffre le plus fréquent des k plus proches voisins de x dans X_train'''
distances = [(d(x, x_train), y_train) for x_train, y_train in zip(X_train, Y_train)] # distances de x à chaque image de X_train
k_distances = heapq.nsmallest(k, distances) # k plus proches voisins
voisins = list(zip(*k_distances))[1] # on récupère les labels des k plus proches voisins
return plus_frequent(voisins)
Essayons avec $5$ voisins ($k = 5$) :
Y_pred = np.array([knn(5, X_train, Y_train, x) for x in X_test])
Y_pred[i] contient la classe prédite pour la $i$ème image de test dans X_test :
plt.imshow(X_test[3], cmap=plt.cm.gray_r) # afficher une image de test
plt.title(Y_pred[3]); # avec sa prédiction
Calculons le pourcentage de bonnes réponses :
(Y_pred == Y_test).mean()
$95$% de réponses correctes ! Regardons quelques exemples incorrects :
wrong = np.argwhere(Y_pred != Y_test).flatten()[:10] # indices de 10 réponses incorrectes
_, axes = plt.subplots(nrows=1, ncols=10, figsize=(20, 3))
for ax, image, label, pred in zip(axes, X_test[wrong], Y_test[wrong], Y_pred[wrong]):
ax.set_axis_off()
ax.imshow(image.reshape(8, 8), cmap=plt.cm.gray_r)
ax.set_title(f"label: {label}\npred: {pred}")
On peut aussi s'intéresser à la matrice de confusion, qui donne en position $i, j$, le nombre de fois que la classe $j$ a été prédite pour une image de test de classe $i$. Les éléments diagonaux sont donc les bonnes réponses, pour chaque chiffre.
from sklearn import metrics
metrics.confusion_matrix(Y_test, Y_pred)
Ci-dessus, nous avons utilisé $k = 5$. On peut changer $k$ pour voir comment cela affecte la précision de notre algorithme :
X, Y = [k for k in range(1, 15)], []
for k in X:
Y_pred = np.array([knn(k, X_train, Y_train, x) for x in X_test])
Y.append((Y_pred != Y_test).mean()) # pourcentage d'erreur
plt.plot(X, Y);
Étonnamment, la meilleure valeur de $k$ ici semble être $1$ ou $2$ (avec une erreur de $3,8$%).
À vous de jouer !
Essayer de faire le même travail, en utilisant un autre jeu de donnée sur sklearn :