机器学习-FPGROWTH算法(56页).ppt

1、机器学习-FP-GROWTH算法,李家豪,1,目录,2,回忆Apriori算法,3,项集：项的集合称为项集，即商品的组合。k项集：k件商品的组合，不关心商品件数，仅商品的种类。频繁项集：如果项集的相对支持度满足给定的最小支持度阈值，则该项集是频繁项集。强关联规则:满足给定支持度和置信度阈值的关联规则支持度：support(A-B)=P(AB)置信度：confidence(A-B)=P(A|B),回忆Apriori算法,4,回忆Apriori算法,5,Apriori算法的挑战,6,挑战 多次数据库扫描 巨大数量的候补项集 繁琐的支持度计算改善Apriori:基本想法 减少扫描数据库的次数 减少候

2、选项集的数量 简化候选项集的支持度计算,FP-GROWTH算法优点,相比Apriori算法需要多次扫描数据库，FPGrowth只需要对数据库扫描2次。第1次扫描事务数据库获得频繁1项集。第2次扫描建立一颗FP-Tree树。,7,FP-GROWTH算法原理-实例1,要找总是一起购买的商品，比如薯片，鸡蛋就是一条频繁模式(规律)。,8,FP-GROWTH算法原理-实例1-统计频次,Step1:先扫描数据库，统计所有商品的出现次数(频数)，然后按照频数递减排序，删除频数小于最小支持度的商品。设最小支持度数为：minsup=4统计频数：牛奶6，鸡蛋7，面包7，薯片7，爆米花2，啤酒4，黄油2.降序排序

3、：薯片7,鸡蛋7,面包7,牛奶6,啤酒4（删除小于minsup的商品）,9,频繁1项集，记为F1,FP-GROWTH算法原理-实例1-重新排序,10,Step2:对每一条数据记录，按照F1重新排序。,FP-GROWTH算法原理-实例1-建立FP树,10,Step3：把第二步重新排序后的记录，插入到fp-tree中Step3.1：插入第一条（第一步有一个虚的根节点）,FP-GROWTH算法原理-实例1-建立FP树,10,Step3.2：插入第二条。根结点不管，然后插入薯片，在step3.1的基础上+1，则记为2；同理鸡蛋记为2；啤酒在step3.1的树上是没有的，那么就开一个分支。,FP-GRO

4、WTH算法原理-实例1-建立FP树,10,Step3.3：插入第三条,FP-GROWTH算法原理-实例1-建立FP树,10,同理，剩余记录依次插入fp-tree中。,FP-GROWTH算法原理-实例1-建立FP树,10,图中左边的一列叫做头指针表，树中相同名称的节点要链接起来，链表的第一个元素就是头指针表里的元素。,虚线连接起来的表示同一个商品，各个连接的数字加起来就是该商品出现的总次数。,FP-GROWTH算法原理-实例1-挖掘频繁项集,Step4：从FP-Tree中找出频繁项集。遍历表头项中的每一项（以“牛奶：6”为例），从FP-Tree中找到所有的“牛奶”结点，向上遍历它的祖先结点，得到

5、4条路径，如表所示。,10,FP-GROWTH算法原理-实例1-挖掘频繁项集,Step4：从FP-Tree中找出频繁项集。对于每一条路径上的节点，其count都设置为牛奶的count（路径中最末尾的商品数）,10,FP-GROWTH算法原理-实例1-挖掘频繁项集,Step4：从FP-Tree中找出频繁项集。因为每一项末尾都是牛奶，可以把牛奶去掉，得到条件模式基，此时的后缀模式是：牛奶。,10,FP-GROWTH算法原理-实例2,把例子简化一下，请看以下实例2,10,FP-GROWTH算法原理-实例2-统计频次,先扫描数据库，统计所有商品的出现次数(频数)定义min_sup=2，按照频数递减排序

6、，删除频数小于最小支持度的商品。重新排列得到频繁1-项目集F,10,FP-GROWTH算法原理-实例2-重新排序,10,FP-GROWTH算法原理-实例2-创建根结点和频繁项目表,10,Null,FP-GROWTH算法原理-实例2-加入第一个事务(I2,I1,I5),10,FP-GROWTH算法原理-实例2-加入第二个事务(I2,I4),10,FP-GROWTH算法原理-实例2-加入第三个事务(I2,I3),10,FP-GROWTH算法原理-实例2-加入第四个事务(I2,I1,I4),10,FP-GROWTH算法原理-实例2-加入第五个事务(I1,I3),10,FP-GROWTH算法原理-实例2-加入第六个事务(I2,I3),10,FP-GROWTH算法原理-实例2-加入第七个事务(I1,I3),10,FP-GROWTH算法原理-实例2-加入第八个事务(I2,I1,I3,I5),10,FP-GROWTH算法原理-实例2-加入第九个事务(I2,I1,I3),10,FP-GROWTH算法原理-实例2-挖掘频繁项集,首先考虑I5，得到条件模式基：、构造条件FP-Tree,10,得到I5频繁项