dm.cs.tu-dortmund.de/mlbits/frequent-pattern-fpgrowth/
Frequent Pattern Growth – Lecture Notes
a
4
g
1
m
4
b
4
h
1
n
2
c
5
i
2
o
2
d
1
j
2
p
3
e
1
k
1
s
2
f
6
l
2
→
minsupp=3:
item
f
6
c
5
a
4
b
4
m
4
p
3
→
Reduced & reordered:
tid
frequent items
1
\(\{ f, c, a, m, p\}\)
2
\(\{ f, c, a, b \}\)
3 [...] frequent itemsets
E.g., transactions \(\{ A, B, C, D\} \times 3\) , \(\{ A, B, C, E\} \times 2\) , \(\{ A, E\} \times 2\) , and \(\{ D\} \times 1\) :
The FP-tree is a compressed summary of the transaction database [...] parallel (or distributed), and merged.
Construction of an FP-tree /2
Initial transactions:
tid
items
1
\(\{ a, c, d, f, g, i, m, p\}\)
2
\(\{ a, b, c, f, l, o \}\)
3
\(\{ b, f, h, j, o \}\)
4
\(\{ b, c, …
