Principes de la programmation par contraintes (PPC)

Principes de la programmation par contraintes (PPC)

Organisation du mémoire

Ce manuscrit est organisé de la façon suivante. La première partie est consacré à un état de l’art sur les problématiques traitées dans cette thèse ainsi que les différents outils exploités pour la résolution. Le chapitre 1 introduit d’abord le problème de l’extraction de motifs fréquents à partir d’une base de transactions d’une façon générale. Il décrit les notions et la terminologie liées à ce problème ainsi que certaines techniques de résolution. Ensuite, il aborde deux instances de ce problème lorsque la base transactionnelle contient des séquences ou des graphes. Pour chaque problématique, il présente les définitions nécessaires à la compréhension du problème, puis il détaille les principales approches proposées pour la résolution. Enfin, il discute les points forts et les points faibles de chacune d’elles. Le chapitre 2 s’intéresse à la fouille déclarative avec la programmation par contraintes. Tout d’abord, il présente les principes de base de la PPC qui englobent le problème de satisfaction de contraintes, les contraintes globales et les contraintes réifiées. Ensuite, il attaque les différentes méthodes qui ont exploité la PPC pour résoudre le problème de l’extraction de motifs séquentiels sous contraintes. Enfin, il discute, le modèle PPC proposé et les obstacles rencontrés afin d’assurer le passage à l’échelle. La seconde partie décrit nos différentes contributions qui ont appréhendé globalement l’extraction de motifs fréquents à partir d’une base transactionnelle, et particulièrement sur les deux problèmes suivants : 1. Extraction de motifs séquentiels à partir d’une base de séquences, 2. Extraction de sous-graphes fréquents à partir d’une base de graphes. Le chapitre 3 présente les définitions nécessaires pour la fouille de séquences avec wildcards. Un wildcard est un symbole qui apparaît dans le motif et peut remplacer n’importe quel item dans la séquence. Ce chapitre présente ensuite, le modèle PPC adopté pour l’extraction de motifs séquentiels avec wildcards. Puis, il montre comment modéliser deux types de contraintes sur les motifs : (1) contraintes locales telles que la contrainte de longueur, appartenance d’item, gap et expression régulière, et (2) contraintes globales qui portent sur un ensemble de motifs tels que les top-k motifs et les sous-groupes pertinents. Enfin, le modèle proposé est validé expérimentalement sur deux types de jeux de données : texte médical extrait à partir de la base Pubmed et un ensemble de romans. Le chapitre 4 décrit l’encodage des motifs sans wildcards. Ensuite, il introduit notre contrainte globale Prefix-Projection en expliquant son algorithme de filtrage. Cette contrainte qui permet d’encoder à la fois la relation de sous-séquence et la contrainte de fréquence, permet aussi d’exprimer d’une façon très simple d’autres contraintes sur les motifs. Cette contrainte a été exploitée avec une nouvelle stratégie d’initialisation afin d’extraire les top-k motifs. Ces deux approches ont été comparées avec des méthodes spécialisées sur une série de bases de séquences réelles. Le chapitre 5 redéfinit quelques notions liées à l’extraction de motifs séquentiels sous contrainte de gap. Ensuite, il détaille notre deuxième contrainte globale GAP-SEQ qui permet de faire l’extraction des motifs séquentiels sans et avec cette contrainte. Enfin, il valide expérimentalement notre approche, et montre qu’elle est nettement meilleure que les approches déclaratives, et concurrence les approches spécialisées et que dans un nombre de cas notre approche est meilleure. Le chapitre 6 porte sur le deuxième problème, à savoir la découverte de sous-graphes fréquents dans une base de graphes. Il détaille notre approche par intervalle qui se base sur deux encodages non canoniques : un encodage inférieur et un encodage supérieur. Il introduit deux instances de ces deux encodages, et montre que ces derniers permettent respectivement de générer un sous-ensemble et un sur-ensemble de l’ensemble exact des sous-graphes fréquents. Les expérimentations menées sur des jeux de données synthétiques et réelles montrent que notre approche est efficace dans le cas des bases de graphes denses lorsque le nombre de sous-graphes cycliques fréquents est énorme

Objectifs et motivations

L’utilisation de la PPC pour exprimer des problèmes de fouille de données offre un cadre déclaratif et générique de résolution. Toutefois, la contrepartie à cette grande généricité est la relative faiblesse des approches déclaratives existantes pour la fouille de motifs séquentiels qui ne passent pas à l’échelle comparées aux méthodes spécialisées. En effet, l’encodage PPC utilisé constitue une limitation forte sur la taille des bases qui peuvent être traitées. Les observations ci-dessous expliquent plus en détail les raisons de cette limitation : – Les approches courantes encodent le problème EMS à l’aide des contraintes réifiées. Pour cela, pour chaque séquence de la base, une contrainte réifiée est définie indiquant si le motif à extraire est une sous-séquence (ou non) de cette séquence. Mais, un tel encodage présente un inconvénient majeur car si la base contient m séquences, on aura besoin de m contraintes réifiées pour encoder toute la base de séquences. – L’encodage de la relation de sous-séquence utilise un ensemble de variables additionnelles pour déterminer les positions où le motif apparaît dans chaque séquence de la base. Un tel encodage nécessite un grand nombre de variables intermédiaires (m × l), sachant que m est la taille de la base et ℓ est la longueur maximale des motifs. Par ailleurs, et comme nous l’avons indiqué précédemment, cette problématique de passage à l’échelle se pose également de manière accrue pour les algorithmes spécialisés dédiés à la fouille de sous-graphes fréquents dans de grandes bases de graphes denses. L’objectif de cette thèse est d’une part, de répondre au verrou du passage à l’échelle des approches déclaratives existantes pour l’extraction de motifs séquentiels qui reposent sur un encodage booléen, et d’autres part de proposer d’autres démarches afin de traiter efficacement l’extraction de sous-graphes fréquents dans de grandes bases de graphes denses. L’originalité de nos travaux consiste à introduire des techniques utilisées en fouille de données pour améliorer les encodages PPC pour la fouille de séquences. Malgré les multiples défis algorithmiques posés par la fouille de séquences, ce travail fondateur a contribué à repenser la manière dont les approches PPC pouvaient tirer bénéfice de méthodes de fouille. Il a permis de montrer, pour la première fois, qu’une approche PPC pouvait concurrencer (et même surpasser) les algorithmes spécialisés de l’état de l’art.

Table des matières

Introduction
1 Contexte
2 Objectifs et motivations
3 Contributions
4 Organisation du mémoire
1 Extraction de motifs fréquents
1.1 Problème d’extraction de motifs fréquents
1.1.1 Description du problème
1.1.2 Techniques de résolution .
1.2 Extraction de motifs séquentiels
1.2.1 Notations et définitions
1.2.2 Extraction de motifs sous contraintes
1.2.3 Approches de résolution
1.2.4 Discussion
1.3 Extraction de sous-graphes fréquents
1.3.1 Terminologie liée aux graphes
1.3.2 Appariement de graphes
1.3.3 Problème de découverte de sous-graphes fréquents
1.4 Conclusion
2 Fouille déclarative par programmation par contraintes
2.1 Principes de la programmation par contraintes (PPC)
2.1.1 Problème de satisfaction de contraintes
2.1.2 Contraintes globales
2.1.3 Contraintes réifiées
2.1.4 CSP dynamiques
2.1.5 Discussion
2.2 Approches PPC pour l’extraction de motifs séquentiels sous contraintes
2.2.1 Première approche basée sur la contrainte regular
2.2.2 Un modèle basé sur une nouvelle contrainte globale
2.2.3 Discussion
2.3 Conclusion : vers une nouvelle approche PPC plus performante
5 Extraction de motifs séquentiels sous contrainte de GAP
5.1 Définitions
5.2 La propriété de préfixe anti-monotonie de gap[M, N]
5.3 Extensions droites d’un motif
5.4 Contrainte globale GAP-SEQ
5.4.1 Modélisation de EMSG
5.4.2 Principes du filtrage .
5.4.3 Algorithme de filtrage .
5.4.4 Complexités temporelle et spatiale de l’algorithme de filtrage
5.5 Expérimentations
5.5.1 Protocole expérimental
5.5.2 GAP-SEQ vs. méthodes PPC .
5.5.3 GAP-SEQ vs. méthodes spécialisées
5.5.4 Évaluation du passage à l’échelle de GAP-SEQ
5.5.5 Traitement de contraintes additionnelles
5.5.6 Résolution du problème EMS avec GAP-SEQ
5.6 Conclusion
6 Une approche par intervalle pour l’extraction des sous-graphes fréquents
6.1 Exemple illustratif
6.2 Encodage par intervalle
6.2.1 Définitions
6.2.2 Une instance d’encodage inférieur
6.2.3 Une instance d’encodage supérieur
6.3 Expérimentations
6.3.1 Protocole Expérimental
6.3.2 Évaluation sur des bases de graphes synthétiques
6.3.3 Évaluation sur des bases réelles de graphes .
6.3.4 Synthèse
6.4 Conclusion
III Conclusion et perspectives
7 Conclusion
8 Perspectives
Bibliographie

Télécharger le rapport complet