"Transporter" les données pour mieux les classer

Publié par Redbran le 12/08/2017 à 00:00
Source et illustrations: CNRS INS2I
...
Restez toujours informé: suivez-nous sur Google Actualités (icone ☆)

International Conference on Machine Learning (ICML) est une des conférences de référence sur l'apprentissage, outil essentiel pour l'analyse efficace d'un grand volume de données. L'opportunité de découvrir des exemples de ce domaine très visible actuellement. Dans ce premier focus, des chercheurs ont développé une nouvelle méthode pour créer des groupes dans des données en exploitant toute la richesse d'un outil mathématique appelé transport optimal.

Dans le domaine de l'apprentissage non supervisée, où les données ne sont pas "étiquetées" par des humains pour les définir, un champ de recherche concerne la classification des données, pour pouvoir créer automatiquement des groupes qui fassent du sens. La classification simple cherche à créer des groupes d'individus qui partagent des caractéristiques proches. La classification croisée (ou co-clustering) effectue la même démarche pour les individus mais aussi pour les caractéristiques qui les définissent (appelées variables). Dans l'exemple ci-dessous, les individus seraient uniquement regroupés en fonction de leur genre ou autres variables, mais on pourrait voir également apparaître des corrélations entre différentes caractéristiques: les personnes brunes ont plus souvent les yeux marrons, les personnes de grande taille ont un poids plus élevé...


En réorganisant les données dans un tableau (ou matrice) qui décrit les individus et leurs différentes variables, les algorithmes de classification croisée visent à créer des blocs homogènes. Ces blocs, appelés aussi co-clusters, peuvent être considérés comme des sous-ensembles de la matrice de données. Cet outil d'interprétation des groupes permet ainsi de faire ressortir des informations pertinentes sur des individus mais aussi sur des variables qui ont des comportements proches.

Pour exploiter ces données, il faut imaginer que les chercheurs représentent les informations par des points dans des dimensions qui peuvent être très grandes. Ainsi, de la même façon qu'un point peut être défini par une abscisse et une ordonnée dans un plan à deux dimensions, un individu peut être défini par un point dans un espace aux dimensions qui correspondent au nombre de variables qui le caractérisent: il se situe à tel niveau sur la dimension "genre", tel autre pour la dimension "taille", et ainsi de suite. Cette constellation de points, difficile à représenter, est également réalisé pour chaque variable. Le nombre de dimensions correspond cette fois au nombre d'individus, qui est généralement beaucoup plus grand dans les bases de données ! Ainsi, pour l'exemple de la couleur des cheveux, la variable ne prendra pas uniquement 4 ou même 10 types de réponses possibles, mais la nuance précise de chaque individu, ce qui créera ainsi une dimension à chaque fois.

Pour permettre le rapprochement entre la constellation de points des individus et celle des variables, toujours dans le but de créer des groupes, les chercheurs de la publication Co-clustering through Optimal Transport ont eu l'idée originale d'exploiter un outil mathématique appelé transport optimal. La force de cet outil est de chercher à transporter des ressources au moindre coût, qu'il s'agisse d'objets réels ou de couleurs dans une image. Le transport optimal définit une distance entre des ensembles en mesurant "l'effort" de transfert de la masse pour passer d'une distribution à l'autre. Cet outil permet ainsi de déterminer les associations entre deux ensembles d'objets en minimisant la distance qui les sépare. Les chercheurs ont ainsi considéré que les deux ensembles devant être transporté l'un vers l'autre, était l'ensemble des individus d'une part et l'ensemble des variables qui les caractérise d'autre part. L'intuition des chercheurs était que plus le coût de transport pour déplacer un point vers un autre était faible, plus les données étaient proches, permettant ainsi de les regrouper en blocs homogènes.

Restaient à déterminer la matrice de coût de transport, récapitulatif de combien peut coûter chaque transport, et le plan de transport, sorte de feuille de route logistique pour mener le transport optimal. Pour cela les chercheurs ont exploité la version régularisée du transport proposée par Marco Cuturi en 2013, qui permet une meilleure répartition des transports et une solution moins stricte dans la distribution. Puis ils ont appliqué l'algorithme de Sinkhorn-Knopp qui permet un calcul efficace. La solution obtenue décompose le plan de transport en une factorisation en trois termes: la matrice de coût associée au transport d'un ensemble sur l'autre et deux vecteurs de normalisations assurant que le plan de transport soit bi-stochastique.


Les chercheurs devaient encore déterminer dans lequel de ces trois éléments (matrice de coût et deux vecteurs) se trouvait la réponse de la répartition en co-clusters. Ils ont pu définir que les vecteurs de normalisations pouvaient être vus comme des approximations de distributions des blocs homogènes des individus et des variables. Autre avancée très importante, grâce à cette méthode les chercheurs sont capables de déterminer automatiquement le nombre de co-clusters, contrairement aux méthodes habituelles qui nécessitent de définir un nombre arbitraire au préalable.

Les chercheurs ont pu tester leur nouvelle méthode sur un jeu de données publiques sur la recommandation de films (900 utilisateurs, 1600 films et 100 000 notes). La méthode classique de recommandation se base sur l'apprentissage de profils d'utilisateurs proches pour conseiller d'autres films que ces utilisateurs voisins ont aimés. Dans l'application de leur approche à ce jeu de données, les chercheurs ont ainsi construit simultanément des groupes d'utilisateurs et des groupes de films homogènes, c'est-à-dire des groupes d'utilisateurs ayant les mêmes goûts en termes de films et des groupes de films recevant les mêmes notes par les utilisateurs. Dans les deux cas, le nombre de groupe a été défini automatiquement, et les chercheurs ont pu donner une interprétation cohérente à ces groupes et montrer la capacité de leur approche pour prédire une bonne recommandation de films aux utilisateurs.


Légende de l'image

Référence publication:
Co-clustering through Optimal Transport, de Charlotte Laclau [1] [2], Ievgen Redko [3], Basarab Matei [1], Younès Bennani [1], Vincent Brault [4]

[1] Laboratoire d'Informatique de Paris-Nord (LIPN - CNRS/Université Paris 13)
[2] Devenue post-doctorante au Laboratoire d'Informatique de Grenoble (LIG, CNRS/Inria/Grenoble INP/Université Grenoble Alpes)
[3] Centre de Recherche en Acquisition et Traitement d'Images pour la Santé (CREATIS - CNRS/Inserm/Université de Lyon/INSA Lyon)
[4] Laboratoire Jean Kuntzmann (LJK – CNRS/Grenoble INP/Université Grenoble Alpes)

Pour plus d'information voir:
- International Conference on Machine Learning
- Co-clustering through Optimal Transport
- couleurs dans une image
Page générée en 0.455 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise