FP GROWTH

3.2.4 FP GROWTH

The algorithm, FP-growth, for mining the FP-tree structure is a recursive procedure during which many sub FP-trees and header tables are created. The process commences by examining each item in the header table, starting with the least frequent. For each entry the support value for the item is produced by following the links connecting all occurrences of the current item in the FP-tree. If the item is adequately supported, then for each leaf node a set of ancestor labels is produced , each of which has a support equivalent to the sum of the leaf node items from which it is generated. If the set of ancestor labels is not null, a new tree is generated with the set of ancestor labels as the dataset, and the process repeated. In our implementation all frequent itemsets thus discovered were placed in a tree, thus providing fast access during the final stage of the process, while at the same time providing for the deletion of FP-subtrees and tables created "on route" as the FP-growth algorithm progressed.

A sample FP Growth is shown below:


Fig 3.2 FP Growth