---
title: "FP-tree on HotDogs data"
subject: "Data Mining"
chapter: 4
key: "semester_7/data_mining:fp-tree-hotdogs"
source: https://www.bctengineer.com/q/semester_7/data_mining/fp-tree-hotdogs
site: BCT Engineering
---

# FP-tree on HotDogs data

Data Mining · Chapter 4: Association Analysis

- Asked in: year not given
- Video: [1. Frequent Pattern (FP) Growth Algorithm Association Rule Mining Solved Example by Mahesh Huddar](https://www.youtube.com/watch?v=7oGz4PCp9jI) — Mahesh Huddar
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/data_mining/fp-tree-hotdogs
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-4

## Question

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 |

## 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.

## Answer

**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)
```text
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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the F-list for the hot dogs data?
   A. HotDogs, Chips, Coke, Buns, Ketchup
   B. Ketchup, Buns, Coke, Chips, HotDogs
   C. Buns, Ketchup, Coke, Chips, HotDogs
   D. HotDogs, Buns, Ketchup, Coke, Chips
   Answer: A. Items are sorted by descending count, with ties broken by first appearance. (Key point: F-list)

2. In the final tree, what is the count of the HotDogs node under root?
   A. 6
   B. 4
   C. 2
   D. 3
   Answer: B. Four transactions (TID1, 2, 3, 6) begin with HotDogs. (Key point: Tree sharing)

3. What is the conditional pattern base of Coke?
   A. {HotDogs: 4}
   B. {Buns: 2}, {Ketchup: 1}
   C. {HotDogs, Chips: 2}, {Chips: 1}
   D. {Chips: 4}
   Answer: C. Coke is reached by HotDogs-Chips twice and by Chips once. (Key point: Mining Coke)

4. What is the frequent pattern found from Coke's conditional tree?
   A. {Coke, Buns}:2
   B. {Coke, Ketchup}:2
   C. {Coke, Chips}:4
   D. {Coke, Chips}:3, {Coke, HotDogs}:2, {Coke, Chips, HotDogs}:2
   Answer: D. Chips has count 3 and HotDogs 2 in the conditional tree. (Key point: Result)

## Related in Data Mining

- [FP-tree on t1-t5 data](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-tree-t1-t5) — Data Mining, chapter 4
- [Apriori on HotDogs data with rules](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-hotdogs-rules) — Data Mining, chapter 4
- [FP-Growth and Apriori disadvantage](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-growth-vs-apriori) — Data Mining, chapter 4

## Related in other subjects

- [AVL delete then insert gives same tree?](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-delete-insert-original) — Data Structure and Algorithm, chapter 6