Impact de la structure de treillis dans le domaine de fouille de données et la représentation des connaissances.

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, ..., G_n} 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.