C20 k plus proches voisins, k-moyennes

Cours

Support de cours chapitre 20

Attention

Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.

Travaux pratiques

Jeu de données

Quelques sites proposant des jeu de données pour les algorithmes de classification :

• Site de l'université Irvine de Californie
• Kaggle

Exercice 1 : Un exemple corrigé pour knn

A propos des notebooks

On utilise pour la première fois les jupyter notebook, c'est-à-dire des documents contenant à la fois :

• des zones de texte explicatives,
• des zones de code Python, executables directement à la façon de ce qui se passe lorsqu'on utilise Python en mode console.

A chaque fois, que nous utilisons cet outil, deux choix s'offrent à vous :

1. l'utiliser localement sur votre ordinateur à condition d'y avoir installé jupyter notebook (c'est le cas sur les ordinateurs de la salle). Pour cela, créer un dossier nommé par exemple Notebook et depuis un terminal lancer jupyter dans ce dossier en écrivant simplement :

   jupyter notebook
   

   L'application se lance dans votre navigateur, télécharger le notebook et utiliser le bouton Téléverser en haut à droit pour le télécharger dans votre dossier et l'ouvrir.

2. Utiliser l'application Capytale de votre environnement numérique de travail metice. Dans ce cas, utiliser le lien de partage fourni dans l'activité. Cette option vous permet notamment de travailler depuis la maison car aucune installation (ni de Python, ni de Jupyter) n'est nécessaire.

Les activités utilisant un notebook proposerons donc toujours les deux options décrites ci-dessus.

• Télécharger le notebook pour l'utiliser en local (installation de jupyter nécessaire)Notebook : Algorithme knn
• Utiliser l'application Capytale (aucune installation nécessaire)

Correction

• Télécharger le notebook pour l'utiliser en local (installation de jupyter nécessaire)Notebook : Correction Algorithme knn
• Utiliser l'application Capytale (aucune installation nécessaire)

Exercice 2 : Un exemple pour k-moyenne

• Télécharger le notebook pour l'utiliser en local (installation de jupyter nécessaire)Notebook : Algorithme knn
• Utiliser l'application Capytale (aucune installation nécessaire)

Exercice 3 : Les passagers du titanic

Le but de l'exercice est d'utiliser un algorithme de classification pour prédire la survie des passagers du Titanic. Les données sont à récupérer sur le site Kaggle et sont déjà séparées en deux parties :

• des données d’entraînements
• des données de test

Les données sont au format csv et le détail des champs est donné sur Kaggle.

Aide

On pourra bien sûr commencer par écrire :

• une fonction permettant de lire les données et de les récupérer dans un format exploitable
• une fonction permettant de calculer une distance entre deux passager

Exercice 4 : Reconnaissance de chiffres manuscrits

Une des plus célèbres bases de données de chiffres manuscrits utilisée pour tester les algorithmes de classification est celle du mnist. Cette base de donnée est disponible sur le site de Yann LeCun et se compose d'un ensemble de 60000 images déjà classés et d'un ensemble de 10000 images pour les tests.

Etant donnée sa taille importante, les images et leur classification sont dans un format binaire appelé idx non directement exploitable. Cependant vous trouverez ci-dessous un extrait de cette base constitué de 5000 images : Chiffres Les images du fichier précédent sont au format PGM bien plus facilement lisible et exploitable à notre niveau. En effet, chaque image est un fichier texte contenant :

• sur la première ligne on trouve on code ("magic number") qui indique le format de l'image PGM ici c'est P2
• sur la seconde ligne on trouve les dimensions de l'image :28 28 (les images sont toutes carrés de 28 pixels de côté)
• sur la troisième ligne le 255 est le niveau de couleur maximal d'un pixel, ici 0 correspond donc au noir, 255 au blanc.
• sur la quatrième on trouve la valeur du chiffre manuscrit précédé de # (c'est en commentaire)
• les 28 lignes suivantes sont les pixels de l'image et sont donc composées chacune de 28 nombres indiquant le niveau de gris de l'image.

A titre d'exemple le première image ci-dessous (celle de numéro 42 commence par les lignes suivantes :) Le but de l'exercice est de tester les deux algorithmes de classification vus en cours sur cet exemple.

1. Télécharger le fichier, le décompresser et visualiser quelques images. Vérifier en comparant avec les exemples suivants :

   Numéro	Image	Chiffre
   42		8
   1515		7
   2023		1

2. Ecrire une fonction lire_image qui prend en argument le numéro d'une image et renvoie un tuple composé du chiffre de l'image et d'une liste représentant les niveaux de gris des pixels de l'image (cette liste sera donc constitué de 28x28 nombres entiers compris entre 0 et 255).

   Aide

   On rappelle que :

   • l'image est au fichier texte,
   • le chiffre se trouve sur la quatrième ligne et qu'il est précédé du caractère #
   • les niveaux de gris de chaque pixel sont sur les lignes suivantes.

3. Ecrire une fonction distance qui permet de calculer le carré de la distance euclidienne entre deux images de dimension 28x28.

4. Mettre en oeuvre la méthode des k plus proches voisins sur cet exemple en utilisant les 4500 premières images comme image déjà classées et en utilisant les 500 suivantes pour les tests.

   Aide

   On pourra tester différentes valeurs de k et choisir une distance différente

5. Mettre en oeuvre la méthode des k-moyennes pour classer les 5000 données.

6. Comparer les résultats des deux méthodes.