Extraction des règles d'association FP-Growth

Règles d’associationArticle 1: Mining Frequent Patterns without candidat

generation

Article 2: Bitmap Based Algorithms For MiningAssociation

Présenté par Bilel IDIRI

1

Présentateur

Commentaires de présentation

Je vais vous présenter aujourd’hui deux articles qui traitent de la même thématique qui est l’« optimisation de l’extraction des règles d’association» mais s’attaquant à des problématiques différentes. Au cours de ma présentation je vais essayer de situer les deux articles dans le processus global d’extraction des règles d’associations.

INTRODUCTION (1)C’est quoi une règle d’association ?

La recherche d’association vise à construire un modèle basé sur des règles conditionnelles « si Conditions alors Résultats » [21]

« Trouver une relation entre des sous ensembles de données »

Exemple (magasin):Mettre en évidence les produits achetés ensemble Transcrire la connaissance sous forme de règle d’association

Si antécédent Alors conséquent 2

Présentateur


Je vais commencer par donner une définition qui m’a plu (c’est celle de René Lefébure édition eyrolles) [21] : René Lefébure et Gilles Venturi, Le Data Mining Edition Eyrolles 1998

Processus d’extraction des règles d’associations :

Recherche des itemsets fréquents (sup > supmin)Support: un indicateur de fiabilité de la règle

Produire des règles à partir des itemsets fréquentsConfiance: un indicateur de précision de la règle

INTRODUCTION (2)

3

Règle « Bonne » = règle avec un bon support et une bonne confiance

Présentateur


Le processus d’extraction des règles d’association est composé de deux étapes :

INTRODUCTION (2)

4

Processus d’extraction des règles d’associations :

Recherche des itemsets fréquents (sup > supmin)Support: un indicateur de fiabilité de la règle

Produire des règles à partir des itemsets fréquentsConfiance: un indicateur de précision de la règle

4

Plusieurs méthodes d’extraction ont été proposées (Apriori, TreeProjection)

mais la plus part ne sont pas optimales

Présentateur


Dans ces deux parties il y a la partie génération des itemsets qui consomme énormément de temps et d’espace (parcourir plusieurs fois la BD, générer un ensemble d’itemsets plus grand que la taille de la BD)

GÉNÉRATION DES ITEMSETS

5

Item CountBread 4Coke 2Milk 4Beer 3Diaper 4Eggs 1

Itemset Count{Bread,Milk} 3{Bread,Beer} 2{Bread,Diaper} 3{Milk,Beer} 2{Milk,Diaper} 3{Beer,Diaper} 3

I te m s e t C o u n t {B re a d ,M ilk ,D ia p e r} 3

Items (1-itemsets)

Triplets (3-itemsets)

Minimum Support = 3

Pairs (2-itemsets)

INTRODUCTION (3)TID Items

1 Bread, Milk

2 Bread, Diaper, Beer, Eggs

3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer

5 Bread, Milk, Diaper, Coke

Base de données

Présentateur


Voici un exemple nous permettons de suivre le processus d’extraction des règles d’associations …..

Etant donné L l’ensemble des itemsetfréquent, il faut trouver tous les ensemble fnon vide tel que f ⊂ L et f → L – f satisfit laconfiance minimum.

si {A,B,C,D} est l’ensemble des itemsets fréquent, les règles générer peuvent être:

ABC →D, ABD →C, ACD →B, BCD →A, A →BCD, B →ACD, C →ABD, D →ABCAB →CD, AC → BD, AD → BC, BC →AD, BD →AC, CD →AB,

6

GÉNÉRATION DES RÈGLESINTRODUCTION (3)

PLAN1

IntroductionProblématique ContributionContexte Résultats Références

7

Présentateur


La présentation suivra le plan suivant

Article 1:Mining Frequent Patterns without candidat generation(Jiawei Han, Jian Pei, and Yiwen Yin, 2000)

8

Source International Conference on Management of Data Actes de la conférence internationale ACM SIGMOD 2000 (Volume 29 , Issue 2 June 2000 ) sur la gestion des donnéesDallas, Texas, United States Pages: 1 - 12Année de publication: 2000Cité 411 fois

AuteursJiawei Han Professor, Univ. of Illinois at Urbana-Champaign USA,

Email: [email protected] Pei Ph.D School of Computing Science, Simon Fraser University

Canada, Email [email protected] Yin School of Computing Science, Simon Fraser University

Canada,

9

Présentateur


L’article est un article accepté à la conférence ACM SIGMOD qui est une prestigieuse conférence en bases de données

INTRODUCTION

La méthode FP-Tree couvre tout le processusd’extraction des règles d’association enproposant d’autres structures de stockage etde nouvelles méthodes de génération desrègles d’association.

10

Présentateur


Après examinassions de la solution Apriori l’auteur est convaincu que le goulot d’étranglement de la solution Apriori et la génération et le test des candidats - donc si quelqu’un pouvait rendre la génération des candidats nulle il améliorera considérablement les performance.

PROBLÉMATIQUE

Méthodes d’extraction de règles d’associationApriori (Agrawal, 93)TreeProjection (Ramesh C. Agarwal, Charu C. Aggarwaland V. V. V. Prasad, 1999)

coûteuses en temps et en espace.

AprioriBottleneck dans la génération des candidats dans Apriori-LikeNon scalable (pas de passage à l’échelle) Scaner la BD (n+1) fois, ou n est la taille du plus long Itemsets fréquent.Heuristique coûteuse quand l’ensemble des fréquents est prolifirique

TreeProjectionAlgorithme peu performant lui aussi 11

Présentateur


La méthode la plus utilisé avant 2000 pour la génération des itemset et la découverte de règle d’association pertinente est APRIORI-LIKE (Agrawal 93). Cette méthode était très couteuse en temps et en espace surtout pour une génération massive de candidats fréquent. Il avait aussi une méthode récente TreeProjection Ramesh C.Agarwal, Charu C.Aggarwal, V.V.V.Prasad IBM T.J.Watson Research Center,York town Heights,NY10598 (Décembre 99) qui est aussi peu performante. L’heuristique consiste à dire si un candidat n’est pas fréquent en (k) il ne le sera pas en (k+1)

CONTRIBUTIONS (1)Contexte

Utilisé pour les objets peu/très fréquentsNon supervisé pas de données d’apprentissage

ContributionsProposition d’une structure efficace d’accès au données fréquentes FP-Tree

Eviter de scanner la base plusieurs fois (parcourir la BD 2 fois)Les nœuds ayant plus de chance d’être partagés sont mis en premier

Utilisation du FP-tree pour l’accélération de la génération des règles d’associationScalabilité de l’approche proposéeLa taille des données générées est inferieure à la taille de la BD originale Transformer le pb de recherche des intemset en recherche de concaténation. 12

Présentateur


le problème a été réglé en attaquant plusieurs aspects. Parmi ces aspects on trouve:…. En effet le fait de sauvegarder les itemset fréquent dans une structure compacte annule le scan répété de la BD.

13

• Politique: Deviser pour conquérir • Construire une structure FP-tree• Exploitation récursive du FP-tree• Pour chaque item fréquent

– Construire les chemins préfixes dans le FP-tree– Fusionner les préfixes identiques et conserver les

sous-chemins de support >= minsup– Générer les ensembles fréquents par combinaison

des nœuds des chemins fréquents• Utiliser Apriori heuristic pour réduire le nombre de

candidats

CONTRIBUTION (2)DÉMARCHE

14

TID Items1 {A,B}2 {B,C,D}3 {A,C,D,E}4 {A,D,E}5 {A,B,C}6 {A,B,C,D}7 {B,C}8 {A,B,C}9 {A,B,D}10 {B,C,E}

Transaction Database Header table

B 8A 7C 7D 5E 3

1ère passe: determiner la table Header

CONTRIBUTION (3)CONSTRUCTION DE FP-TREE

Présentateur


Dans le construction de l’FP-Tree l’algorithme commence par créer une table Header qui trie les 1-itemset par ordre croissant de leur support. Représentation des items fréquents par un index spécial FP-tree (Frequent Pattern Tree) Construction du FP-tree Déterminer les produits fréquents (1-ens.) Trier par fréquence décroissante (table) Créer une racine vide Pour chaque transaction: ajout des chemins de produits ordonnés par fréquence fusion des sous-chemins communs mise à jour des compteurs de fréquence des produits Exploitation récursive du FP-tree Pour chaque item fréquent Construire les chemins préfixes dans le FP-tree conditional pattern base Fusionner les préfixes identiques et conserver les sous-chemins de support >= minsup conditional FP-tree Générer les ensembles fréquents par combinaison des nœuds des chemins fréquents


BD des transactions

Header tableB:1

A:1

null

B 8A 7C 7D 5E 3

A 1

C

D

E

B A C D

15


2ème passe: Construction de FP-Tree

Conditional pattern base

Présentateur


La conditional pattern base permet ….il donne en ligne les suffixes et en colonne les préfixes. B n’apparaît pas en ligne car il n’est le suffixe de aucun autre item et E n’apparaît pas en colonne car il n’ai le préfixe d’aucun item. On peut trouver tout les apparition d’un itemset en suivant le chemin relient les même itemsets avec la Header Table comme point d’accès. Chaque nœud contient trois champs Nom, La fréquence des transaction ayant ce préfixe Lien vers le nœud suivant Chaque transaction est mappé en un chemin, et un chemin peut représenter plusieurs transactions sans ambigüité La longueur maximale de l’FP-Tree est limité par la plus longue transaction Et ça taille est limité par l’apparition des itemset dans la BD

A 1

C 1

D 1 1

E

B A C D

B:2

A:1

null

C:1

D:1

16


BD des transactions

Header table

B 8A 7C 7D 5E 3


A 1

C 1 1

D 1 1 2

E 1 1 1

B A C D

B:2

A:1 C:1

D:1

null

A:1

C:1

D:1

E:1

17


BD des transactions

Header table

B 8A 7C 7D 5E 3


A 1

C 1 1

D 1 2 2

E 2 1 2

B A C D

B:2

A:1 C:1

D:1

null

A:2

C:1

D:1

E:1

D:1

E:1

18


BD des transactions

Header table

B 8A 7C 7D 5E 3


A 2

C 2 2

D 1 2 2

E 2 1 2

B A C D

B:3

A:2 C:1

D:1

null

A:2

C:1

D:1

E:1

D:1

E:1C:1

19


BD des transactions

Header table

B 8A 7C 7D 5E 3


A 3

C 3 3

D 2 3 3

E 2 1 2

B A C D

B:4

A:3 C:1

D:1

null

A:2

C:1

D:1

E:1

D:1

E:1C:2

D:1

20


BD des transactions

Header table

B 8A 7C 7D 5E 3


A 3

C 4 3

D 2 3 3

E 2 1 2

B A C D

B:5

A:3 C:2

D:1

null

A:2

C:1

D:1

E:1

D:1

E:1C:2

D:1

21


BD des transactions

Header table

B 8A 7C 7D 5E 3


A 4

C 5 4

D 2 3 3

E 2 1 2

B A C D

B:6

A:4 C:2

D:1

null

A:2

C:1

D:1

E:1

D:1

E:1C:3

D:1

22


BD des transactions

Header table

B 8A 7C 7D 5E 3


A 5

C 5 4

D 3 4 3

E 2 1 2

B A C D

B:7

A:5 C:2

D:1

null

A:2

C:1

D:1

E:1

D:1

E:1C:3

D:1

D:1

23


BD des transactions


A 5

C 6 4

D 3 4 3

E 1 2 2 2

B A C D

B:8

A:5 C:3

D:1

null

A:2

C:1

D:1

E:1

D:1

E:1C:3

D:1

D:1 E:1

24


BD des transactions


25

B:8

A:5

null

C:3

D:1

A:2

C:1

D:1

E:1

D:1

E:1C:3

D:1

D:1 E:1

Des chaines de pointeurs pour chaque élément de « Header Table» sont crées pour permettre un accès plus rapide.

Header table

B 8A 7C 7D 5E 3


26

Suffix E(New) Header table

B:8

C:3

null

A:2

C:1

D:1

E:1

D:1

E:1E:1

A 5

C 6 4

D 3 4 3

E 1 2 2 2

B A C D

C

D

A C

A 2C 2D 2

CONTRIBUTION (15)CONSTRUCTION DE FP-GROWTH

Présentateur


Maintenant on fixe les suffixes et on cherche le FP-tree conditionnel. La méthode FP-growth est développé pour construire des FP-tree conditionnels peuvent être chargé en mémoire. En remarque que la méthode est basé sur le partitionnement « diviser pour conquérir » Dans la nouvelle Conditional pattern base on remarque qu’on n’a écarté A des lignes car il n’a pas de préfixe et E des colonnes car il n’a pas de suffixe

null

FP-Tree conditionnelle B:8

C:3

null

A:2

C:1

D:1

E:1

D:1

E:1E:1

27

Suffix E (insérer BCE)


(New) Header table

C

D

A C

A 2C 2D 2

C:1

A:1

C:1

D:1

C 1

D 1 1

A C

28

C:1

null


C:3

null

A:2

C:1

D:1

E:1

D:1

E:1E:1

28

Suffix E (insérer ACDE)


(New) Header table

A 2C 2D 2

D:1

C 1

D 2 1

A C

29

A:2

C:1

D:1 29

C:1

null


C:3

null

A:2

C:1

D:1

E:1

D:1

E:1E:1

29

Suffix E (insérer ADE)


(New) Header table

A 2C 2D 2

3030

ORGANIGRAMME DE FP-GROWTHCONTRIBUTION (18)

30

Présentateur


B est le conditional pattern pour l’itemset alpha Béta est l’itemset dans B

31

D1: T25.I10D10K (taille moy trans:25, taille max itemsets:10, Nb transaction: 10K)D2: T25.I20D100K (taille moy trans:25, taille max itemsets:20, Nb transaction: 100K)

RÉSULTATS (1)FP-GROWTH VS. APRIORI

Présentateur


Ce graphe montre les performances de FP‐growth et Apriori en temps d’exécution. Quand le support décroit, le temps d’exécution augmente très rapidement. On remarque que FP‐growth monte à l’échelle mieux que Apriori surtout pour les petits supports. Quand le seuil du support décroit, le nombre des itemset augmente, ce qui impose à Apriori de gérer un ensemble de candidats extrêmement large et rend la recherche très coûteuse. Deux ensembles de données ont été pris pour évaluer les résultats : D1 : T25.I10.D10K avec 1 k d’items, où le T25 veut dire que la taille moyenne des transactions est de 25, le I10 veut dire que la taille moyenne maximale des itemset est de 10 et enfin D10k représente le nombre de transactions dans la base de données. D2 : T25.I20.D100k, la même chose que D1 à par que la taille moyenne maximale des itemset est de 20 et le nombre de transactions dans la base de données est de 100K. Remarque : Les résultats d’exécution de FP‐growth incluent le temps de construction de l’FP‐Tree

32

RÉSULTATS (2)SCALABILITÉ PAR RAPPORT AU SUPPORT

Présentateur


Ce graphe montre le temps d’exécution de FP‐growth par itemset. On voie clairement que le FP‐growth affiche une très bonne scalabilité pour les petites valeurs de support et que l’évolution et presque linéaire que ça soit pour le petit ensemble de données ou le grand.

33

SCALABILITÉ EN NOMBRE DE TRANSACTIONSRÉSULTATS (3)

Présentateur


On prend le support égal à 1.5 % et on étudié le temps d’exécution quand la taille des transactions augmente. On remarque que les deux algorithmes FP‐growth et Apriori évolues linéairement mais FP‐growth est plus scalable. Plus la taille des transactions grandit, plus l’écart entre les deux méthodes devient de plus en plus grand.

RÉSULTATS (4)FP-GROWTH VS. TREEPROJECTION

34

TreeProjection (Agrawal 2000) est une méthode de d’extraction efficace, limitant le comptage de support, et offrant un arbre lexicographique qui facilite la gestion et le comptage des candidats

Présentateur


TreeProject (Agrawal 2000) est un algorithme récent par rapport à l’article. L’idée principale de cet algorithme c’est qu’il construit un arbre lexicographique et projette la base de données dans un ensemble réduit de données. Le nombre de noeuds de l’arbre correspond au nombre d’itemset. Treeprojection présente plusieurs avantages parmi les quelles on trouve : Une facilité de gestion Réduit le coût du calcule du support Malgré ses avantages, il reste toujours peu performant par rapport à FP‐growth. En effet le premier graphe issu de la comparaison des performances de l’algorithme avec FP‐growth, 19 montre que ce dernier est plus performant en terme de temps d’exécution. L’écart de performance entre les deux algorithmes augmente en fonction de la taille de la base de données (D2 contient dix fois plus de transactions que D1). Maintenant en prenant le support égal à 1% les auteurs ont fait varier la taille de la base de données (nombre de transactions) et ils ont obtenus le deuxième graphe ci‐dessus. Il est clair que les deux algorithmes ont une scalabilité linéaire mais FP‐growth est plus scalable que TreeProjection. Le coût principale de Tree‐projection est dans le calcule de la matrice et la projection des transactions alors dans une BD avec un grand nombre d’itemset fréquent la matrice est large ce qui augmente considérablement le coût de calcule. La projection aussi coûte cher quand la base de données est volumineuse. Petite conclusion : FP‐tree est un algorithme qui bat à coup de couture toutes les méthodes de recherche de règles d’association existantes surtout quand les supports sont petits.

DISCUSSION (1)

Le FP-tree peut ne pas tenir en mémoire si il est volumineux

Sauvegarder le FP-Tree sur disque et l’indexer

La définition du bon support

Mises à jour incrémentale de l’FP-Tree

Ne traitent pas des problèmes liés à la qualité de données (valeurs aberrantes, manquante et nulle)

35

Présentateur


La structure B+ peut être utilisée pour indexer le FP-Tree La mise à jour incrémentale à besoin de sauvegarder tous les intemset ou de définir un seuil de support très petit

DISCUSSION (2)Problème liée aux mesures Support et Fréquence (mesures non suffisantes) :

Le support est symétrique : A ⇒ B ou B ⇒ A ?Whisky ⇒ Viande a une confiance élevée

confiance(X ⇒ Y) = P(Y/X) = P(XY)/P(X). ignore P(Y) élevée si P(X) est faible et P(Y) fort

Fp-growth est inclus à DBMiner fait ses preuves sur un environnement réel

36

Présentateur


La structure B+ peut être utilisée pour indexer le FP-Tree La mise à jour incrémentale à besoin de sauvegarder tous les intemset ou de définir un seuil de support très petit

RÉFÉRENCES1. R. Agarwal, C. Aggarwal, and V. V. V. Prasad. Depth-first generation of large itemsets for association rules. IBM

Tech. Report RC21538, July 1999.

2. Ramesh C. Agarwal , Charu C. Aggarwal , V. V. V. Prasad, A tree projection algorithm for generation of frequentitem sets, Journal of Parallel and Distributed Computing, v.61 n.3, p.350-371, March 1, 2001 [doi>10.1006/jpdc.2000.1693], Cité 65 fois.

3. Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994, Cité 1278 fois.

4. Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the EleventhInternational Conference on Data Engineering, p.3-14, March 06-10, 1995, Cité 483 fois

5. Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States, Cité 198 fois

6 . Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, United States, Cité 162 fois.7 . Guozhu Dong , Jinyan Li, Efficient mining of emerging patterns: discovering trends and differences, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.43-52, August 15-18, 1999, San Diego, California, United States, Cité 92 fois.

37

Présentateur


Source http://portal.acm.org

8. G. Grahne, L. Lakshmanan, and X. Wang. Efficient mining of constrained correlated sets. In ICDE'00.

9. Efficient Mining of Partial Periodic Patterns in Time Series Database, Proceedings of the 15th International Conference on Data Engineering, p.106, March 23-26, 1999 , Cité 83 fois.

10. J. Han, J. Pei, and Y. Yin. Mining partial periodicity using frequent pattern trees. In GS Tech, Rep, 99-10, Simon Fraser University, July 1999.

11. M. Kamber, J. Han, and J. Y. Chiang. Metaruleguided mining of multi-dimensional association rules using data cubes. In KDD'97, pp. 207-210.

12 . Mika Klemettinen , Heikki Mannila , Pirjo Ronkainen , Hannu Toivonen , A. Inkeri Verkamo, Finding interestingrules from large sets of discovered association rules, Proceedings of the third international conference on Information and knowledge management, p.401-407, November 29-December 02, 1994, Gaithersburg, Maryland, United States, Cité 138.

13. Brian Lent , Arun N. Swami , Jennifer Widom, Clustering Association Rules, Proceedings of the ThirteenthInternational Conference on Data Engineering, p.220-231, April 07-11, 1997, Cité 65 fois.

14. Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997, Cité 161 fois.

15. Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han , Alex Pang, Exploratory mining and pruning optimizationsof constrained associations rules, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.13-24, June 01-04, 1998, Seattle, Washington, United States , cité 145 fois.

16. Jong Soo Park , Ming-Syan Chen , Philip S. Yu, An effective hash-based algorithm for mining association rules, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.175-186, May 22-25, 1995, San Jose, California, United States, Cité 214 fois.

38

17. Sunita Sarawagi , Shiby Thomas , Rakesh Agrawal, Integrating association rule mining withrelational database systems: alternatives and implications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.343-354, June 01-04, 1998, Seattle, Washington, United States, cité 69 fois.

18. Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conferenceon Very Large Data Bases, p.432-444, September 11-15, 1995, Cité 227.

19. Craig Silverstein , Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman, Scalable Techniques for Mining Causal Structures, Proceedings of the 24rd International Conference on Very Large Data Bases, p.594-605, August 24-27, 1998 , cité 40 fois.

20. R. Srikant, Q. Vu, and R. Agrawal. Mining association rules with item constraints. In KDD'97, pp. 67-73.

21. René Lefébure et Gilles Venturi, Le Data Mining Edition Eyrolles 1998

39

Article 2:Bitmap Based Algorithms For Mining Association (George GARDARIN, Philippe PUCHERAL, Fei WU)

40

PLAN2

IntroductionProblématique ContributionRésultats Références

41

INTRODUCTION

Plutôt que d’avoir une liste de valeurs, un bitmap permet de les représenter par des bits (1: valeur présente, 0: sinon).

42

DÉFINITION DE BITMAP

Ménagère Produits Prix

1 {P1, P3, P5} 1202 {P2, P3} 703 {P4} 1504 {P2, P5} 1105 {P3,P4,P6} 220

P1 P2 P3 P4 P5 P61 0 1 0 1 00 1 1 0 0 00 0 0 1 0 00 1 0 0 1 00 0 1 1 0 1

Présentateur


L’optimisation des règles d’associations est cruciale pour la scalabilité surtout que la plupart des données traitées actuellement sont très volumineuse. Pour que l’algorithme d’extraction des règles d’associations soit scalable, il doit réduire le nombre de balayages de la base de données et réduire le coût de calcule du support

PROBLÉMATIQUE

43

Optimisation des règles d’associations

beaucoup de techniques ont été proposés pour réduire le nombre de passes et augmenter leurs efficacité [AS 94, SON95]

MaisFastidieux travail de comptage du support

Peu de travaux s’intéressent à l’évaluation du comptage (coût du support)

Présentateur


Alors que la plupart des algorithmes se concentrent sur la réduction du nombre de balayages de la base de données (c.à.d., le coût en E/S), les auteurs de cet article (GG & PP 98) ont proposé une méthode de calcul des supports qui optimise le coût CPU, sans générer d'E/S supplémentaire. Leur solution est basé sur un indexe bitmap pour représenter les couples (transaction, article) et réduire ainsi le coût de comptage. En effet, il suffit d’appliquer l'opérateur logique AND à l'ensemble des colonnes concernées dans l'indexe pour calculer le support. L’optimisation des règles d’associations est très importante surtout si on a affaire à des bases de données très volumineuse. efficacité (candidats générés, coût du support)

CONTRIBUTION (1)Les auteurs (George Gardarin et Philippe Pucheral)

de l’article ont proposés deux algorithmes pour optimiser le comptage:

• N-BM Naïve Bitmap• H-BM Hirarchical Bitmap

44

Présentateur


Cette idée d’utiliser les indexes bitmaps pour réduire le coût de calcule des supports a été introduite pour la première fois par [SON 95] mais sans développer l’idée.

CONTRIBUTION (1)

45

* Liste 3 5 7 12 35 42

Bitmap niveau 1 (TIDs)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0

1

0

1

Bitmap niveau 2* Bitmap

Groupe 0

Groupe 1

Groupe 2

Présentateur


Dans [SON95], la tidlists sont maintenus comme des tableaux et il faut utiliser sort-merge algorithm (Tri-fusion) pour faire l'intersection des listes de transactions. Les auteurs [SON95] suggèrent également d’utiliser un ensemble de bits comme alternative aux tableaux très coûteux mais ils ne poursuivent pas cette idée. Cette idée de hiérarchisation des bitmaps est utile vu le nombre important de zéros dans le bitmap il n’est inutile de faire des additions de zéros. Regardez bien comment la TID 3 de Liste est représenté par un bite à la troisième position, la TID 5 à la cinquième position et ainsi de suite.

46

CONTRIBUTION (2)N-BM

Structure de données

procedure count_support(itemset1,itemset2){(1) new_itemset.max_group=min(itemset1.max_group, itemset2.max_group) ;(2) for (i = 0 ; i < new_itemset.max_group ; i++) do {(3) new_itemset.tidbit[i] = itemset1.tidbit[i] & itemset2.tidbit[i] ;(4) new_itemset.support += nbbit[new_itemset.tidbit[i]] ;(5) }}

Algorithme

Repose sur le N-BM avec une organisation HiérarchiquePropose un schéma de compression Evite les accès inutiles

47

CONTRIBUTION (3) H-BM

Présentateur


Dans chaque groupe de 1-BM ont peu représnter l’existance ou l’absence de 16 transactions ayant des numéros successifs. Le H-BM comme son nom l’indique il repose sur le N-BM au quelle l’auteur à ajouté une structure de compression pour éviter les accès inutiles On suppose qu’on a un nombre de transaction égale à 100K et que le support est égale à 0.2% alors on 2000 sont différents de zéro. Ce qui me fait 100K/16 -2000 zéros dans notre Tidbit. Par exemple le groupe 0 ayant la valeur 0804 en hexadécimale représente un sous ensemble de TID {5, 14} peuvent être codé sur 16 bits. En effet 0804 en hexa = 0000 1000 0000 0100 en binaire. Dans le premier groupe on a 0000 donc il ne y a aucune transaction ayant un TID entre 17 et 32. le 2-BM et une hiérarchisation de 1-BM pour éviter de faire des accès si le groupe de 1-BM est nule.

CONTRIBUTION (4) H-BM

procedure count_support(itemset1, itemset2) do { for (i := 0 ; i < WORD_NUM ; i++) do {new_itemset.2-BM[i] = itemset1.2-BM[i] & itemset2.2-BM[i] ;}for (i := 0 ; i < BYTE_NUM ; i++) do{ posi = -1;b = new_itemset.2-BM[i];for (; b != 0 ; b >>= 1) do { // shift a bit to the right until b=0posi++;

if (b & 1) do { // if the first bit is 1bm= itemset1.1-BM[posi+i*8] & itemset2.1-BM[posi+i*8]; new_itemset.support+=nbbit[bm] ;} } }}

48

Algorithme

LA PARALLÉLISATIONS

1-BM et 2-BM sont de taille fixes facilement partitionableH-BM est rapide et ne consomme pas beaucoup de mémoire

Deux phases de H-BM peuvent être parallélisé :

1. La construction du bitmap2. Calcule du support

49

RÉSULTATS ET ÉVALUATION (1)

50

Coût de List

Présentateur


Chaque groupe de 1‐BM renseigne sur l’existence ou l’absence d’un article dans un groupe de transactions ayant des numéros de TID successifs (l’espace des TID est découpé en 16 bits). Les 1‐itemset sont représentés par un short dans le 1‐BM, un bit dans le 2‐BM et une valeur du support calculé, par contre les K‐itemset sont représentés par des itemcode (tableau de code d’item) dans le 1‐BM, un tableau de bits dans le 2‐BM et enfin un support. Par exemple le groupe 0 ayant la valeur 0804 en hexadécimale représente un sous ensemble de TID {5, 14} codé sur 16 bits. En effet 0804 en hexa est égal à 0000 1000 0000 0100 en binaire. Dans le premier groupe on a 0000 donc il n’y a aucune transaction ayant un TID compris entre 17 et 32. Le H‐BM comme son nom l’indique repose sur la hiérarchisation des N‐BM pour éviter les accès inutiles en cas où la matrice est creuse (pleins de zéros). Pour illustrer l’intérêt de H‐BM, on suppose qu’on a une base de données contenant 100K de transactions et que le support est égal à 0.2%, ce qui nous fait une portion de 2000 articles dans la base de données. Le bitmp contient alors 100K/16 ‐2000 zéros, ce qui représente beaucoup d’accès inutiles. 26 L ’évaluation des performances entre l’algorithme List et H-BM en faisant varier la corrélation entre les items. Le support AB est calculé comme la corrélation AB * min (supportA, supportB)


51

Coût de List

Présentateur


Dans le pire des cas l’analyse du coût de List est égale à : T=…. Où T représente le nombre des transactions et SA, SB, SAB sont respectivement le support de A, de B et de AB. 28 L’analyse du coût de HB‐M a donné le résultat suivant : La comparaison entre les deux algorithmes va se faire sur la base du ratio suivant : Ce ratio élimine T pour mettre en évidence la corrélation et les supports. Le support de AB est calculé comme la corrélation AB multiplié par le minimum du support de A et B. 52Cor:

52

Cor: Corrélation entre l’item A et B Freq: nombre de fréquence 1-itemsetsSup: support minimum

Temps d’exécution Consommation mémoire

0,0

0,5

1,0

1,5

2,0

2,5

H-B

M/L

ist

Cor

Sa=Sb=2%

Sa=Sb=0,75%

Sa=Sb=0,25%

Sa=2% Sb=0,25%

0

0,2

0,4

0,6

0,8

1

1,2

1,4

H-BM

/Lis

tSup

Freq=50

Freq=100

Freq=500


Présentateur


Voici des évaluations analytiques sur le temps d’exécution et la consommation de mémoire entre H-BM et List. On peut voir par ces deux figures que H-BM dépasse List dans a plupart de cas, et List est meilleure que H-BM seulement quand les supports sont petits et la corrélation est grande. Quand la corrélation est mauvaise H_BM l’emporte pour la grande sélectivité de 2-BM. En 0.01 H-BM est 10 fois plus rapide. On remarque aussi que H-BM ce comporte très bien quand les supports sont différents Pour la consommation mémoire le H-BM est largement meilleur pour les grands supports et les grande fréquences de 1-itemsets car la taille de la liste augmente linéairement par rapport au support. On déduit que H-BM est plus adapté au parallélisme Avant de conclure je tiens à vous signaler que N-BM surclasse H-BM et List si on cherche (non A intersection B ) avec la fréquence de A et non A sont presque égale.

RÉFÉRENCES

[AIS93]Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami. Mining Association Rules betweenSets of Items in Large Databases. In Proceedings of the 1993 ACM SIGMOD InternationalConference on Management of Data, Washington, D.C., 1993 , pp. 207-216.[AS94]R. Agrawal, R. Srikant. Fast Algorithms for Mining Association Rules in Large Databases.InProceedings of the 20th International Conference on Very Large Data Bases, Santiago deChile, Chile, 1994, pp. 487-499.[AS96]R. Agrawal and J. C. Shafer. Parallel Mining of Association Rules, Design, Implementation and Experience. IBM Research Report 1996. 53

RÉFÉRENCES[BMS97] Sergey Brin, Rajeev Motwani, Craig Silverstein. Beyond MarketBaskets : GeneralizingAssociation Rules to Correlations. In Proceedings ACM SIGMOD International Conferenceon Management of Data, Tucson, Arizona, USA, 1997, pp. 265-276.[BMU+97] Sergey Brin, Rajeev Motwani, Jeffrey D. Ullman, Shalom Tsur. Dynamic Itemset Countingand Implication Rules for Market Basket Data. In Proceedings ACM SIGMODInternational Conference on Management of Data, Tucson, Arizona, USA, 1997, pp. 255-264.[CHN+96] D. W. Cheung, J. Han, V. Ng, A. Fu and Y. Fu. A Fast DistributedAlgorithm for MiningAssociation Rules. Int’l Conf. on Parallel and Distributed Information Systems (PDIS),Miami Beach, Florida, USA, 1996.[HF95] Jianwei Han, Yongjian Fu. Discovery of Multiple-level Association Rules from LargeDatabases. In Proceedings of the 21st International Conference on Very Large Data Bases,Zurich, Swizerland, 1995, pp. 420-431.

54

RÉFÉRENCES[MPC96]R. Meo, G. Psalia, S. Ceri. A New SQL-like Operator for Mining Association Rules. InProceedings of 22th International Conference on Very Large Data Bases, Mumbai(Bombay), India, 1996, pp. 122-133.[PCY95]Jong Soo Park, Ming-Syan Chen, Philip S. Yu. An Effective Hash Based Algorithm forMining Association Rules. In Proceedings ACM SIGMOD International Conference on Management of Data, San Jose, California, 1995, pp. 175-186.[PCY95+]Jong Soo Park, Ming-Syan Chen, Philip S. Yu. Efficient Parallel and Data Mining forAssociation Rules. International Conference on Information and Knowledge Management (CIKM), Baltimore, Maryland, 1995.[SA95]R. Srikant, R. Agrawal. Mining Generalized Association Rules. In Proceedings of the 21st International Conference on Very Large Data Bases, Zurich, Swizerland, 1995, pp. 407-419.

55

Questions?

56

Documents

Extraction des règles d'association FP-Growth