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.