Ph.D Marion Leleu

Extraction de motifs séquentiels sous contraintes dans des données avec répétitions consécutives

Download Draft here

Date de soutenance : 09/01/2004

Lieu (établissement) : INSA de Lyon

Jury              

Dr. Jean-François Boulicaut (Directeur de thèse, INSA Lyon)

Dr. Guillaume Euvrard (Examinateur, Informatique CDC)

Pr. François Jacquenet (Rapporteur, Université de Saint-Etienne)

Dr. Fosca Giannotti (Examinateur, CNR Pise, Italie)

Pr. Pascal Poncelet (Rapporteur, Ecole des Mines d’Ales)

Dr. Christophe Rigotti (Examinateur, INSA Lyon)

Résumé. Le développement de l'informatique a entraîné la création de bases de données de plus en plus nombreuses et de plus en plus volumineuses dans de nombreuses disciplines (biologie, finance, réseaux, internet, commerce, ...).  Aujourd'hui, les utilisateurs de ces bases de données ne sont plus uniquement demandeurs d'outils d'interrogations efficaces mais souhaitent aussi des synthèses intéressantes ou plus généralement l’explicitation de connaissances depuis leurs données. Cette demande a fait émerger le domaine de la fouille de données au milieu des années 1990 (« Data Mining » en anglais). Un axe de recherche typique en « data mining » concerne le traitement de données séquentielles, e.g., des séquences d'achats dans la grande distribution, des traces d’usagers sur des sites WWW ou encore des séquences d'ADN en biologie. La recherche de régularités dans de grandes bases de séquences a reçu une intention toute particulière et de nombreux algorithmes ont été proposés pour traiter l’extraction de motifs séquentiels satisfaisant des contraintes variées (e.g., être assez fréquent, ne pas contenir certains sous-motifs, être présents dans un intervalle temporel ou spatial de taille déterminée). Dans notre contexte d’application (traitement de données financières où l’évolution de produits boursiers est représentée par des séquences d’événements), nous avons voulu appliquer des algorithmes efficaces développés par M. Zaki entre 1999 et 2001 aux USA. Ils exploitent une représentation en mémoire des positions de motifs (listes d’occurrences, algorithmes Spade et CSpade). Les premières expériences ont montré que ces algorithmes fonctionnent mal en présence de répétitions consécutives dans les séquences, une situation justement fréquente dans le traitement des séries temporelles boursières mais aussi dans de nombreux autres contextes applicatifs. Ainsi, on peut avoir souvent des clients qui achètent plusieurs fois un même article, des usagers de site WWW qui charge plusieurs fois une même ressource ou encore, dans le cas typique des vocabulaires d’événements réduits (cas des séquences ADN), des probabilités de répétitions consécutives d’un même symbole très élevées. Dans cette thèse, nous tentons d'apporter des solutions au problème de l'extraction de motifs séquentiels sous contraintes dans le cas de données contenant des répétitions consécutives. La solution apportée s’appuie sur une généralisation des listes d'occurrences et propose de condenser les informations qu'elles contiennent, sans perte pour les extractions de motifs visées. Nous avons développé deux extracteurs de motifs séquentiels, GoSpade (traitement de la seule contrainte de fréquence minimale)  et GoSpec (introductions d’autres contraintes fixées par l’utilisateur). Les algorithmes correspondants ont respectivement fait l'objet d'une démonstration de justesse et de complétude.  Nous avons procédé à des expérimentations sur des jeux de données réelles et synthétiques qui montrent une nette amélioration des performances en présence de répétitions consécutives. Les gains obtenus, en terme  d'espace mémoire et de temps d'exécution, permettent de travailler sur des volumes de données plus importants et à des seuils de fréquence plus faibles, ce qui est l’une des principales préoccupations dans ce domaine de recherche. La dernière partie de cette thèse concerne une application, dans le domaine des marchés financiers visant à construire une représentation synthétique de différentes tendances boursières sous forme de motifs séquentiels caractéristiques. Nous avons pu montrer que les motifs fréquents constituant une tendance contiennent une information qui est bien spécifique de la tendance représentée.

Publications liées à la thèse

M. Leleu, J-F. Boulicaut. Signing stock market situations by means of characteristic sequential patterns. Proceedings of the Third International Conference on Data Mining Methods and Databases for Engineering, Finance and Other Fields Data Mining 2002, Bologna (I), September 2002. pp. 655-664. WIT Press.

M. Leleu, C. Rigotti, J-F. Boulicaut, G. Euvrard. GO-SPADE: mining sequential patterns over datasets with consecutive repetitions. Proceedings of the IAPR Third International Conference on Machine Learning and Data Mining in Pattern Recognition MLDM'03, Leipzig (D), July 2003. Springer LNCS 2734. pp. 293-306.

M. Leleu, C. Rigotti, J-F. Boulicaut, G. Euvrard. Constraint-based sequential pattern mining over datasets with consecutive repetitions. Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases PKDD 2003, Cavtat-Dubrovnik (HR), September 2003.  Springer LNAI 2838. pp. 303-314.

M. Leleu, N. Meger, C. Rigotti. Extraction de motifs séquentiels fréquents sous contraintes dans des données contenant des répétitions consécutives. RSTI Ingénierie des Systèmes d’Information ISI  9(3/4):133-160, 2004.