机器学习-FPGROWTH算法教学教材.ppt

《机器学习-FPGROWTH算法教学教材.ppt》由会员分享，可在线阅读，更多相关《机器学习-FPGROWTH算法教学教材.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、-GROWTH算法优点相比Apriori算法需要多次扫描数据库，FPGrowth只需要对数据库扫描2次。第1次扫描事务数据库获得频繁1项集。第2次扫描建立一颗FP-Tree树。6FP-GROWTH算法原理-实例1要找总是一起购买的商品，比如薯片，鸡蛋就是一条频繁模式(规律)。IDItems1牛奶，鸡蛋，面包，薯片2鸡蛋，爆米花，薯片，啤酒3牛奶，面包，啤酒4牛奶，鸡蛋，面包，爆米花，薯片，啤酒5鸡蛋，面包，薯片6鸡蛋，面包，啤酒7牛奶，面包，薯片8牛奶，鸡蛋，面包，黄油，薯片9牛奶，鸡蛋，黄油，薯片7FP-GROWTH算法原理-实例1-统计频次Step1:先扫描数据库，统计所有商品的出现次数(

3、频数)，然后按照频数递减排序，删除频数小于最小支持度的商品。设最小支持度数为：minsup=4统计频数：牛奶6，鸡蛋7，面包7，薯片7，爆米花2，啤酒4，黄油2.降序排序：薯片7,鸡蛋7,面包7,牛奶6,啤酒4（删除小于minsup的商品）IDItems1牛奶，鸡蛋，面包，薯片2鸡蛋，爆米花，薯片，啤酒3牛奶，面包，啤酒4牛奶，鸡蛋，面包，爆米花，薯片，啤酒5鸡蛋，面包，薯片6鸡蛋，面包，啤酒7牛奶，面包，薯片8牛奶，鸡蛋，面包，黄油，薯片9牛奶，鸡蛋，黄油，薯片 频繁1项集，记为F18FP-GROWTH算法原理-实例1-重新排序IDItems1牛奶，鸡蛋，面包，薯片2鸡蛋，爆米花，薯片，啤酒

4、3牛奶，面包，啤酒4牛奶，鸡蛋，面包，爆米花，薯片，啤酒5鸡蛋，面包，薯片6鸡蛋，面包，啤酒7牛奶，面包，薯片8牛奶，鸡蛋，面包，黄油，薯片9牛奶，鸡蛋，黄油，薯片IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step2:对每一条数据记录，按照F1重新排序。9FP-GROWTH算法原理-实例1-建立FP树IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒

5、7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step3：把第二步重新排序后的记录，插入到fp-tree中Step3.1：插入第一条（第一步有一个虚的根节点）10FP-GROWTH算法原理-实例1-建立FP树IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step3.2：插入第二条。根结点不管，然后插入薯片，在step3.1的基础上+1，则记为2；同理鸡蛋记为2；啤酒在step3.1的树上是没有的，那么就开一个分支。11FP-GR

6、OWTH算法原理-实例1-建立FP树IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step3.3：插入第三条12FP-GROWTH算法原理-实例1-建立FP树IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶同理，剩余记录依次插入fp-tree中。13FP-GROWTH算法原理-实例1-建立FP

7、树图中左边的一列叫做头指针表，树中相同名称的节点要链接起来，链表的第一个元素就是头指针表里的元素。虚线连接起来的表示同一个商品，各个连接的数字加起来就是该商品出现的总次数。14FP-GROWTH算法原理-实例1-挖掘频繁项集Step4：从FP-Tree中找出频繁项集。遍历表头项中的每一项（以“牛奶：6”为例），从FP-Tree中找到所有的“牛奶”结点，向上遍历它的祖先结点，得到4条路径，如表所示。15FP-GROWTH算法原理-实例1-挖掘频繁项集Step4：从FP-Tree中找出频繁项集。对于每一条路径上的节点，其count都设置为牛奶的count（路径中最末尾的商品数）16FP-GROWT

8、H算法原理-实例1-挖掘频繁项集Step4：从FP-Tree中找出频繁项集。因为每一项末尾都是牛奶，可以把牛奶去掉，得到条件模式基，此时的后缀模式是：牛奶。17FP-GROWTH算法原理-实例2把例子简化一下，请看以下实例2TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I318FP-GROWTH算法原理-实例2-统计频次先扫描数据库，统计所有商品的出现次数(频数)定义min_sup=2，按照频数递减排序，删除频数小于最小支持度的商品。重新排列得到频繁1-项目集FI1I2I3I4I567622

9、I2I1I3I4I57662219FP-GROWTH算法原理-实例2-重新排序I27I16I36I42I52TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I320FP-GROWTH算法原理-实例2-创建根结点和频繁项目表Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNull21FP-GROWTH算法原理-实例2-加入第一个事务(I2,I1,I5)22FP-GROWTH算法原理-实例2-加入第二个事务(I2,I4)23FP-GROWTH算法原理

10、-实例2-加入第三个事务(I2,I3)24FP-GROWTH算法原理-实例2-加入第四个事务(I2,I1,I4)25FP-GROWTH算法原理-实例2-加入第五个事务(I1,I3)26FP-GROWTH算法原理-实例2-加入第六个事务(I2,I3)27FP-GROWTH算法原理-实例2-加入第七个事务(I1,I3)28FP-GROWTH算法原理-实例2-加入第八个事务(I2,I1,I3,I5)29FP-GROWTH算法原理-实例2-加入第九个事务(I2,I1,I3)30FP-GROWTH算法原理-实例2-挖掘频繁项集首先考虑I5，得到条件模式基：、构造条件FP-Tree得到I5频繁项集：I2,

11、I5,I1,I5,I2,I1,I531FP-GROWTH算法原理-实例2-挖掘频繁项集接着考虑I4，得到条件模式基：、构造条件FP-Tree得到I4频繁项集：I2,I432FP-GROWTH算法原理-实例2-挖掘频繁项集然后考虑I3，得到条件模式基：、构造条件FP-Tree由于此树不是单分支路径，因此需要递归挖掘I333FP-GROWTH算法原理-实例2-挖掘频繁项集递归考虑I3，此时得到I1条件模式基,即I1,I3的条件模式基为构造条件FP-Tree得到I3的频繁项目集I2,I3,I1,I3,I2,I1,I334FP-GROWTH算法原理-实例2-挖掘频繁项集最后考虑I1，得到条件模式基：构

12、造条件FP-Tree得到I1的频繁项目集：I2,I135FP-GROWTH算法实现-数据处理项集e,m,q,s,t,y,x,zx,s,r,o,ns,u,t,w,v,y,x,zq,p,r,t,y,x,z h,r,z,p,jz格式化处理36代码实现-FP树数据结构37代码实现-构造FP树步骤38代码实现-构造FP树39代码实现-构造FP树40代码实现-构造FP树（updateTree函数）41代码实现-构造FP树（updateHeader函数）42代码实现-构造FP树（验证）43代码实现-挖掘频繁项集步骤从构建好的FP树中抽取频繁项集的步骤如下：(1)从FP树中获取条件模式基；(2)利用条件模式基

13、，构建一个条件FP树；(3)迭代重复(1)(2)，直到树包含一个元素项为止。44条件模式基定义条件模式基是以所查找元素项为结尾的路径集合所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径前缀路径。简而言之，一条前缀路径就是介于所查找元素项与树根节点之间的所有内容。每一个频繁项的所有前缀路径（条件模式基）：45代码实现-抽取条件模式基eg：t的第1条前缀路径prefixPath=t,s,y,x,z；46代码实现-抽取条件模式基47代码实现-抽取条件模式基（验证）48代码实现-创建条件FP树49代码实现-创建条件FP树50代码实现-运行51示例：从新闻网站点击流中挖掘新闻报道-数据格式52示例：从新闻网站点击流中挖掘新闻报道-代码在源数据集合中，包含将近100w条记录，该文件中的每一行代表某个用户浏览过的新闻报道。一些用户只看过一篇报道，而有些用户看过2498篇报道，用户和报道被编码成整数。53示例：从新闻网站点击流中挖掘新闻报道-结果54谢谢！55此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢56