Programmation linéaire pour l’extraction des ensembles de motifs

Télécharger le fichier original (Mémoire de fin d’études)

Extraction sous contraintes

En pratique, l’expert porte souvent son intérêt sur un sous-ensemble de tous les motifs extraits ayant des carac-téristiques un peu particulières. Généralement, ces caractéristiques sont décrites par des contraintes permettant de délimiter l’ensemble des motifs extraits. Ainsi, il est possible de cibler les connaissances désirées par l’expert tout en réduisant leur nombre, rendant leur interprétation une tâche plus aisée. De plus, certaines contraintes permettent d’élaguer considérablement l’espace de recherche grâce à certaines propriétés (cf. sections 3.2.2b et 3.2.2c) offrant une dimension algorithmique importante pour l’extraction des motifs sous contraintes.
Une contrainte q(T , φ) est un prédicat défini sur un langage, relativement à un ensemble de transactions T et un motif φ.
Dans le but de décrire avec plus de précisions les motifs recherchés, plusieurs contraintes peuvent être combi-nées, formant ainsi une requête d’extraction de motifs.

REQUÊTE D’EXTRACTION

Une requête est une conjonction ou une disjonction de contraintes des motifs recherchés.
L’extraction de motifs sous contraintes consiste à extraire d’une base D décrite par des éléments du langage LI les motifs satisfaisant une contrainte q. Plus formellement, il s’agit de déterminer la théorie correspondante (l’ensemble des motifs satisfaisant q dans D) [Mannila et Toivonen, 1996] :
Définition 3.6. THÉORIE
Pour un langage donné LI , une base de données D et une contrainte q, la théorie T h(LI , D, q) est l’ensemble des motifs de LI satisfaisant la contrainte q dans D.
Nous nous focalisons, dans ce document, sur les bases de données transactionnelles, par conséquent, nous adoptons T pour toutes les formulations des différentes mesures et contraintes.

Extraction de motifs sous contraintes locales

Contraintes de base

Un motif local est un motif qui satisfait des contraintes locales unaires. Il existe de nombreuses contraintes permettant d’évaluer la pertinence et la qualité des motifs locaux, comme par exemple les contraintes exprimées à
L’ensemble vide est exclus car il est rarement porteur du sens.
Motifs ensemblistes et ensembles de motifs l’aide de mesures définissant l’intérêt des motifs extraits [Geng et Hamilton, 2006]. Le nombre d’occurrences d’un motif dans la base de données, défini par la mesure de sa fréquence, est l’une des mesures les plus classiques. La contrainte de fréquence découlant de cette mesure (définition 3.8) servira d’exemple pour présenter les différentes notions dans la suite de ce chapitre. D’autres critères sont utiles pour construire des motifs intéressant l’utilisateur. Par exemple, supposons que l’utilisateur recherche des motifs suffisamment fréquents et longs, cela pourrait être achevé en contraignant que l’aire des motifs doit être supérieure à un certain seuil (cf. définition 3.10).
Les notions de support et de fréquence d’un motif sont définies comme suit :
Définition 3.7. SUPPORT
Une transaction t ∈ T supporte le motif φ (ou φ est présent dans t) ssi φ ⊆ t (ou ∀i ∈ φ, R(i, t) = 1). Le support d’un motif φ, noté cover(φ), est l’ensemble des transactions qui le supportent.
La fréquence d’un motif φ = (I, T ), où I est l’ensemble d’items (I ⊆ I) constituant le motif φ, et T est l’ensemble de transactions (T ⊆ T ) supportant le motif φ, est le cardinal du support :
f req(φ, T ) = |T |.
Définition 3.9. TAILLE, LONGUEUR
La taille d’un motif φ = (I, T ) est le nombre d’items constituant le motif φ :
taille(φ, T ) = |I|.
Définition 3.10. AIRE
Soit φ = (I, T ) un motif. L’aire du motif φ est le produit de sa taille par sa fréquence :
aire(φ, T ) = |I| × |T |.
Exemple 3.1.
La requête suivante est un exemple d’extraction des motifs locaux, constituée de la conjonction de contraintes locales sur les mesures de fréquence et de taille suivantes :
f req(φ, T ) ≥ 3 ∧ taille(φ, T ) ≥ 2.
Cette requête stipule que la fréquence d’un motif φ, f req(φ, T ), doit être supérieure ou égale à 3 et que sa taille, taille(φ, T ), doit être supérieure ou égale à 2. L’ensemble des solutions répondant à cette requête pour notre exemple du tableau 3.1 est {C, E}, {C, G}, {E, G}, {A, E} et {C, H}.
Définition 3.11. MOTIF FRÉQUENT
Un motif est fréquent (ou minf req -fréquent) si et seulement si sa fréquence est supérieure ou égale à un seuil de fréquence minimale minf req fixé par l’utilisateur. On note F(T , minf req ) l’ensemble des motifs fréquents dans la base de transactions T pour une fréquence minimale minf req .
Exemple 3.2.
Dans notre exemple du tableau 3.1, les motifs {A}, {B}, {C}, {E}, {G}, {C, E}, {C, G}, {E, G}, {A, E} et {C, H} sont 3-fréquents.
Extraction de motifs sous contraintes locales
L’extraction des motifs fréquents est considérée comme une méthode non supervisée permettant l’identification des corrélations entre les données, telle que la construction des règles d’association.
Définition 3.12. MOTIF FERMÉ
Un motif φ = (I, T ) est dit fermé dans T si et seulement si aucun sur-ensemble contenant φ n’a le même support que φ dans T . On note closed(φ) l’unique sur-ensemble de φ ayant le même support que φ, un motif fermé est égal à sa propre fermeture.
Définition 3.13. MOTIF FERMÉ FRÉQUENT
Un motif φ est dit fermé fréquent dans T si et seulement si φ est un motif fermé et que sa fréquence f req(φ, T ) est supérieure ou égale à un certain seuil minf req .
partir de l’ensemble des motifs fermés fréquents, noté Fclos, et de leurs fréquences, nous pouvons générer tous les motifs fréquents avec leurs fréquences exactes F(T , minf req ). Étant donné un motif φ, si φ n’a pas un sur-ensemble dans Fclos, alors closed(φ) n’est pas fréquent, et donc, φ ne peut pas être un motif fréquent. Si φ a au moins un sur-ensemble dans Fclos, alors f req(φ, T ) = f req(ψ, T ), où ψ = closed(φ) est le plus petit sur-ensemble de φ dans Fclos.
Élagage de l’espace de recherche
Espace de recherche
La formulation du langage pour l’extraction de motifs est simple. Toutefois, sa résolution est une tâche algo-rithmiquement difficile car l’espace de recherche des motifs est très grand : si |I| = n, alors la taille de l’espace de recherche est O(2n). Pour les motifs ensemblistes, l’espace LI dans lequel les motifs sont recherchés correspond à un treillis.
Définition 3.14. SPÉCIALISATION – GÉNÉRALISATION
Une relation de spécialisation, notée , est un ordre partiel défini sur les motifs de LI . Un motif φ est plus spécifique qu’un motif ψ (resp. plus général) si ψ φ (resp. φ ψ).
L’inclusion entre deux motifs définit une relation de spécialisation [Mitchell, 1982]. Ainsi, si un motif φ est inclus dans un motif ψ, on dit que ψ est plus spécifique que φ ou que φ est plus général que ψ. Par exemple, le motif {C, E} est inclus dans le motif {C, E, G}.
L’idée maîtresse des travaux qui traitent la découverte de motifs locaux sous contraintes est d’exploiter les propriétés de monotonie/anti-monotonie de certaines contraintes afin d’élaguer l’espace de recherche.

Anti-monotonie

Une contrainte q(φ, T ) est anti-monotone suivant la spécialisation si et seulement si :
∀φ, ψ ∈ LI , φ ⊆ ψ ⇒ (q(ψ, T ) ⇒ q(φ, T )).
freq(φ) ≥ minf req est un exemple de contrainte anti-monotone.

Motifs ensemblistes et ensembles de motifs

Monotonie

Une contrainte q(φ, T ) portant sur un motif φ de LI relativement à une base de données T , est monotone suivant la spécialisation si et seulement si :
∀φ, ψ ∈ LI , φ ⊆ ψ ⇒ (q(φ, T ) ⇒ q(ψ, T )).
taille(φ) ≥ mintaille est un exemple de contrainte monotone.
L’(anti-)monotonie conduit à une importante propriété d’élagage. Si un motif φ ne satisfait pas une contrainte anti-monotone (respectivement monotone) q, alors toutes ses spécialisations (respectivement généralisations) ne la satisfont pas.
Bordure positive et négative Étant donné une contrainte anti-monotone, les bordures [Mitchell, 1982, Mannila et Toivonen, 1996] parti-tionnent l’espace de recherche en deux sous-espaces : l’espace des motifs satisfaisant la contrainte et l’espace des motifs ne satisfaisant pas la contrainte.
Définition 3.17. BORDURE POSITIVE – MOTIFS MAXIMAUX
Soit S un ensemble de motifs de LI satisfaisant une contrainte anti-monotone q. La bordure positive de S, notée
Bd+(S) est l’ensemble des motifs φ de LI tels que :
φ ∈ Bd+(S) ssi q(φ, T ) ∧ (∀ψ, φ ψ ⇒ ¬q(ψ, T )).
Bd+(S) rassemble les motifs maximaux de S.
De manière duale, on définit la bordure négative.
Définition 3.18. BORDURE NÉGATIVE – MOTIFS MINIMAUX
Soit S un ensemble de motifs de LI satisfaisant une contrainte anti-monotone q. La bordure négative de S, notée
Bd−(S) est l’ensemble des motifs φ de LI tels que :
φ ∈ Bd−(S) ssi φ ∈ LI \ S et ∀ψ φ, q(ψ, T ).
Bd−(S) rassemble les motifs minimaux de LI \ S.

Table des matières

Remerciements
Introduction
1 Contexte
1.1 Méthodes hybrides parallèles
1.2 Extraction des ensembles de motifs
2 Objectifs
2.1 Méthodes hybrides parallèles exploitant la structure d’un problème
2.2 Extraction d’ensembles de motifs
3 Contributions
3.1 Méthodes hybrides parallèles
3.2 Extraction des ensembles de motifs à l’aide de la PLNE
4 Plan du mémoire
4.1 État de l’art
4.2 Contributions
I État de l’art
1 Outils de modélisation et de résolution classiques
1.1 Problèmes d’optimisation combinatoire
1.2 Programmation linéaire
1.2.1 Définitions
1.2.2 Principaux algorithmes
1.2.3 Génération de colonnes
1.3 Programmation par contraintes
1.3.1 Formalisme CSP
1.3.2 Méthodes de recherche arborescente des CSP
1.3.3 Méthodes de filtrage des CSP
1.4 Réseaux de fonction de coût
1.4.1 Formalisme WCSP
1.4.2 Recherche par séparation et évaluation en profondeur d’abord ( DFBB)
1.4.3 Filtrage par cohérences locales souples
1.5 Exploiter la structure du problème
1.5.1 Décomposition arborescente
1.5.2 Méthodes de décomposition arborescente
1.5.3 Raffinement des décompositions arborescentes
1.6 Méthodes complètes exploitant la décomposition arborescente pour les WCSP
1.6.1 Cluster Tree Elimination CTE
1.6.2 Backtrack Bounded By Tree-Decomposition BTD
1.6.3 AND/OR tree search
1.7 Conclusion
2 Méthodes de recherche à voisinage variable
2.1 Recherche locale
2.2 Métaheuristiques
2.3 Recherche à voisinage variable
2.3.1 Schéma de base
2.3.2 Recherche à voisinage variable réduite
2.3.3 Recherche à voisinage variable biaisée
2.3.4 Recherche à voisinage variable avec décomposition
2.3.5 Recherche à voisinage variable primale-duale
2.3.6 Recherche à formulation variable
2.3.7 Recherche à voisinage large
2.4 Extensions de VNS pour la résolution des WCSP
2.4.1 VNS/LDS+CP
2.4.2 VNS guidée par la décomposition arborescente (DGVNS)
2.5 Stratégies parallèles pour VNS
2.5.1 Parallélisme
2.5.2 Parallélisation de VNS
2.5.3 Recherche VNS parallèle synchrone
2.5.4 Recherche VNS parallèle répliquée (RPVNS)
2.5.5 Recherche VNS parallèle avec phase de shaking répliquée (RSVNS)
2.5.6 Recherche VNS parallèle à voisinages coopératifs (CNVNS)
2.6 Évaluation des métaheuristiques
2.6.1 Temps CPU et taux de réussite
2.6.2 Profil de performance
2.6.3 Profils de rapport de performance
2.7 Conclusion sur les métaheuristiques
3 Motifs ensemblistes et ensembles de motifs
3.1 Théorie d’une base transactionnelle
3.1.1 Contexte transactionnel
3.1.2 Extraction sous contraintes
3.2 Extraction de motifs sous contraintes locales
3.2.1 Contraintes de base
3.2.2 Élagage de l’espace de recherche
3.2.3 Représentations condensées
3.2.4 LCM : Extraction des motifs fermés en temps linéaire
3.3 Extraction d’ensembles de motifs
3.3.1 Définitions de base
3.3.2 Contraintes n-aires
3.4 Problèmes de l’extraction d’ensembles de motifs
3.4.1 Clustering conceptuel
3.4.2 Problème du tuilage
3.4.3 Algorithmes d’extraction
3.5 Bilan
4 Jeu de test
4.1 Problème d’allocation de fréquences à des liens radio
4.1.1 Description du problème
4.1.2 Modélisation sous forme d’un WCSP
4.1.3 Description des instances
4.2 Instances générées par GRAPH
4.3 Problème de planification d’un satellite de prise de vue
4.3.1 Description du problème
4.3.2 Modélisation sous forme d’un WCSP
4.3.3 Présentation des instances
4.4 Problème de sélection de TagSNP
4.4.1 Description du problème
4.4.2 Modélisation sous forme d’un WCSP
4.4.3 Présentation des instances
4.5 Bases de données de l’UCI
4.5.1 Descriptions des bases de données
4.6 Conclusion
II Contributions
5 Méthodes parallèles exploitant la décomposition arborescente
5.1 Exploitation parallèle des clusters de la décomposition arborescente
5.1.1 Modèle maître-travailleurs
5.1.2 Modes de communication
5.2 VNS coopératif parallèle exploitant la décomposition arborescente
5.2.1 Algorithme du processus maître
5.2.2 Algorithme du processus travailleur
5.3 Stratégies de réplication parallèles pour DGVNS
5.3.1 Réplication parallèle asynchrone de DGVNS
5.3.2 Réplication parallèle synchrone de DGVNS
5.3.3 Algorithme du processus travailleur
5.4 Intensification et diversification
5.4.1 Stratégies d’intensification
5.4.2 Stratégies de diversification
5.5 Résultats expérimentaux
5.5.1 Apports de la parallélisation
5.6 Bilan
6 Découverte d’ensembles de motifs utilisant la PLNE
6.1 Démarche en deux étapes
6.1.1 Aperçu général
6.1.2 Catégorisation des contraintes
6.1.3 Résolution des contraintes locales
6.1.4 PLNE et contrainte n-aires
6.2 Reformulation linéaire des contraintes n-aires
6.2.1 Contrainte de taille (Ctaille,≶ taille )
6.2.2 Contrainte de couverture (Cfreq,≶ cov )
6.2.3 Contrainte d’aire (Caire,≶ aire )
6.2.4 Contrainte de redondance (C,≶ redd)
6.2.5 Contrainte de généralisation (C gen)
6.2.6 Contrainte de spécialisation (C spe)
6.2.7 Contrainte de représentativité (Crep,≶,Ti rep )
6.3 Contraintes d’agrégation
6.3.1 Contrainte d’agrégation moyenne (Cavg,≶ avg )
6.3.2 Contrainte d’agrégation somme (Csum,≶ sum )
6.3.3 Contrainte d’agrégation maximum et minimum (Cmax max ,Cmin min )
6.4 Approximations linéaires des contraintes n-aires difficiles
6.5 Conclusion
7 Programmation linéaire pour l’extraction des ensembles de motifs
7.1 Applications de l’extraction d’ensembles de motifs
7.1.1 Clustering conceptuel et ses variantes
7.1.2 Problème du tuilage
7.2 Extraction des ensembles de motifs en PLNE
7.2.1 Encodage PLNE des problèmes de clustering
7.2.2 Clustering conceptuel dur
7.2.3 Co-clustering
7.2.4 Soft clustering et soft co-clustering
7.2.5 Problème du tuilage
7.2.6 Modélisation d’autres types de requêtes
7.3 Évaluation des modèles PLNE
7.3.1 Protocole expérimental
7.3.2 Passage à l’échelle
7.3.3 Relaxation du nombre k de clusters
7.3.4 Qualité des résultats
7.4 Conclusion
8 Conclusion et perspectives
8.1 Conclusions
8.1.1 Méthode parallèle coopérative exploitant la décomposition arborescente dans VNS
8.1.2 Stratégies parallèles répliquées pour DGVNS
8.1.3 Clustering Conceptuel en PLNE
8.1.4 PLNE pour l’extraction des ensembles de motifs
8.2 Perspectives
Bibliographie

Télécharger le rapport complet