Module : Classification par kPPV

Classification par k Plus Proches Voisins (kPPV)
proposé par :
Michel Roux (at telecom-paristech.fr, 8128)
complexité : moyenne, cumulable avec d’autres modules

 

Descriptif
Lorsque l’on dispose d’un nombre important de données, il peut être envisagé de les classer, en exploitant un critère de similarité entre ces données. Par exemple, on peut vouloir créer une classe d’images qui se ressemblent en termes de couleurs ou créer une classe de sons qui ont des similarités acoustiques. Ces classes peuvent être connues à l’avance ou non, on parle alors de classification supervisée ou non supervisée. Les kPPV sont une méthode de classification supervisée, pour laquelle les classes souhaitées sont connues à l’avance et l’on dispose d’exemples de données associées à ces classes. Le terme kPPV désigne finalement la méthodologie employée pour classer une nouvelle donnée : cette donnée est comparée à toutes celles dont la classe est connue ; cette comparaison nécessite une mesure (distance, similarité) permettant de trouver les voisins, ie les données les plus proches selon cette mesure. La classe prédite pour la nouvelle donnée est généralement la classe majoritaire parmi ses k plus proches voisins. La valeur de k est un paramètre important dont la valeur est à discuter. Les données que nous manipulerons seront vectorielles. Il est possible de faire des opérations similaires sur des graphes, mais cela serait trop lourd à mettre en oeuvre dans PACT. Il est à noter qu’il existe de nombreux autres classificateurs (supervisés ou non). Différentes UE du cycle master vous sont proposées pour les découvrir, en particulier SI221 (Laurence Likforman).

 

Ressources dont le module dépend
  • aucune dépendance a priori mais possibilité d’exploiter une librairie JAVA (à choisir avec l’expert) pour développer le code de la classification.
  • UE de reconnaissance des formes (SI221)
  • définition mathématique d’une mesure, d’une distance, d’une similarité
  • une base de données (vectorielles) définie dans le projet du groupe

 

Exemples d’utilisation du module
  • sur des signatures d’images ou sons, en vue d’une classification ou pour retrouver une signature similaire dans une base de données

 

 Objectifs d’apprentissag
  • Notion en apprentissage automatique : distances, similarités, apprentissage, évaluation, validation croisée
  • Compétence à développer : à l’issue de ce module vous aurez défini et programmé un classificateur kPPV en Java et vous saurez l’évaluer sur une base de données

 

 Résultats attendus
  • PAN1 :
    • Savoir définir les termes suivants : une distance, une similarité, apprentissage automatique, classification.
    • Savoir expliquer en quoi cet outil de classification est a priori intéressant dans le projet du groupe.
  • PAN2 :
    • Livrable : Etude bibliographique sur les notions de distance et similarité
    • Livrable : Pseudo code implémentant la classification par kPPV, en Java et le programme de test afférant.
  • PAN3 :
    • Livrable : code Java et premières mesures de performance sur des données standards (par forcément en lien avec votre projet).
  • PAN4 : Livrable : rapport de performance, en situation d’usage.

 

Laisser un commentaire