La méthode des K plus proches voisins sur un afficheur 7 segments

On cherche à voir le lien entre la forme d'un chiffre sur l'afficheur 7 segments, et la parité du nombre représenté par ce chiffre. Por ce faire on va utiliser la méthode des k plus proches voisins, avec diverses valeurs de k : la parité d'un chiffre est vraisemblablement celle qui est majoritaire parmi ceux qui ont une forme voisine de celle du chiffre. Pour cela, on choisit comme métrique, la distance de Hamming qui est le nombre de segments différents entre les deux chiffres. Voici la table des distances de Hamming entre les chiffres de 0 à 9 :

La plus grande distance dans ce tableau est 6. Cela veut dire que les chiffres 1 et 6 sont ceux qui se ressemblent le moins.

I/ Début de l'apprentissage

1) Apprentissage sans test

Pour commencer, on associe la donnée 0 (nombre pair) au chiffre (1,1,1,1,1,1,0) (chiffre 0) :

Les chiffres 0 et 1 sont à distance 4 l'un de l'autre (4 segments verts sans être également rouges) :

Et on confirme qu'ils ne sont pas dans la même classe, en associant la donnée 1 (impair) au chiffre (0,1,1,0,0,0,0) (le chiffre 1). Maintenant qu'on dispose de deux chiffres chacun dans sa classe, on peut appliquer la méthode 1nn pour essayer de deviner la parité du chiffre suivant, avant même la phase d'apprentissage pour ce chiffre.

2) Apprentissage correct

Le chiffre 2 est à distance 3 du chiffre 0 et à distance 5 du chiffre 1 :

Comme le chiffre 2 est plus proche (plus ressemblant) du chiffre 0 (distance 3) que du chiffre 1 (distance 5), on suppose que 2 est pair. Il n'y a pas d'erreur d'apprentissage, et aucune information n'est apportée lorsqu'on associe la donnée 0 (pair) au chiffre (1,1,0,1,1,0,1) (le chiffre 2).

3) Une erreur d'apprentissage

Le chiffre 3 est à distances respectives 3, 3 et 2 des chiffres 0, 1 et 2 :

• D'après la méthode 1nn, il est donc probablement pair (comme le chiffre 2 qui lui ressemble),
• D'après la méthode 3nn, il est également pair puisque parmi ses 3 (seuls) voisins, il y en a 2 qui sont pairs et un seul qui est impair.

Cette erreur d'apprentissage permet alors à l'apprentissage d'apporter une nouvelle information, en asoociant l'information 1 (3 est impair) au chiffre (1,1,1,1,0,0,1) qui représente le chiffre 3 sur 7 segments.

II/ Suite de l'apprentissage

1) le chiffre 4

Le chiffre 4 ressemble un peu au chiffre 1 (distance 2) :

En fait il est à distances respectives 4, 2, 5 et 3 des chiffres dont la parité est déjà connue. Donc

• 1nn le classe comme impair (à l'instar de 1 dont il est le plus proche),
• 2nn le classe aussi comme impair (distance 2 de 1 et distance 3 de 3),
• 3nn le classe aussi comme impair (parmi ses 3 plus proches voisins, il y a 0 qui est pair mais 1 et 3 qui sont impairs : la majorité de ses voisins sont impairs, donc lui aussi).

Il s'agit là encore d'une erreur d'apprentissage puisque 4 est pair. On corrige donc cette erreur en associant la valeur 0 (parité) au chiffre (0,1,1,0,0,1,1) (chiffre 4).

2) Le chiffre 5

Le chiffre 5 ressemble un peu au chiffre 3 (distance 2) :

Il est donc classé comme impair par 1nn. Mais 3nn le classe comme pair (parmi les 3 plus proches voisins 0, 3 et 4 à distances respectives 3, 2 et 3, il y a deux pairs et seul 3 est impair). On peut donc là encore parler d'erreur d'apprentissage et en associant 1 (impair) à (1,0,1,1,0,1,1) (le chiffre 5) on apporte de l'information, et c'est en cela que consiste un apprentissage. Noter que 5nn (applicable dès maintenant) prédisait aussi un chiffre pair, puisque parmi les 5 seuls voisins, il y a 3 chiffres pairs et 2 chiffres impairs : des données d'apprentissage trop peu nombreuses ne sont pas exploitables.

3) Le chiffre 6

Le chiffre 6 ressemble au chiffre 5 (distance 1 seulement) :

La méthode 1nn le classe donc (à tort) comme impair, la méthode 3nn ne le classe pas (il y a 2 voisins à distance 3, et ils ne sont pas de la même parité) et la méthode 5nn le classe comme pair (les 5 plus proches voisins sont 0, 2, 3, 4 et 5 parmi lesquels il y a 3 chiffres pairs et seulement 2 chiffres impairs). On associe donc 0 (pair) à (1,0,1,1,1,1,1) (le chiffre 6).

4) Le chiffre 7

Le chiffre 7 ressemble, c'est bien connu, au chiffre 1 :

Il est donc classé

• comme impair par 1nn,
• comme impair par 3nn (les plus proches sont 1 et 3 qui sont impairs, ainsi que 0 ou 4 qui est pair mais minoritaire),
• mais n'est pas classé par 5nn (2 et 5 sont équidistants de lui mais pas de même parité).

5) Le chiffre 8

Si on trie les voisins de 8 dans l'ordre croissant des distances, on trouve 0, 6, 2, 3, 5, 4, 7, 1  donc

• selon 1nn, 8 est pair (il ressemble à 0 et 6 qui sont pairs),
• selon 3nn, 8 est pair également,
• selon 5nn, 8 est pair également (0, 6 et 2 sont pairs, 3 et 5 sont impairs mais minoritaires),
• et selon 7nn, 8 est pair également (4 chiffres pairs et 3 chiffres impairs dans son voisinage).

On n'apporte donc pas beaucoup d'information en associant 0 (pair) à (1,1,1,1,1,1,1) (le chiffre 8).

6) Le chiffre 9

Le chiffre 9 ressemble à 3, 5 et 8 :

Or, parmi ces 3 chiffres, il y en a 2 qui sont impairs, on s'attend donc à ce que 9 soit aussi impair (c'est ce que dit 3nn). Plus généralement,

• 1nn ne peut classer 9 (si on choisit 8 comme voisin le plus proche au lieu de 3 ou 5, on n'obtient pas la même réponse),
• 3nn classe 9 comme impair,
• 5nn le classe comme pair (les trois chiffres à distance 2 sont tous pairs),
• 7nn le classe également comme comme pair (4 voisins pairs et 3 voisins impairs, ou 5 voisins pairs et 2 voisins impairs selon qu'on choisisse 2 ou 7 à distance 3).

On apporte donc une information utile en associant 1 (impair) à (1,1,1,1,0,1,1) (le chiffre 9).

L'apprentissage est maintenant terminé, on dispose maintenant d'un moyen de deviner la parité d'un chiffre inconnu à partir de sa forme.

III/ Données de test

1) Le chiffre A

En hexadécimal, le nombre dix se représente par un seul chiffre, noté A. Quelle est sa parité ?

Parmi les chiffres pairs, il y en a qui ressemblent à A :

Distance 1 seulement, du chiffre 8 :

Distance 2, seulement, des chiffres 0, 4 et 6 :

En fait, on peut classer dans l'ordre du plus ressemblant au moins ressemblant, les chiffres de 0 à 9 :

Du coup,

• selon 1nn, A est pair,
• selon 3nn, A est pair,
• selon 5nn, A est pair,
• selon 7nn, A est pair.

Dans ce cas, knn estime, à juste titre, que dix est un nombre pair, pour k = 1, 3, 5 ou 7, à partir de sa forme : il a une tête de nombre pair, si on peut dire.

2) Le chiffre b

Sur un afficheur 7 segments, la lettre B ressemble trop au 8 pour qu'on puisse la représenter. On choisit donc une lettre minuscule b qui ressemble beaucoup au chiffre 6 :

Le classement des données d'apprentissage du plus ressemblant au moins ressemblant donne

De ce fait, 1nn, 3nn, 5nn et 7nn classent b comme ayant l'aspect typique d'un chiffre pair, ce qui n'est pas le cas (onze est impair !).

3) Le chiffre C

Le chiffre C (douze en hexadécimal) est, par contre, bien classé comme pair :

4) Le chiffre d

Le chiffre d est par contre classé comme pair (treize est impair) par 3nn, 5nn et 7nn :

5) Le chiffre E

Le chiffre E est considéré comme pair par 3nn, 5nn et 7nn :

Ce qui est correct puisque le nombre quatorze est pair.

6) Le chiffre F

Le chiffre F est aussi considéré comme pair par 3nn, 5nn et 7nn :

Ce qui est faux puisque le nombre 15 est impair.

En conclusion, la forme d'un chiffre (en tout cas sur un afficheur 7 segments) ne semble pas avoir un rapport évident avec sa parité. Pour savoir s'il y a une information de nature arithmétique portée par la forme d'un chiffre, il faudrait utiliser un algorithme d'apprentissage non supervisé comme celui des k moyennes. Mais là, la distance de Hamming ne fonctionne pas.