Frequent Pattern (FP) Growth Algorithm Solved Example
This article discusses how to use the Frequent Pattern (FP) Growth Algorithm to construct Frequent Pattern Tree and frequent Pattern Rules with simple.
Video Tutorial:
The given data is a hypothetical dataset of transactions with each letter representing an item. The minimum support given is 3.
| TID | Items Bought |
| 100 | f, a, c, d, g, i, m, p |
| 200 | a, b, c, f, l, m, o |
| 300 | b, f, h, j, o |
| 400 | b, c, k, s, p |
| 500 | a, f, c, e, l, p, m, n |
In the frequent pattern growth algorithm, first, we find the frequency of each item. The following table gives the frequency of each item in the given data.
| Item | Frequency | Item | Frequency |
| a | 3 | j | 1 |
| b | 3 | k | 1 |
| c | 4 | l | 2 |
| d | 1 | m | 3 |
| e | 1 | n | 1 |
| f | 4 | o | 2 |
| g | 1 | p | 3 |
| h | 1 | s | 1 |
| i | 1 |
A Frequent Pattern set (L) is built, which will contain all the elements whose frequency is greater than or equal to the minimum support.
These elements are stored in descending order of their respective frequencies.
As minimum support is 3.
After insertion of the relevant items, the set L looks like this:-
L = { (f:4), (c:4), (a:3), (b:3), (m:3), (p:3) }
Now, for each transaction, the respective Ordered-Item set is built.
Frequent Pattern set L = { (f:4), (c:4), (a:3), (b:3), (m:3), (p:3) }
| TID | Items Bought | (Ordered) Frequent Items |
| 100 | f, a, c, d, g, i, m, p | f, c, a, m, p |
| 200 | a, b, c, f, l, m, o | f, c, a, b, m |
| 300 | b, f, h, j, o | f, b |
| 400 | b, c, k, s, p | c, b, p |
| 500 | a, f, c, e, l, p, m, n | f, c, a, m, p |
Now, all the Ordered-Item sets are inserted into a Trie Data Structure (frequent pattern tree).
Now, for each item, the Conditional Pattern Base is computed which is the path labels of all the paths which lead to any node of the given item in the frequent-pattern tree.
| Item | Conditional Pattern Base |
| p | {{f, c, a, m : 2}, {c, b : 1}} |
| m | {{f, c, a : 2}, {f, c, a, b : 1}} |
| b | {{f, c, a : 1}, {f : 1}, {c : 1}} |
| a | {{f, c : 3}} |
| c | {{f : 3}} |
| f | Φ |
Now for each item, the Conditional Frequent Pattern Tree is built. It is done by taking the set of elements that 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.
| Item | Conditional Pattern Base | Conditional FP-Tree |
| p | {{f, c, a, m : 2}, {c, b : 1}} | {c : 3} |
| m | {{f, c, a : 2}, {f, c, a, b : 1}} | {f, c, a :3} |
| b | {{f, c, a : 1}, {f : 1}, {c : 1}} | Φ |
| a | {{f, c : 3}} | {f, c : 3} |
| c | {{f : 3}} | {f : 3} |
| f | Φ | Φ |
From the Conditional Frequent Pattern tree, the Frequent Pattern rules are generated by pairing the items of the Conditional Frequent Pattern Tree set to the corresponding item.
| Item | Conditional Pattern Base | Conditional FP-Tree | Frequent Patterns Generated |
| p | {{f, c, a, m : 2}, {c, b : 1}} | {c : 3} | {<c, p : 3>} |
| m | {{f, c, a : 2}, {f, c, a, b : 1}} | {f, c, a :3} | { <f, m : 3>, <c, m : 3> <a, m : 3>, <f, c, m : 3> <f, a, m : 3>, <c, a, m :3>} |
| b | {{f, c, a : 1}, {f : 1}, {c : 1}} | Φ | {} |
| a | {{f, c : 3}} | {f, c : 3} | {<f, a : 3>, <c, a : 3>, <f, c, a:3>} |
| c | {{f : 3}} | {f : 3} | { <f, c : 3>} |
| f | Φ | Φ | {} |
For each row, two types of association rules can be inferred.
For example for the first row which contains the element, the rules K -> Y and Y -> K can be inferred.
To determine the valid rule, the confidence of both the rules is calculated and the one with confidence greater than or equal to the minimum confidence value is retained.
Summary
This article discusses the Frequent Pattern (FP) Growth Algorithm Solved Example. Don’t forget to give your comment and Subscribe to our YouTube channel for more videos and like the Facebook page for regular updates.