4.6.2 Bases !!pire des cas!!
Pour toutes ces experimentation, la valeur de minsup est fixee
a 1. Nous avons teste 26 bases "pire des cas" representant la variation de la
valeur de n de 1 a 26. Etant donne que ces bases representent le pire
des cas, tout itemset candidat est un generateur minimal
Temps d'execution (en seconde)
Temps d'execution (en seconde)
T40I10D100K
262144
65536
16384
4096
1024
256
64
16
4
1
Prince
Close A-Close Titanic
T10I4D100K
Prince Close A-Close Titanic
2048
1024
512
256
128
64
32
16
8
4
2
0.55 0.45 0.35 0.25
0.15 0.05 9.5 8.5 7.5 6.5 5.5 4.5 3.5 2.5 1.5
m insup (en %)
0.5
m insup (en %)
Temps d'execution (en seconde)
262144
65536
16384
4096
1024
256
64
16
0.1
0.08
0.06
Retail
Prince Close A-Close Titanic
0.04
0.02
0
Temps d'execution (en seconde)
262144
65536
16384
4096
1024
256
64
16
4
90
80
70
Accidents
60
Prince
Close A-Close Titanic
50
40
30
m insup (en %) m insup (en %)
FIG . 4.12 -- Les performances de PRINCE vs. CLOSE, A-CLOSE et
TITANIC pour les bases éparses
fréquent et est égal a sa fermeture.
Les temps d'exécution des quatre algorithmes ne
commencent a être distinguables qu'à partir d'une valeur de
n égale a 15. Pour les bases "pire des cas", les performances de
PRINCE restent meilleures que celles de CLOSE, A-CLOSE et TITANIC. Chaque
générateur minimal fréquent est aussi un fermé.
Ainsi, PRINCE n'exécute pas sa deuxieme étape, le treillis des
générateurs minimaux étant construit des la fin de sa
premiere étape. De son coté, A-CLOSE ne calcule pas les
fermetures. D'oft, ses performances sont meilleures que celles de CLOSE et
celles de TITANIC. Notons que dans ce type de bases, chaque candidat est un
générateur minimal fréquent. Ainsi, pour chaque
itemset g de taille k (qui est un générateur
minimal fréquent), A-CLOSE et TITANIC effectuent un balayage des
sous-ensembles de g de taille (k-1). Dans le cas de A-CLOSE,
ce balayage permet de vérifier que le candidat g a un support
différent de celui de ces sous-ensembles en question pour le qualifier
de générateur minimal fréquent. Dans le cas de TITANIC, ce
balayage permet d'optimiser le calcul de la fermeture de g en
collectant les items appartenant aux fermetures des sous-ensembles en question.
De plus, TITANIC essaie l'étendre l'itemset résultat de ce
balayage par les items adéquats. De son coté, CLOSE est aussi
contraint a calculer la fermeture de tout itemset fréquent, ce dernier
étant un générateur minimal
frequent. Il est important de noter que les calculs de
fermetures effectues par CLOSE et TITANIC s'avereront sans utilite car tout
generateur minimal est egal a sa fermeture. L'execution de ces deux algorithmes
n'ont pu se terminer pour une valeur de n egale a 24, en raison du
manque d'espace memoire. Pour la meme raison, l'execution de A-CLOSE n'a pu se
terminer pour une valeur de n egale a 25. L'execution de notre
algorithme prend aussi fin, pour n26. La figure 4.13 et le tableau 4.9
donnent le comportement des algorithmes suivant la variation de la valeur
de n. Dans le tableau 4.9, les trois dernieres colonnes indiquent le
facteur multiplicatif des temps d'execution de CLOSE, A-CLOSE et TITANIC par
rapport a l'algorithme PRINCE. "/" signifie que l'execution n'a pas pu arriver
a terme et que le ratio correspondant ne peut etre calcule.
Ce test de mise a l'echelle montre aussi l'interêt de
l'utilisation d'un seul trie pour stocker les informations relatives a tous les
generateurs minimaux (cas de PRINCE) comparee a l'utilisation de plusieurs
tries dans le cas des trois autres algorithmes. En effet, pour CLOSE, A-CLOSE
et TITANIC, un trie est utilise pour stocker les informations relatives a
chaque ensemble de generateurs minimaux d'une taille k donnee. Ceci
rend eleve le nombre d'informations redondantes stockees dans ces tries et
augmente ainsi l'espace memoire necessaire.
L'algorithme PRINCE reste meilleur que les algorithmes CLOSE,
A-CLOSE et TITANIC sur les bases "pire des cas". La difference entre les
performances de PRINCE et celles de CLOSE (resp. A-CLOSE et TITANIC) est
maximale pour n21 (resp. 19 et 23). En effet, pour ces valeurs de
n, PRINCE est environ 29 (resp. 4 et 10) fois plus rapide que CLOSE (resp.
A-CLOSE et TITANIC). Pour ces bases "pire des cas", PRINCE est en moyenne 16
(resp. 3 et 4) fois plus rapide que CLOSE (resp. A-CLOSE et TITANIC).
Temps d'execution (en seconde)
65536
16384
4096
1024
256
64
16
4
1
Prince
Close A-Close Titanic
15 16 17 18 19 20 21 22 23 24 25
n
| 