Fouille de données déclarative basée sur la programmation par contraintes.

Declarative Itemset Mining Based on Constraint Programming 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).