Extraction des bases génériques informatives de règles sans calcul de fermetures

précédent sommaire suivant

1.3.3 Connexion de Galois

- Operateurs de fermeture :

Soit un ensemble partiellement ordonne (E,=). Une application ã de (E,=) dans (E,=) est appelee un operateur de fermeture, si et seulement si elle possede les proprietes suivantes. Pour tout sous-ensemble S, S' ? E [21] :

1. Isotonie : S = S' ã(S) ? ã(S')

2. Extensivite : S ? ã(S)

3. Idempotence : ã(ã(S)) = ã(S)

Etant donne un operateur de fermeture ã sur un ensemble partiellement ordonne (E,=), un element x ? E est un element ferme si l'image de x par l'operateur de fermeture ã est egale a lui-même, cad ã(x) = x [21].

- Connexion de Galois :

Soit un contexte d'extraction K = ~O,I,R~. Soit l'application ö, de l'ensemble des parties de OM dans l'ensemble des parties de I, qui associe a un ensemble d'objets O ? O l'ensemble des items i ? I communs a tous les objets o ? O [27] :

ö : 2^O ? 2I
ö(O) = {i ? I|?o ? O ? oRi }

Soit l'application ø, de l'ensemble des parties de I dans l'ensemble des parties de O, qui associe a tout ensemble d'items (communement appele itemset) I ? I l'ensemble des objets o ? O contenant tous les items i ? I [27] :

ø : 2I ? 2O
ø(I) = {o ? O|?i ? I ? oRi }

Le couple d'applications (ö,ø) est une connexion de Galois entre l'ensemble des parties de O et l'ensemble des parties de I [3, 27]. Etant donne une connexion de Galois, les proprietes suivantes sont verifiees quelques soient I, I₁, I₂ ? I et O, O₁, O₂ ? O [27] :

1. I₁ ? I₂ ø(I₂) ? ø(I₁);

2. O₁ ? O₂ ö(O₂) ? ö(O₁) ;

3. O ? ø(I) ? I ? ö(O) ? (I,O) ? R.

- Fermeture de la connexion de Galois :

Nous considerons les ensembles des parties 2^I et 2^O dotes de la relation d'inclusion ?, cad les ensembles partiellement ordonnes (2^I, ? ) et (2^O, ? ). Les operateurs ã = ö ? ø de (2^I, ? ) dans (2^I, ? ) et ã'= ø ? ö de (2^O, ? ) dans (2^O, ? ) sont des operateurs de fermeture de la connexion de Galois [3, 27]. Etant donne une connexion de Galois, les proprietes suivantes sont verifiees quelques soient I, I₁, I₂ ? I et O, O₁, O₂ ? O [27] :

1. I ? ã(I) 1'. O ? ã'(O)

2. ã(ã(I))=ã(I) 2'. ã'(ã'(O))=ã^~(O)

3. I₁ ? I₂ ã(I₁) ? ã(I₂) 3'. O₁ ? O₂ ã'(O₁) ? ã'(O₂)

4. ã(ø(I)) = ø(I) 4'. ã(ö(O)) = ö(O)

- Treillis de concepts formels (de Galois) :

Etant donne un contexte d'extraction K=(O,I,R), l'ensemble de concepts formels CK est un treillis complet LC,, = (CK, =), appele treillis de concepts formels (de Galois), quand l'ensemble CK est considere avec la relation d'inclusion entre les itemsets [3, 27]. La relation d'ordre partiel entre des concepts formels est definie comme suit [27] : ? c₁= (O₁,I₁), c2 =(O₂,I₂) ? CK, c₁ = c₂ ? I₂ ? I₁ (? O₁ ? O₂) avec I₁, I₂ ? I et O₁, O₂ ? O.

Dans un treillis de concepts, l'element ø(O) x O est appele element Bottom du treillis (note 1) et l'element Z x ö(Z) est appele element Top du treillis (note T). Le chemin amenant du Bottom jusqu'au Top est appele chaine maximale du treillis [27].

Dans un treillis de concepts, les operateurs Join et Meet permettent d'obtenir, respectivement, la plus petite borne superieure et la plus grande borne inferieure. Les operateurs Join et Meet sont definis comme suit [27] :

V O₁, O₂ C O et I₁, I₂ C Z :

- (O₁, I₁) V (O₂, I₂) = (ã(O₁ U O₂), I₁ n I₂),

- (O₁, I₁) A (O₂, I₂ = (O₁ n O₂, ã(I₁ U I₂)).

La relation d'ordre partiel est utilisee pour generer le graphe du treillis, appele Diagramme de Hasse, comme suit [27] :

Il existe un arc (c₁, c₂), si c₁ c₂ oft est la reduction transitive de <, cad Vc₃ E CK,

c₁ < c3 < c₂ c₁ =c₃ ou c₂ =c₃.

Dans ce graphe, les sommets correspondent aux elements de l'ensemble Ck et les arcs aux relations de couverture entre les sommets. Chaque element c E Cic est connecte aussi bien a un ensemble de ses successeurs immediats, appele Couverture superieure (Couv^s), et a un ensemble de ses predecesseurs immediats, appele Couverture inferieure (Couvi).