Utilisation des arbres de radicaux pour les algorithmes de Data ...

Sujets

• Sciences et techniques

Informations

• Publié par: igobygar
• Nombre de lectures: 85
• Langue: Français

Extrait

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