MODL est à l'origine une technique de discrétisation inventée par Marc Boullé, chercheur à Orange Labs, avec qui j'ai le plaisir d'encadrer Romain Guigourès. Marc a tiré de ce travail initial un principe général d'estimation de densité par une approche en grille. L'idée est de construire totalement automatiquement une sorte d'histogramme multi-dimensionnel (la grille) dont les paramètres (taille des cases, regroupement de valeurs dans le cas nominal, etc.) sont déterminés par une approche de type Maximum à posteriori qui réalise un compromis entre complexité de la grille et ajustement aux données.

MODL pour l'analyse exploratoire

En tant qu'outil d'estimation de densité, MODL est un candidat naturel pour l'analyse exploratoire de données (comme le mélange de Gaussiennes, par exemple). Cependant, MODL cherche à bien estimer la densité d'une variable aléatoire multi-dimensionelle, même au prix d'une solution très complexe (du moment qu'on dispose d'assez de données pour rendre cette solution vraisemblable). Les recherches de Romain Guigourès portent donc sur la mise au point d'un ensemble de techniques permettant d'exploiter les résultats de MODL et son principe général en analyse exploratoire.

Nous avons étudié par exemple comme une approche de fusion à posteriori des groupes construits par MODL conduisait à une estimation certes plus grossière de la densité de la variable considérée mais aussi plus facile à interpréter. Les résultats sont disponibles dans l'article suivant.

» Clustering hiérarchique non paramétrique de données fonctionnelles. Marc Boullé, Romain Guigourès et Fabrice Rossi. Dans les actes de la 12ème Conférence Internationale Francophone sur l'Extraction et la Gestion des Connaissances (EGC'2012), pages 101-112, Bordeaux, France, Février 2012.

MODL pour la classification des sommets d'un graphe

De façon peut être étonnante, MODL est une alternative très intéressante aux approches de type stochastic blocmodels. On considère en effet la classification des sommets comme un sous-produit de l'estimation d'une variable aléatoire à deux composantes. Chaque réalisation de cette variable produit un couple (a,b) interprété comme un arc entre les sommets a et b. En estimant la distribution de cette variable à partir d'un échantillon (c'est-à-dire d'un graphe) dans l'approche MODL, on obtient une grille décrite par une partition des sommets émetteurs et récepteurs dans le graphe.

Nous avons appliqué cette approche à un journal d'appels téléphoniques dans l'article suivant.

» Segmentation géographique par étude d'un journal d'appels téléphoniques. Romain Guigourès, Marc Boullé et Fabrice Rossi. Présenté à la 2ème Journée thématique : Fouille de grands graphes, Grenoble (France), Octobre 2011.

En ajoutant une troisième dimension à la variable aléatoire, on étend cette approche aux graphes temporels. J'ai présenté ce travail le 21 novembre 2012 au séminaire de statistique du CNAM (cf les transparents) et nous avons publié l'article suivant à ce sujet.

» Triclustering pour la détection de structures temporelles dans les graphes. Romain Guigourès, Marc Boullé et Fabrice Rossi. Présenté à la 3ème conférence sur les modèles et l'analyse des réseaux : Approches mathématiques et informatiques (MARAMI 2012),

Romain présentera ce travail en décembre au workshop sur le Co-clustering organisé à ICDM 2012. Notre article sur une application de la méthode à des données de France Telecom vient aussi d'être accepté pour EGC 2013.

MODL pour la classification de trajectoires

Je travaille aussi avec Mohamed Khalil El Mahrsi sur la classification de trajectoires d'objets mobiles évoluant sur un réseau contraint. Avec l'aide de Romain, nous avons appliqué récemment MODL à ce problème, en produit une classification croisée des trajectoires et des segments routiers. Ce travail vient d'être accepté pour EGC 2013.

Date de publication

24 novembre 2012

Mots clés

research

2013

EGC

clustering

trajectory

graph

MODL

coclustering