FP-growth Algorithm

The FP-growth algorithm is a data mining technique used for frequent itemset mining. It constructs a compact an FP-tree to efficiently mine frequent itemsets by traversing the tree and identifying conditional patterns with support values above a predefined threshold. This approach eliminates the need for candidate generation and multiple database scans, making it particularly efficient for large datasets.

Let's use the FP-tree created in the previous chapter as an example:

Let's take the prefix {bread, eggs} as an example.

To find the conditional patterns for this prefix we need to identify transactions containing this prefix and then collect the items that occur after {bread, eggs} in those transactions. It can be easily done using FP-tree:

These patterns represent the items that frequently occur after {bread, eggs} in the provided transactions, along with their counts.

FP-growth vs Apriori

The main idea of the FP-growth algorithm is to traverse the FP-tree and build all possible conditional patterns that have a support value greater than a predefined threshold. This process allows for the efficient discovery of frequent itemsets without the need for costly candidate generation and testing steps, as required in traditional algorithms like Apriori.

Note

Pay attention that itemset support equals the count of the itemset divided by the total number of transactions.