L'algorithme que nous allons voir est très utilisé dans ce qu'on appelle le "machine learning" (apprentissage automatique).

En TP, nous allons l'utiliser pour classer des images ; reconnaître des chiffres écrits par des personnes : si la personne a écrit un 1, il faut classer correctement cette image dans la catégorie 1 etc

1) Machine Learning

L'apprentissage automatique consiste à permettre à des ordinateurs d'apprendre en utilisant des modèles à partir d'un ensemble de données. Dans notre cas, notre modèle sera l'algorithme des k plus proches voisins et nos données seront des photos de chiffres manuscrits.

Il nous faut à minima deux échantillons différents : un échantillon pour que le modèle puisse apprendre à partir des données et un échantillon pour tester notre modèle.

En effet, tester sur le même jeu de données que celui utilisé pour l’apprentissage ne permet pas de savoir si notre modèle à vraiment appris quelque chose, c’est à dire s’il est capable de généraliser son apprentissage à des données nouvelles, qu’il n’a “jamais vu”.

Il nous faut également une ou plusieurs fonctions qui vont permettre de donner un score, c'est-à-dire une valeur chiffrée, qui sera utilisée pour mesurer l’écart entre ce qui a été prédit par le modèle et ce qui aurait dû être prédit. Il existe une multitude de fonctions. Nous donnons ci-dessous un exemple dans le cas d'un problème de classification binaire. Ce problème consiste à déterminer si une observation appartient à une classe A ou à une classe B ; par exemple si on cherche à reconnaître si une photo est une photo de chat ou de chien, alors il s'agit d'un problème de classification binaire.

L’exactitude permet de mesurer le taux de prédictions correctes.

\(\begin{equation*} \frac{VP+VN}{VP+VN+FP+FN} \end{equation*}\)

Où VP = Vrai positif, VN = Vrai négatif FP = Faux positif, FN = Faux négatif.

Dans le machine learning il existe plusieurs types d’apprentissages et types de problèmes.

2) Types d’apprentissages et types de problèmes

2.1) Types d’apprentissages

Il existe plusieurs types d'apprentissage, dont principalement :

• Apprentissage supervisé
• Apprentissage non supervisé
• Apprentissage par renforcement

Dans le cas de l'apprentissage supervisé, on fournit à notre modèle la valeur prédite attendue pour l’échantillon d’apprentissage et de test. L'algorithme des k plus proches voisins fait partie des algorithmes d'apprentissage supervisé : dans notre cas, on doit indiquer dans les données utilisées pour l’apprentissage le chiffre correspondant à l'image ; l'algorithme ne peut pas trouver seul sans aide de notre part le chiffre correspondant.

2.2) Types de problèmes

Il existe deux types de problèmes :

• Des problèmes de régression
• Des problèmes de classification

Dans le cas des problèmes de régression, on prédit une ou des valeurs quantitatives. Par exemple : Prédire le prix d’une maison dans un an en fonction de son emplacement, de son nombre de chambres, etc

Dans le cas des problèmes de classification, on prédit une ou des valeurs qualitatives, appelées catégories. Par exemple : le problème que l’on va chercher à résoudre où l’on va devoir déterminer s’il s’agit d’une photo d’un 1, d’un 2 etc, c’est un problème de classification.

L’algorithme des k plus proches voisins est un algorithme supervisé. On ne s’intéressera ici qu’aux problèmes de classification, en prenant le cas d’images qui appartiennent à des classes différentes :classe du chiffre 1, classe du chiffre 2 etc

3) K plus proches voisins

Une représentation visuelle :

L’algorithme des k plus proches voisins est extrêmement simple (dans sa version basique en tout cas) :

• D’abord, nous aurons besoin d’une fonction pour mesurer la distance entre deux images.

• On choisit un paramètre k qui correspond au nombre de voisins les plus proches (en utilisant la fonction d pour mesurer la distance) de l’image dont on cherche à savoir si elle appartient à telle ou telle classe.

• Ensuite on effectue un “vote” : combien d’images voisines parmi les k voisins correspondent à des images de la catégorie A ? Combien correspondent à des images de la catégorie B ?

• On attribue à l’image dont on cherche à apprendre la catégorie l’étiquette (A ou B dans notre exemple) correspondant à la catégorie qui a le plus de voix.

Comment déterminer la distance entre deux objets ?

Si on a deux variables numériques, alors on peut simplement utiliser la distance euclidienne :

D'autres distances (on parle aussi de métriques) existent. Le concept de distance est beaucoup moins évident qu'il n'y paraît. N'hésitez pas à jeter un coup d'oeil ici : https://fr.wikipedia.org/wiki/Distance_(math%C3%A9matiques) si le coeur vous en dit, ne vous privez pas surtout, même si vous n'y comprenez pas grand chose pour le moment !

Mais comment peut-on déterminer la distance entre deux images, ou deux mots ? On va convertir nos images en vecteurs numériques dont on va comparer les distances.

Un vecteur, c’est une flêche qui a une direction, un sens et une norme. Dans une image, l’ensemble des vecteurs peuvent être représentés sous la forme d’une matrice (un tableau de nombres).

Ensuite si on souhaite comparer la distance entre deux images en utilisant la distance euclidienne, cela revient à prendre la racine carrée de la la somme des écarts au carré entre chacune des valeurs de la matrice.

La distance entre une matrice A et une matrice B peut se formaliser ainsi :

\(d_2(\mathbf{A}, \mathbf{B}) = \sqrt{\sum_{i=1}^n \sum_{j=1}^n (a_{ij} - b_{ij})^2}\)

Même sans comprendre cette formule, vous remarquerez j'espère à quel point elle est similaire à la formule précédente.

Dans le cas de mots l’approche est similaire : on convertit le mot en vecteur, nous ne rentrerons pas dans le détail, mais vous pouvez lire cet article si cela vous intéresse : https://en.wikipedia.org/wiki/Word_embedding (Oui c'est en anglais car malheureusement les versions en français sont objectivement moins correctes et précises pour le moment).

Dans le prochain TP nous allons utiliser la librairie scikit-learn pour classifier des images de chiffres manuscrits : nous allons reconnaître automatiquement le chiffre correspondant à l’image.

En attendant, si ce sujet vous intéresse, vous pouvez en apprendre plus en faisant un tour sur https://www.kaggle.com/.