Utilisation des arbres de radicaux pour les algorithmes de Data ...
35
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
35
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Utilisation des arbres de radicaux pour les algorithmes de Data ...
Voir
Publié par
Langue
Français
Utilisation des arbres de radicaux pour les algorithmes de Data-Mining sur grille de calcul.
Stage de DEA en Informatique Parallèle Répartie et Combinatoire..
Gaël Le Mahec encadré par C. Cérin et M. Koskas
Laboratoire de recherche en informatique d'Amiens - Université de Picardie Jules Verne -
24 juillet 2004
Table des matières 1 Introduction 1.1 Grilles et bases de donn�es.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Extraction de Connaissances à partir de Donn�es. . . . . . . . . . . . . . . . . . . . 1.3 Règles associatives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Obtenir une règle d'association à partir d'un motif. . . . . . . . . . . . . . . 2 Analyse du problème. 2.1 Formalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Les principaux algorithmes de recherche d'itemsets fr�quents. . . . . . . . . . . . . 2.2.1 L'algorithme 'Apriori'. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 L'algorithme 'AprioriTID'. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 L'algorithme 'Count Distribution'. . . . . . . . . . . . . . . . . . . . . . . . 2.2.4 L'algorithme 'Data Distribution'. . . . . . . . . . . . . . . . . . . . . . . . 2.2.5 L'algorithme 'Eclat' . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.6 Synthèse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3Propri�t�sdesitemsets.................................. 2.4 Treillis d'itemsets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Itemsets ferm�s.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Résolution du problème. 3.1 Apriori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 L'algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 G�n�rationdes candidats dans Apriori . . . . . . . . . . . . . . . . . . . . . 3.1.3 Complexit�.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Eclat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Partitionnement en classes d'�quivalences. . . . . . . . . . . . . . . . . . . 3.3 L'algorithme 'Eclat' . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Phase d'initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 La phase de transformation. . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3 La phase asynchrone. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.4 La phase de r�ductionnale. . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.5 Complexit�.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Les arbres de radicaux. 4.1 Pr�sentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Op�rationssur les arbres de radicaux. . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Parallelisation des op�rationssur les arbres de radicaux. . . . . . . . . . . . . . . . . 4.4 Stockage sur disque à l'aide d'arbre de radicaux. . . . . . . . . . . . . . . . . . . . 5 Utilisation des arbres de radicaux pour la recherche des itemsets fréquents. 5.1 Insertion d'un item dans un arbre de radicaux. . . . . . . . . . . . . . . . . . . . . . 5.2 Insertion d'ensemble dans les arbres de radicaux. . . . . . . . . . . . . . . . . . . . 5.2.1 Produit d'ensembles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Treillis d'itemsets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
4 4 5 5 6 7 7 7 7 8 8 8 8 8 9 9 9 10 10 10 11 12 12 12 13 13 13 14 15 15 15 15 15 16 18 20 20 20 21 21 22
6
5.3.1Compositionsansr�p�titiondes�l�mentsd'unensemble.. 5.3.2 Élagage d'arbre de radicaux . . . . . . . . . . . . . . . . 5.4 G�n�rationde candidats. . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Construction du treillis des itemsets. . . . . . . . . . . . . 5.5 Transformation verticale de la base. . . . . . . . . . . . . . . . . 5.6 Construction du treillis des itemsets fr�quents. . . . . . . . . . . . 5.7 Recherche des itemsets fr�quents. . . . . . . . . . . . . . . . . . 5.8 Recherche parallèle des itemsets fr�quents. . . . . . . . . . . . . 5.9 L'algorithme parallèle de recherche des itemsets fr�quents. . . . .
Conclusion.
2
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
22 23 24 24 25 25 26 27 27
29
