文档介绍：第10讲 关联规则分析——FP-growth
-growth算法基本概念
2. FP-growth算法实例
3. FP-growth算法优点
1. FP-growth算法基本概念
Apriori 算法通过连接步和剪枝步找出频繁项集。
Apriori 算法的缺点：
多次扫描数据库，产生巨大数量的候选集，繁琐的支持度计算......
Frequent Pattern
FP-growth 算法不产生候选项集，而是采用分而治之的策略：
首先，压缩数据库，并将频繁项放入频繁模式树（FP- 树），它仍保留项集的关联信息。
然后，将压缩数据库分成多个条件数据库，每个条件数据库关联到一个频繁项集，并分开来对其进行挖掘。
该算法只需要扫描两次数据库。
第一次扫描，得到所有频繁项及其支持度计数，并在每个事务中将频繁项依据支持度计数进行降序排列；
第二次扫描，将每个事务的项都合并进FP- 树，对在不同事务中出现的公共项进行计数。
-growth算法实例
设最小支持度为3 第1次扫描，得到频繁项列表， 并将频繁项重新排序
TID
Items
1
f,a,c,d,g,i,m,p
2
a,b,c,f,l,m,o
3
b,f,h,j,o
4
b,c,k,s,p
5
a,f,c,e,l,p,m,n
TID
sorted
1
f,c,a,m,p
2
f,c,a,b,m
3
f,b
4
c,b,p
5
f,c,a,m,p
TID
sorted
1
f,c,a,m,p
2
f,c,a,b,m
3
f,b
4
c,b,p
5
f,c,a,m,p
Item
count
f
1
c
1
a
1
b
0
m
1
p
1
TID
sorted
1
f,c,a,m,p
2
f,c,a,b,m
3
f,b
4
c,b,p
5
f,c,a,m,p
Item
count
f
1
c
1
a
1
b
1
m
1
p
0
扫描第3个事务时，得到分支：
<(𝑓:1),(𝑏:1)>
TID
sorted
1
f,c,a,m,p
2
f,c,a,b,m
3
f,b
4
c,b,p
5
f,c,a,m,p
Item
count
f
1
c
0
a
0
b
1
m
0
p
0
扫描第4个事务时，得到分支：
<(c:1),(𝑏:1),(p:1)>
TID
sorted
1
f,c,a,m,p
2
f,c,a,b,m
3
f,b
4
c,b,p
5
f,c,a,m,p
Item
count
f
0
c
1
a
0
b
1
m
0
p
1
TID
sorted
1
f,c,a,m,p
2
f,c,a,b,m
3
f,b
4
c,b,p
5
f,c,a,m,p
Item
count
f
1
c
1
a
1
b
0
m
1
p
1
挖掘数据库中的频繁项集→挖掘FP-树:
由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基。条件模式基是一个子数据库，由FP- 树中与该后缀模式一起出现的前缀路径集组成。然后由此构造频繁模式的条件FP- 树，并递归地在该树上进行挖掘。
Item
count
f
4
c
4
a
3
b
3
m
3
p
3