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

# FP-tree on t1-t5 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-t1-t5
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-4

## Question

Use the data set of the previous question (transactions t1 to t5 below) with the same minimum support 2 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 | Items |
| --- | --- |
| t1 | {A, C, D} |
| t2 | {B, C, E} |
| t3 | {A, B, C, E} |
| t4 | {B, E} |
| t5 | {A, B, C, E} |

## Short answer

After dropping D (support 1), build FP-tree with header order B,C,E,A. FP-growth yields frequent itemsets (min sup=2): A:3, B:4, C:4, E:4; AB, AC, AE, BC, BE, CE; ABC, ABE, ACE, BCE; ABCE (15 total).

## Answer

Minimum support count = 2. Transactions: t1 {A, C, D}; t2 {B, C, E}; t3 {A, B, C, E}; t4 {B, E}; t5 {A, B, C, E}.

#### Step 1: counts and F-list
A 3, B 4, C 4, D 1, E 4. D is infrequent and dropped. Order of descending support (ties alphabetical): **B, C, E, A**.

Ordered transactions: t1 {C, A}; t2 {B, C, E}; t3 {B, C, E, A}; t4 {B, E}; t5 {B, C, E, A}.

#### Step 2: FP-tree after each transaction
```text
After t1:  null - C:1 - A:1

After t2:  null
            |-C:1 - A:1
            |-B:1 - C:1 - E:1

After t3:  null
            |-C:1 - A:1
            |-B:2 - C:2 - E:2 - A:1

After t4:  null
            |-C:1 - A:1
            |-B:3
               |-C:2 - E:2 - A:1
               |-E:1

After t5 (final tree):
           null
            |-C:1 - A:1
            |-B:4
               |-C:3 - E:3 - A:2
               |-E:1
```
Header table: B:4, C:4, E:4, A:3 with node-links (C has two nodes, A has two nodes under C and under E, E has two nodes).

#### Step 3: mining with FP-growth (bottom-up)
| Item | Conditional pattern base | Conditional FP-tree (min_sup 2) | Frequent patterns generated |
| --- | --- | --- | --- |
| A (3) | {B, C, E: 2}, {C: 1} | ⟨B:2, C:3, E:2⟩ (tree: B:2-C:2-E:2 and C:1) | {A, C}:3, {A, B}:2, {A, E}:2, {A, C, B}:2, {A, C, E}:2, {A, B, E}:2, {A, B, C, E}:2 |
| E (4) | {B, C: 3}, {B: 1} | ⟨B:4, C:3⟩ | {E, B}:4, {E, C}:3, {E, B, C}:3 |
| C (4) | {B: 3} | ⟨B:3⟩ | {C, B}:3 |
| B (4) | none | - | - |

Mining A in detail: with suffix A, the pattern base has items B:2, C:3, E:2, all ≥ 2. For A-E: base {B, C: 2} gives B:2, C:2, so A-E-C:2, A-E-B:2, and A-E-C-B:2. For A-C: base {B: 2} gives A-C-B:2.

**Answer: frequent itemsets (15): A:3, B:4, C:4, E:4; AB:2, AC:3, AE:2, BC:3, BE:4, CE:3; ABC:2, ABE:2, ACE:2, BCE:3; ABCE:2.** These are the same as obtained by Apriori, found with only two database scans and no candidate generation.

## Check yourself

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

1. What is the F-list order?
   A. B, C, E, A
   B. A, B, C, E
   C. D, A, B, C, E
   D. E, C, B, A
   Answer: A. B 4, C 4, E 4, A 3; D is infrequent and dropped. (Key point: F-list)

2. In the final tree, what is the count of node B under the root?
   A. 5
   B. 4
   C. 3
   D. 2
   Answer: B. t2, t3, t4 and t5 all start with B. (Key point: Tree construction)

3. What is the conditional pattern base of A?
   A. {B, C, E: 3}
   B. {B: 4}
   C. {B, C, E: 2}, {C: 1}
   D. {C: 3}, {E: 2}
   Answer: C. A has two nodes: under E with count 2 and under C with count 1. (Key point: Conditional base of A)

4. How do FP-growth results compare with Apriori's?
   A. Fewer itemsets, found faster
   B. More itemsets, since the tree includes D
   C. Same itemsets but needing four scans
   D. Same 15 frequent itemsets, found with two scans and no candidate generation
   Answer: D. Both algorithms are complete; FP-growth is more efficient. (Key point: Comparison)

## Related in Data Mining

- [FP-tree on HotDogs data](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-tree-hotdogs) — Data Mining, chapter 4
- [Apriori on t1-t5 with rules](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-t1-t5-rules) — Data Mining, chapter 4
- [Apriori on 8 transactions, 25% support](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-b65-transactions) — 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
- [Apriori on four transactions, support 2](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-y63-min-support-2) — 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