Abstract

Apriori is a frequent pattern mining algorithm for discovering association rules. It is one of the most well-known algorithms for discovering frequent patterns along with FP-Growth algorithm. However, as a result of the current advances in the area of storage of very large databases and the tremendous growth in number of transactions, sequential Apriori becomes a bottleneck because of the long running time of the algorithm. In this paper, our goal is to develop a new parallel version of Apriori that aims to reduce the overall running time of the algorithm. Although Apriori is not known to be highly parallelizable, several attempts have been made to parallelize it in various ways, either by using parallel I/O hardware to optimize database scans or by distributing the workload on multiple processors. However, many of the parallel approaches suffer from noticeable latencies in synchronizing results being collected from each individual processor after a parallel iteration terminates. Our approach focuses on trying to maximize the workload being executed in parallel and to minimize the synchronization point delays by adopting a parallel pre-computing scheme during generation of the superset. By applying our new approach, the running time of the algorithm is reduced by an order of magnitude compared to other parallel implementations of the same algorithm.

Présentation :

Cet article constitue la troisième et dernière partie de la serie consacrée à l’algorithme FP-Growth. Dans l’article précédent  j’ai introduit la construction d’une structure FP-tree, structure utilisée par l’algorithme FP-Growth pour stocker les informations concernant tous les motifs (itemsets) fréquents dans une base de transactions.

Dans cet article je vais présenter la manière dont sont identifiés les itemsets fréquents de la base de transactions à partir de la structure FP-tree construite à la suite du parcours des éléments de la bases de transactions. Le but étant de générer à partir de ces ensembles d’itemsets fréquents les règles d’associations.

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.

Définitions :

L’algorithme A-priori¹ est un algorithme d’exploration de données conçu en 1994, par Rakesh Agrawal et Ramakrishnan Sikrant, dans le domaine de l’apprentissage des règles d’association. Il sert à reconnaître des propriétés qui reviennent fréquemment dans un ensemble de données et d’en déduire une catégorisation.

A-Priori détermine les règles d’association présentes dans un jeu de données, pour un seuil de support et un seuil de confiance fixés. Ces deux valeurs peuvent être fixées arbitrairement par l’utilisateur. (Continuer la lecture…)