Declarative Approaches for Mining Frequent Itemsets over Transactional Databases

Approches déclaratives pour l'extraction des itemsets fréquents à partir des bases de données transactionnelles La fouille de données est une étape primordiale du processus d’extraction de connaissances à partir des données. Elle a pour but d’analyser de grandes quantités de données afin de découvrir des connaissances. L’extraction des itemsets fréquents à partir d’une base de données transactionnelle est l’une des tâches principales de la fouille de données, qui consiste à identifier divers types de motifs afin de répondre aux besoins des utilisateurs ou des applications. Différentes approches d’extraction des itemsets fréquents ont été introduites dans la littérature et peuvent être scindées en deux catégories: spécialisées et déclaratives.Les travaux de cette thèse se situent dans la seconde catégorie d’approches. Les approches déclaratives basées sur SAT pour l’extraction des itemsets fréquents se distinguent par leurs flexibilités et permettent d’extraire divers types de motifs particuliers par ajout de contraintes. Toutefois, ces approches sont inefficaces pour traiter les grandes bases de données transactionnellesdû principalement à la taille des encodages et au nombre élevé des itemsets à extraire. Dans notre première contribution, nous montrons les limites des approches d’énumération de modèles à base des solveurs CDCL pour ces encodages et proposons une solution alternative de type DPLL plus appropriée. Dans la deuxième contribution, et pour pallier le problème de la taille del’encodage, nous proposons d’utiliser une technique de partitionnement. Cela permet de ramener l’énumération de tous les modèles en l’énumération de modèles de sous-problèmes de taille réduite. Cette approche permet un passage à l’échelle et se montre plus performante que les approches basées sur la programmation par contraintes. Nous étendons également ce cadre pour considérer la résolution en parallèle des sous-problèmes générés. Notre troisième contribution est une nouvelle approche d’extraction des motifs fréquents maximaux, appelé SATMax, utilisant de manière originale les solveurs SAT pour énumérer efficacement tous les itemsets maximaux d’une base de données transactionnelle. L’évaluation expérimentale sur différents jeux de données montre l’efficacité de cette approche par rapport à quelques algorithmes spécialisés et déclaratifs de l’état de l’art. La dernière contribution de cette thèse porte sur l’énumération des motifs fréquents à partir des données incertaines. Nous étendons les approches déclaratives basées sur les contraintes. Nous montrons que la contrainte de support (expected support) donne lieu à une contrainte non linéaire. Nous introduisons par la suite une approche incrémentale en la taille des itemsets associée et une relaxation de la contrainte d’expected support exprimée par une contrainte linéaire permettant d’accélérer l’énumération.