3.2.2 Algorithme Genall
L'algorithme « Genall
»élaboré par Ben Tekaya et al. construit le treillis
dans lequel chaque concept formel est décoré par l'ensemble de
générateurs minimaux qui lui est associé. Les
données d'entrées sont sous forme de contexte d'extraction et en
sortie nous aurons l'arbre lexicographique de la famille F des
concepts formels Ck, la liste ImmSucc des successeurs
immédiats du concept Ck ainsi que la liste des
générateurs minimaux du concept.[12]
1. Algorithme Genall
Entrée Le contexte d'extraction K = (X, Y,
R)
Sortie Arbre lexicographique de F, ImmSucc,
Liste - gen
Début
// Initialiser la famille des concepts à l'ensemble
des attributs
2. F = (ø,Y )
3. Pour chaque tuple t ? K Faire
// Initialiser la liste de l'ensemble des concepts
trouvés dans une itération
4. L = ø
30
5. Pour chaque concept Ck E F
Faire
6. C.intent = Ck.intent f1 t.items
7. Si C.intent E6 F Alors
// Nouveau concept
8. F=FUC
9. C.extent = Ck.extent U t.TID
10. C.ImmSucc = {t} U {Ck} \ {C}
11. L=LUC
12. Sinon
// Concept existant
13. C.extent = C.extent U Ck.extent U t.TID
14. Si C E6L Alors
15. L=LUC
16. Fin Si
17. C.LP = {t} U {Ck} \ {C} // Mise à jour de
C.ImmmSucc
18. Pour chaque Pk E C.LP
Faire
19. Pour chaque Succ E C.ImmSucc
Faire
20. Compare - Concept(Succ, Pk)
21. Fin Pour
22. Fin Pour
23. Fin Si
24. Fin Pour
// déterminer l'ensemble des successeurs
immédiats et les générateurs minimaux
25. Pour chaque concept Ck E L
Faire
26. Ck.ImmSucc = Find - Succ(Ck, L)
27. Pour chaque Succ E Ck.ImmSucc
Faire // Calcul de la face du successeur
immédiat
28. face = Succ \ Ck
29. Pour chaque facek E Succ.liste - face
Faire
30. Succ.liste - face = Compare - Face(face, facek)
31. Fin Pour
32. Fin Pour
33. Fin Pour
34. Fin Pour Fin
Sont presentés dans la table 3.1, les notations
utilisées dans l'algorithme GE-NALL Cet algorithme est
scindé deux partie : D'une part il génère les concepts
formels et de l'autre, il raffine la liste des successeurs immédiats et
détermine les générateurs minimaux.[5]
31
TABLE 3.1 - Notation utilisée dans
l'algorithme GENALL Génération des concepts formels
Cette génération est montrée à
partir de la ligne 4 jusqu'à la ligne 22. Dans cette étape, nous
commençons par initialiser la liste L avec l'ensemble vide
(ligne 4). Cette liste sera utile pour la mise à jour de l'ensemble des
successeurs immédiats de chaque concept formel trouvé dans une
itération.
Pour calculer l'ensemble des concepts formels, nous effectuons
une intersection entre l'intension de chaque concept formel de la famille F
et chaque transaction de la base de données. Il en résulte
deux cas:
1. L'intention n'existe pas dans la famille F : Dans
ce cas, un nouveau concept formel est trouvé et doit être
ajouté à la famille F. Ensuite l'exten-sion du concept
est calculée (ligne 9). Les successeurs immédiats potentiels de
ce nouveau concept formel sont alors initialisés avec les concepts
formels utilisés(ligne 10). En effet, pour déterminer le
successeur immédiat potentiel d'un concept formel, nous devrions
distinguer deux cas particuliers :
- Si le concept formel produit est égal à la
transaction, alors seul le concept formel utilisé dans cette
intersection peut être un successeur immédiat. En effet un concept
formel ne peut pas être égal à son successeur
immédiat;
- Sinon la transaction et le concept formel sont
considérés comme successeurs immédiats potentiels du
concept formel.
Ensuite, ce nouveau concept formel est ajouté à la
liste L(ligne 11).
2. L'intention existe déjà dans la famille
F : Dans ce cas l'extension du concept formel (ligne 13) doit
être mise à jour, et nous vérifions si le concept existe
déjà dans la liste L (14-15). Le but étant de
mettre à jour la liste des successeurs immédiats ImmSucc
du concept formel, et étant donné que nous maintenons, pour
chaque concept formel, une liste ImmSucc, nous allons construire une
liste LP devant contenir les concepts formels utilisés. Cette
liste est nécessaire pour pouvoir faire les comparaisons et mettre
à jour la liste des ImmSucc. En effet pour chaque
élément dans LP et pour chaque élément
dans la liste des ImmSucc, nous examinons l'inclusion de ces concepts
formels en utilisant la fonction Compare-concept(ligne 20).
Cette fonction est appliquée
32
pour mettre à jour la liste ImmSucc des
concepts formels considérés. Ainsi cette liste ne peut subir des
modifications que dans les deux cas suivants :
(a) L'élément de LP est plus petit (en
terme d'inclusion) par rapport à un élément de
ImmSucc. Dans ce cas, l'ancien successeur sera remplacé par le
nouveau successeur.
(b) les deux concepts sont incomparables : un nouveau
successeur sera alors ajouté à la liste ImmSucc du
concept formel en considération.
Raffinement de la liste des successeurs immédiats et la
détermination des généateurs minimaux
Les concepts formels trouvés dans une itération,
représentent une branche du treillis, cela veut dire que pour chaque
concept formel (excepté le plus grand), nous trouvons un autre concept
formel calculé dans cette même itération, qui le couvre.
Pour cela, nous parcourons la liste L des concepts formels
trouvés dans l'itération et pour chacun des concepts de la liste
L, nous faisons appel à la fonction Find - Succ
(ligne 26). Cette fonction est basée sur le fait qu'un concept
formel de cardinalité n(c'est-à-dire la longueur de son
intention est égal à n) soit au moins couvert par un
concept de cardinalité (n + 1) ou plus. Pour cela, étant
donné que la liste L est triée selon l'ordre croissant
de la cadinalité de l'intention, nous cherchons pour chaque concept
formel de cardinalité n, un concept formel qui le couvre dans
la liste de cardinalité (n + 1). En cas de défaut, nous
passons à la cardinalité (n + 2), et ainsi de suite
jusqu'à ce que nous trouvons un concept qui le couvre. Par la suite,
nous allons comparer ces différents concepts formels pour une mise
à jour de la liste de ImmSucc.
Une fois que la liste des successeurs immédiats du
concept formel courant est établie, nous parcourons cette liste et pour
chaque successeur immédiat nous devons calculer l'ensemble de ses
générateurs minimaux.Comment obtenir ce
résultat?
Pour y arriver, nous allons d'abord calculer les faces
associées aux successeurs immédiats (ligne 28) et ensuite nous
les comparons à la liste des faces correspondante en faisant appel
à la fonction Compare - face (ligne 30). L'ensemble de
faces Liste - face(successeur immédiat) d'un concept
formel ne peut être modifié que dans les deux cas suivants :
1. face est plus petit (en terme d'inclusion) que
l'élément Liste - face : Dans ce cas nous
calculons Compare - face, et nous remplaçons
l'ancienne face par la nouvelle. Si Compare - face n'existe
pas dans une des faces du concept formel, alors nous supprimons chaque
générateur contenant cette différence. Cette suppression
est fondée étant donné qu'un attribut qui n'existe pas
dans les faces ne peut exister les générateurs.
2. face est incomparable avec toutes les faces
Liste - face : Dans ce cas, nous ajoutons cette face à
la liste - face.[12]
Exemple 3 Soit le contexte d'extraction illustré
à la table 3.2 avec l'ensemble d'attri-buts I = {a, b, c, d, e,
f, g, h, i} et lensemble de transactions du contexte d'extraction,
dénotées de 1 à 8.
Considerons la transaction 4 = {acghi},
la famille F, après traitement des trois premières
itérations est comme suit :
F = {(abcdefghi, Ø), (abg,
123), (abgh, 23), (abcgh, 3)}.
L'ensemble des successeurs immédiats de chaque concept
est comme suit :
33
TABLE 3.2 - Le contexte d'extraction K
{abg}.ImmSucc = {{abgh}};
{abgh}.ImmSucc = {{abcgh}};
{abcgh}.ImmSucc = {{abcdefghi}}.
Première étape : Génération
des concepts formels
Chaque concept formel de F est manipulé
individuellement. Par conséquent, pour
le premier concept formel C1, nous aurons C1.intent =
{abcdefghi} l'application de
l'opérateur d'intersection avec la quatrième
transaction donne un nouveau concept
formel avec une intention égale à {acghi}.
L'extension de ce nouveau concept formel
sera calculée dans les lignes qui suivent. Ainsi, la
famille F est mise à jour en lui
ajoutant cette nouvelle intention C5 qu'on vient de
calculer:
F = {(abcdefghi, 0), (abg, 123), (abgh,
23), (abcgh, 3), (acghi, 4)}.
L'ensemble des successeurs immédiats de C5 est
initialisé avec C1 et l'extension
de C5 est initialisé avec l'union de C1.extent et
l'identificateur de la transaction
considéré. Par conséquent, C5.extent =
{4} et C5.ImmSucc = {abcdefghi} et la
liste L et initialisé avec {acghi}
Le processus mentionné ci-dessus est
répété pour tous les concepts formels existants
dans la famille F.
A la fin de cette première étape, nous obtenons
la famille des concepts formels mises
à jour:
F = {(abcdefghi, 0), (abg, 123), (abgh,
23), (abcgh, 3), (acghi, 4), (ag, 1234),
(agh, 234), (acgh, 34)}
Ainsi la liste des successeurs immédiats de chaque
concept formel est la suivante :
{ag}.ImmSucc = {{abg}, {acghi}}
{agh}.ImmSucc = {{abgh}, {acghi}}
{acgh}.ImmSucc = {{abcgh}, {acghi}}
{acghi}.ImmSucc = {{abcdefghi}}
La liste L contient toutes les intentions des concept formels
découverts dans l'itéra-
tion courante :
L = {{ag}, {agh}, {acgh}, {acghi}}
Raffinnement de la liste des successeurs immédiats
et détermination des
générateurs minimaux
Pour le premier concept de la liste L, nous avons
{ag}.ImmSucc = {{abg}, {acghi}}.
L'intention du concept formel {agh} couvre {ag} et nous avons
{agh} Ç {acghi}.
Nous allons donc remplacer {acghi} par {agh} dans
{ag}.ImmSucc. Ainsi, l'an-
cien arc liant {ag} à {acghi} est un lien transitif.
Par conséquent {ag}.ImmSucc =
34
FIGURE 3.5 - Treillis des concepts formels, extrait du contexte
K, décoré par quelques générateurs
minimaux
{{abg}, {agh}}
Pour chaque successeur immédiat de {ag}, nous devons
calculer liste - face et liste - gen qui devra contenir la liste des
générateurs minimaux, en utilisant la fonction Compare - face. Il
vient donc que :
1. {abg}.liste - face = {b} et {abg}.liste
- gen = {b}
2. {agh}.liste - face = {h} et {agh}.liste
- gen = {h}
Après le traitement de {ag}.ImmSucc, nous devons
manipuler la liste de succes-
seurs du concept formel dont l'intention est égal
à {agh} c'est-à-dire {agh}.ImmSucc.
Ainsi nous avons {agh}.ImmSucc = {{abgh}, {acghi}}.
Commençons par raffiner
la liste des successeurs immédiats {agh}.ImmSucc. Nous
constatons que {acgh} Ç
{acghi}. Alors nous devons remplacer {acghi} par {acgh} dans
{agh}.ImmSucc.
Ainsi les successeurs immédiats de {agh} sont
{agh}.ImmSucc = {{abgh}, {acgh}}.
Après le calcul de liste - face de {abgh} nous
obtenons :
{abgh}.liste - face = {h} U {b}. Etant
donné que {h} n {b} = Ø, alors {b}
ne peut pas être un bloqueur pour l'ensemble des faces
{{h}, {b}}. Raison pour
laquelle nous remplacerons la liste des générateurs
minimaux par {bh} c'est-à-dire
{abgh}.liste - gen = {bh}
Le processus de raffinnement tels que decrit ci-dessus est
appliqué sur {acghi}.ImmSucc
Ainsi:
{acghi}.ImmSucc = {{abcdefghi}};
{abcdefghi}.liste - face = {defi} U {bdef};
{abcdefghi}.liste - gen = {defbi}
Le processus de génération et de raffinement sont
repetés pour toute les transactions
restantes. La figure 3.4 décrit le treillis des concepts
formels associé au contexte d'ex-
traction K presenté dans la table 3.2. Notons que
certains générateurs minimaux
sont indiqués par des flèches, décorant les
noeuds des concepts formels.[6]
35
| 
