Skip to main content

FP-tree on t1-t5 data

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

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 idItems
t1{A, C, D}
t2{B, C, E}
t3{A, B, C, E}
t4{B, E}
t5{A, B, C, E}

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

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)

ItemConditional pattern baseConditional 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.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Mining chapter 4 questions →