3.2 Algorithme de construction de treillis de
concepts
Un concept étant un regroupement maximal d'objets
possédant des caractéristiques communes, l'algorithme de
construction de treillis de concepts construit un treillis dans lequel chaque
concepts formel est décoré par l'ensemble de
générateurs minimaux qui lui est associé. Les «
input »sont représentés sous forme de contexte
formel. Un contexte est représenté sous forme d'un tableau dont
les objets X sont en lignes et les attributs Y en
colonnes.[5]
3.2.1 Définitions
Définition 1 (Contexte d'extraction ou contexte
formel)
Un contexte d'extraction ou formel est un triplet K =
(X, Y, R) où X et Y sont respectivement
l'ensemble d'objets et celui d'attributs et R Ç X X
Y une relation binaire telle que ?(x, y) E R, y est
un attribut de l'objet x.
Définition 2 (Contexte binaire)
Un contexte K = (X, Y, R) est dit binaire si
les éléments de Y ont uniquement deux valeurs (0 ou 1)
qui indique l'absence ou la présence de l'attribut concerné
respectivement.
27
Définition 3 (Fermeture des ensembles)
Soient deux fonctions g et h qui nous serviront à
calculer la fermeture des sous ensembles d'objets O et d'attributs A. Ainsi,
les ensembles fermés sont définis comme suit :
O» = h(g(O))
A» = g(h(A))
Alors, un ensemble est dit fermé s'il est égal
à sa fermeture.[4]
Définition 4 (Concept formel)
Un concept formel est une paire Ck = (O, A)
avec O C X et A C Y tel que :
O = {x E X/Va E A, (x, a) E R}
où O = h(A)
est l'extension ou objets couverts, elle est notée
Ext(Ck).
A = {y E Y/Vo E O,(o,y) E R}
où A = g(O)
est l'intention ou attributs partagés, elle est
notée Int(Ck).[11] Définition 5 (Ordre
sur les concepts)
Soient C1 = (O1, A1) et C2 = (O2,
A2) deux concepts, une relation d'ordre notée « <
»peut être définie sur ces deux concepts de la manière
suivante :
(O1, A1) < (O2, A2) = O1
C O2 et A1 D A2
C1 < C2 = (O1, A1) est un sous-concept de
(O2, A2) et
(O2, A2)est un sur-concept
de(O1, A1).
Définition 6 (Ordre lexicographique)
La plupart des méthodes proposées dans les
fouilles des données définissent un ordre total sur les
itemsets ou sous ensemble d'attributs. Cet ordre total pouvant
s'étendre en un ordre lexicographique, permet à la fois
d'éviter des redondances des calculs en parcourant chaque itemset au
plus une seule fois, mais également de stocker efficacement les itemsets
dans des structures de données appropriées. Ainsi, on
étend l'ordre total sur X en un ordre lexicographique comme suit :
Soient A, B deux sous-ensembles distincts d'un ensemble X
totalement ordonné. On dit que A est inférieur
lexicographiquement à B si le plus petit élément qui
distingue A et B appartient à A. On note « A
-<lex B »et on lit « A est inférieur
lexicographiquement à B. »[5]
Définition 7 (Arbre lexicographique)
Soit une liste de mots ordonnée. Si l'ordre sur les
mots est obtenu comme un ordre lexicographique à partir des composants
des mots, alors on peut représenter un ensemble de mots en utilisant la
structure d'arbre de recherche lexicographique.
Soit le dictionnaire constitué des mots suivants : AI,
AIL, AILE, AINE, ALE, BAT, BAS ; où à chaque mot du dictionnaire
on adjoindra un chemin de la racine à un noeud comme representé
dans l'arbre lexicographique de la Figure 3.3 :[5]
28
FIGURE 3.3 - Arbre lexicographique associé au dictionnaire
Définition 8 (Treillis de Galois)
La notion de treillis de Galois ou treillis de concepts est
definie sur l'ensemble des concepts L
L = {(o, a) E P(X) x P(Y )/O =
h(A), A = g(O)} muni de la relation d'ordre <. On le note T = (L,
<).[1][11]
Définition 9 (Face)
Soit Ck = (O, A) un concept formel et soit
predi(Ck) le ième prédécesseur immédiat de
Ck. La ième face du concept formel Ck
correspond à la différence entre son intention et
l'intention de son ième prédécesseur. Soit p le
nombre de prédécesseurs immédiats du concept formel Ck
et FCk la famille des faces. La famille des faces du
concept formel Ck est exprimée par la relation suivante[5] :
FCk = {A - Intent(predi(Ck))}, i
E {1, ..., p}. Définition 10
(Bloqueur)
Soit G = {G1, ..., Gn}
une famille de n ensembles, un bloqueur B de la famille de
G est un ensemble où son intersection avec tout ensemble Gi
E G est non vide.[12]
Définition 11 (Bloqueur minimal)
Un bloqueur B est dit minimal s'il n'existe pas
B1 C B et VGi E G, B1f1Gi =6 0.[5]
Définition 12 (Générateur minimal)
Soit Ck un concept formel et FCk
sa famille de faces. L'ensemble G des générateurs
minimaux associés à l'intention A du concept formel
Ck, correspond aux bloqueurs minimaux associés à la
famille de ses faces FCk.
D'une manière équivalente, soit Y un
ensemble d'attribut, un itemset a C_ Y est appelé
générateur minimal d'un concept formel Ck = (O,
A), si et seulement si h(a) = A et , a1 C a
tels que h(a1) = A.[5][12]
29
FIGURE 3.4 - Matrice decrivant la relation R du contexte
K = (X, Y, R) Exemple 2
Soit une application permettant de calculer une correspondance de
galois, un
concept et les opérateurs de fermeture à partir
d'une matrice binaire (Figure 3.4)
générée par un contexte K = (X,
Y, R)
X =
{1,2,3,4,5,6,7} et Y
= {a,b,c,d,e,f,g,h};
g({1,2,3,4}) =
{a,b,c,d} et h({a,b,c,d}) =
{1,2,3,4}
On constate que ({1, 2, 3, 4},
{a, b, c, d}) est un concept; alors que ({1, 2},
{e, f})
ne l'est pas parce que :
g({1, 2}) = {a, b, c, d, e, f} et
h({e, f}) = {1, 2}
Si X = {2, 4, 5} alors
g(X) = {a, b, d}
X» = {1, 2, 3,4,
5} = h(g(X))
Si X = {1,5} alors g(X) =
{a,b,d,e,g}; X» = {1,3,5}
Si Y = {a}, alors h(Y ) =
{1, 2, 3, 4, 5, 6, 7};
Y » = {a}
Si Y = {a,c}, alors h(Y ) =
{1, 2, 3, 4, 6, 7}; Y
» = {a,c}
Seuls les ensembles {a} et {a, c} sont fermés.
| 
