Stage M2R - 2005/2006
Recherche de motifs
séquentiels sous-contraintes
Encadrants
: M. Teisseire - A. Laurent
Dans de nombreux domaines, la
recherche de connaissances temporelles est très
appréciée. Des techniques ont été
proposées aussi bien en fouille de données qu’en
apprentissage, afin d’extraire et de gérer de telles
connaissances, en les associant à la spécification de
contraintes temporelles, notamment dans le contexte de la recherche de
motifs séquentiels.
Toutefois, si l’extraction de tels
motifs est à la fois utile et efficace, elle peut encore
être améliorée. En effet, la fouille de grandes
bases de données rencontre deux limites majeures. D’une part,
l’augmentation de la taille des bases de données
analysées faite croître de façon
exponentielle les espaces de
recherche et de solutions, ce qui rend la fouille de moins en moins
efficace et parfois même impossible. D’autre part, une solution
comportant un trop grand nombre de séquences extraites est
inutilisable car leur analyse et leur interprétation rendues
difficiles par la masse d’information. Il est alors nécessaire
de mettre en place une phase de post-traitement importante et
coûteuse.
L’objectif de ce stage est donc de
définir un formalisme de contraintes pour la recherche de motifs
séquentiels et la mise en oeuvre d’un algorithme efficace pour
la recherche de motifs séquentiels sous-contraintes afin de
pouvoir extraire des ensembles de séquences fréquentes
utiles et exploitables, sans post-traitement conséquent.
Travail à réaliser :
- Etude bibliographique du problème.
- Extension des définitions et méthodes existantes de
recherche de motifs séquentiels afin de permettre la prise en
compte de contraintes.
- Définition d’un formalisme complet intégrant toutes
les contraintes ayant été définies pour la
recherche de motifs séquentiels.
- Implémentation, mise en oeuvre et évaluation sur
des exemples.
Quelques références
[1] S. Bistarelli, and F. Bonchi. Interestingness is Not a
Dichotomy : Introducing Softness in Constrained Pattern Mining. In 9th
European Conference on Principles and Practice of Knowledge Discovery
in Databases (PKDD’05), 10 2005.
[2] J. Pei, J. Han, and W. Wang. Mining Sequential Patterns with
Constraints in Large Databases. In 11th International Conference on
Information and Knowledge Management (CIKM’02), 2002.
[3] N. M´eger, and C. Rigotti. Constraint-Based Mining of Episode
Rules and Optimal Window Sizes. In 8th European Conference on
Principles and Practice of Knowledge Discovery in Databases (PKDD’04),
09 2004.
[4] M. Zaki. Sequence Mining in Categorical Domains : Incorporating
constraints. In 9th International Conference on Information and
Knowledge Management (CIKM’00), 2000.
[5] R. Srikant, and R. Agrawal. Mining Sequential Patterns :
Generalization and Performance Improvements. In 5th International
Conference on Extending Database Technology (EDBT’96), 1996