Résumé en ligne d’un flux de données selon une approche de coclustering régularisé

When:
30/06/2018 – 01/07/2018 all-day
2018-06-30T02:00:00+02:00
2018-07-01T02:00:00+02:00

Annonce en lien avec l’Action/le Réseau : aucun

Laboratoire/Entreprise : Orange Labs Lannion
Durée : 3 ans
Contact : marc.boulle@orange.com
Date limite de publication : 2018-06-30

Contexte :
Le contexte de la thèse est celui de l’analyse de données, aussi appelée fouille de données ou data mining. C’est un processus visant à découvrir, expliquer, décrire des connaissances à partir de données en utilisant des technologies basées sur des techniques statistiques, mathématiques et d’apprentissage automatique, de façon supervisée ou non supervisée.

L’analyse non supervisée, ou exploratoire, vise à étudier les corrélations entre les données, à construire des modèles de clustering ou à estimer des probabilités jointes entre les variables. La thèse se place dans ce contexte d’analyse exploratoire, dans le cas de donnée arrivant en flux, avec une volumétrie telle qu’il n’est pas envisageable de les stocker intégralement. L’objectif sera alors de produire des résumés en ligne de flux, permettant d’explorer et d’analyser le flux a posteriori, alors même que les données à l’origine du résumé auront été perdues (stream), ou sont extrêmement lourdes à manipuler (big data).

L’analyse exploratoire est actuellement le parent pauvre des recherches en analyse de données, d’une part parce que le problème est intrinsèquement difficile, d’autre part parce que les résultats ne se prêtent pas facilement au processus de publication scientifique. Jusqu’à présent, sur les volumes de données relativement limités qu’on analyse couramment, on dispose de techniques exploratoires qui sont à leurs limites (cf. état de l’art) et de techniques supervisées qui sont largement surdimensionnées en termes de capacité. Cette situation asymétrique ne saura perdurer avec l’afflux de données plus volumineuses (big data), voir de données arrivant en flux (stream mining [6]). Les techniques supervisées ont été construites pour supporter la grande volumétrie avec des extensions aux flux de données, mais les techniques exploratoires sont tout simplement dépassées, d’où l’intérêt de s’en préoccuper car l’afflux de grands volumes n’a rien changé au processus général du traitement des données, l’analyse supervisée succède à l’analyse exploratoire et en dépend.

Les masses de données collectées actuellement sont difficiles à exploiter avec les méthodes d’analyse de données classiques pour de nombreuses raisons. Les problèmes suivants reviennent de façon récurrente dans le cadre de l’analyse exploratoire [4]:
– les données réelles sont de type mixte, numérique ou catégoriel, alors que les modèles sont en général spécifiques à un type de données [1, 5]
– les résultats des méthodes classiques sont difficiles à interpréter et/ou à exploiter
– les méthodes classiques sont rarement capables de traiter les masses de données disponibles actuellement.
Outre ces problèmes classiques, dans le cas de données en flux, les approches de stream mining [6,7] doivent trouver un compromis entre la précision et le volume des modèles de résumé. Les méthodes existantes principales sont basées sur :
de l’échantillonnage aléatoire,
– des histogrammes pour avoir des évaluations de densité conditionnellement au temps,
– l’utilisation de fenêtres glissantes pour traiter les données par morceaux,
– des modèles à résolution multiple, principalement basés sur des arbres de décision ou à base de micro-clusters
– des sketches, pour approximer des comptages de valeurs sans avoir à les stocker exhaustivement.

Sujet :
L’objectif de cette thèse est de participer au développement de méthodes d’analyse exploratoire, en étendant l’approche MODL [2] développée depuis plusieurs années à Orange Labs. L’approche MODL s’apparente à une classification croisée entre les valeurs des variables décrivant les individus (K-classification, soit une biclassification dans le cas à deux variables), qui permet d’approximer la densité jointe entre les variables. Une extension récente la rend applicable à une co-classification entre d’une part les individus, d’autre part l’ensemble de toutes les variables, avec des applications à l’analyse exploratoire comme la détection de groupes de variables fortement corrélées ou la segmentation d’individus en groupes similaires.
La méthode a une complexité sous quadratique qui la rend applicable à des très grands volumes de données. Elle est associée à de nombreux outils d’exploitation des grilles basés sur la théorie de l’information [3].

La thèse présentée concerne l’analyse exploratoire sur flux de données, pour lequel une dimension temporelle apparait naturellement, et la collecte des données se fait indéfiniment. L’utilisation de modèle de coclustering intégrant une dimension temporelle permet dès lors d’estimer des densités jointes entre variables, évoluant au cours du temps. Il s’agit ici d’étendre les algorithmes de coclustering existant au cas de données en flux, en tenant compte des contraintes suivantes :
– à chaque instant, la quantité de mémoire disponible pour le traitement d’une fenêtre de données est limitée
– le temps de traitement d’une fenêtre de données est limité
– la mémoire disponible pour stocker le résumé de données est limitée
L’extension des modèles de coclustering est également possible, en envisagent potentiellement une hiérarchie de modèles par fenêtre temporelles.
L’extension de l’approche MODL à ce type de problème repose principalement sur l’élaboration d’algorithmes permettant le calcul de modèle de coclustering sur flux de données, respectant les contraintes de ressources mémoire et temps de calcul.

La première année sera consacrée à un état de l’art sur les méthodes d’analyse exploratoire les plus utilisées sur flux de données, notamment dans le cas de l’estimation de densité univariée (à base de histogrammes) ou multi-variée (à base de micro-clusters), à étudier l’approche MODL et ses extensions actuelles au cas non supervisé, puis à étudier l’extension de cette approche au cas des flux de données. Le passage au flux de données se fera en premier en traitant le cas le plus simple, le traitement d’une seule variable numérique ou catégorielle en flux, qui par bi-clustering avec la variable de temps permet de construire des histogrammes en ligne. La généralisation au cas multivarié sera considérée ensuite, en étendant les modèles de coclustering individus x variables avec l’incorporation d’une dimension temporelle supplémentaire.
Il s’agira ensuite de proposer une méthodologie d’usage de cette approche, d’en explorer les applications en analyse exploratoire et d’en explorer les limites.

La suite du planning sera réalisée en collaboration avec le doctorant. A la fin de la première année : on aura déterminé la suite des travaux à mener sur les deux années à venir.
Typiquement, la deuxième année sera consacrée à l’approfondissement de la voie de recherche identifiée en première année. La troisième année consistera à finaliser ces travaux, à les valoriser sous formes d’articles scientifiques, et à la rédaction du manuscrit de thèse.

Références
[1] S. Boriah, V. Chandola et V. Kumar : Similarity measures for categorical data : A comparative evaluation. In SDM, pages 243–254, 2008.
[2] M. Boullé. Data grid models for preparation and modeling in supervised learning. In Hands-On Pattern Recognition: Challenges in Machine Learning, volume 1, I. Guyon, G. Cawley, G. Dror, A. Saffari (eds.), pp. 99-130, Microtome Publishing, 2011.
[3] R. Guigourès. Utilisation des modèles de co-clustering pour l’analyse exploratoire. Phd thesis. 2013.
[4] A.K. Jain et R.C. Dubes : Algorithms for clustering data. Prentice-Hall, Inc.,1988.
[5] R.D. Wilson et T.R. Martinez : Improved Heterogeneous Distance Functions. Journal of Artificial Intelligence Research, 6:1–34, 1997.
[6] J. Gama (2010). Knowledge Discovery from Data Streams. Data Mining and Knowledge Discovery. Chapman and Hall
[7] B. Babcock, S. Babu, M. Datar, R. Motwani, and J.r Widom, Models and Issues in Data Stream Systems, in Proc. 21st ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS 2002), 2002.

Profil du candidat :
Le profil souhaité est BAC + 5, école d’ingénieur ou Master Recherche statistiques et/ou mathématiques appliquées et/ou informatique.

Formation et compétences requises :
Le doctorant devra avoir une bonne connaissance des statistiques et des mathématiques.
Des connaissances en apprentissage statistique sont un réel plus.
Des compétences en programmation sont nécessaires: maitrise d’un langage de script (à minima) dédié à l’analyse de données (R, matlab, python avec bibliothèque scikit-learn…). La connaissance d’un langage orienté objet serait appréciée.
Une forte motivation, des capacités de synthèse, à bien rédiger et présenter les travaux (anglais) et à s’intégrer dans une équipe sont également demandées.
Une expérience est souhaitée sous la forme d’un stage dans le domaine statistique

Adresse d’emploi :
Orange Labs Lannion
2 avenue Pierre Marzin
22307 Lannion Cedex
France

Pour postuler en ligne :
https://orange.jobs/jobs/offer.do?joid=69229&lang=FR

Document attaché :