L?extraction des r�gles d?association est un important th�me de recherche qui a attir� l?attention et l?int�r�t de nombreux chercheurs en fouille de donn�es. Dans plusieurs travaux inspir�s de l?algorithme Apriori (Agrawal et Strikant, 1994), la g�n�ration des r�gles se fait en deux �tapes : la d�tection des motifs ferm�s fr�quents, puis la g�n�ration des r�gles d?association ayant une confiance>=minconf (confiance minimale tol�r�e). La deuxi�me �tape est relativement simple alors que le premi�re pr�sente de grands d�fis et peut �tre tr�s co�teuse puisque le nombre de motifs obtenus peut �tre exponentiel par rapport au nombre total d?items. La recherche de motifs ferm�s fr�quents (MFF) est reconnue comme �tant une solution satisfaisante pour r�duire le nombre de motifs ferm�s et donc de r�gles d?association g�n�r�es ? partir de ces motifs (Pasquier, Bastide et al., 1999, Pei, Han et al., 2000,Wang, Han et al., 2003, Zaki, 2000, Zaki et Hsiao, 2002). Toutefois, le nombre de MFF reste parfois tr�s �lev� m�me pour des bases de donn�es de petite taille.

Dans cette �tude, nous cherchons � am�liorer le processus d?extraction des motifs ferm�s fr�quents en rendant l?approche plus param�trable que les m�thodes classiques et en offrant des possibilit�s d?approximation du r�sultat. L?id�e est d?utiliser un graphe de d�pendances comme support � la g�n�ration des MFF ainsi que des techniques d?�lagage fond�es sur trois seuils�: le support, la co-occurrence et la tol�rance. Les deux derniers param�tres peuvent �tre choisis de mani�re � obtenir soit la totalit� soit une partie des MFF. Dans le deuxi�me cas, le nombre de MFF peut �tre largement r�duit sachant que le plus souvent, les MFF les moins pertinents se trouvent �cart�s. Notre but est de limiter la prospection des MFF aux candidats qui auront le plus de chance d?appara�tre dans de grands motifs tout en �liminant les couples d?items faiblement li�s entre eux.

L?article est organis� comme suit : la section 2 fournit un rappel des concepts et une br�ve �tude de la litt�rature portant sur l?extraction des r�gles d?association. Notre solution est d�taill�e dans les sections 3 et 4 o� sont d�crites la construction du graphe de d�pendances et l?exploration de ce m�me graphe pour g�n�rer un ensemble de MFF. Des r�sultats empiriques fond�s sur la comparaison de CIGA+ avec BAMBOO�(Wang, Han et al., 2003) sont pr�sent�s dans la section 5. Enfin, une conclusion est fournie en section 6.

La g�n�ration des r�gles d?association a fait l?objet d?un nombre consid�rable de travaux de recherche dans le domaine de la fouille de donn�es. Dans cette section, nous rappelons d?abord quelques notions �l�mentaires, puis nous pr�sentons une revue de la litt�rature sur la production des r�gles d?association.

Soit I = {i1,i2,?,im} un ensemble de m items distincts. Une transaction T contient un ensemble d?items contenus dans I, et poss�de un identifiant unique TID. Un sous-ensemble Y de I o� k=|Y| est un motif de taille k (k-itemset). Une base de transactions D est l?ensemble de transactions effectu�es sur un sous-ensemble d?items de I. XD est un ensemble de transactions (appel� tidset) tandis que la fraction de transactions dans D contenant Y est appel�e support de Y et not�e supp(Y). Ainsi, on dit qu?un motif est fr�quent lorsque son support d�passe un support donn� appel� minsupp. ? un tidset X donn� correspond un motif dont la valeur est f(X). Cela correspond � l?ensemble des items communs � toutes les transactions de X. De la m�me mani�re, g(Y) repr�sente l?ensemble des transactions qui contiennent tous les items de l?ensemble Y.

Un motif Y est dit ferm� lorsqu?il n?existe aucun motif Z de taille sup�rieure � Y mais avec le m�me support que Y. En d?autres termes, tout motif poss�de le m�me support que sa fermeture. De fa�on similaire, un tidset est ferm� lorsque aucun autre tidset de taille sup�rieure ne poss�de le m�me support. Une autre fa�on d?�crire la condition de fermeture revient � dire que Y (resp. X) est ferm� si et seulement si Y=f(g(Y)) (resp. X=g(f(X))).

Depuis l?apparition de l?algorithme Apriori, plusieurs algorithmes d?extraction des r�gles d?association ont vu le jour. Pour la plupart d?entre eux, le but est d?am�liorer l?efficacit� de la m�thode initiale (Hipp, Guntzer et al., 2000) tandis que le principal probl�me reste le vaste ensemble de MFF qui est difficilement manipulable � l?�tape subs�quente de production des r�gles. Pour r�duire la taille de cet ensemble, plusieurs �tudes ont d�j? �t� conduites sur les motifs ferm�s (Zaki et Hsiao, 2002, Pasquier, Bastide et al., 1999, Bastide, Taouil et al., 2000, Pei, Han et al., 2000) et les motifs maximaux (MFM) 1 (Bayard, 1998, Burdick, Calimlim et al., 2001). Bien qu?il puisse y avoir un nombre exponentiellement plus grand de MFF que de MFM, les premiers ont l?avantage de n?engendrer aucune perte d?information.

Une r�gle d?association r est une implication de la forme Y₁ =>?Y₂, o� Y₁ et Y₂ sont des sous-ensembles de I, et le support de

Avec Apriori (Agrawal et Strikant, 1994), le calcul des r�gles d?associations � partir de l?ensemble des MFF se fait de la fa�on suivante. Pour chaque motif fr�quent Y, on g�n�re les divers sous-ensembles non vides de Y. Ensuite, pour chaque sous-ensemble de Y, une r�gle de la forme Y₁=>Y?Y₂ est retenue si le rapport supp(Y)/supp(Y₁) est au moins �gal � minconf. Dans le cadre des MFF, certaines �tudes se sont int�ress�es � la g�n�ration des ensembles non redondants de r�gles (Lakhal, Pasquier et al.,1999, Luxemburger, 1991, Valtchev, Missaoui et al., 2003) o� est un g�n�rateur, c.?.d., un sous-ensemble minimal de Y tel que sa fermeture est �gale � Y (Pfaltz et Taylor, 2002).

AClose, Close�(Pasquier, Bastide et al., 1999), ChARM (Zaki et Hsiao, 2002) et Closet+ (Wang, Han et al., 2003) font partie des premiers algorithmes de calcul de MFF. Titanic (Stumme, Taouil et al., 2002) h�rite de l?approche fond�e sur la notion de g�n�rateur pr�sente dans AClose, mais propose des simplifications int�ressantes. Closet et son am�lioration r�cente Closet+ g�n�rent tous les deux les MFF comme les branches maximales d?un arbre appel� FP-tree, une structure bas�e sur un arbre pr�fixe (ou arbre tri�) augment�e par une liste transversale de pointeurs. BAMBOO (Wang et Karypis, 2004) est une version am�lior�e de Closet+ dans la mesure o� elle produit un r�sultat plus concis et propose des performances plus int�ressantes. BAMBOO exploite la contrainte de support de longueur d�croissante en plus d?un certain nombre d?�lagages et d?optimisations pour am�liorer l?efficacit� du calcul des MFF. La contrainte de support d�croissant consiste � fournir un support sous forme d?une fonction d�croissante qui varie selon la taille du motif de mani�re � r�duire le nombre de motifs de petite taille. Les exp�rimentations conduites dans (Wang et Karypis, 2004) montrent que BAMBOO est g�n�ralement plus performant que trois algorithmes connus de g�n�ration des MFF pour les divers types de bases de donn�es. Toutefois, la fonction de support d�croissant n?est pas �tablie par les auteurs d?une mani�re th�orique mais davantage par des exp�rimentations et pour une base de donn�es tr�s sp�cifique.

Notre algorithme, appel� CIGA+, est similaire � BAMBOO dans la mesure o� il g�n�re un sous-ensemble concis de MFF et propose des temps d?ex�cution int�ressants. ? la diff�rence de BAMBOO qui fonde son �lagage sur la fonction de support d�croissant, CIGA+ utilise les co-occurrences d?items pour d�terminer rapidement les motifs de grande taille et s?inspire des propri�t�s des treillis de concepts en analyse formelle de concepts (Ganter et Wille, 1999).

Dans ce qui suit, nous d�crivons CIGA+, un algorithme qui utilise trois param�tres de seuil pour produire un ensemble complet ou approximatif des motifs ferm�s fr�quents (MFF) en explorant un graphe de d�pendances dans lequel les noeuds sont des items et les ar�tes repr�sentent des liens (fr�quences de cooccurrence) entre deux items. Les seuils utilis�s sont�: le support minimal (minsupp), la confiance minimale entre deux items (mincooc) et la tol�rance minimale (mintol). Le premier param�tre est d�j? connu par la communaut� du data mining, le second param�tre mincooc permet d?�carter des liens faibles entre deux items individuels en se basant sur leur fr�quence de co-occurrence et le dernier param�tre permet d?�liminer d?�ventuels liens qui ne sont pas n�cessaires entre deux items. Par cons�quent, le graphe de d�pendances est simplifi� pour faciliter son parcours et la production d?un ensemble plus r�duit de MFF. Le param�trage du seuil mintol d�pend du degr� d?approximation souhait� par l?utilisateur. Un seuil de 100% permet d?obtenir l?ensemble complet des MFF tandis qu?une valeur non nulle g�n�re une approximation plus ou moins importante de cet ensemble.

CIGA+ comporte deux �tapes : la construction du graphe de d�pendances (section 3) puis la g�n�ration des MFF (section 4). Les seuils de co-occurrence et de tol�rance sont utilis�s lors de la premi�re �tape tandis que le support est utilis� dans la seconde.

? titre d?exemple, nous allons consid�rer la petite base de transactions de la table (tab1). Elle comporte huit transactions et neuf items {a,b,c,d,e,f,g,h,i} qui d�crivent des paniers de consommateurs (achat de produits).

Les items sont tri�s selon l?ordre d�croissant de leur support car les items les plus fr�quents apparaissent plus souvent dans le r�sultat et donc sont trait�s en premier. Le tri des items est aussi une condition n�cessaire pour appliquer l?�lagage d�crit dans la section 3.

Cette section d�crit l?�tape de pr�traitement qui consiste � construire un graphe de d�pendances � partir d?une matrice de cooccurrences. Le graphe servira ensuite � la g�n�ration des MFF. Le graphe peut �tre partiel ou complet (i.e tous les MFF sont g�n�r�s) selon les valeurs qui sont attribu�es � mincooc et mintol. La signification de ces param�tres est expliqu�e dans cette section.

La construction du graphe de d�pendances d�bute par la construction d?une matrice de cooccurrences (voir table 2) pour les items fr�quents. Il s?agit d?une matrice triangulaire dont les lignes et les colonnes sont ordonn�es par ordre d�croissant du support des items. La valeur d?une cellule cooc[i,j] (avec j>=i) repr�sente le nombre de fois que l?item appara�t avec a_i et cooc[i,i] repr�sente le support (absolu) de l?item. Par exemple, cooc[a,d]=4.

Un ensemble de mesures sur des r�gles �l�mentaires (c.?.d. r�gles qui mettent en jeu deux items individuels) peut �tre directement extrait de la matrice de co-occurrence :

• Le support relatif d?une r�gle est a_i =>a_j. Le param�tre minsupp est sa valeur minimale tol�r�e.

• La confiance d?une r�gle est a_i =>a_j. Sa plus petite valeur tol�r�e est appel�e mincooc.

• La tol�rance d?un lien (aj,ai),o� supp(a_j) <= supp(a_j) est �quivalente � la confiance d?une r�gle. Sa plus petite valeur accept�e est mintol.

Par exemple, conf(f=>d)=100%, ce qui signifie que l?item f appara�t toujours en pr�sence de l?item d.

On d�finit un graphe de d�pendances G=<N,T> comme �tant un graphe orient� et acyclique dont les noeuds dans N correspondent aux items fr�quents. Il repr�sente les d�pendances qui ont lieu entre deux items selon leur fr�quence de cooccurrence. Ainsi, une ar�te dans T allant du noeud a_i au noeud a_j, et not�e (ai,aj), indique que conf(a_i=>a_j) >= mincooc et supp(a_i) >= supp(a_j).

Comme pour la plupart des algorithmes de type Apriori, un des �lagages utilis�s dans CIGA+ consiste ? ignorer les items non fr�quents (c.�.d., les items qui ont un support inf�rieur � minsupp). Les autres �lagages permettent d?�carter des MFF que l?on juge non pertinents. Les param�tres sont exploit�s de la mani�re suivante : utilisation de minsupp pour �carter les items non fr�quents, utilisation de mincooc pour �carter les liens faibles entre deux items donn�s dans le graphe de d�pendances, et utilisation de mintol pour �liminer les ar�tes inutiles entre deux items donn�s.

Propri�t� 1 Lorsque g(a_j) g(a_i) (c.-?-d. conf(a_j =>a_i) = 100%)), alors l?ar�te (ah,aj) du graphe de d�pendances est toujours inutile quelque soit tel que supp(a_k) >= supp(a_i).

La propri�t� 1 (figure 1) signifie que lorsqu?un item appara�t syst�matiquement dans une transaction avec a_i, alors l?ar�te (ah,aj) dans le graphe de d�pendances est redondante pour tout noeud a_h qui pr�c�de a_i. Ceci est toujours vrai dans la mesure o� tout MFF contenant a_j va n�cessairement inclure a_i, et par cons�quent un chemin qui court-circuite a_i en allant de ?_h � a_j conduit toujours vers un motif non ferm�. Il est important de noter que a_i n?est pas n�cessairement le parent direct de a_j, et que la pr�sence de (ah,aj) dans le graphe de d�pendances, par d�finition, implique supp(a_k) >= supp(a_i).

Dans notre exemple, l?item Roquefort appara�t toujours avec biscuits puisque conf(Roquefort => biscuits) = 100%. Ainsi, tout MFF qui contient Roquefort et tout autre item ayant un support sup�rieur ou �gal au support de biscuits (i.e., eau min�rale) va n�cessairement contenir l?item biscuits. En d?autres termes, la fermeture de {eau min�rale, Roquefort} contiendra toujours l?item biscuits. L?ar�te (eau min�rale, Roquefort) est alors inutile.

La propri�t� 1 est adaptable pour approximer (simplifier) le graphe de d�pendances. La propri�t� suivante en est une g�n�ralisation.

Propri�t� 2 Si conf (a_j=>a_i) >= mintol, alors l?ar�te (ah,aj) est rarement utile pour tout noeud a_h tel que supp(a_k) >= supp(a_i).

La propri�t� 2 permet d?�carter l?ar�te (ah,aj) chaque fois que l?item a_j appara�t avec a_i (en se basant sur la valeur de mintol) puisque tout motif qui contient a_j aura de fortes chances de contenir a_i.

Un cas particulier de l?�lagage bas� sur mintol intervient lorsque repr�sente l?�tat initial. Dans un tel cas, cela implique que le noeud ne sera pas connect� au noeud initial d�s que la condition conf (a_j=>a_i) >= mintol aura lieu.

Le graphe de d�pendances de la figure 2 a �t� g�n�r� en utilisant mintol=100 %. On peut remarquer qu?il n?y a pas syst�matiquement d?ar�tes allant du noeud initial vers chaque noeud du graphe. Par exemple, on observe que Roquefort appara�t tout le temps en pr�sence de l?item biscuits et par cons�quent, une ar�te allant de {} vers Roquefort est non justifi�e puisqu?il existe un chemin aboutissant � Roquefort en passant par biscuits, et que Roquefort ne peut pas constituer � lui seul un MFF. De m�me, les ar�tes (eau min�rale, Roquefort), (beurre, Roquefort) et (baguette, Roquefort) sont inappropri�es.

Dans cette sous-section, nous pr�sentons l?algorithme qui construit le graphe de d�pendances.

L?algorithme 1 construit le graphe de d�pendances � partir de la matrice de cooccurrences. Il poss�de trois param�tres en entr�e : la matrice de co-occurrence cooc[n,n] o� n est le nombre d?items fr�quents, mincooc et mintol. N repr�sente l?ensemble de noeuds dans le graphe de d�pendances. { } est le noeud initial et (ai,aj) repr�sente l?ar�te allant du noeud ai au noeud aj.

La construction du graphe de d�pendances s?effectue de la fa�on suivante. Comme l?indiquent les deux boucles ��pour��, les items sont trait�s par ordre d�croissant de leur support, c.?.d. en consid�rant en premier les items les moins fr�quents puis en int�grant progressivement ceux qui sont les plus fr�quents. Deux items distincts (identifi�s respectivement par la ligne i et la colonne j de la matrice de co-occurrence) sont compar�s pour d�terminer si l?ar�te (ai, aj) doit �tre trac�e. Sauf dans le cas o� la propri�t� 1 (ou la propri�t� 2) est v�rifi�e, il existe une ar�te allant de ?_i � a_j tant que la condition supp(a_i) >= supp(a_j) est vraie. La ligne�5 tient compte de la confiance (fr�quence de co-occurrence) tandis que les lignes�8 et 9 exploitent le seuil de tol�rance (figure 1). En d?autres termes, la ligne�5 v�rifie si a_i et a_j sont connect�s dans la base de transactions tandis que la ligne�8 applique l?�lagage mentionn� pr�c�demment (sous-section 3.3). ? la ligne�14, les points d?entr�e sont g�n�r�s. Par d�faut, aucun (?item?) noeud du graphe de d�pendances n?est connect� au noeud initial. D�s qu?un item n?appara�t ?presque jamais? en pr�sence d?un autre, alors on choisit de le relier au noeud initial.

Comme mentionn� ci-dessus, la confiance (exprim�e comme la fr�quence de co-occurrence entre deux items) est un moyen de r�duire la taille du graphe de d�pendances. Le graphe partiel (figure 3) est pr�sent� (par opposition au graphe complet de la figure 2) o� le seuil de confiance mincooc vaut 50 %. Par exemple, l?ensemble d?items {beurre, eau min�rale, baguette} n?appara�tra pas dans l?ensemble des MFF puisque le chemin correspondant dans le graphe n?existe pas du fait que conf(eau min�rale => baguette)=40%.

Preuve de compl�tude : Nous allons montrer que le graphe de d�pendances G est une base compl�te pour g�n�rer tous les MFF lorsque aucune approximation n?est utilis�e (c.-?-d. mincooc=0% et mintol=100%). Tout d?abord, nous supposons qu?aucun �lagage n?est appliqu� en se basant sur la propri�t� 2. Dans ce cas, lorsque a_i et a_j apparaissent dans une m�me transaction T, alors, il y a toujours une ar�te allant de a_i vers a_j avec supp(a_i) >= supp(a_j). Si maintenant on tient compte de l?�lagage d�crit par la propri�t� 1, on cherche alors � montrer que l?ar�te (ah,aj) �cart�e ne contribue pas � la construction d?un MFF not� Z et repr�sentant le chemin allant de l?�tat initial au noeud a_j.

L?id�e derri�re CIGA+ est la suivante. Le support de a_i a plus de chances d?�tre �lev� que le support de a_j si l?item le moins fr�quent dans Y est tel que conf(a_i=>a_j)>conf(a_i=>a_k). Cela permet de se diriger rapidement vers les motifs de plus grande taille.

Par exemple, consid�rons le motif Y={beurre, baguette} (voir figure 2) o� baguette est l?item dans Y qui poss�de le plus petit support. L?extension de Y est g(Y)={3,4,6,7,8}. Donc, le candidat le plus prometteur pour augmenter Y est biscuits plut�t que saumon fum� puisque conf(baguette => biscuits)=3/5 tandis que conf(baguette => saumon fum�)=2/5.

Dans cette section, nous d�crivons tout d?abord l?algorithme CIGA+ en indiquant comment les tidsets ferm�s et les motifs sont calcul�s puis nous illustrons l?ex�cution de CIGA+ par un exemple.

L?algorithme CIGA+ (voir l?algorithme 2) poss�de quatre param�tres : la matrice de co-occurrences cooc[n,n], minsupp, mincooc et mintol. La variable globale L est utilis�e dans la proc�dure CIGA+_SUB pour stocker les MFF calcul�s. CIGA+ proc�de en deux �tapes. Tout d?abord, le pr�traitement des donn�es bas� sur la construction du graphe de d�pendances est effectu�. Ensuite, un appel de la proc�dure r�cursive que nous appelons CIGA+_SUB est effectu� pour chaque noeud directement li� au noeud initial. Tant que le support du chemin courant (c.-�-d. l?ensemble d?items situ�s sur le chemin) est plus grand que minsupp ou bien qu?un noeud terminal n?est pas atteint, l?algorithme 3 continue � parcourir le graphe de d�pendances en explorant les successeurs du noeud courant.

Dans l?algorithme 3, la variable a repr�sente l?item associ� au dernier noeud du chemin courant. X est le tidset associ� au motif constitu� du chemin courant dans le graphe. Le traitement dans l?algorithme 3 inclut�:

• le calcul de X=g(Y) et du support de Y (c.-?-.d. la taille de X),

• une exploration r�cursive du graphe de d�pendances,

• le calcul des MFF (voir ligne 10).

La premi�re �tape est la plus co�teuse. C?est pourquoi, il est important d?utiliser une structure de donn�es adapt�e pour stocker et retrouver les g(a) ainsi qu?une mani�re efficace de calculer les intersections entre g(a) et X. Nous avons utilis� un index pour les items individuels afin d?obtenir rapidement la valeur du tidset r�sultant.

Le calcul de f(X) intervient lorsque le support du motif courant est inf�rieur � minsupp ou bien lorsqu?on atteint un noeud terminal (voir ligne�3 de l?algorithme 3). Chaque fois que l?on identifie une �galit� entre le support de Y et Y ?a au cours du parcours, alors le calcul de la fermeture g(Y) de Y n?est pas effectu� puisque Y n?est pas ferm�. Le calcul � la ligne 10 intervient lorsque aucun successeur du noeud courant a ne conserve le m�me support que celui du motif Y=f(X) qui correspond au chemin se terminant par a. Ce type de calcul intervient plus ou moins souvent selon les seuils retenus pendant la construction du graphe de d�pendances.

La g�n�ration des MFF dans CIGA+ consiste � explorer le graphe de d�pendances de fa�on r�cursive. Un chemin allant du noeud initial jusqu?au noeud courant repr�sente la s�quence d?items qui correspond au motif Y. Pour chaque chemin dans le graphe, le tidset correspondant 2 associ� � la s�quence d?items courante est calcul�.

La propri�t� 3 permet de mettre � jour X en se basant sur la valeur de g(Y) pour y inclure un nouvel item � partir d?une simple intersection. Cette propri�t� est utile pour g�n�rer rapidement le tidset associ� au chemin courant dans le graphe de d�pendances. De plus, nous savons que X est un tidset ferm� puisqu?il est construit � partir d?une intersection entre deux tidsets ferm�s (Ganter et Wille, 1999). Par exemple, g(beurre, cracker) = {5,6,7,8}. Lorsque le noeud Roquefort est atteint (figure 3), le calcul de g(beurre, cracker, Roquefort) est effectu� en faisant l?intersection des deux tidsets : {5,6,7,8} et {5,6,8}.

L?algorithme 3 parcourt le graphe en utilisant la propri�t� 3 pour g�n�rer les tidsets ferm�s X. Une fois que le tidset X relatif au chemin courant a �t� calcul� et que sa taille est bien sup�rieure ou �gale au support absolu, le motif correspondant Y=g(X) peut �tre calcul�. Cependant, un tel calcul risque d?�tre co�teux et parfois inutile. C?est la raison pour laquelle nous �vitons de le faire syst�matiquement. Comme indiqu� auparavant, un chemin dans le graphe de d�pendances est explor� progressivement jusqu?� ce que le support de son motif associ� devienne inf�rieur � minsupp ou bien qu?un noeud terminal soit atteint. Pendant ce parcours, � chaque fois que l?ajout d?un noeud au chemin courant ne r�duit pas le support, on en d�duit que le motif courant n?est pas ferm� et on �vite de calculer sa fermeture (ligne 5). Lorsque la condition de la ligne�3 n?a pas lieu, alors le motif devient un candidat int�ressant et sa fermeture est calcul�e � la ligne�10.

Le traitement complet de la g�n�ration des MFF comprend trois �tapes principales :

• la transformation des donn�es,

• la construction du graphe de d�pendances,

• l?extraction des MFF.

�La transformation des donn�es et la construction du graphe font partie du pr�traitement car leur co�t est n�gligeable par rapport au calcul des MFF. La complexit� de l?algorithme de construction du graphe de d�pendances (algorithme 1) est O(m²) o� m repr�sente le nombre d?items. La transformation des donn�es, quant � elle, permet de r�arranger la base pour obtenir de meilleures performances lors du calcul des MFF. L?op�ration la plus commune pendant ce calcul est l?intersection entre deux ensembles de transactions g(I) et g(a_i) o� a_i est un item. Aussi, la base de donn�es est r�arrang�e pour stocker tous les g(a_i) sous forme binaire.

La figure 4 illustre l?ex�cution de l?algorithme CIGA+ ? partir des donn�es de la table�1 et du graphe de d�pendances de la figure�2. Les param�tres minsupp, mincooc, et mintol ont comme valeur 0%, 0% et 100% respectivement de sorte que l?algorithme g�n�re l?ensemble complet des MFF.

Lorsque l?algorithme commence l?exploration du graphe de d�pendances, chaque descendant direct du noeud initial est tout d?abord pris en compte (voir ligne 4 de l?algorithme 3). Dans la figure 4, on voit que seul le noeud a est directement accessible depuis la racine. X=g(a) est alors �gal � {1,2,...,8}. Une fois que le noeud a est trait�, ses successeurs b, c, et d sont alors pris en consid�ration. Supposons que le chemin [a,c,g,h,i] est suivi. L?exploration du noeud h m�ne au calcul de

Lorsque le noeud i est atteint, X devient �gal � {4}. Comme i est un noeud terminal, on calcule f(X)=f({4})={a,c,g,h,i} et ensuite on obtient un MFF. Sachant que le support reste constant en passant de la s�quence [a,c,g,h] � [a,c,g], il n?est pas n�cessaire d?effectuer un calcul de fermeture au niveau du noeud g.

La table 3 repr�sente l?ensemble complet des motifs ferm�s MF g�n�r�s � partir de la table�1.

Il est difficile de faire une �tude comparative de CIGA+ avec d?autres algorithmes puisqu?il n?existe aucune proc�dure qui utilise le m�me type d?approximation que la n�tre. Toutefois, BAMBOO est un algorithme efficace de g�n�ration des MFF bas� sur CLOSET+ qui permet aussi de faire de l?approximation mais sous d?autres formes et hypoth�ses. Comme les deux algorithmes partagent un objectif similaire, nous en faisons une �tude comparative dans cette section. Cependant, nous �cartons l?usage du support d�croissant dans BAMBOO et optons pour un support fixe puisque aucune m�thode rigoureuse n?est fournie par les auteurs pour g�n�rer la fonction du support d�croissant pour une base donn�e.

Les exp�rimentations ont �t� conduites sous GNU Linux en utilisant un Pentium IV � 3 Ghz et avec 1024 Mo de m�moire. La comparaison des deux algorithmes s?est faite selon leur temps d?ex�cution et le nombre de MFF g�n�r�s en consid�rant trois types de bases de transactions connues dans la communaut� de fouille de donn�es : Chess, Pumsb et Mushroom.

Comme le montrent les figures ci-apr�s, CIGA+ affiche des temps d?ex�cution plus faibles car il g�n�re moins de MFF. Mais dans tous les cas, le taux d?accroissement des courbes que nous obtenons est fortement similaire pour les deux algorithmes, ce qui montre que les performances sont identiques si on se rapporte � la m�me �chelle. Toutefois, CIGA+ est relativement plus stable et offre une performance relative plus avantageuse lorsque le volume de donn�es devient grand ou lorsque le support minimal devient tr�s faible. Par exemple, avec minsupp = 45%, BAMBOO g�n�re une sortie dix fois plus volumineuse que celle produite par CIGA+, et n�cessite 51 fois plus de temps � s?ex�cuter avec la base Pumsb en utilisant mintol= 95 % et mincooc = 10 %.

La figure 5 montre les performances de CIGA+ par rapport � BAMBOO lorsque mincooc = 10 % et mintol = 95 %. La valeur non nulle du premier param�tre permet d?�carter certains MFF peu pertinents conduisant par la suite � un ensemble plus faible de r�gles d?associations. Avec minsupp = 20 %, CIGA+ g�n�re une sortie qui est 254 fois plus petite que celle de BAMBOO et s?ex�cute 620 fois plus rapidement que BAMBOO. La courbe de la figure 6 confirme nos conclusions pour la base de donn�es dense Pumsb.

Nous n?avons pas illustr� l?influence du seuil de tol�rance dans les graphiques. En effet, le comportement de CIGA+ face au param�tre mintol d�pend fortement des donn�es qui sont utilis�es. Pour des donn�es denses, l?�lagage a tendance � �tre plus important au fur et � mesure que ce seuil diminue.

Nous avons pr�sent� un algorithme appel� CIGA+ qui permet de calculer un ensemble concis de MFF en se focalisant sur ceux qui sont les plus prometteurs. CIGA+ r�duit l?ensemble des MFF gr�ce � l?utilisation de deux nouveaux param�tres�: la confiance entre deux items �l�mentaires et le seuil de tol�rance. Le premier param�tre a pour but d?�carter les liens faibles entre deux items individuels. Le seuil de tol�rance mintol permet de simplifier le graphe de d�pendances en identifiant les paires d?items qui apparaissent souvent ensemble. Les ar�tes peu pertinentes du graphe de d�pendances sont ainsi �cart�es, ce qui am�liore le parcours du graphe et r�duit l?ensemble de MFF qu?il contient. Le param�trage de mintol d�pend du degr� d?approximation souhait�. Une valeur de 100 % permet d?obtenir l?ensemble complet de MFF tandis qu?une valeur faible conduit vers une forte approximation de cet ensemble. En exploitant ces deux param�tres, l?utilisateur est en mesure d?avoir le contr�le sur le temps d?ex�cution de l?algorithme ainsi que sur la taille du r�sultat et le nombre de r�gles d?association qu?il souhaite obtenir.

Notre prochaine �tape consistera � enrichir le cadre de CIGA+ en lui permettant de calculer les g�n�rateurs ainsi que les inclusions (ordre partiel) entre les MFF (Ganter et Wille, 1999) g�n�r�s afin d?exploiter nos travaux ant�rieurs sur la g�n�ration de r�gles d?associations et la construction du treillis de concepts. Le but �tant de faire de CIGA+ une proc�dure compl�te pour la g�n�ration des r�gles d?associations. Le cadre propos� pourra aussi �tre adapt� pour permettre une construction efficace du treillis de concepts et de l?iceberg de concepts (Stumme, Taouil et al., 2002).

Nous remercions Le Conseil de Recherches en Sciences Naturelles et en G�nie du Canada (CRSNG) et le Fonds Qu�b�cois de la Recherche sur la Nature et les Technologies (FQRNT) pour les subventions accord�es. Nous remercions �galement Professeur Jianyong Wang de nous avoir fourni l?ex�cutable de l?algorithme BAMBOO.