Sujet de thèse (2014)
 
Algorithmique et stockage distribués pour la fouille de grandes masses de données
Distributed Algorithms and storage for mining big data

Pour candidater, envoyer CV et lettre de motivation à lucas.nussbaum@loria.fr

Contexte et sujet de la thèse

À l'heure actuelle, l'informatique est confrontée à deux problèmes majeurs et récurrents dans tous les domaines : la décentralisation (voire la dématérialisation) des données et leur volume sans cesse croissant. Pour s'adapter à une telle évolution, il faut modifier la façon classique et centrale de résoudre les problèmes et de les voir sous un "angle décentralisé", pour la localisation des données comme pour les traitements (il faut prendre en compte de gros volumes de données et travailler avec des ordinateurs en réseaux). Ce défi est aussi bien réel en découverte de connaissances dans les données. C'est dans ce contexte que se place ce sujet de thèse et qui va étudier un double passage à l'échelle : la distribution des calculs et la gestion de très grands volumes de données. Pour l'heure, il n'existe aucune plate-forme robuste et généraliste qui autorise le traitement de grandes masses de données du point de vue de la découverte de connaissances. Pour répondre à un tel besoin, il faut connaître et s'appuyer sur l'algorithmique de la découverte de connaissances mais aussi sur le traitement et le stockage de données distribuées et volumineuses.

L'équipe Orpailleur mène de nombreux travaux en découverte de connaissances notamment sur l'extraction de motifs et de règles et sur l'analyse formelle de concepts et ses variations . En particulier, la plate-forme Coron, qui est alimentée par ces recherches, renferme une collection d'algorithmes aux caractéristiques diverses permettant de fouiller des données et fonctionne en mode centralisé . Pour aller plus loin et élargir les possibilités d'une telle plate-forme, il faut mettre en oeuvre un traitement décentralisé de données distribuées et volumineuses.

Objectifs de la thèse

Le processus de découverte de connaissances dans les données (KDD) cherche à extraire dans de grands volumes de données des éléments significatifs et réutilisables (règles, corrélations, concepts). Ce processus est itératif et interactif et se divise en trois grandes étapes, (1) la préparation des données, (2) la fouille des données, (3) l'interprétation et la validation des éléments extraits. Dans l'étape centrale, les méthodes de fouilles de données sont numériques ou symboliques. Ce sont les méthodes symboliques qui nous intéressent, avec l'analyse formelle de concepts (FCA) , ainsi que l'extraction de motifs et de règles (PM pour "pattern mining") . Les treillis de concepts produits par le FCA, les motifs et les règles sont liés : la recherche de motifs fréquents revient à parcourir le treillis ou l'ensemble des parties sous-jacent aux ensembles des objets et attributs considérés.

L'objectif de cette thèse est d'étendre les méthodes de découverte de connaissances pour les adapter à de très grands volumes de données. Pour cela, il sera nécessaire de travailler au niveau algorithmique pour pouvoir utiliser efficacement des infrastructures HPC modernes, mais aussi au niveau du stockage des données pendant le processus. De nombreuses solutions de stockage "Big Data" ont été proposées récemment - Memcached, Ceph, Cassandra, Redis, etc. - utilisant divers paradigmes, mais il apparait nécessaire de concevoir de manière conjointe les algorithmes de découverte de connaissance, les représentations des données et enfin les solutions de stockage pour assurer les meilleures performances.

Cette thèse devrait avoir des impacts sur les dimensions théoriques et pratiques. Du point de vue théorique, la thèse va permettre de passer de modes de calcul et de pensée centralisés à un mode décentralisé, pour ainsi rejoindre les recherches de pointe qui s'intéressent à la découverte et à la gestion de connaissances décentralisées . Du point de vue pratique ou applicatif, la thèse va apporter à la plate-forme Coron des algorithmes décentralisés de découverte de connaissances qui seront réutilisés dans les projets de l'équipe mais aussi diffusés à l'extérieur. De plus, la thèse aura aussi des impacts en représentation des connaissances et en ingénierie des ontologies. Actuellement, de nombreux travaux se penchent sur la gestion des ontologies en réseaux et sur le partage de connaissances et le raisonnement distribué qui en découle . Il faut construire dynamiquement des ontologies locales, les mettre en réseau, les tenir à jour et les faire évoluer. Ici, le coût de la création et du maintien des ontologies est un problème majeur. Une des clés pour résoudre ce problème est d'être capable de suivre l'évolution des ressources sur le web et de savoir en tirer les éléments qui peuvent servir d'unités de connaissances dans une ontologie. D'autres applications peuvent aussi être bénéficiaires et se développer à plus grande échelle comme l'annotation sémantique de documents guidée par une ontologie du domaine, la recherche d'informations et de documents en fonction du contenu, ainsi que la recherche et l'édition collaboratives. Dans toutes ces activités, les connaissances, leur découverte et leur disponibilité sont de première importance : il faut savoir extraire ces connaissances à partir de grandes masse de documents disponibles sur le web et les rendre disponibles pour réaliser des systèmes intelligents.

Enfin, cette thèse pourra bénéficier et apporter des cas d'utilisations au travail actuel mené par Lucas Nussbaum au sein de l'équipe Algorille pour améliorer les capacités Big Data de la plate-forme Grid'5000 (https://www.grid5000.fr/), à travers l'initiative nationale Constellation et le projet européen en cours de soumission RENEGAID.

Le plan de travail lié à la thèse

Le plan de travail lié à la thèse peut se décomposer de la façon suivante.

Bibliographie

Daniel Balouek, Alexandra Carpen Amarie, Ghislain Charrier, Frédéric Desprez, Emmanuel Jeannot, Emmanuel Jeanvoine, Adrien Lèbre, David Margery, Nicolas Niclausse, Lucas Nussbaum, Olivier Richard, Christian Pérez, Flavien Quesnel, Cyril Rohr, and Luc Sarzyniec. Adding Virtualization Capabilities to the Grid'5000 Testbed. In IvanI. Ivanov, Marten Sinderen, Frank Leymann, and Tony Shan, editors, Cloud Computing and Services Science, volume 367 of Communications in Computer and Information Science, pages 3--20. Springer International Publishing, 2013.

Tomasz Buchert, Lucas Nussbaum, and Jens Gustedt. A workflow-inspired, modular and robust approach to experiments in distributed systems. In CCGRID - 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, Chicago, United States, May 2014.

Bernhard Ganter and Rudolph Wille. Formal Concept Analysis. Springer, Berlin, 1999.

Mehdi Kaytoue, Sergei O. Kuznetsov, and Amedeo Napoli. Revisiting Numerical Pattern Mining with Formal Concept Analysis. In Toby Walsh, editor, IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 1342--1347, Barcelona, Spain, 2011. IJCAI/AAAI.

Mehdi Kaytoue, Sergei O. Kuznetsov, Amedeo Napoli, and Sébastien Duplessis. Mining Gene Expression Data with Pattern Structures in Formal Concept Analysis. , 181(10):1989-2001, 2011.

Luc Sarzyniec, Tomasz Buchert, Emmanuel Jeanvoine, and Lucas Nussbaum. Design and Evaluation of a Virtual Experimental Environment for Distributed Systems. In PDP2013 - 21st Euromicro International Conference on Parallel, Distributed and Network-Based Processing, pages 172 -- 179, Belfast, United Kingdom, February 2013. IEEE.

Laszlo Szathmary, Petko Valtchev, Amedeo Napoli, Robert Godin, Alix Boc, and Vladimir Makarenkov. A Fast Compound Algorithm for Mining Generators, Closed Itemsets, and Computing Links Between Equivalence Classes. , 2014. to be published.

Jacopo Urbani. Scalable and parallel reasoning in the semantic web. In Lora Aroyo, Grigoris Antoniou, Eero Hyvönen, Annette ten Teije, Heiner Stuckenschmidt, Liliana Cabral, and Tania Tudorache, editors, Proceedings of th 7th Extended Semantic Web Conference (ESWC 2010), Lecture Notes in Computer Science 6089, pages 488--492. Springer, 2010.