2.2.3 Les algorithmes hybrides
Dans cette section, nous allons nous interesser aux
algorithmes adoptant la strategie hybride. Ces algorithmes ne font qu'enumerer
les itemsets fermes frequents [69]. Cette strategie evite le goulot
d'etranglement de la première strategie, a savoir la generation d'un
nombre eleve de candidats, et ceci en ne generant qu'un seul candidat a la
fois. En plus, cette strategie explore l'espace de recherche en profondeur
d'abord tel que les algorithmes bases sur la strategie
"Diviser-et-générer". Cependant, les algorithmes hybrides ne
divisent pas le contexte d'extraction en sous-contextes, evitant ainsi une
saturation de la memoire.
Dans la litterature actuelle, nous trouvons essentiellement un
seul algorithme implementant cette strategie, a savoir l'algorithme CHARM [69].
Des ameliorations de cet algorithme, tels que LCM [60, 61, 62] et DCI-CLOSED
[43, 44], ont ete aussi proposees.
L'algorithme CHARM a ete propose par Zaki et al. [69]. Il a
plusieurs caracteristiques, qui le distinguent des algorithmes adoptant les
deux premières strategies. En effet, contrairement a ces algorithmes qui
n'exploitent que l'espace des itemsets (fermes), CHARM explore simultanement
l'espace des itemsets fermes ainsi que celui des transactions. Pour cela, il
utilise une structure d'arbre particulière appelee IT-Tree
(Itemset-Tidset Tree) introduite dans [69]. Dans cette structure, chaque nceud
est forme par un couple compose par un itemset ferme frequent candidat ainsi
que l'ensemble des transactions auxquelles il appartient (cad son extension ou
tidset [69]).
CHARM determine tous les itemsets fermes frequents en
parcourant l'arbre IT-Tree a partir de la racine de gauche a droite et en
profondeur d'abord, en considerant un par un les 1-itemsets frequents tries par
ordre lexicographique. Le parcours en profondeur d'abord rappelle la strategie
"Diviser-et-générer".
L'algorithme CHARM opere de la maniere suivante : pour chaque
deux candidats item-sets fermes frequents A et B avant les
mimes nceuds parents, CHARM teste s'ils sont ou non des fermes et ceci en
comparant leurs tidsets. Pour cela, il distingue quatre cas [69] :
1. Si ø(A) =
ø(B) alors ã(A) =
ã(B) = ã(AUB). Ainsi, ni
A, ni B ne sont des itemsets fermes frequents. Alors, CHARM
remplace toutes les occurrences de A dans l'arbre IT-Tree par
(A U B) et elimine B de l'arbre.
2. Si ø(A) C
ø(B) alors ã(A)
ã(B) et ã(A)=
ã(A U B). Alors, l'itemset A ne peut etre un
itemset ferme frequent. Dans ce cas, toutes les occurrences de A dans
l'arbre IT-Tree sont remplacees par (A UB). B n'est pas
supprime de l'arbre IT-Tree car il peut etre un generateur d'un autre itemset
ferme frequent.
3. Si ø(A) D
ø(B) alors ã(A)
ã(B) et ã(B)=
ã(A U B). Alors, l'itemset B ne
peut etre un
itemset ferme frequent. Dans un tel cas, B est elimine de l'arbre
IT-Tree et (A U B) est ajoute comme descendant de A.
Ce dernier n'est pas supprime de l'arbre IT-Tree puisqu'il peut etre un
generateur d'un autre itemset ferme frequent.
4. Si ø(A)
ø(B) alors ã(A)
ã(B) ã(A U B). Ici, l'algorithme
CHARM ajoute
(A U B) comme descendant de A si et seulement
si (A U B) est frequent ; sinon l'arbre IT-Tree reste inchange (cad
dans le cas oft (A U B) est un itemset infrequent).
Dans les quatre cas mentionnes ci-dessus, la comparaison entre
ø(A) et ø(B) se fait en
effectuant l'intersection de ø(A) et
ø(B). La generation de (A U B) a partir de
A et B nous rappelle la phase combinatoire d'APRiORi-GEN [2].
Cependant, le resultat est toujours un candidat unique.
CHARM genere un candidat et calcule son support dans la
même etape. Si un candidat A ne peut plus etre etendu, CHARM ne
l'ajoute dans la liste des itemsets fermes frequents retenus que s'il n'est pas
couvert par un autre itemset ferme frequent appartenant a cette liste. Si
A est couvert alors il ne represente pas un itemset ferme. Notons que, ce
même test est effectue par CLOSET avant de developper un contexte
d'extraction conditionnel. Pour accelerer ce test de couverture, CHARM utilise
une table de hachage pour stocker les itemsets fermes frequents retenus [69].
Dans le cas oft A ne peut plus etre etendu, CHARM libere le lien qui
lie le nceud representant A et le nceud parent, car ce lien ne sert
plus a rien.
CHARM est ameliore par l'utilisation d'une representation de
donnees appelee Diffset [68] permettant un stockage incremental des
tidsets [9]. Dans cette structure, CHARM ne fait qu'enregistrer, pour chaque
candidat itemset ferme frequent, la difference qui existe
entre son intention et l'intention de son parent immediat.
Diffset permet d'accelerer le calcul des quatre cas mentionnes plus haut, etant
donne que l'intersection des transactions, resultat de la difference entre
ø(A) et ø(P) d'une part et
entre ø(B) et ø(P) d'autre
part (tel que P est le parent immediat de A et B),
est nettement plus rapide que l'intersection de ø(A)
et ø(B) [69]. Un autre avantage de Diffset est qu'il
permet aussi de reduire la memoire necessaire pour stocker les informations
relatives aux candidats contenus dans l'arbre IT-Tree [69] et ceci en reduisant
le stockage redondant des tidsets.
En revanche, l'inconvenient majeur de l'algorithme CHARM
reside dans le fait qu'il est exigeant en espace memoire. En effet, le fait de
stocker les itemsets et leurs tidsets ne fait qu'accroitre la quantite d'espace
memoire utilisee [9].
Enfin, signalons que l'algorithme CHARM necessite un seul
acces au contexte d'extraction pour determiner les listes des transactions
auxquelles appartiennent les items frequents du contexte en question.
| 