Ce TP met en œuvre l'algorithme des \(k\) plus proches voisins et la matrice de confusion du cours d'apprentissage.

Données MNIST¶

Note : ce TP en C est volontairement très peu guidé. Si toutefois vous avez vraiment du mal à démarrer, le squelette du code, sans le corps des fonctions demandées, avec la visualisation en raylib, se trouve ici.

On va considérer ici le jeu de données MNIST qui fournit des milliers d'images en basse résolution de chiffres écrits à la main par des Américains (ça a son importance sur la forme des chiffres).

Source des données : base MNIST de Yann LeCun, Corinna Cortes et Christopher J. C. Burges.

On dispose de deux jeux de données, des données d'entraînement et des données de tests.

Chaque jeu de données est composé de deux fichiers :

un fichier finissant par images-idx3-ubyte qui contient les images dans le format suivant :
- un entier sur 4 octets en grand boutiste indiquant le format du fichier, c'est ce qu'on appelle un nombre magique, comme PK au début des fichiers zip. On va l'ignorer ;
- un entier dans le même format indiquant le nombre \(N\) d'images ;
- deux entiers dans le même format indiquant la hauteur \(H\) (le nombre de lignes) puis la largeur \(W\) (le nombre de colonnes) des images, ici \(H = W = 28\) ;
- une suite de \(W \times H\) octets pour chacune des \(N\) images, ligne par ligne, indiquant l'image en niveaux de gris.
un fichier finissant par labels-idx1-ubyte :
- un entier sur 4 octets en grand boutiste indiquant le format du fichier (le nombre magique), qu'on va ignorer ;
- un entier dans le même format indiquant le nombre \(N\) d'images ;
- une suite de \(N\) octets où le \(i\)-ème octet indique la classe de l'image, entre 0 et 9.

Vous pouvez trouver les données ici :

Entraînement :
- train-images-idx3-ubyte
- train-labels-idx1-ubyte
Tests :
- t10k-images-idx3-ubyte
- t10k-labels-idx1-ubyte

Remarque

Si on considère l'entier s'écrivant 0x12345678 en hexadécimal, il consiste en 4 octets qui en hexadécimal s'écrivent 12, 34, 56 et 78. L'octet 12 est celui de poids fort (il est multiplié par \(2^{24}\)) et l'octet 78 celui de poids faible (multiplié par \(2^0\)).

En mémoire, on peut représenter cet entier de deux manières :

soit en grand boutiste (big endian), où les octets sont dans cet ordre dans le fichier ou en mémoire : 12 34 56 78 ;
soit en petit boutiste (little endian), où les octets sont dans cet ordre dans le fichier ou en mémoire : 78 56 34 12.

Le nom indique par quel « bout » on commence : par l'octet de poids fort dans le premier cas, par l'octet de poids faible dans le second. Les processeurs de nos machines (x86, ARM) sont petit boutistes : il faudra donc convertir les entiers lus dans les fichiers MNIST.

Question 1. Écrire une fonction réalisant la conversion d'une représentation à l'autre.

On pourra utiliser des divisions et des modulos pour extraire les octets, puis des multiplications pour recomposer.

Par exemple, (x / 256) % 256 va être le deuxième octet en partant du poids faible.

Question 2. Définir un type permettant de représenter une donnée : la classe et l'image.

Attention : il est crucial d'avoir des unsigned char pour les pixels et pas des char, sinon rien ne va marcher !

Question 3. Décoder les fichiers pour obtenir des tableaux de données.

On va utiliser ici la fonction fread :

BIBLIOTHÈQUE
       Bibliothèque C standard (libc, -lc)

SYNOPSIS
       #include <stdio.h>

       size_t fread(void *restrict ptr, size_t taille, size_t nbelem,
                    FILE *restrict flux);

DESCRIPTION
       La  fonction  fread()  lit  nbelem  éléments  de données de
       taille octets chacun depuis le flux pointé par flux, et les
       stocke à l'emplacement pointé par ptr.

On rappelle qu'on obtient un FILE* avec fopen (attention, peut-être en "rb" si vous êtes sous Windows) et qu'on le ferme avec fclose.

Plus proches voisins¶

Question 4. Écrire une fonction permettant de calculer la distance euclidienne entre deux images.

Question 5. Implémenter l'algorithme KNN.

Question 6. Calculer les matrices de confusion pour \(k = 1, 3, 5, 7\) et le taux d'erreur sur le jeu de test.

Remarque

Pour vérifier vos résultats : avec la distance euclidienne, les \(60\,000\) images d'entraînement et les \(10\,000\) images de test, on obtient un taux d'erreur d'environ \(3\,\%\) pour chacune de ces valeurs de \(k\) (\(3{,}09\,\%\) pour \(k = 1\) et \(2{,}95\,\%\) pour \(k = 3\), en départageant les égalités de votes par la plus petite classe). Le calcul complet prend de l'ordre de la minute : on pourra commencer par tester sur les premières images de test seulement.

Aller plus loin¶

Question 7. Réaliser une interface minimaliste avec raylib pour écrire à la souris et voir la reconnaissance.

On affichera notamment les images des \(k\) plus proches voisins.