Frequent Pattern (FP) Growth Algorithm

Algorithm

Steps of the FP-Growth Algorithm

1. Calculate the frequency of every itemset.
   Scan the transaction database and count the occurrence of each item.
2. Build the frequent pattern set (L).
   Select the itemsets whose support is greater than or equal to the minimum support:
   
   Support ≥ Minimum Support
3. Build an ordered itemset for each transaction.
   Arrange the items in each transaction in descending order of their frequency. Items that are not frequent are removed.
4. Build the FP-Tree.
   Insert the ordered itemsets into the FP-Tree. Common prefixes of transactions are shared to reduce the size of the tree.
5. Compute the Conditional Pattern Base.
   For each item, identify the prefix paths in the FP-Tree that lead to that item. These prefix paths form its conditional pattern base.
6. Build the Conditional Frequent Pattern Tree.
   Construct a conditional FP-Tree from the conditional pattern base of each item, considering only items that satisfy the minimum support requirement.
7. Generate Frequent Patterns.
   Mine the conditional FP-Trees to generate all frequent itemsets that satisfy the minimum support requirement.
8. Rule Formation.
   Generate association rules from the frequent itemsets and evaluate them using measures such as support, confidence, and lift.

Example

FP Growth Algorithm

Transactions Table

Transaction ID	Items
T1	{E, K, M, N, O, Y}
T2	{D, E, K, N, O, Y}
T3	{A, E, K, M}
T4	{C, K, M, U, Y}
T5	{C, E, I, K, O}

Step 1: Frequency Count

Item	Frequency
A	1
C	2
D	1
E	4
I	1
K	5
M	3
N	2
O	3
U	1
Y	3

Step 2: Frequent Pattern Set (L)

A frequent pattern set (L) is built which will contain all the elements whose frequency is greater than or equal to the minimum support.

Minimum support = 3

L = {K:5, E:4, M:3, O:3, Y:3}

The frequent items are arranged in descending order of their frequency.

Now, for each transaction, the respective ordered item set is built.

Frequent Pattern Set L = {K:5, E:4, M:3, O:3, Y:3}

Step 3: Transaction Table and Ordered Item Sets

Transaction ID	Items	Ordered Item Set
T1	{E, K, M, N, O, Y}	{K, E, M, O, Y}
T2	{D, E, K, N, O, Y}	{K, E, O, Y}
T3	{A, E, K, M}	{K, E, M}
T4	{C, K, M, U, Y}	{K, M, Y}
T5	{C, E, I, K, O, O}	{K, E, O}

Note: Items are ordered according to the frequent pattern set L = {K, E, M, O, Y}, dropping non-frequent items.

---

Step 4: Next, Build a Trie Data Structure

---

Now, for each item, the conditional pattern base is computed, which is the path labels of all the paths that lead to any node of the given item in the frequent-pattern tree.

Step 5: Conditional Pattern Base Table

Items	Conditional Pattern Base
Y	{ {K, E, M, O : 1}, {K, E, O : 1}, {K, M : 1} }
O	{ {K, E, M : 1}, {K, E : 2} }
M	{ {K, E : 2}, {K : 1} }
E	{ {K : 4} }
K	—

---

Now, for each item, the conditional frequent pattern tree is built. It is done by taking the set of elements which is common in all the paths in the conditional pattern base of that item and calculating its support count by summing the support counts of all the paths in the conditional pattern base.

Step 6: Conditional Frequent Pattern Tree Table

Items	Conditional Pattern Base	Conditional Frequent Pattern Tree
Y	{ {K, E, M, O : 1}, {K, E, O : 1}, {K, M : 1} }	{K : 3}
O	{ {K, E, M : 1}, {K, E : 2} }	{K, E : 3}
M	{ {K, E : 2}, {K : 1} }	{K : 3}
E	{ {K : 4} }	{K : 4}

---

Step 7: Frequent Pattern Generated Table

Items	Frequent Pattern Generated
Y	{ <K, Y : 3> }
O	{ <K, O : 3>, <E, O : 3>, <E, K, O : 3> }
M	{ <K, M : 3> }
E	{ <E, K : 4> }
K	—

---

Step 8: Rule formation

Now, for the frequent pattern {K, Y}, two possible association rules can be generated:

• K → Y
• Y → K

The rule that satisfies the minimum confidence requirement will be considered a valid association rule.