Ph.D Cyrille Masson

Contributions au cadre des bases de données inductives: formalisation et évaluation de scénarios d'extraction de connaissances

Download Draft here

Date de soutenance : 07/07/2005

Lieu (établissement) : INSA de Lyon

Jury              

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

Pr. Anne Doucet (Rapporteur, Université Paris 6)

Dr. Olivier Gandrillon (Examinateur, CGMC CNRS/Université Lyon 1)

Pr. Dominique Laurent (Rapporteur, Université de Cergy-Pontoise

Pr. Arno Siebes (Examinateur, Université Utrecht, Pays-Bas)

Pr. Laurent Trilling  (Examinateur, Université Grenoble 1)

Résumé. La popularité des technologies de bases de données et d'acquisition de données permettent de récolter une quantité toujours plus grande d'informations, aussi bien en sciences expérimentales (biologie, astrophysique, etc) que dans les domaines commerciaux (supermarchés, marketing ciblé, etc). Il faut aller plus loin dans le processus d'interrogation des données afin d'y découvrir de la connaissance. Cela a conduit au développement du domaine de l'ECD (Extraction de Connaissance dans les données) qui désigne le processus non trivial d'extraction d'information et de connaissance cachées dans les grandes bases de données. La notion de base de données inductive (BDI), présentée en 96, généralise le concept de base de données en intégrant données et motifs extraits à partir des données dans un cadre commun. De ce point de vue, le processus d'ECD peut être vu comme un processus d'interrogation étendu sur une BDI. Ce mémoire de thèse s'inscrit dans le cadre du projet européen cInQ (IST-FET 2000-26469) qui s'intéressait au développement du cadre des Bases de Données Inductives, et auquel il apporte plusieurs contributions aussi bien méthodologiques qu'algorithmiques. Après une première étude critique des langages de requêtes déjà proposés, nous nous intéressons à la formalisation des scénarios d'extraction dans le cadre des BDI. Pour cela, nous montrons comment utiliser un langage abstrait pour les bases de données inductives pour décrire de manière formelle et non ambigüe des processus d'extraction à partir des requêtes de l'utilisateur final. Cela nous permet d'obtenir ce que nous appelons un scénario prototypique, c'est à dire une objet formel, constitué d'une séquence de requêtes inductives sur lequel il devient possible de raisonner. Ce type de scénario sert donc avant tout à formaliser des traitements dans un but de transfert d'expertise entre utilisateurs finaux et spécialistes en ECD. Une autre utilisation possible du concept de scénario est l'évaluation de différentes solutions BDI, dans la lignée des benchmarks déjà existant dans le domaine des bases de données. Ainsi, nous proposons le concept de scénario d'évaluation qui permet de comparer sur une base commune différentes implémentations de BDI. Concrètement, un tel scénario a la même forme qu'un scénario prototypique, mais ici on cherche non pas à faire du transfert d'expertise mais plutôt à mettre en évidence des problèmes algorithmiques et d'optimisation de séquences de requêtes inductives particuliers. Lors de la mise au point d'un plan d'exécution du scénario, le système devra analyser les propriétés des requêtes inductives afin de réaliser un traitement efficace de celui-ci. Cela pourra consister en l'analyse de dépendances entre les requêtes constituant le scénario ou la mise en évidence de conjonctions de contraintes sur un type de motif donné pour lesquelles nous souhaitons disposer d'outils d'extraction efficaces. Nous présentons un premier exemple de scénario d'évaluation dans le domaine de la bioinformatique et nous montrons comment il est possible de le résoudre en utilisant différents techniques déjà existantes dans l'équipe, ou bien développées pour les besoins de l'exécution du scénario.

Publications liées à la thèse

C. Masson, F. Jacquenet. Mining frequent logical sequences with SPIRIT-LoG. Proceedings of  the 12th International Conference on Inductive Logic Programming ILP'02, Sydney (Australia), July 2002. Springer LNAI 2583. pp. 166-182.

C. Masson, F. Jacquenet. Découverte de séquences logiques fréquentes sous contraintes. Actes du 13e Congrès Francophone AFRIF-AFIA de Reconnaissance des Formes et Intelligence Artificielle RFIA'02, Angers (F), janvier 2002. pp. 673-684.

M. Capelle, J-F. Boulicaut, C. Masson. Extraction de motifs séquentiels sous contrainte de similarité. Actes des Journées francophone d'Extraction et de Gestion de Connaissances EGC'02. Montpellier (F), janvier 2002. Hermes. pp. 65-76.

M. Capelle, C. Masson, J-F. Boulicaut. Mining frequent sequential patterns under a similarity constraint. Proceedings of the Third International Conference on Intelligent Data Engineering and Automated Learning IDEAL 2002, Manchester (UK), August 2002. Springer LNCS 2412. pp. 1-6.

M. Botta, J-F. Boulicaut, C. Masson, R. Meo. A comparison between query languages for the extraction of association rules. Proceedings of the Fourth International Conference on Data Warehousing and Knowledge Discovery DaWaK'02, Aix-en-Provence (F), September 2002. Springer LNCS 2454. pp. 1-10.

K. Hatonen, J-F. Boulicaut, M. Klemettinen, M. Miettinen, C. Masson. Comprehensive log compression with frequent patterns. Proceedings of the 5th International Conference on Data Warehousing and Knowledge Discovery DaWaK 2003, Prague (CZ),  September 2003. Springer LNCS 2737, pp. 360-370.

C. Masson, C. Robardet, J-F. Boulicaut. Optimizing subset queries: a step towards SQL-based inductive databases for itemsets. Proceedings of 2004 ACM Symposium of Applied Computing (SAC'2004), Special Track on Data Mining (DM) March 2004, Nicosia, Cyprus. ACM Press. pp. 535-539.

M. Botta, J-F. Boulicaut, C. Masson, R. Meo. Query languages supporting descriptive rule mining: a comparative study. Database support for Data Mining Applications Applications - Discovering Knowledge with Inductive Queries,  R. Meo, P-L. Lanzi and M. Klemettinen Eds., Springer LNCS 2682. pp. 27-54, 2004.

J-F. Boulicaut, C. Masson. Data mining query languages. Data Mining and Knowledge Discovery Handbook, O. Maimon and L. Rokach Editors, Springer, pp. 715-727, 2005.