TP no 6 - Apprentissage automatique 1

1 Reconnaissance des chiffres manuscrits

Les caractères manuscrits peuvent présenter une grande variabilité : forme de chiffres, grosseur du trait,
inclinaison. . . On souhaite écrire un programme qui reconnaisse automatiquement des chiffres manuscrits. Pour
cela, on dispose d’un échantillon d’images bitmap représentant chacune un des 10 chiffres écrit à la main.
Plus précisément, les données constituent les lignes du fichier [Link] que j’ai placé en ligne sur
mon site, c’est-à-dire un fichier texte, avec ici le champs séparés par des virgules. En l’occurrence, chaque
ligne de données est formée de 65 nombres.

§ d’abord une donnée xi , formée par les pixels d’une image en niveaux de gris. Le niveau de gris est donné
par un nombre entier entre 0 et 16 (disons 0 pour noir et 16 pour blanc), et l’image comporte 8 lignes
et 8 colonnes (donc 8 ˆ 8 “ 64 nombres). D’abord sont donnés les pixels de la première ligne, puis les
pixels de la deuxième ligne, etc. On obtient ainsi une liste de 64 nombres. C’est toujours de cette
matière que seront représentées les images dans la suite.

§ ensuite un chiffre entre 0 et 9 : c’est l’étiquette yi de l’image xi , c’est-à-dire le chiffre manuscrit que
représente l’image.

1 Importer les données du fichier [Link], dans une matrice (liste de liste) d’entiers X et un
vecteur (liste d’entiers) Y (respectivement les données et les étiquettes). Vous pourrez par exemple utiliser les
commandes open, read et readlines. . . , et aussi la commande split.

2 De combien d’images étiquetées dispose-t-on ? Dans la suite, on appelera N cette quantité.

Pour l’affichage, avec les 64 nombres de chaque xi “ pxℓ q0ďℓď63 (les pixels d’une image), il s’agit de former
une matrice 8 ˆ 8 (liste de 8 listes de 8 nombres). Dans le tableau à gauche sur la figure 1, les indices ℓ des
pixels d’une image sont à l’intérieur du tableau. Les indices de lignes i et de colonnes j de la matrice associée
figurent en en-têtes à gauche et en haut.

3 Exprimer l’indice ℓ du pixel à la ligne i et colonne j.

4 Écrire une fonction affiche(x,y) qui prend en argument une image x (liste de 64 nombres entre 0
et 15) et affiche cette image, avec en titre l’étiquette y passée en argument (utiliser la fonction title de
[Link], que vous chercherez dans l’aide si besoin). Voir par exemple au milieu sur la figure 1.
Vous pourrez d’abord mettre l’image sous forme de matrice (liste de listes) comme expliqué au-dessus, et
donner cette matrice à manger à la fonction imshow de [Link] (par exemple avec l’argument
cmap=’gray’, qui s’occupe de tout !).

1.1 Apprentissage supervisé

Il s’agit de faire apprendre à l’ordinateur comme reconnaître les différents chiffres, en lui montrant d’abord
un grand nombre de chiffres manuscrits avec les bonnes réponses associées. Ceci pourrait être utile pour le tri
automatique du courrier à la Poste, la lecture du montant d’un chèque lu par un automate, etc.
Il s’agit d’un problème de classement de données, qu’on va effectuer à l’aide de l’algorithme des k plus
proches voisins.

5 En utilisant la commande shuffle du module random, écrivez une fonction permutation(A) qui renvoie
une permutation aléatoire des entiers entre 0 et A ´ 1. Par exemple :
1 >>> permutation(17)
2 [1, 5, 6, 2, 12, 15, 0, 3, 14, 8, 10, 4, 11, 16, 7, 13, 9]

[Link] MP - ITC 2024-2025

TP no 6 - Apprentissage automatique 2

0 1 2 3 4 5 6 7

0 0 1 2 3 4 5 6 7

1 8 9 10 11 12 13 14 15

2 16 17 18 19 20 21 22 23

3 24 25 26 27 28 29 30 31

4 32 33 34 35 36 37 38 39

5 40 41 42 43 44 45 46 47

6 48 49 50 51 52 53 54 55

7 56 57 58 59 60 61 62 63

Figure 1 – Affichages pour l’apprentissage supervisé des chiffres manuscrits

Dans la suite, on se réservera 80% de l’ensemble des données pour l’entraînement, et 20% pour les tests
(à une donnée près, si ça ne tombe pas juste. . . ).

6 Définissez les deux variables Ne et Nt comptant respectivement le nombre de données d’entraînement

et le nombre de données de test (on doit avoir N e ` N t “ N ).

7 Partagez aléatoirement le jeu de données en données d’entraînement et données de test. Concrètement,

créez deux listes images_e et images_t, de longueurs respectives N e et N t, et contenant respectivement les
indices des images d’entraînement, et les indices des images de test. Pour ce faire, vous n’avez qu’à prendre
pour la première liste, le début d’une permutation des nombres entre 0 et N ´1 (N “nombre total de données),
et comme données de test la fin.

8 Écrire une fonction distance2(xA,xB) qui calcule le carré (inutile de calculer la racine carré pour
comparer des ÿ
distances !) de la distance euclidienne entre les images passées en argument (listes de 64 pixels),
c’est-à-dire paj ´ bj q2 si xA“ paj q0ďjď63 et xB“ pbj q0ďjď63 .
0ďjď63

9 ‹ Écrire une fonction knn(x,k) qui donne une prédiction sur la classe de l’image passée en argument,
en utilisant l’algorithme des plus proches voisins (voisinage de taille k), en apprenant à partir de Xe/Ye. En
cas d’égalité, vous pourrez prendre par exemple la première étiquette la plus fréquente. . .

10 Modifiez votre fonction affiche en une fonction affiche2(x,y_vraie,y_predite) qui affiche l’image x
avec en titre son étiquette vraie, et son étiquette prédite. Voir par exemple à droite sur la figure 1. Écrire
une fonction un_test(k) qui lance l’algorithme knn avec k voisins sur une image choisie au hasard parmi les
données de test, et affiche le résultat avec la fonction affiche2.

11 Calculez taux de réussite et matrice de confusion des prédictions pour différentes valeurs de k. Observez
l’effet de la diminution du nombre de données d’apprentissage.

1.2 Apprentissage non supervisé

Des extra-terrestres découvrent notre écriture et cherchent à la comprendre. En particulier, disposant d’un
vaste échantillon de chiffres manuscrits, ils souhaitent le classifier en clusters de chiffres identiques, c’est-à-dire

[Link] MP - ITC 2024-2025

TP no 6 - Apprentissage automatique 3
regrouper les images en clusters homogènes, chaque cluster correspondant à un chiffre.
Il s’agit d’un problème de classification de données, qu’on va effectuer à l’aide de l’algorithme des k-
moyennes.
On maintient à un jour une liste poles (liste de K “ 10 images, qui ne sont a priori pas dans les données).
On maintient aussi à jour une liste pos, de taille N et tel que pos[i] est l’indice du pôle à laquelle est
actuellement associée l’image d’indice i de donnees (donc un nombre entier entre 0 et 9).

12 Écrire une fonction pole_plus_proche(x, poles), qui renvoie l’indice du pôle k le plus proche de x
parmi les pôles passés en argument.

13 Écrire une fonction re_partitionne(poles,pos) qui met à jour la liste pos étant donnée la liste des
pôles (liste d’images) donnée en argument. Cette fonction agit par effet de bord sur pos. On demande aussi
à ce qu’elle renvoie True dès qu’au moins une image change de pôle associé, et False si aucune image ne
change de pôle.

14 ‹ Écrire une fonction nouveaux_poles(poles,pos) qui modifie par effet de bord la liste de pôles passée
en argument (et ne renvoie rien). Les nouveaux pôles sont calculés comme les iso-barycentres des différents
clusters lus dans pos (le premier cluster est formé de toutes les images d’indice i de X tel que pos[i] est égal
à 0, le deuxième cluster tel que pos[i] est égal à 1, etc). On peut convenir que si un cluster est vide, alors
son pôle est pris égal à p0, 0, . . . , 0q (image noire), mais ce cas ne devrait pas se produire.

15 ‹ Enfin, écrire une fonction kmeans(K) (bien sûr qu’on l’appelera avec K “ 10 car 10 chiffres !), qui
réalise un partionnement de donnees en K clusters. Vous pourrez choisir les pôles initiaux au hasard parmi
les données, en utilisant la fonction sample du module random. Ensuite, une itération de l’algorithme des k-
moyennes consiste en : re-partitionnement des données suivant les pôles passées en argument, puis recalcul
des nouveaux pôles. Quand toutes les itérations sont terminées, il faut calculer la partition à partir de pos.
La fonction doit renvoyer le nombre A d’itérations nécessaires, les pôles à la fin, ainsi que la partition obtenue
(liste de clusters, chaque cluster étant une liste d’indices d’images).

16 Lancez des tests. Par exemple, dans chaque cluster, regardez combien d’images sont étiquetés avec
l’étiquette la plus fréquente du cluster.

17 Par curiosité, vous pouvez afficher les pôles à l’aide de la fonction avec imshow. Vous pouvez aussi
observer l’inertie totale diminuer. . .

2 Accidents de la route
Dans le fichier [Link] que j’ai placé en ligne sur mon site, sont répertoriés les lieux des accidents
survenus en 2019 en Basse-Normandie. On désire faire des clusters à partir de ces accidents. Exercice à but
purement pédagogique. Est-ce vraiment significatif de faire ça ?
On admet que la distance sur la sphère terrestre entre le point de latitude λ1 et de longitude φ1 , et le
point de latitude λ2 et de longitude φ2 vaut environ
a
pφ2 ´ φ1 q2 cos2 pλ1 q ` pλ2 ´ λ1 q2

et c’est cette quantité que nous pourrons retenir pour déterminer le pôle le plus proche d’un accident. Avec
nos latitudes proches de 49o N, on remplacera simplement cos2 pλ1 q par 0.43.

18 Reprenez et adaptez votre implémentation de l’algorithme des k-moyennes écrite à la section précédente.

[Link] MP - ITC 2024-2025

TP no 6 - Apprentissage automatique 4

19 Dessinez, avec une couleur différente pour chaque cluster.

20 Le top du top : utiliser le module cartopy.

[Link] MP - ITC 2024-2025