A frequent pattern tree (FP tree) represents transaction data as a prefix tree. Shared item sequences are merged, while node counts record item frequencies, reducing the need to generate candidate item sets. section 4.6 section 4.11
Construct an FP tree by following these steps:
- Scan all transactions and count each item's occurrences, producing support counts. section 4.6
- Order items by descending frequency; break equal-frequency ties arbitrarily. section 4.6
- Create a NULL root, then insert each transaction in frequency order, extending existing paths and increasing their counts. section 4.6
- Derive conditional pattern bases and conditional FP trees to generate frequent patterns. 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 initial branch; later transactions reuse shared paths and increment node counts.
