FP-Growth Algorithm
The FP Growth algorithm is a popular method for frequent pattern mining in data mining. It works by constructing a frequent pattern tree (FP-tree) from the input dataset. The FP-tree is a compressed representation of the dataset that captures the frequency and association information of the items in the data.
FP Growth algorithm was developed by Han in 2000 and is a powerful tool for frequent pattern mining in data mining. It is widely used in various applications such as market basket analysis, bioinformatics, and web usage mining.
The FP Growth algorithm in data mining has several advantages over other frequent pattern mining algorithms, such as Apriori. The Apriori algorithm is not suitable for handling large datasets because it generates a large number of candidates and requires multiple scans of the database to mine frequent items.
In comparison, the FP Growth algorithm requires only a single scan of the data and a small amount of memory to construct the FP tree. It can also be parallelized to improve performance.
FP Tree
The FP-tree (Frequent Pattern tree) is a data structure used in the FP Growth algorithm that stores the frequent item sets and their support counts.
Working of FP Growth Algorithm
The working of the FP Growth algorithm in data mining can be summarized in the following steps:
Step 1: Scan the database
In this step, the algorithm scans the input dataset to determine the frequency of each item.
Step 2: Sort items
In this step, the items in the dataset are sorted in descending order of frequency. The infrequent items that do not meet the minimum support threshold are removed from the dataset. This helps to reduce the dataset's size and improve the algorithm's efficiency.
Step 3: Construct the FP-tree
In this step, the FP-tree is constructed. The FP-tree is a compact data structure that stores the frequent itemsets and their support counts. In this items are added to the FP tree, with the most frequent items added first.
Step 4: Generate frequent itemsets
Once the FP-tree has been constructed, frequent itemsets can be generated by recursively mining the tree. Starting at the bottom of the tree, the algorithm finds all combinations of frequent item sets that satisfy the minimum support threshold.
Step 5: Generate association rules
Once all frequent item sets have been generated, the algorithm post-processes the generated frequent item sets to generate association rules, which can be used to identify interesting relationships between the items in the dataset.
FP Growth Algorithm Example
Consider the below dataset and find frequent item sets and generate association rules for them. Assume that Minimum support count is 2 and minimum confident threshold (c = 70%).
| Transaction ID | Items |
|---|---|
| T1 | A, C, D |
| T2 | B, C, E, F |
| T3 | A, B, C, E |
| T4 | B, E |
| T5 | A, C, E |
Solution
The above dataset contains 5 transactions and 6 items.
Step 1: Scan the dataset
In this step, we will first calculate the support count of all the items in the transaction dataset. The results have been tabulated below.
| Item | Support Count |
|---|---|
| A | 3 |
| B | 3 |
| C | 4 |
| D | 1 |
| E | 4 |
| F | 1 |
Now, let's sort the above table by the support count.
| Item | Support Count |
|---|---|
| C | 4 |
| E | 4 |
| A | 3 |
| B | 3 |
| D | 1 |
| F | 1 |
Step 2: Sort items
After calculating the support count of each item, we will sort the items in each transaction according to their support count in descending order. If two items have the same support count, we will keep their order in topological order.
The given minimum support count is 2. In the above table Items D and F doesn't meet minimum support count. So we need to remove Items D and F from each transaction the above dataset.
The resulting dataset is as follows.
| Transaction ID | Items |
|---|---|
| T1 | C, A |
| T2 | C, E, B |
| T3 | C, E, A, B |
| T4 | E, B |
| T5 | C, E, A |
Step 3: Construct the FP-tree
After sorting the items in each transaction in the dataset by their support count, we need to create an FP Tree using the dataset.
To create an FP-Tree in the FP growth algorithm, we use the following steps.
1. First, we create a root node and name it Null or None. This node contains no data.
2. Next, for each transaction in the database, we insert the items in descending order of their support count into the FP-tree as follows:
T1: C, A
The transaction T1: C, A contains two items C and A, where C is linked as a child to root node and A is linked to C.
Here, all the items are simply linked one after the other in the order of occurrence in the set and initialize the support count for each item as 1. i.e. {C: 1, A: 1}.
T2: C, E, B
The transaction T2: C, E, B wherein C already linked with root node, So increment the support count of C by 1 and E is linked to C and B is linked to E. Hence initialize the support count for E and B as 1.
T3: C, E, A, B
The transaction T3: C, E, A, B where C and E already linked, So increment the support count of C and E by 1 and A is linked to E and B is linked to A. Hence initialize the support count for A and B as 1.
T4: E, B
The transaction T4: E, B where E is linked with root node and B is linked with E, so set the support count for E and B as 1.
T5: C, E, A
The transaction T5: C, E, A where C, E and A already linked, so increment the support count of C, E and A by 1.
The following is the complete FP-Tree along with support count:
Step 4: Generate frequent item sets
In this step, we need to generate frequent item sets by the help of the above FP-Tree.
To generate the frequent item sets, first we need to create a pattern base for all the items in the transaction dataset.
Create a pattern base:
| Item | Pattern Base |
|---|---|
| A | {C:1},{C,E:2} |
| B | {C,E:1},{C,E,A:1},{E:1} |
| C | {} |
| E | {C:3} |
Next, we need to create a conditional fp-tree for each frequent item. Here, we will calculate the count of items in the conditional fp tree of each item.
| Item | Pattern Base | Conditional FP Tree |
|---|---|---|
| A | {C:1},{C,E:2} | {C:3},{E:2} |
| B | {C,E:1},{C,E,A:1},{E:1} | {C:2},{E:3} |
| C | {} | - |
| E | {C:3} | {C:3} |
After creating the conditional fp-tree, we need to generate frequent item sets for each item. To generate the frequent item sets, we take all the combinations of the items in the conditional fp-tree with their count.
| Item | Pattern Base | Conditional FP Tree | Frequent item sets |
|---|---|---|---|
| A | {C:1},{C,E:2} | {C:3},{E:2} | {A,C}:3, {A,E}:2, {A,C,E}:2 |
| B | {C,E:1},{C,E,A:1},{E:1} | {C:2},{E:3} | {B,C}:2, {B,E}:3, {B,C,E}:2 |
| E | {C:3} | {C:3} | {E,C}:3 |
Step 5: Generate association rules
Thus, we have discovered all the frequent item-sets. Now we need to generate strong association rules (satisfies the minimum confidence threshold) from frequent item sets. For that we need to calculate confidence of each rule.
The given Confidence threshold is 70%.
(i) {A, C}
The all possible association rules from the above frequent item set are:
{A} ⇒ {C}
= (3/ 3)* 100 = 100% (Selected)
{C} ⇒ {A}
= (3/ 4)* 100 = 75% (Selected)
(ii) {A, E}
The all possible association rules from the above frequent item set are:
{A} ⇒ {E}
= (2/ 3)* 100 = 66.6% (Rejected)
{E} ⇒ {A}
= (2/ 4)* 100 = 50% (Rejected)
(iii) {A, C, E}
The all possible association rules from the above frequent item set are:
{A, C} ⇒ {E}
= (2/ 3)* 100 = 66.6% (Rejected)
{A, E} ⇒ {C}
= (2/ 2)* 100 = 100% (Selected)
{C, E} ⇒ {A}
= (2/ 3)* 100 = 66.6% (Rejected)
Among the rules calculated above, {A} ⇒ {C}, {C} ⇒ {A} and {A, E} ⇒ {C} satisfy the minimum confidence threshold of 70%, so these association rules are strong.
Exercise1: FP Growth Algorithm
Consider the below dataset and find frequent item sets and generate association rules for them. Assume that Minimum support count is 3 and minimum confident threshold (c = 60%).
| Transaction ID | Items |
|---|---|
| T1 | I1, I2, I3 |
| T2 | I2, I3, I4 |
| T3 | I4, I5 |
| T4 | I1, I2, I4 |
| T5 | I1, I2, I3, I5 |
| T6 | I1, I2, I3, I4 |
Exercise2: FP Growth Algorithm
Consider the below dataset and find frequent item sets Assume that Minimum support count is 3.
| Transaction ID | Items |
|---|---|
| T100 | {N, O, M, K, E, Y} |
| T200 | {E, O, N, K, D, Y} |
| T300 | {M, A, K, E} |
| T400 | {M, U, C, K, Y} |
| T500 | {K, O, O, C, I, E} |
Exercise3: FP Growth Algorithm
Consider the below dataset and find frequent item sets. Assume that Minimum support count is 2.
| TID | List of item_IDs |
|---|---|
| T100 | I1, I2, I5 |
| T200 | I2, I4 |
| T300 | I2, I3 |
| T400 | I1, I2, I4 |
| T500 | I1, I3 |
| T600 | I2, I3 |
| T700 | I1, I3 |
| T800 | I1, I2, I3, I5 |
| T900 | I1, I2, I3 |