2.2.1.3 L'algorithme TITANIC
L'algorithme TITANIC a été proposé par
Stumme et al. [55, 57], pour la découverte des itemsets fermés
fréquents. L'idée clé est de minimiser le coUt du calcul
des fermetures en adoptant un mécanisme de comptage par inférence
[6]. Ainsi, l'algorithme traverse
l'espace de recherche par niveau en focalisant sur la
determination des generateurs minimaux (ou itemsets cles [55, 57]) frequents
des differentes classes d'equivalence induites par l'operateur de fermeture
ã.
Une des particularites de TITANIC est qu'il considere,
contrairement a CLOSE et A-CLOSE, l'ensemble vide (0) comme etant un generateur
minimal. Pour calculer la fermeture de l'ensemble vide, TITANIC collecte les
items de meme support que cet ensemble, cad qui se repetent dans toutes les
transactions. Ainsi, l'ensemble vide est le generateur minimal de support egal
au nombre de transactions du contexte d'extraction (cad 101).
En plus, TITANIC evite le balayage supplementaire (des generateurs
minimaux frequents retenus de taille (k-1)) effectue dans A-CLOSE pour
chaque candidat g de taille k. En effet, TITANIC utilise une
variable dans laquelle il stocke le support estime de g. Ce dernier
est egal au minimum des supports des (k-1)-generateurs minimaux
frequents inclus dans g et il doit etre different du support reel
de g sinon g n'est pas minimal [55, 57].
De meme que CLOSE et A-CLOSE, TITANIC parcourt l'espace de
recherche par niveau. Il initialise l'ensemble des 1-generateurs minimaux par
les 1-itemsets du contexte d'extraction, tries par ordre lexicographique.
TITANIC calcule alors le support de ces itemsets et determine ensuite la
fermeture de l'ensemble vide. Les items infrequents ou ayant le meme support
que l'ensemble vide ne sont pas des generateurs minimaux frequents. Ensuite, a
chaque iteration k, TITANIC genere un ensemble de candidats moyennant
l'utilisation de la phase combinatoire d'APRIORI-GEN [2]. De cet ensemble, sont
elimines les candidats ne verifiant pas l'ideal d'ordre des generateurs
minimaux frequents. Un acces au contexte d'extraction permet de calculer le
support des candidats non elagues. De ces candidats, sont elimines les
generateurs infrequents ou ayant des supports reels egaux a leurs supports
estimes. Une fois les k-generateurs minimaux frequents determines,
TITANIC calcule la fermeture des generateurs minimaux frequents retenus lors de
l'iteration precedente (cad de taille (k-1)). Neanmoins, TITANIC evite
l'acces au contexte d'extraction pour calculer les fermetures et ceci en
adoptant un mecanisme de comptage par inference [6]. Ainsi, pour chaque
(k-1)-generateur minimal frequent g, TITANIC fait appel a la
fonction CLOSURE [55, 57]. Cette derniere se deroule de la maniere suivante
[55, 57] :
1. Pour alleger les calculs, la fermeture de g,
ã(g), serait egale a l'union des fermetures de ses
sous-ensembles de taille (k - 2), calculees lors de l'iteration
precedente.
2. Ensuite, pour tout item frequent i n'appartenant pas
a ã(g) a ce moment du traitement, i est
ajoute a ã(g) si Supp(g U {i}) =
Supp(g). Deux cas sont a distinguer :
(a) Si g ? {i} est un candidat generateur
minimal, le support de g ? {i} est directement determine.
(b) Si g ? {i} n'est pas un candidat
generateur minimal, TITANIC utilise un mecanisme de comptage par inference [6]
permettant de trouver le support de g ? {i} sans acceder au
contexte d'extraction. Ce mecanisme est fonde sur le fait que le support d'un
itemset non generateur minimal peut etre calcule en utilisant l'ensemble des
generateurs minimaux frequents GMFK et la bordure negative des
generateurs minimaux notee GBd- [39]. Cette
dernière est formee par l'ensemble des generateurs minimaux infrequents
dont tous leurs sous-ensembles sont des generateurs minimaux
frequents. TITANIC utilise alors la proposition suivante :
Proposition 2 [55, 571 Soit GMK l'ensemble des
generateurs minimaux ex-traits du contexte K. Si X est un
itemset non generateur minimal alors SuPP(X) > min
{SuPP(g) | g ? GMK et g ? X}.
Pour pouvoir utiliser cette proposition et etant donne que
X peut etre un itemset non frequent, TITANIC est amene a gerer le stockage
de l'ensemble GBd-. En effet, si TITANIC se
contente seulement des generateurs minimaux frequents pour calculer le support
de X, ce support serait egal au minimum des supports des generateurs
minimaux frequents contenus dans X. Ceci contredit le fait que
X pourrait etre infrequent. Ainsi, l'affirmation de Stumme et al. dans
[57] de pouvoir supprimer les generateurs minimaux infrequents est erronee.
L'execution de l'algorithme TITANIC prend fin quand il n'y plus
de candidats a generer.
TITANIC utilise la même structure de donnees (cad un
trie) que les algorithmes CLOSE et A-CLOSE. Il necessite au pire des cas
|I| accès au contexte d'extraction (|I| etant la taille
maximale possible d'un candidat generateur minimal).
2.2.2 Les algorithmes de type
!!Diviser-et-générer!!
Dans cette section, nous allons nous interesser aux
algorithmes les plus connus operant selon la strategie "Diviser-et-generer"
[34]. Ces algorithmes ne font qu'enumerer les item-sets fermes frequents [51].
Cette strategie, "Diviser-et-generer", est consideree comme une solution au
principal handicap des algorithmes de type "Generer-et-tester", a savoir la
generation d'un grand nombre de candidats. Malgre l'existence de plusieurs
algorithmes
opérant selon cette stratégie tels que CLOSET+
[65] et FP-CLOSE [30], ces derniers ne sont que des améliorations ou des
variantes de l'algorithme CLOSET proposé par Pei et al. [51].
L'algorithme CLOSET utilise une structure de données
avancée, basée sur la notion de trie, appelée arbre
FP-Tree [34, 35]. La particularité de cette structure réside dans
le fait que plusieurs transactions partagent un même chemin, de
longueur n dans l'arbre FP-Tree, s'ils ont les n premiers
items en commun. L'algorithme CLOSET effectue le processus d'extraction des
itemsets fermés fréquents en deux étapes successives [9]
:
1. Construction de l'arbre FP-Tree : Les items des
transactions sont ordonnés par support décroissant après
avoir élagué les items infréquents. Ensuite, l'arbre
FP-Tree est construit comme suit. Premièrement, le nceud racine est
créé et est étiqueté par "root". Pour chaque
transaction du contexte, les items sont traités et une branche est
créée suivant le besoin. Dans chaque nceud de la structure
FP-Tree, il y a un compteur qui garde la trace du nombre de transactions
partageant ce nceud. Dans le cas oft une transaction présente un
préfixe commun avec une branche dans le FP-Tree, le compteur de chaque
nceud appartenant a ce préfixe est incrémenté et une
sous-branche va être créée contenant le reste des items de
la transaction.
2. Exploration de l'arbre FP-Tree : Au lieu d'une exploration
en largeur d'abord des itemsets fermés candidats, CLOSET effectue une
partition de l'espace de recherche pour effectuer ensuite une exploration en
profondeur d'abord. Ainsi, il commence par considérer les 1-itemsets
fréquents, triés par ordre croissant de leurs supports
respectifs, et examine seulement leurs sous-contextes conditionnels (ou FP-Tree
conditionnels) [9]. Un sous-contexte conditionnel ne contient que les items qui
co-occurrent avec le 1-itemset en question. Le FP-Tree conditionnel
associé est construit et le processus se poursuit d'une manière
recursive.
Pour faciliter le parcours d'un FP-Tree, une table d'entete
lui est associée. Cette table contient la liste des items contenus dans
ce FP-Tree, triés par ordre décroissant de leurs supports
respectifs. Pour chaque item, son support est stocké ainsi qu'un lien
vers le premier nceud qui le contient. Des liens inter-nceuds permettent de
lier tous les nceuds contenant un même item dans le FP-Tree [34, 35].
concatenation des 1-itemsets qui sont aussi frequents que
p (dans le sous-contexte conditionnel).
P2 : Il n'y a nul besoin de developper un sous-contexte
conditionnel d'un itemset p qui est inclus dans un itemset ferme
frequent dejà decouvert c, tel que
Supp(p)=Supp(c). Dans ce cas, p est dit couvert
par c.
Pour calculer les fermetures, CLOSET traite les items
frequents un par un en commencant par le moins frequent. Pour chaque item
i, il construit son FP-Tree conditionnel. Un FP-Tree conditionnel relatif
à un item i contient l'ensemble des transactions on se trouve
i. Dans ce FP-Tree, i est exclu ainsi que les items
dejà traites, puisque tous les itemsets fermes frequents contenant ces
items traites ont ete dejà determines. Le FP-Tree conditionnel ne
contient alors que les items non traites et dont le support est superieur ou
egal à minsup. Cette condition est imposee pour ne generer que des
itemsets fermes qui sont frequents. La fermeture de i est egale
à sa concatenation avec les items de même support (d'apres P1). Le
même traitement est realise pour tout itemset forme par la concatenation
de i avec un item, dont le support dans le FP-Tree conditionnel est
different de celui de i. Ainsi, d'une maniere recursive et en operant
en profondeur d'abord, CLOSET determine tous les itemsets fermes frequents.
Pour reduire le cont du processus d'extraction, CLOSET ne developpe le FP-Tree
conditionnel d'un itemset p qu'apres avoir verifie que p
n'est pas couvert par un itemset ferme frequent c dejà
decouvert (d'apres P2) car sinon la fermeture de p est dejà
extraite.
Il est important de noter que CLOSET est gourmand en espace
memoire [9]. En effet, les appels recursifs necessitent de maintenir un nombre
generalement eleve de FP-Trees en memoire centrale. De plus, CLOSET necessite
de maintenir en memoire centrale les itemsets fermes frequents dejà
trouves et ceci afin d'accelerer le test associe à la propriete P2. Les
auteurs de CLOSET [51] affirment que leur algorithme ne genere pas de candidats
contrairement aux algorithmes de la premiere strategie. Cependant, pour des
supports bas et dans le cas de contextes epars, chaque generateur frequent est
un ferme. Ainsi, les deux proprietes sur lesquelles se base CLOSET ne donnent
plus l'effet escompte. D'on, l'itemset ferme frequent, extrait à partir
du sous-contexte conditionnel d'un itemset X, est egal à
X et n'est couvert par aucun itemset ferme frequent dejà trouve. De
ce fait, CLOSET construit recursivement un FP-tree conditionnel pour tout
itemset frequent (qui est lui même son propre ferme). Ceci rend eleve le
nombre de FP-trees presents en même temps en memoire centrale.
En plus du cont non negligeable de l'etape du tri du contexte
d'extraction, la structure
FP-Tree proposee est malheureusement non adaptee pour un
processus de fouille interactif, dans lequel l'utilisateur peut etre amene a
varier la valeur du support [9]. Dans ce cas, la structure doit etre
entièrement reconstruite [9]. Les travaux presentes dans [8, 19]
permettent de pallier cette insuffisance.
Notons que, l'algorithme CLOSET necessite deux accès au
contexte d'extraction : un premier accès pour extraire la liste des
1-itemsets frequents et un deuxième pour construire l'arbre FP-Tree.
| 