FP-Growth算法讲解

讲解人：XXXFrequentPatternAlgorithm频繁模式算法FrequentPatternAlgorithm频繁模式算法TidItems1牛奶,鸡蛋,面包,薯片2鸡蛋,爆米花,薯片,啤酒3鸡蛋,面包,薯片4牛奶,鸡蛋,面包,爆米花,薯片,啤酒5牛奶,面包,啤酒6鸡蛋,面包,啤酒7牛奶,面包,薯片8牛奶,鸡蛋,面包,黄油,薯片9牛奶,鸡蛋,黄油,薯片ItemsTimes啤酒,鸡蛋3啤酒,面包3牛奶,鸡蛋4牛奶,鸡蛋,面包3牛奶,鸡蛋,面包,薯片3牛奶,鸡蛋,薯片4牛奶,面包5牛奶,面包,薯片4牛奶,薯片5鸡蛋,面包5鸡蛋,面包,薯片4鸡蛋,薯片6面包,薯片5频繁模式算法FrequentPatternAlgorithm频繁模式算法项与项集基本概念这是一个集合的概念，在一篮子商品中的一件消费品即为一项（Item），则若干项的集合为项集，如{尿布，面包}构成一个二元项集。支持度支持度是指在所有项集中{X,Y}出现的可能性，即项集中同时含有X和Y的概率。通过设定最小阈值（minsup），剔除“出镜率”较低的无意义规则设定最小阈值为5%，由于{尿布，啤酒}的支持度为800/10000=8%，满足基本输了要求，成为频繁项集，保留规则；而{尿布，面包}的支持度为100/10000=1%，被剔除。有10000个消费者购买了商品，其中购买尿布1000个，购买啤酒2000个，购买面包500个，同时购买尿布和面包800个，同时购买尿布和面包100个。FrequentPatternAlgorithm频繁模式算法1FP-Growth算法演示-------构造FP树TidItems1I1,I2.I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3事务数据库的建立扫描事务数据库得到频繁项目集FI1I2I3I4I567622定义minsup=20%,即最小支持度为2,重新排列FI2I1I3I4I576622FrequentPatternAlgorithm频繁模式算法TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3重新调整事务数据库FrequentPatternAlgorithm频繁模式算法构建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:1742FrequentPatternAlgorithm频繁模式算法rootI2:I1:I5:14I4:1I3:2I4:1I1:2I3:2I3:2I5:17FP树1FP-Growth算法演示----FP-树挖掘挖掘从表头header的最后一个项开始I2I1I3I4I576622FrequentPatternAlgorithm频繁模式算法rootI2:I1:I5:14I4:1I3:2I4:1I1:2I3:2I3:2I5:17挖掘I5FP树在FP树中可以看到，从根节点到i5:1的路径有两条：•i2:7--i1:4--i5:1•i2:7--i14--i3:2--i5:1i2:7--i1:4和i2:7--i14--i3:2因为最终到达的节点肯定是i5，所以将i5省略就是i5的条件模式基，记为{i2,i1:1}{i2,i1,i3:1}为什么每个条件模式基的计数为1呢？虽然i2和i1的计数都很大，但是由于i5的计数为1，最终到达i5的重复次数也只能为1。所以条件模式基的计数是根据路径中节点的最小计数来决定的。FrequentPatternAlgorithm频繁模式算法rootI2:I1:2I3:2挖掘I5条件FP树1条件模式基：{i2,i1:1}{i2,i1,i3:1}根据条件模式基，我们可以得到该商品的条件FP树因为i3:1x小于最小支持度2,所以讲i3:1省略不计,i5的条件FP树记为{i2:2,I1:2}项条件模式基条件FP树产生的频繁模式I5{{I2I1:1}，{I2I1I3:1}}I2:2,I1:2{I2I5:2},{I1I5:2},{I2I1I5:2}I4{{I2I1:1},{I2:1}}I2:2{I2I4:2}I3{{I2I1:2},{I2:2},{I1:2}}I2:4,I1:2,I1:2{I2I3:4},{I1I3:4},{I2I1I3:2}I1{{I2:4}}I2:4{I2I1:4}FrequentPatternAlgorithm频繁模式算法根据条件FP树，我们可以进行全排列组合，得到挖掘出来的频繁模式（这里要将商品本身，如i5也算进去，每个商品挖掘出来的频繁模式必然包括这商品本身）