Abhatoo - Centre Nationale de Documentation

L'extraction de connaissances dans les bases de données est une discipline récente visant à la découverte de nouvelles connaissances. L'extraction de motifs y est une tâche centrale et cette thèse traite de deux cas présentant un caractère générique et particulièrement utile dans de nombreuses applications : celui des bases de données entachées de valeurs manquantes ou comportant un grand nombre d'attributs. Le premier cas est un problème ancien concernant les données issues du monde réel. Sans traitement particulier, les valeurs manquantes sont sources de graves dommages dans les connaissances extraites.

Pour faire face à ce problème, nous proposons un mécanisme de désactivation temporaire des objets incomplets. Il permet d'effectuer des calculs dans une base incomplète, qui mettent en évidence des propriétés des données qui sont compatibles avec les propriétés de la base complète. Nous montrons un résultat de consistance des motifs k-libres extraits dans la base avec des valeurs manquantes. Ces propriétés sont exploitées avec celles issues de la base opposée pour proposer une méthode originale de construction de règles d'association informatives généralisées. Un outil logiciel a été développé pour l'extraction des motifs k-libres en présence de données incomplètes. Le deuxième cas concerne les bases de données aux dimensions inhabituelles, comportant nettement plus d'attributs que d'objets, configuration rendant difficile voire impossible l'application des algorithmes classiques. De nombreuses applications sont caractérisées par des données de ce type. Par exemple le domaine scientifique émergent de l'analyse du génome produit des données sur des dizaines de milliers de gènes, mais les expériences biologiques qui déterminent la séquence de gènes sont coûteuses et donc peu nombreuses. Nous avons développé un cadre formel pour l'extraction de motifs contraints dans ces données, en utilisant un principe de transposition et les propriétés de la connexion de Galois. Ce cadre permet de choisir l'orientation de la base de données qui est la plus favorable pour les algorithmes d'extraction. Les contraintes de recherche sont également transposables, et permettent d'obtenir les motifs contraints en menant les extractions dans le contexte transposée. Enfin, à partir des contributions précédentes, l'utilisation de règles d'association généralisées à des fins d'apprentissage supervisé et de motifs émergents forts complète ces travaux dans le cadre d'applications concernant des données médicales et génomiques.