Frequent Pattern Growth Mining Algorithm.pdf

Frequent Pattern Growth Mining Algorithm in Data Mining

1. FP-Growth Algorithm
Consider the following database containing five transactions. Let min_sup=50%
TID Item
T1 B, C, E, J
T2 B, C, J
T3 B, M, Y
T4 B, J, M
T5 C, J, M
Mine frequent itemset using FP-growth algorithm.
Solution
Given that, min_sup=50%
Therefore, Sup_count=(50x5)/100=2.5=3
Step-01: Count support for each item
Item Sup_count
B 4
C 3
E 1
J 4
M 3
Y 1
Step-02: The frequent items are now sorted according to their frequency
Item Sup_count
B 4
J 4
C 3
M 3
Step-03: Rearrange each transaction of the database according to the order of the item in the list
TID Item Sorted Item
T1 B, C, E, J B, J, C
T2 B, C, J B, J, C
T3 B, M, Y B, M
T4 B, J, M B, J, M
T5 C, J, M J, C, M

2. Figure: FP-growth tree
Item Conditional Pattern Base Conditional FP-tree
Frequent Item
Generated
M {(B, J:1), (B:1), (J, C: 1)}
C {(B, J: 2), (J: 1)} (J: 3) (C, J)
J {(B: 3)} (B: 3) (B, J)