FP-Growth represents the frequent transactions in a consolidated data structure called FP Tree, and the frequent patterns are mined using the FP Tree.
There are two major steps while mining frequent patterns using the FP-Growth algorithm, building the FP Tree, and deriving frequent patterns from the FP Tree.
Let's assume a database with the following information. For each transaction, we have a list of items that were sold.
|
Transaction ID |
Items |
|---|---|
|
1 |
Fish, Milk, Egg, Bread, and Biscuit |
|
2 |
Lemon, Fish, Bread, and Tea |
|
3 |
Fish and Milk |
|
4 |
Egg and Tea |
|
5 |
Fish, Biscuit, Bread, and Cup |
Let the minimum support be 2. We first compute the frequency of occurrence of each item in the transaction table. If you are not able to recall what is meant by support, please revisit the section Frequent pattern mining in Chapter 2, Core Concepts in Machine Learning.
The frequency of occurrence of items is as shown here:
|
Items |
Frequency |
|---|---|
|
Fish |
4 |
|
Milk |
2 |
|
Egg |
2 |
|
Bread ... |