Présentation

Présentation:

Cet article est le deuxième article de la série concernant l’algorithme FP-Growth. Dans le premier article j’ai présenté l’algorithme, son fonctionnement global ainsi que ses avantages et inconvénients.

Dans cet article je vais introduire la construction d’une structure FP-tree. Pour rappel, l’algorithme FP-Growth utilise une structure de donnée appelée Frquent Pattern tree. Il permet de trouver les itemsets fréquents dans une base de transactions. Grace à la structure FP-tree on conserve l’ensemble des éléments fréquents de la base des transactions dans une structure compacte. Ainsi il n’est plus nécessaire de devoir parcourir la base de transactions. De plus, ces éléments se retrouvent triés ce qui accélère la recherche des règles d’association.

Présentation :

Nous avons vu que l’algorihme Apriori effectue plusieurs passes (scans) de la base de données. Ceci peut être très pénalisant lorsqu’il s’agit de données voluminineuses. Afn d’éviter les parcours répétés de la base de données, Han et al. [1] ont proposé  une méthode différente des approches par niveaux permettant d’extraire des itemsets fréequents sans génération de candidats.

Cette méthode s’appelle FP-growth (Frequent Pattern growth). Elle consiste d’abord à compresser la base de données en une structure compacte appelée FP-tree (Frequent Pattern tree), puis à diviser la base de donnees ainsi compressée en sous projections de la base de données appelées bases conditionnelles.

Chacune de ces projections est associée à un item fréquent. L’extraction des itemsets fréquents se fera sur chacune des projections séparement.

L’algorithme FP-growth apporte ainsi une solution au problème de la fouille de motifs fréquents dans une grande base de données transactionnelle. En stockant l’ensemble des éléments fréquents de la base de transactions dans une structure compacte, on supprimer la nécessité de devoir scanner de façon répétée la base de transactions. De plus, en triant les éléments dans la structure compacte, on accélère la recherche des motifs.

Résumé

Ce papier présente les premiers éléments de définition d’un algorithme permettant de  déterminer le nombre optimal de machines virtuelles (VM – Virtual Machines) lors de  l’exécution des applications de fouille de données dans un environnement Cloud. L’efficacité  de traitement des problèmes de fouille de données requiert d’obtenir au préalable un  partitionnement intelligent de données par clustering de manière à effectuer le plus  indépendamment que possible les traitements des fragments de données à cohérence sémantique forte.

Nous pensons que l’exécution sur les données distribuées dans le Cloud d’une variante parallèle de l’algorithme de clustering h-means adaptée en phase de présélection du processus PMML [18] pour (Predictive Model Markup Language) permettrait d’assurer un partitionnement optimal des données et de déterminer un nombre de VM optimal avant l’exécution de l’application.

Mots-clés : Cloud computing, h-means, classification, parallélisme dans des grilles, partitionnement de données, fouille de données.