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

Illustration:

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.