1.4 Derivation des bases generiques de regles
d'association
Depuis l'apparition de l'approche basee sur l'extraction des
itemsets fermes frequents [48], une nouvelle formulation du probleme de
l'extraction des regles d'association est proposee et qui consiste a extraire
les itemsets fermes frequents au lieu des itemsets frequents. Ceci permet [47]
:
D'ameliorer les temps de calcul, puisque dans la plupart des
cas, le nombre d'itemsets fermes frequents est largement inferieur au nombre
d'itemsets frequents, surtout pour les bases de transactions fortement
correlees ou denses.
De generer que des regles d'association non redondantes.
Cette nouvelle approche -- l'extraction des itemsets fermes
frequents -- a donne lieu a une selection de sous-ensembles de regles sans
perte d'information. La selection de regles sans perte d'information repose sur
l'extraction d'un sous-ensemble de toutes les regles
d'association, appele base generi que, a partir duquel le
reste des regles pourrait etre derive. Dans ce memoire, nous allons nous
interesser en particulier a l'approche de Bastide et al. [4, 5]. Cette
approche presente deux bases generiques qui sont definies comme suit :
1. La Base generi que de regles d'association exactes, adaptee
de la base d'implications globales de Guigues et Duquenne [31], est definie
comme suit [4, 5] :
Definition 2 Soit IFFK l'ensemble des itemsets
fermes frequents extrait d'un contexte d'extraction K. Pour
cha que itemset ferme frequent f ? IFFK, nous designons par GMf
l'ensemble de ses generateurs minimaux. La base generi que de regles
d'association exactes est donnee par : BG = {R :
g (f - g) | f ? IFFK et g ? GMf
et g f(3)}
2.
.
La base generique de regles d'association approximatives
appelee Base informative de regles d'association approximatives,
adaptee de la base d'implications partielles de Luxenburger [45], est definie
comme suit [4, 5] :
Definition 3 Soit GMFK l'ensemble des generateurs
minimaux frequents extrait d'un contexte d'extraction K. La
base informative de regles d'association approximatives BI est donnee
par : BI = {R : g (f - g) | f
? IFFK et g ? GMFK et ã(g) ? f
et Conf (R) = minconf}.
Afin de reduire le nombre de regles generiques approximatives,
Bastide et al. proposent une reduction transitive de la base informative [4,
5], qui est elle-meme une base pour toutes les regles approximatives, definie
de la maniere suivante :
Definition 4 La reduction transitive RI de la base
informative est donnee par : RI {R : g (f
- g) | f ? IFFK et g ? GMFK et
ã(g) ? f et Conf (R) =
minconf}.
Ainsi, il est possible de determiner toutes les regles de la
base informative et donc toutes les regles approximatives a partir de la
reduction transitive [4, 5]. Ceci a pour avantage de presenter un ensemble
minimal de regles a l'utilisateur, ce qui lui permet de mieux les visualiser et
les utiliser.
Dans la suite, nous allons considerer les regles d'association
generiques formees par l'union de la base generique de regles exactes et la
reduction transitive de la base informative. Ces regles seront designees par
regles d'association informatives. Ainsi, etant donne un treillis d'Iceberg,
dans lequel chaque itemset ferme frequent est decore par sa liste de
generateurs minimaux, la derivation de ces regles peut se faire d'une maniere
directe. En
3La condition g 0 f permet de ne pas
retenir les regles de la forme g Ø.
effet, les regles approximatives génériques sont
des implications "inter-nceuds" assorties d'une mesure de confiance. Cette
implication met en jeu deux classes d'équivalence comparables, cad d'un
itemset fermé vers un autre itemset fermé le couvrant
immédiatement dans la structure partiellement ordonnée. En
revanche, les regles génériques exactes sont des implications
"intra-nceud", avec une confiance égale a 1, extraites de chaque nceud
dans la structure partiellement ordonnée.
Il faut noter que les bases considérées
présentent plusieurs avantages [4, 5, 41] :
1. Ces bases donnent des regles génériques avec
un nombre minimal d'items dans la prémisse et un nombre maximal d'items
dans la conclusion [38]. Ceci donne les regles les plus informatives pour
l'utilisateur [47].
2. Ces bases n'induisent aucune perte d'information. En
effet, ces bases génériques présentent un ensemble minimal
de regles, a partir duquel toutes les regles valides peuvent etre
retrouvées par application d'axiomes d'inférence comme ceux
proposés dans [10]. En plus, ces bases sont informatives, cad qu'elles
permettent de retrouver, pour chaque regle redondante, son support et sa
confiance sans acces au contexte d'extraction.
3. Ces bases sont valides, cad qu'elles ne permettent de
générer que les regles redondantes ayant un support et une
confiance dépassant respectivement minsup et minconf.
4. La réduction transitive regroupe les regles
approximatives génériques ayant des confiances
élevées. En effet, chacune des regles, formant la
réduction transitive, constitue un lien entre deux classes
d'équivalence dont l'une couvre l'autre immédiatement. Ces
classes d'équivalence ont généralement des supports
proches. Ceci permet d'avoir des regles d'association présentant des
confiances élevées. Sauf rares exceptions, ces regles sont les
plus intéressantes [4].
Les algorithmes présentés dans [5, 47]
permettent d'extraire ces bases en supposant l'existence des itemsets
fermés fréquents ainsi que leurs générateurs
minimaux respectifs. Ceci nécessite l'application en amont d'un autre
algorithme tel que CLOSE [48, 49] ou A-CLOSE [50], etc. La
génération de la base générique de regles
d'association exactes se fait alors d'une maniere directe. Cependant pour les
regles d'association approximatives, des tests d'inclusion coitteux, mettant en
jeu les itemsets fermés fréquents, sont réalisés
pour déterminer les successeurs immédiats de chaque classe
d'équivalence.
| 