<note> Thèmes : fouille de données (data mining), apprentissage statistique (machine learning), problème d'énumération, big data, data science Encadrant(s) : Marc Plantevit, Anes Bendimerad, Adnene Belfodil Laboratoire : LIRIS Equipe : DM2L </note>

La fouille de motifs permet d'extraire des connaissances dans de gros volumes de données. Conjugués à diverses mesures d'intérêt,de nombreux langages de motifs ont été considérés (ensembles, séquences, graphes, graphes dynamiques, etc.) au travers de solutions algorithmiques efficaces. Toutefois, la découverte de motifs reste un problème très difficile (NP-Complet) pour lequel nous n'avons aucune garantie sur les temps d'exécution. Il est donc nécessaire de travailler sur des heuristiques pour retourner, de façon instantanée, des motifs intéressants à l'utilisateur.

Dans cette optique, de nombreux travaux se sont intéressés à l'échantillonnage des motifs avec garantie (la probabilité de retourner un motif est proportionnelle à l'intérêt du motif par rapport à la mesure considérée). Ces travaux se répartissent en deux grandes familles : les approches stochastiques qui vont faire des marches aléatoires dans l'espace des motifs et l'échantillonnage direct qui va identifier un tuple, puis générer un motif à partir de ce tuple.

L'objectif de ce projet est de comprendre puis d'implémenter et comparer ces différentes méthodes d'échantillonnage de motifs. On se restreindra à des langages de motifs simples (motifs ensemblistes) pour lesquels nous considérerons un ensemble de mesures d'intérêt. Idéalement, une librairie (python) est attendue.

Ce projet est pertinent pour les étudiants désirant s'orienter vers les parcours de masters 2 DS, TIW, IA.

Mohammad Al Hasan: Mining interesting subgraphs by output space sampling. SIGKDD Explorations 12(1): 73-74 (2010)

Mohammad Al Hasan, Mohammed J. Zaki: Output Space Sampling for Graph Patterns. PVLDB 2(1): 730-741 (2009)

Mario Boley, Sandy Moens, Thomas Gärtner: Linear space direct pattern sampling using coupling from the past. KDD 2012: 69-77

Mario Boley, Claudio Lucchese, Daniel Paurat, Thomas Gärtner: Direct local pattern sampling by efficient two-step random procedures. KDD 2011: 582-590

Mario Boley, Thomas Gärtner, Henrik Grosskreutz: Formal Concept Sampling for Counting and Threshold-Free Local Pattern Mining. SDM 2010: 177-188

Arnaud Giacometti, Arnaud Soulet: Dense Neighborhood Pattern Sampling in Numerical Data. SDM 2018: 756-764