Association Rule Mining Algorithms ?

What is FP Growth Algorithm ?

An efficient and scalable method to find frequent patterns. It allows frequent itemset discovery without candidate itemset generation.

Following are the steps for FP Growth Algorithm


Consider the below tansaction in which B = Bread, J = Jelly, P = Peanut Butter, M = Milk and E = Eggs. Given that minimum threshold support = 40% and minimum threshold confidence = 80% [13].

Step-1: Scan DB once, find frequent 1-itemset (single item in itemset)

Step-2: As minimum threshold support = 40%, So in this step we will remove all the items that are bought less than 40% of support or support less than 2.

Step-3: Create a F -list in which frequent items are sorted in the descending order based on the support.

Step-4: Sort frequent items in transactions based on F-list. It is also known as FPDP.

Step-5: Construct the FP tree

Step-6: Construct the conditional FP tree in the sequence of reverse order of F - List {E,M,P,B} and generate frequent item set. The conditional FP tree is sub tree which is built by considering the transactions of a particular item and then removing that item from all the transaction.

The above table has two items {B , P} that are bought together frequently.

As for items E and M, nodes in the conditional FP tree has a count(support) of 1 (less than minimum threshold support 2). Therefore frequent itemset are nil. In case of item P, node B in the conditional FP tree has a count(support) of 3 (satisfying minimum threshold support). Hence frequent itemset is generated by adding the item P to the B.