II.3 Les algorithmes d'extraction des règles
d'association
Dans cette section, nous essayons de présenter
quelques algorithmes d'extraction de règles association les plus
utilisés. Ils sont classés selon [Hip et al., 2000]:
· la stratégie de parcours de l'espace de
recherche ;
· la stratégie de calcul des supports des
Itemsets.
AIS [Agrawal et al., 1993],[Agrawal et
Srikant., 1994]
Cet algorithme fut le premier proposé pour
l'extraction de règles d'association. Il extrait des règles
d'association dont la tête est formée par un seul Item. Une
règle est alors de la forme X?Y avec Y un
élément de Items. Pour cela, la base de données est
parcourue plusieurs fois afin de dégager les Itemsets fréquents.
Le kème parcours est réalisé pour extraire les
Itemsets de cardinalité k qu'on appellera dorénavant k-Itemsets.
Pendant le premier parcours, c'est l'extraction des 1-Itemsets fréquents
(F1) qui se fait. Pour extraire les 2-Itemsets fréquents (F2),
l'algorithme parcourt la base de données pour tester les supports des
2-Itemsets appartenant à l'ensemble des 2-Itemsets candidats noté
C2. C2 est généré à partir de F1, ensemble des
1-Itemsets fréquents. Les 2-Itemsets candidats sont
générés en étendant les 1-Itemsets fréquents
par un Item de la même transaction. Pour généraliser, cet
algorithme parcourt deux fois la base de données pour
générer les k-Itemsets fréquents :
- la première fois sert à
générer les k-Itemsets candidats ;
- la deuxième fois sert à calculer le
support de chaque candidat, le candidat ayant un support supérieur au
seuil minimum est inséré dans l'ensemble Fk, sinon il est
rejeté.
Chapitre II : L'extraction de règles d'association -
38 -
L'inconvénient de l'algorithme AIS est le fait
qu'il scanne la base de données plusieurs fois et qu'il
génère trop de candidats.
Algorithme : AIS Début
Input : L1 = { large 1-Itemsets
}
C1= data base D
min_sup min_conf
Output : association rules R
L1 = { large 1-Itemsets }
for ( k=2 ;
Lk-1 ? Ø ; k++)
faire
ct=Ø
Forall transaction t E D
do begin
Lt=subset(Lk-1 , t)
forall large itemsets lt
E Lt do begin
if ( c E Ck ) then
add 1 to the count of c inthe corresponding entry in
Ck
else
add 1 to Ck with a count of
1
end
end
Lk={c E Ck / c.support =
min_sup}
end
L = Uk Lk ;
R=Generate_Rules(L) Fin
FP-Growth [Han et al., 2000]
C'est un algorithme qui réalise la tâche
après deux parcours de la base de données en s'appuyant sur une
structure d'arbre.
Le processus d'extraction de patterns se déroule
en deux grandes étapes :
(1) la construction de l'arbre appelée FP-Tree
(une représentation condensée de la base de données)
;
(2) la génération des patterns
fréquents à partir de cette structure, l'arbre FP-Tree. La racine
de l'arbre ne porte aucune information (`null'), alors qu'un noeud autre que la
racine porte deux informations, l'Item qu'il représente et son support.
Un index est associé à l'arbre FP-Tree, et il contient tous les
Items fréquents. A chaque Item est associé un pointeur vers le
premier noeud de l'arbre qui le contient.
Chapitre II : L'extraction de règles d'association -
39 -
La première étape qui consiste à
construire l'arbre FP-Tree, se déroule comme suit :
(a) la base de données est parcourue pour
calculer le support des Items. Les Items fréquents sont
générés dans un ensemble qu'on notera F1 ;
(b) la base de données est parcourue une
deuxième fois, et chaque transaction (ensemble d'Items) est triée
selon le support des Items de manière décroissante. Chaque
transaction t est représentée par sa tête p (l'Item le plus
fréquent dans ce panier) et par la queue Q (ensemble trié des
Items moins fréquents que p). Pendant le même parcours, pour
chaque transaction, une fonction Insert(p,Q,T) procède ainsi : Si la
racine T a un noeud fils N tel que N.Item=t.p alors son support est
incrémenté, sinon un noeud fils N est créé avec un
support égal à 1. Ensuite, on affecte récursivement
à p le premier Item de Q, et à Q le reste des Items, on
vérifie s'il existe un noeud N' fils de N tel que N'.Item=t.p, si oui on
incrémente son support, sinon on créé un nouveau noeud N'
(fils de N) avec un support égal à 1. Cette fonction est
exécutée récursivement jusqu'à ce que Q soit
vide.
Il faut noter que l'objectif de tri des Items (dans
l'ordre décroissant de leur fréquence) est de réduire la
taille de l'arbre, ainsi les Items les plus fréquents seraient
partagés par les transactions.
Algorithme : FP-Growth Début
Entrée : L'arbre FP-Tree noté T
Seuil minimum de support min_s
Sortie : Ensemble des Itemsets Fréquents :
F(D,min_s)
FP-Growth (T, á)
Si T contient un seul chemin Alors
Pour chaque combinaison f3 des noeuds du chemin
faire
Générer le pattern f3 U á avec
support=support minimum des noeuds dans f3
FinPour
Sinon
Pour chaque ai de l'index de T faire
Générer le pattern f3 = ai U á avec
support = ai.support
Construire le pattern de base de f3
Construire le FP-Tree conditionnel de f3 et l'affecter
à T
FinPour
Si T ? Ø Alors FP-Growth (T,f3)
Fin
Chapitre II : L'extraction de règles d'association -
40 -
Apriori [Agrawal et Srikant., 1994]
Cet algorithme fut une évolution dans
l'histoire de l'extraction des règles d'association. Il fonctionne selon
le principe suivant :
(1) générer les Itemsets ;
(2) calculer les fréquences des Itemsets
générés;
(3) garder les Itemsets qui ont un support minimum i.e.
les Itemsets fréquents ;
(4) générer et ne garder que les
règles avec une confiance minimale.
Apriori est plus efficient que AIS au niveau de la
génération des Itemsets candidats, du moment où il
élague encore plus l'espace de recherche. Le dégagement des
Itemsets fréquents se fait sur deux étapes : tout d'abord, les
Itemsets candidats sont générés, ensuite la base de
données est parcourue pour calculer les supports des candidats, et
accepter les candidats dont le support est supérieur au seuil minimum
comme étant des Itemsets fréquents. L'apport d'Apriori
réside dans la génération des candidats. En effet, un
k-Itemset candidat n'est généré que si tous ses
sous-ensembles de cardinal k-1 sont fréquents. Cependant, Apriori
«s'étouffe» sans aucun doute sur deux phases : la
génération des candidats qui est un processus complexe, et le
calcul des supports des Itemsets candidats qui nécessite plusieurs
parcours de la base de données.
Algorithme : Apriori Début
Entrée : Base de données D
Seuil minimum de support min_s Seuil minimum de confiance
min_c
Sortie : Ensemble des règles d'association
R
F1 = 1-Itemsets fréquents;
Pour ( k=2; Fk-1?Ø; k++ )
faire
Ck =Apriori_gen(Fk-1);
Pour ( chaque transaction t de D ) faire
Pour ( chaque candidat c de Ck ) faire Si ( c est inclus
dans t ) alors c.support++ ;
Finsi
Finpour
Finpour
Fk={c?Ck / c.support = min_s}
;
Finpour
F = Uk Fk ;
R=Generer_Regles(F) ;
Fin
Chapitre II : L'extraction de règles d'association -
41 -
Discussion
Nous avons consulté des articles dont l'objet
est l'étude comparative des algorithmes d'extraction de motifs
fréquents [Goethals et Van den Bussche, 2002], [Zaki et al., 1997], [Hip
et al., 2000]. Il est dit que l'application de ces algorithmes sur une
même base de données avec les mêmes seuils de support et de
confiance, donne globalement les mêmes résultats (les mêmes
règles d'association). Ceci est dû au fait que les algorithmes
d'extraction de règles d'association sont tous plus ou moins proche l'un
de l'autre. Il en découle que la comparaison concerne seulement les
performances des algorithmes et non la qualité des
résultats.
Nous avons constaté que ces études sont
subjectives car les conclusions tirées ne sont pas les mêmes.
Cette subjectivité est due au fait que le même algorithme peut
être implémenté de plusieurs manières
différentes d'où la différence de point de vue performance
et efficience.
Ceci dit, nous présentons ici quelques
conclusions se rapportant à Apriori communément tirées par
les études que nous avons consultées, ceci du fait que cet
algorithme est communément jugé plus ou moins efficace par
rapport aux autres :
· Apriori parcourt la base de données k
fois, k étant le cardinal du plus long Itemset fréquent. Ceci
entraîne beaucoup d'opérations d'entrée/sortie qui sont
coûteuses. Il faut noter aussi que dans le cas de bases de données
volumineuses, Apriori met du temps pour générer les Itemsets
fréquents. En effet dans ce type de base de données, le nombre
d'Itemsets fréquents est très grand, ce qui augmente le
coût de la génération des Itemsets candidats et du calcul
de leurs supports. En général, lorsque le nombre d'Itemsets
fréquents est grand, le coût d'extraction est élevé.
Le nombre d'Itemsets fréquents dépend du seuil minimum de support
(plus le seuil est petit, plus le nombre d'Itemset fréquent est grand)
et du volume de la base de données ;
· Apriori est l'algorithme le plus
approprié à l'exploration des bases de données. Sa
puissance réside dans son élagage, plus le minimum support est
petit plus l'élagage est faible.
Chapitre II : L'extraction de règles d'association -
42 -
| 
