FP-growth mines frequent itemsets for association rules by compressing transactions into a frequent pattern tree (FP-tree). It improves on Apriori by avoiding explicit candidate generation, reducing the costly computation associated with large datasets. section 4.6 section 4.11
Build and mine an FP-tree through these steps:
- Scan all transactions and count each item's frequency or support count. section 4.6
- Order items by descending frequency, allowing either order when frequencies tie. section 4.6
- Create a NULL root, then insert each transaction in the shared frequency order; reuse existing paths and increase node counts. section 4.6
- Derive conditional pattern bases and conditional FP-trees, then generate frequent patterns for each item. section 4.6
Nine-transaction grocery dataset
For transactions containing Apples, Milk, Eggs, Cheese, and Bread, the support counts are Milk 7, Apples 6, Bread 6, Cheese 2, and Eggs 2. Milk therefore leads the ordering; shared transaction prefixes are represented as branches beneath the NULL root. Conditional mining produces patterns such as Milk-Cheese, Milk-Bread, Apples-Bread, and Milk-Apples-Bread. section 4.6
Table 4.7 Dataset to understand the F-P algorithm
|
Transactions
|
Item sets
|
|---|---|
|
T1
|
Apples, Milk, Eggs
|
|
T2
|
Milk, Cheese
|
|
T3
|
Milk, Bread
|
|
T4
|
Apples, Milk, Cheese
|
|
T5
|
Apples, Bread
|
|
T6
|
Milk, Bread
|
|
T7
|
Apples, Bread
|
|
T8
|
Apples, Milk, Bread, Eggs
|
|
T9
|
Apples, Milk, Bread
|
Use the transaction table to trace frequency counting, item ordering, and insertion of each invoice into the tree. section 4.6
Table 4.9 Table for the F-P algorithm
|
Items
|
Conditional pattern base
|
Conditional F-P tree
|
Frequent pattern generated
|
|---|---|---|---|
|
Cheese
|
|||
|
Bread
|
|||
|
Eggs
|
|||
|
Apples
|
Use the conditional-pattern table to inspect how each item yields a conditional pattern base, conditional FP-tree, and frequent patterns. section 4.6
