1.3.4 Itemsets fermes et leurs generateurs minimaux
Dans cette section, nous definissons :
G les itemsets fermes qui peuvent être ordonnes sous la
forme d'un treillis des itemsets fermes.
G les itemsets fermes frequents qui peuvent être ordonne
sous la forme d'un treillis d'Iceberg.
les generateurs minimaux.
- Itemset ferme :
Etant donne l'operateur de fermeture de la connexion de
Galois ã, un itemset l C Z tel que
ã(l) = l est appele itemset ferme. Un itemset
ferme est donc un ensemble maximal d'items communs a un ensemble d'objets
[47].
[BC} n'est pas un itemset ferme car il n'est pas un ensemble
maximal d'items communs a certains objets : tous les objets contenant
les items B et C, cad les objets 2,3 et 5 contiennent egalement l'item
E.
- Ensemble d'itemsets fermes :
Soit un contexte d'extraction K =
(O,I,R) et l'operateur de fermeture de la connexion
de Galois ã. L'ensemble IF des itemsets fermes dans le
contexte K est defini comme suit [47] :
IF = {l ? I 1 l= Ø ?
ã(l~=lP.
Le plus petit (minimal au sens de l'inclusion) itemset ferme
contenant un itemset l est obtenu par l'application de l'operateur
ã a l [47].
- treillis des itemsets fermes :
L'operateur de fermeture ã induit une
relation d'equivalence sur l'ensemble de parties de I, cad l'ensemble
de parties est partionne en des sous-ensembles disjoints, appeles aussi classes
d'equivalence. Dans chaque classe, tous les elements possedent la meme valeur
de support. Les generateurs minimaux d'une classe sont les elements
incomparables (selon la relation d'inclusion) les plus petits, tandis que
l'itemset ferme est l'element le plus large de cette classe. Ces classes
d'equivalence sont ordonnees sous forme d'un treillis de concepts formels (de
Galois) oft chaque concept formel est dans ce cas un itemset ferme. Ainsi, le
couple LIF =-- (IF,?) est un treillis complet appele
treillis des itemsets fermes [47].
- Itemset ferme frequent :
Un itemset ferme l est dit frequent si son support
relatif, Supp(l) = |ø~l~|
|O| ,excede un seuil minimum fixe par l'utilisateur note
minsup [47]. Notons que |ø(l~| est appele
support absolu de l.
Agrawal et al. ont introduit dans [1], les deux proprietes
suivantes relatives aux supports des itemsets frequents :
1. Tous les sous-ensembles d'un itemset frequent sont
frequents.
2. Tous les sur-ensembles d'un itemset infrequent sont
infrequents.
Ces proprietes restent applicables dans le cas des itemsets
fermes frequents [47]. Ainsi,
1. Tous les sous-ensembles d'un itemset ferme frequent sont
frequents.
2. Tous les sur-ensembles d'un itemset ferme infrequent sont
infrequents.
Sachant que le support d'un itemset (frequent) l est
egal au support de sa fermeture ã(l) qui est le plus
petit itemset ferme contenant l : Supp(l) =
Supp(ã(l~) [47].
- Treillis d'Iceberg :
Quand nous considerons seulement l'ensemble des itemsets
fermes frequents ordonnes par la relation d'inclusion ensembliste, la structure
obtenue (àL, ? ) preserve seulement l'operateur
Join. Cette structure forme un semi-treillis superieur et elle est designee par
treillis d'Iceberg [6, 57, 63].
- Generateur minimal :
Un itemset g ? I est dit generateur minimal d'un
itemset ferme f, si et seulement si ã(g)
= f et il n'existe pas g1 ? I tel que
g1 ? g [5]. L'ensemble GMf des generateurs
minimaux d'un itemset ferme f est defini comme suit :
GMf = { g ? I l
ã(g)=f ? l g1 ? g
tel que ã(g1) =f }.
Dans la suite, nous allons montrer la connexion de l'analyse
formelle de concepts avec l'extraction des bases generiques de regles
d'association.
| 