FP-Growth算法讲解

1、讲解人： XXXFrequent Pattern Algorithm频繁模式算法Frequent Pattern Algorithm 频繁模式算法TidItems1牛奶,鸡蛋,面包,薯片2鸡蛋,爆米花,薯片,啤酒3鸡蛋,面包,薯片4牛奶,鸡蛋,面包,爆米花,薯片,啤酒5牛奶,面包,啤酒6鸡蛋,面包,啤酒7牛奶,面包,薯片8牛奶,鸡蛋,面包,黄油,薯片9牛奶,鸡蛋,黄油,薯片ItemsTimes啤酒,鸡蛋3啤酒,面包3牛奶,鸡蛋4牛奶,鸡蛋,面包3牛奶,鸡蛋,面包,薯片3牛奶,鸡蛋,薯片4牛奶,面包5牛奶,面包,薯片4牛奶,薯片5鸡蛋,面包5鸡蛋,面包,薯片4鸡蛋,薯片6面包,薯片5频繁模式算法

2、Frequent Pattern Algorithm 频繁模式算法项与项集基本概念这是一个集合的概念，在一篮子商品中的一件消费品即为一项（Item），则若干项的集合为项集，如尿布，面包构成一个二元项集。支持度 支持度是指在所有项集中X, Y出现的可能性，即项集中同时含有X和Y的概率。通过设定最小阈值（minsup），剔除“出镜率”较低的无意义规则设定最小阈值为5%，由于尿布，啤酒的支持度为800/10000=8%，满足基本输了要求，成为频繁项集，保留规则；而尿布，面包的支持度为100/10000=1%，被剔除。 有10000个消费者购买了商品，其中购买尿布1000个，购买啤酒2000个，购买面

3、包500个，同时购买尿布和面包800个，同时购买尿布和面包100个。Frequent Pattern Algorithm 频繁模式算法1FP-Growth算法演示-构造FP树TidItems1I1,I2.I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3事务数据库的建立扫描事务数据库得到频繁项目集FI1I2I3I4I567622定义minsup=20%,即最小支持度为2,重新排列FI2I1I3I4I576622Frequent Pattern Algorithm 频繁模式算法TidItems1I2,I1,I52I2,I4

4、3I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3重新调整事务数据库Frequent Pattern Algorithm 频繁模式算法构建FP树TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3rootI2:1I1:2I5:11I4:13I3:142I4:1I1: 1I3: 1522263I3:1I5:1742Frequent Pattern Algorithm 频繁模式算法rootI2:I1:I5:14I4:1I3:2I4:1I1:

5、 2I3: 2I3:2I5:17FP树1FP-Growth算法演示-FP-树挖掘挖掘从表头header的最后一个项开始I2I1I3I4I576622Frequent Pattern Algorithm 频繁模式算法rootI2:I1:I5:14I4:1I3:2I4:1I1: 2I3: 2I3:2I5:17挖掘I5FP树 在FP树中可以看到，从根节点到i5:1的路径有两条：i2:7-i1:4-i5:1i2:7-i14-i3:2-i5:1 i2:7-i1:4和i2:7-i14-i3:2因为最终到达的节点肯定是i5，所以将i5省略就是i5的条件模式基，记为i2,i1:1i2,i1,i3:1为什么每个

6、条件模式基的计数为1呢？ 虽然i2和i1的计数都很大，但是由于i5的计数为1，最终到达i5的重复次数也只能为1。所以条件模式基的计数是根据路径中节点的最小计数来决定的。Frequent Pattern Algorithm 频繁模式算法rootI2:I1:2I3:2挖掘I5条件FP树1条件模式基：i2,i1:1i2,i1,i3:1根据条件模式基，我们可以得到该商品的条件FP树因为i3:1x小于最小支持度2,所以讲i3:1省略不计,i5的条件FP树记为 i2:2,I1:2项条件模式基条件FP树产生的频繁模式I5I2 I1:1，I2 I1 I3:1I2 I5:2, I1 I5:2, I2 I1 I5:2I4I2 I1:1,I2:1I2 I4:2I3I2 I1 :2,I2:2,I1:2,I2 I3:4,I1 I3:4,I2 I1 I3:2I1I2:4I2 I1:4Frequen