La fouille de séquences est un domaine actif de la fouille de données, étant un élément clé de nombreuses applications réelles dès lors que l'information est structurée par une relation d'ordre (e.g., le temps). Elle vise à extraire des sous-séquences qui apparaissent fréquemment dans les données et permet ainsi de mettre en évidence des relations entre éléments au cours du temps et peut être utilisée à des fins de prédiction (e.g., classification, classification au plus tôt) ou de description (e.g., élicitation d'hypothèses, regroupement). Elle est appliquée avec succès dans de nombreux domaines tels que la biologie (séquences ADN ou de protéines), le traitement automatique de la langue (séquences de mots/lemmes), etc.
Depuis son introduction en 1995, de nombreux algorithmes de découverte de séquences fréquentes ont été introduits. Curieusement, tous ces algorithmes sont exhaustifs. L'espace de recherche est bien souvent parcouru en profondeur d'abord en énumérant des éléments candidats suivant un ordre arbitraire (souvent l'ordre lexicographique) et toutes les solutions satisfaisant la contrainte (e.g., être fréquent) sont retournées. Ceci est une réelle limite à l'application de tels algorithmes : le nombre de solutions retournées peut être combinatoire et le temps pour les extraire prohibitif.
L'objectif de ce projet de recherche est de proposer une méthode d'échantillonnage de séquences intéressantes (e.g., fréquentes, discriminantes, etc.). L'échantillon retourné doit être représentatif de l'ensemble complet des séquences d'intérêt. Il faut également s'assurer d'une bonne diversité des résultats.
Dans ce contexte, le travail demandé est le suivant :
Ce projet est pertinent pour les étudiants désirant s'orienter vers les masters 2 DS, TIW, IA.