Declarative Itemset Mining Based on Constraint Programming

Data mining is the art of discovering knowledge from databases. The user specifies the type of patterns to be mined, and the miner uses techniques to find the required patterns. Many techniques have been introduced for mining traditional patterns like frequent itemsets, association rules, etc. However, mining patterns with additional properties remains a bottleneck for specialists nowadays due to the algorithmic effort needed to handle these properties.Recently, researchers have taken advantage of the flexibility of constraint programming to model various data mining problems. In terms of CPU time, constraint programming-based methods have not yet competed with ad hoc algorithms. However, their flexibility allows the modeling of complex user queries without revising the solving process.In this thesis we propose to use constraint programming for modeling and solving some well known data mining problems.Our first contribution is a constraint programming model for mining association rules. To implement our model, we introduce a new global constraint, CONFIDENT, for ensuring the confidence of rules.We prove that completely propagating CONFIDENT is NP-hard. We thus provide a non-complete propagator and a decomposition for CONFIDENT. We also capture the minimal non-redundant rules, a condensed representation of association rules, by introducing the global constraint GENERATOR. GENERATOR is used for mining itemsets that are generators. For this constraint, we propose a complete polynomial propagator.Our second contribution is a generic framework based on constraint programming to mine both borders of frequent itemsets, i.e. the positive border or maximal frequent itemsets and the negative border or minimal infrequent itemsets. One can easily decide which border to mine by setting a simple parameter. For this, we introduce two new global constraints, FREQUENTSUBS and INFREQUENTSUPERS, with complete polynomial propagators. We then consider the problem of mining borders with additional constraints. We prove that this problem is coNP-hard, ruling out the hope for the existence of a single CSP solving this problem (unless coNP is in NP).La fouille de données est l'art de découvrir des informations à partir de bases de données.L'utilisateur spécifie le type de motifs à extraire et le spécialiste utilise des techniques pour trouver les motifs requis.De nombreuses techniques ont été introduites pour l'extraction des motifs classiques tels que les motifs fréquents, les règles d'association, etc.Cependant, l'extraction des motifs avec des propriétés supplémentaires restent un problème pour les spécialistes car des efforts algorithmiques sont requises pour gérer ces propriétés.Récemment, les chercheurs ont profité de la flexibilité de la programmation par contraintes pour modéliser plusieurs problèmes de la fouille de données.En termes de temps d'exécution, les méthodes basées sur la programmation par contraintes ne sont pas encore concurrentes avec les algorithmes spécialisées.Cependant, leur flexibilité permet la modélisation des requêtes complexes sans la nécessité de réviser le processus de résolution.Dans cette thèse, nous proposons d’utiliser la programmation par contraintes pour résoudre des problèmes de la fouille de données.Notre première contribution est un modèle basé sur la programmation par contraintes pour l'extraction des règles d'association.Pour mettre en œuvre notre modèle, nous introduisons une nouvelle contrainte globale,CONFIDENT, pour assurer la confiance des règles.Nous prouvons que propager complètement CONFIDENT est NP-difficile.Nous fournissons donc un propagateur non-complet et une décomposition pour la contrainte CONFIDENT.Nous capturons également les règles minimales non redondantes, une représentation condensée des règles d'association, en introduisant la contrainte globale GENERATOR. GENERATOR est utilisé pour extraire des motifs qui sont des générateurs. Pour cette contrainte, nous proposons un propagateur polynomial complet.Notre deuxième contribution est un model générique basé sur la programmation par contraintes permettant l'extraction des deux frontières des motifs fréquents, à savoir la frontière positive ou les motifs maximaux fréquents et la frontière négative ou les motifs minimaux infréquents.Il est facile de choisir la frontière à extraire en fixant un simple paramètre.Pour cela, nous introduisons deux nouvelles contraintes globales, FREQUENTSUBS et INFREQUENTSUPERS,avec des propagateurs polynomiaux complets.Nous examinons ensuite le problème de l'extraction des frontières avec des contraintes supplémentaires.Nous prouvons que ce problème est coNP-difficile. Cela implique qu’il n’existe aucun CSP représentant ce problème (sauf si coNP est dans NP)