Upload
rogier-lavaud
View
104
Download
0
Embed Size (px)
Citation preview
1
Modifications controlées des implications de la base de
Guigues-Duquenne
LIMOS – Clermont-Ferrand
Alain Gély
6 Février 2006
Séminaire Maison des Sciences Economiques
2
I. Représentation des systèmes de fermeture
II. Le problème du calcul d’une base minimale
III. Combinatoire & Eléments clones
IV. Influence des implications Unitaires
3
I. Représentation des systèmes de fermeture
4
5 6 7 8
1 2 3 4
2
23
3
34
134
1234
Système de fermeture
Eléments
inf-Irréductibles
134, 23, 34, 2
M(F) est une représentation de FD’autres représentations existent
FM(F)
Graphe Biparti
5
2
23
3
34
134
1234
Système de fermeture
Système d’implications
4 3
1 34
42 13
F
premise
conclusion
, une famille d’implications est une représentation de F.
Voyons les différences entre les deux représentations
6
Liens entre les représentations
7
1 2 3 4
12 13 14 23 24 34
123 234134 124
1234
4 1
1, 2, 3, 4
12, 13, 14, 23, 24, 34
123, 124, 134, 234
1234
1, 2, 3
12, 13, 14, 23,
123, 124, 134,
1234
1 2 3 4
12 13 14 23 24 34
123 234134 124
1234
8
1 2 3 4
12 13 14 23 24 34
123 234134 124
1234
13 24 1
1, 2, 3
12, 13, 14, 23,
123, 124, 134,
1234
1, 2, 3
12, 14, 23,
123, 124
1234
1 2 3 4
12 13 14 23 24 34
123 234134 124
1234
34 2
Implications redondantes \ {X Y} {X Y}
9
Ajouter 4 est possible
4 1
1, 2, 3
12, 14, 23,
123, 124,
1234 13 2
, 13, 134
1 2 3 4
12 13 14 23 24 34
123 234134 124
1234
1 2 3 4
12 13 14 23 24 34
123 234134 124
1234
Propriétés des systèmes de fermeture
Ajouter 34 est impossible
4 est un ensemble quasi-fermé
10
1 23 4
12 13 14 23 24 34
123 234134 124
1234
12
13
1234
24
12
123 124
4
134
3
13
1234
14
Pour les ensembles quasi-fermés ayant la même fermeture, les ensembles minimaux sont appelés
ensembles pseudo-fermés
3 13 12 1234 4 1234
11
II. Le problème du calcul d’une base minimale
12
1. Systèmes de fermeture & Systèmes d’implications
2. Problématique
3. Eléments clones
4. Influence des implications unitaires
Sortie : , une base d’implications minimum de FEntrée : M(F)
M(F) Algorithme
13
1. Systèmes de fermeture & Systèmes d’implications
2. Problématique
3. Eléments clones
4. Influence des implications unitaires
Pas d’algorithmes d’énumération polynomiaux connus
(Quasi-polynomial O(nlog(n)) [Fredman & Khachiyan 95] pour un cas particulier)
[Mannila & Räihä, 92]
| | exponentiel par rapport à|M(F)|
Sortie : , une base d’implications minimum de FEntrée : M(F)
14
[Mannila & Räihä, 92]
| | exponentiel par rapport à|M(F)|
Complexité des algorithmes d’énumération
Un algorithme d’énumération est polynomial si sa complexité est polynomiale
en la taille de l’entrée (|M(F)|) et de la sortie ( | | )
O( (|M(F)| + | | )k )
15
Pas d’algorithmes d’énumération polynomiaux connus
(Quasi-polynomial O(nlog(n)) [Fredman & Khachiyan 95] pour un cas particulier)
5 6 7 8
1 2 3 4
2
23
3
34
134
1234
F
4 31 3442 13
M(F)
Polynomial
Polynomial
Polynomial
Polynomial?
?
16
Recherche d’un algorithme d’énumération polynomial
Rendre le calcul plus facile en modifiant les données
De nombreuses recherches sont faites dans plusieurs domaines
Clones
Implications Unitaires
EntréePré-traitement
Entrée modifiée + meta-information
17
III. Combinatoire & Eléments clones
18
1. Systèmes de Fermetures & Systèmes d’Implications
2. Problématiques
3. Eléments clones
4. Influence des implications unitaires
Généralité - Exemple
Soit J = { 1 , 2 , 3 , 12 , 13 , 23 , 123 } défini sur J={1,2,3}
φ1,2
12 3 12 23 13 123J’ = { , , , , , , } = J1 2 3 12 2313 123 Jr = { , , , , } + 1≈2
Famille réduite Méta-Information (classe d’équivalence)
19
1. Système de fermeture & Système d’implications
2. Problématique
3. Eléments Clones
4. Influence des implications unitaires
Généralités
J une famille d’ensembles sur J, et a,b J
Soit φa,b une fonction sur un ensemble, qui échange a et b
Soit J’ = { φa,b ( X ) | X J }
Si J= J’ alors a et b sont dit J-clones
Il y a une symétrie entre les éléments a et b
J’Jφa,b
φa,b
φa,b
20
Base minimum canonique (base de Guigues-Duquenne) [Guigues & Duquenne 86]
Soit F un système de fermeture
= { P P | P est un ensemble pseudo-fermé de F }est une base minimale d’implications pour F.
[Mannila et Räiha, 92]
| | exponentiel par rapport à |M(F)|
Y-a-t-il des éléments clones dans une base minimum ?
[Medina & Nourine 04] [Gély & al 05]
Il nous faut choisir une base minimum …
21
13
14
15
16
23
24
25
26
35
36
45
46
1234
125
1234
126
1234
1234
125
126
3456
3456
3456
3456
P-Clones : ExempleLes éléments P-Clones sont clones dans la famille des
ensembles pseudo-fermés
22
13
14
15
16
23
24
25
26
35
36
45
46
P-clones:
1 2
P-Clones : Exemple
23
13
14
15
16
35
36
45
46
P-clones:
1 2
P-Clones : Exemple
24
13
14
15
16
35
36
45
46
P-clones:
1 2
3 4
P-Clones : Exemple
25
13
15
16
35
36
P-clones:
1 2
3 4
P-Clones : Exemple
26
13
15
16
35
36
P-clones:
1 2
3 4
5 6
P-Clones : Exemple
27
13
15 35
P-clones:
1 2
3 4
5 6
P-Clones : Exemple
28
P-clones:
1 2
3 4
5 6
13
15 35
14
16
23
24
25
26
36
45
46
P-Clones : Exemple
1234
126
1234
1234
125
126
3456
3456
3456
1234
125 3456
29
Problème ouvert :– Entrée : M(F)– Question : a et b sont-ils P-clone ?
P-Clones
Expliquent l’exponentialité de [Mannila & Räihä92]
Nouveau problème :– Entrée : M(F)– Question : a et b sont-ils F-clone ?
30
F-Clones
Définition
Détection
Réduction
Reconstruction
Relation entre F-Clones et P-Clones
31
F- Clone1 3
1 2 3 4
12 23 14 34
123
1234
φ1,3
φ1,3
φ1,3
F-Clones : Définition & Exemple
32
F- Clone et P- Clone
B
F- CloneClone P- CloneClone
A
A B P
φa,b (P)P
P
φa,b (P)
φa,b (P)AB
φa,b (AB)
33
Théorème:
a et b sont F-clone ssi
a et b sont M(F)-clones
F-Clones : Détection
A B
34
• Le problème– Entrée : M(F)– Question: a et b sont-ils F-clones ?
• est polynomial
F-Clones : Détection
Trouver les classes de clones : J x || M(F) || [Medina & al 05]
L’image d’un élément inf-irréductible est un élément inf-irréductible
35
F-Clones : Réduction
1x
2 3 4x x123
12
23
1434
x xx x
x xxx
x
1 2 3 4
12 23 14 34
123
1234
36
F-Clones : Réduction
1 2 4
12 14
123
1234
1x
2 3 4x x123
12
23
1434
x xx
xxx
37
F-Clones : Reconstruction
1 2 4
12 14
123
1234
1
x2 3 4
x x123
12
14
x x2 x4 x
xx φ1,3
φ1,3
φ1,3
23 xx34 xx
38
M(F)Détection
Réduction
Clones
Calcul de la base
Reconstruction
39
F-Clones : Reconstruction de la base3 étapes
1 2 3 4
12 23 14 34
123
1234
3 12I. Retrait des implications artificiellement rajoutées lors de la réduction
40
F-Clones : Reconstruction de la base3 étapes
I. Retrait des implications artificiellement rajoutées lors de la réduction
II. Ajout des implications artificiellement écartés lors de la réduction
BA
AB
41
F-Clones : Reconstruction de la base3 étapes
I. Retrait des implications artificiellement rajoutées lors de la réduction
II. Ajout des implications artificiellement écartés lors de la réduction
III. Application de la fonction φ
13
15 35
14
16
23
24
25
26
36
45
461234
126
1234
1234
125
126
3456
3456
3456
1234
125 3456
42
Théorème :
F’’ le système de fermeture après F–clone réduction
Est tel que|M(F’)| ≤ |M(F)|
F-Clones : Résultats
Théorème:
F-Clone P-clones
P-Clone F-clones
43
IV. Influence des implications Unitaires
44
P-Clone F-clone : Exemple
21
13
123
12 123
3 13
P-Clone : 1≈2F-Clone : 1≈2
φ1,2 (13)φ1,2
φ1,2
45
1. Systèmes de fermeture & Système d’implications
2. Problématique
3. Eléments Clones
4. Influence des implications unitaires
Implications Unitaires
Soit F un système de fermeture sur J, et sa base de Guigues-Duquenne .
= J
Avec 1. = P P avec |P|>12. J = P P avec |P|=13. = P P avec |P|=0
46
1. Systèmes de fermeture & Système d’implications
2. Problématique
3. Eléments Clones
4. Influence des implications unitaires
Implications Unitaires
Soit F un système de fermeture sur J, et sa base de Guigues-Duquenne .
= J
Avec 1. = P P avec |P|>12. J = P P avec |P|=1
47
Implications Unitaires
Les implications de J sont
• Facile à calculer
• En nombre polynomial
Modifier J sans modifier
On recherche des systèmes de fermeture - équivalent
On note C(F) la famille des systèmes de fermeture - équivalents
48
21
13
12312 1233 13
3
23
Comment 1 et 2
Peuvent-ils devenir clones ?
Solution 1 : Retirer une implication / Ajouter des ensembles fermés.
1. Systèmes de fermeture & Système d’implications
2. Problématique
3. Eléments Clones
4. Influence des implications unitaires
49
Retrait d’une implication unitaire de la base de Guigues-Duquenne
Retrait d’une Implication Unitaire
1 2 4
342414
1234134 1234234 1234
3 34
J
12 1234
50
1 2 3 4
12 342413 14 23
234123 124 134
1234
1 2 4
342414
1234134 1234234 1234
3 34
J
12 1234
51
1 2 3 4
12 342413 14 23
234123 124 134
1234134 1234234 1234
3 34
J
12 1234
52
1 2 3 4
12 342413 14 23
234123 124 134
1234
234 1134 212 34
134 1234234 1234
3 34
J
12 1234
53
1 2 3 4
12 342413 14 23
123 234124 134
1234134 1234234 1234
3 34
J
12 1234
54
1 2 3 4
12 342413 14 23
123
1234
12 34
3 34
134 1234234 1234
3 34
J
12 1234
55
1 2 3 4
12 342413 14 23
123
1234134 1234234 1234
3 34
J
12 1234
Copies d’ensembles fermés
56
1 2
13 24 25
1234
12345 12 1234245 12345
3 134 245 25
Base de Guigues-Duquenne
4
14
134
Calcul de F’ à partir de F
J
57
Retrait d’une implication unitaire & Duplication d’ensembles convexes
2
13
123
1
58
Retrait d’une implication unitaire & Duplication d’ensembles convexes
1 2
13
123
4
24
4
4
4
Duplication de convexe Retrait d’une implication unitaire
1 2
13
123
3
23
59
Retrait d’une implication unitaire de la base de Guigues-Duquenne
Le problème
Entrée : M(F), P P J
Sortie : M(F’), avec (F’) = (F) \ { P P }
est polynomial
Mais qu’en est-il de la taille de M(F’) ?
Résultat
60
12 1234245 12345
3 135 25Base de Guigues-Duquenne
Calcul de F’ depuis F
J
1 2
13 24 25
1234
12345
5 éléments Inf-irreductibles
4 24
61
1 2
13 24 25
1234
12345
12 1234245 12345
3 135 25Base de Guigues-Duquenne
4
14
134
Calcul de F’ depuis F
J
6 éléments Inf-irréductibles
4 24
1 2
13 24 25
1234
12345
5 éléments Inf-irréductibles
62
|M(F┬) | par rapport à |M(F)| ?
Soit
F un système de fermeture, et sa base de Guigues-Duquenne.
F┬ un système de fermeture tel que est sa base de Guigues-Duquenne
|M(F┬)| peut être exponentiel par rapport à |M(F)|
2 31
14 25 36
7
Retirer des implications n’est pas une solution
63
21
13
12312 123
3 133 23 123
Comment 1 et 2
Peuvent-ils devenir clones ?
Solution 2 : Retirer des ensembles fermés / Ajouter des implications
[Gély & Nourine 06]
1. Systèmes de fermeture & Système d’implications
2. Problématique
3. Eléments Clones
4. Influence des implications unitaires
64
Ajout de l’implication a b :
{a b} n’est pas forcément une base de Guigues-Duquenne
Ajout d’implications unitaires
12 123
12
123
1 23
2313
2 3
12
123
1 23
2313
J 2 23
J
65
Pour tout P P
Caractérisation : -équivalence en ajoutant a b
(i) Si a P alors b P
(ii) Si a P alors b P
(iii) Si a j , j P, alors (jb) ≠ P
Conclusion inchangéeReste un ensemble
quasi-fermé
Reste un ensemble quasi-fermé minimal
Résultat
a b peut être ajoutée sans modifications de ssi
66
Caractérisation : relation de couverture dans C(F)
(i) Pour tout P P , P ≠ a , Si a P alors b P
(ii) Pour tout P P Si a P alors b P
(iii’) Pour tout P P Si a P alors (ab) ≠ P
Résultat
a b peut être ajouté sans modification de ,
et F’ couvre F dans C(F) ssi
67
123
1 23
2313
123
1 2
23
123
1 2
123
1 2
13
12 123
12 123 3 13
12 123 3 23
12 123 3 123
3 2 3 1
3 1 3 2
1 2 3 2
3 1
68
123
1 2
12 124 1234 3 123
124 1234 3 123
14
1234
123
2 1
1224
1234
4 14 4 24
123
1 2
12 3 123
1234
4 1234
La famille des systèmes de fermeture -équivalent n’est pas un système de fermeture
La famille des systèmes de fermeture J - équivalent est un système de fermeture [Nation & Pogel 97]
69
Caractérisation : Relation de couverture C(F)
(i) Pour tout P P , P ≠ a , Si a P alors b P
(ii) Pour tout P P Si a P alors b P
(iii’) Pour tout P P , Si a P alors (ab) ≠ P
Résultat
a b peut être ajouté sans modification de ,
et F’ couvre F dans C(F) ssi
Conditions sur les implications
70
Caractérisation : relation de couverture de C(F)En utilisant M(F)
Résultat
Le problème:
• Entrée : M(F) , a b• Question :
F’ est-il le S.F. correspondant à {a b} tel que
F’ C(F) F couvre F’
est polynomial
Résultat
71
(i) et (ii)
Isomorphisme entre A et A*
système de fermeture – Ajout de a b
A la famille d’ensembles fermés F tels que a F et b F
A* la famille d’ensembles fermés F tels que A* F, a F et b F
A = aF B = bF
A* le prédécésseur immédiat de A dans F
12
123
1 23
2313
3 1
A =
B =
A* =
A
A*(iii’)
A (A* B) F F
72
Si F couvre F’ dans C(F) |M(F’)| ≤ |M(F)|
Résultat
Les éléments Inf-irreductibles d’un système de fermeture minimal
de C(F) peuvent être calculés en temps polynomial
Résultat principal
73
Il est possible d’ajouter une implication a b
Conditions nécessaires et suffisantes vérifiables en temps polynomial
Transformation des données en temps polynomial
Détection possible de plus de clones
La nouvelle donnée est plus petite que la donnée initiale
Le système de fermeture est plus petit que le système de fermeture initial
Méthode intéressante pour traiter les données
74
Entrée
Pré-traitement
(en temps polynomial)
• Réduction des clones
• Ajout d’implications unitaires
Utilisation de ces résultats ?
Datamining, énumération des ensembles fermés,
calcul d’une base minimum, …
75
Conclusions
• Eléments Clones pour réduire la combinatoire
• Implications Unitaires pour détecter plus de clones
• Implications Unitaires pour réduire le système de fermeture
Système d’Implications
76
Perspectives
• Liens entre les implications de et J
• Comportement pour d’autres bases ?
• Propriétés structurelles de C(F)
• Liens avec la duplication d’ensembles convexes [Day 70][Caspard 99]
• Algorithmes efficaces pour l’ajout d’implications
Systèmes d’Implications
77
Merci