- Year not given
FP-tree on HotDogs data
Short answer
Build FP-tree with item order HotDogs, Chips, Coke, Buns, Ketchup, then mine conditional pattern bases. Frequent itemsets match Apriori: 10 itemsets including {Coke,Chips,HotDogs}:2. FP-Growth avoids candidate generation.
Use the data set of the HotDogs transaction table (previous question) with the same min_sup=33.34% to build FP-tree. Show for each transaction, how the tree evolves. Then use FP-Growth approach to discover the frequent item set from this FP tree.
| Transaction ID | Item set |
|---|---|
| TID1 | HotDogs, Buns, Ketchup |
| TID2 | HotDogs, Buns |
| TID3 | HotDogs, Coke, Chips |
| TID4 | Coke, Chips |
| TID5 | Chips, Ketchup |
| TID6 | HotDogs, Coke, Chips |
Assumption: min_sup = 33.34% of 6 transactions = 2 transactions.
Step 1: Frequent items and F-list
Counts: HotDogs 4, Chips 4, Coke 3, Buns 2, Ketchup 2. All are frequent. Order (descending count; the ties HotDogs/Chips and Buns/Ketchup are broken by order of first appearance): HotDogs, Chips, Coke, Buns, Ketchup.
Ordered transactions: TID1 {HotDogs, Buns, Ketchup}; TID2 {HotDogs, Buns}; TID3 {HotDogs, Chips, Coke}; TID4 {Chips, Coke}; TID5 {Chips, Ketchup}; TID6 {HotDogs, Chips, Coke}.
Step 2: FP-tree after each transaction (item:count)
After TID1 After TID2 After TID3
null null null
|-HotDogs:1 |-HotDogs:2 |-HotDogs:3
|-Buns:1 |-Buns:2 |-Buns:2
|-Ketchup:1 |-Ketchup:1 | |-Ketchup:1
|-Chips:1
|-Coke:1
After TID4 After TID5 After TID6 (final)
null null null
|-HotDogs:3 |-HotDogs:3 |-HotDogs:4
| |-Buns:2 | |-Buns:2 | |-Buns:2
| | |-Ketchup:1 | | |-Ketchup:1 | | |-Ketchup:1
| |-Chips:1 | |-Chips:1 | |-Chips:2
| |-Coke:1 | |-Coke:1 | |-Coke:2
|-Chips:1 |-Chips:2 |-Chips:2
|-Coke:1 |-Coke:1 |-Coke:1
|-Ketchup:1 |-Ketchup:1
Header table: HotDogs:4, Chips:4, Coke:3, Buns:2, Ketchup:2, each linked to its nodes (Ketchup, Chips and Coke have two nodes each).
Step 3: FP-growth mining (from the least frequent item upward)
| Item | Conditional pattern base | Conditional FP-tree | Frequent patterns |
|---|---|---|---|
| Ketchup (2) | {HotDogs, Buns: 1}, {Chips: 1} | each item has count 1 < 2, so empty | Ketchup:2 |
| Buns (2) | {HotDogs: 2} | ⟨HotDogs:2⟩ | Buns:2, {Buns, HotDogs}:2 |
| Coke (3) | {HotDogs, Chips: 2}, {Chips: 1} | ⟨Chips:3, HotDogs:2⟩ | Coke:3, {Coke, Chips}:3, {Coke, HotDogs}:2, {Coke, Chips, HotDogs}:2 |
| Chips (4) | {HotDogs: 2} | ⟨HotDogs:2⟩ | Chips:4, {Chips, HotDogs}:2 |
| HotDogs (4) | empty (child of root) | - | HotDogs:4 |
Answer: frequent itemsets are HotDogs:4, Chips:4, Coke:3, Buns:2, Ketchup:2; {HotDogs, Buns}:2, {Coke, Chips}:3, {Coke, HotDogs}:2, {Chips, HotDogs}:2; {Coke, Chips, HotDogs}:2. They are the same as those found by Apriori.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- FP-tree on t1-t5 data · Data Mining, chapter 4
- Apriori on HotDogs data with rules · Data Mining, chapter 4
- FP-Growth and Apriori disadvantage · Data Mining, chapter 4
- AVL delete then insert gives same tree? · Data Structure and Algorithm, chapter 6