版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、2021/3/91机器学习-FP-GROWTH算法李家豪2021/3/92目录2021/3/93回忆Apriori算法 项集:项的集合称为项集,即商品的组合。 k项集:k件商品的组合,不关心商品件数,仅商品的种类。 频繁项集:如果项集的相对支持度满足给定的最小支持度阈值,则该项集是频繁项集。 强关联规则:满足给定支持度和置信度阈值的关联规则 支持度:support(A-B) = P(AB) 置信度:confidence(A-B) = P(A|B) 2021/3/94回忆Apriori算法2021/3/95回忆Apriori算法2021/3/96Apriori算法的挑战挑战 多次数据库扫描 巨大
2、数量的候补项集 繁琐的支持度计算改善Apriori: 基本想法 减少扫描数据库的次数 减少候选项集的数量 简化候选项集的支持度计算2021/3/97FP-GROWTH算法优点 相比Apriori算法需要多次扫描数据库,FPGrowth只需要对数据库扫描2次。 第1次扫描事务数据库获得频繁1项集。 第2次扫描建立一颗FP-Tree树。2021/3/98FP-GROWTH算法原理-实例1 要找总是一起购买的商品,比如薯片,鸡蛋就是一条频繁模式(规律)。IDItems1牛奶,鸡蛋,面包,薯片2鸡蛋,爆米花,薯片,啤酒3牛奶,面包,啤酒4牛奶,鸡蛋,面包,爆米花,薯片,啤酒5鸡蛋,面包,薯片6鸡蛋,面
3、包,啤酒7牛奶,面包,薯片8牛奶,鸡蛋,面包,黄油,薯片9牛奶,鸡蛋,黄油,薯片2021/3/99FP-GROWTH算法原理-实例1-统计频次Step1:先扫描数据库,统计所有商品的出现次数(频数),然后按照频数递减排序,删除频数小于最小支持度的商品。设最小支持度数为:minsup=4统计频数:牛奶6,鸡蛋7,面包7,薯片7,爆米花2,啤酒4,黄油2.降序排序:薯片7,鸡蛋7,面包7,牛奶6,啤酒4(删除小于minsup的商品)IDItems1牛奶,鸡蛋,面包,薯片2鸡蛋,爆米花,薯片,啤酒3牛奶,面包,啤酒4牛奶,鸡蛋,面包,爆米花,薯片,啤酒5鸡蛋,面包,薯片6鸡蛋,面包,啤酒7牛奶,面包
4、,薯片8牛奶,鸡蛋,面包,黄油,薯片9牛奶,鸡蛋,黄油,薯片 频繁1项集,记为F12021/3/910FP-GROWTH算法原理-实例1-重新排序IDItems1牛奶,鸡蛋,面包,薯片2鸡蛋,爆米花,薯片,啤酒3牛奶,面包,啤酒4牛奶,鸡蛋,面包,爆米花,薯片,啤酒5鸡蛋,面包,薯片6鸡蛋,面包,啤酒7牛奶,面包,薯片8牛奶,鸡蛋,面包,黄油,薯片9牛奶,鸡蛋,黄油,薯片IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step2:对每一条数据记
5、录,按照F1重新排序。2021/3/911FP-GROWTH算法原理-实例1-建立FP树IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step3:把第二步重新排序后的记录,插入到fp-tree中Step3.1:插入第一条(第一步有一个虚的根节点)2021/3/912FP-GROWTH算法原理-实例1-建立FP树IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包
6、,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step3.2:插入第二条。根结点不管,然后插入薯片,在step3.1的基础上+1,则记为2;同理鸡蛋记为2;啤酒在step3.1的树上是没有的,那么就开一个分支。2021/3/913FP-GROWTH算法原理-实例1-建立FP树IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step3.3:插入第三条2021/3/914FP-GROWTH算法原理-实例1-建立FP树IDItem
7、s1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶同理,剩余记录依次插入fp-tree中。2021/3/915FP-GROWTH算法原理-实例1-建立FP树图中左边的一列叫做头指针表,树中相同名称的节点要链接起来,链表的第一个元素就是头指针表里的元素。虚线连接起来的表示同一个商品,各个连接的数字加起来就是该商品出现的总次数。2021/3/916FP-GROWTH算法原理-实例1-挖掘频繁项集Step4:从FP-Tree中找出频繁项集。遍历表头项中的每一项(以
8、“牛奶:6”为例),从FP-Tree中找到所有的“牛奶”结点,向上遍历它的祖先结点,得到4条路径,如表所示。2021/3/917FP-GROWTH算法原理-实例1-挖掘频繁项集Step4:从FP-Tree中找出频繁项集。对于每一条路径上的节点,其count都设置为牛奶的count(路径中最末尾的商品数)2021/3/918FP-GROWTH算法原理-实例1-挖掘频繁项集Step4:从FP-Tree中找出频繁项集。因为每一项末尾都是牛奶,可以把牛奶去掉,得到条件模式基,此时的后缀模式是:牛奶。2021/3/919FP-GROWTH算法原理-实例2 把例子简化一下,请看以下实例2TidItems1
9、I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I32021/3/920FP-GROWTH算法原理-实例2-统计频次 先扫描数据库,统计所有商品的出现次数(频数) 定义min_sup=2,按照频数递减排序,删除频数小于最小支持度的商品。重新排列得到频繁1-项目集FI1I2I3I4I567622I2I1I3I4I5766222021/3/921FP-GROWTH算法原理-实例2-重新排序I27I16I36I42I52TidItems1I2, I1,I52I2,I43I2,I34I2, I1,I45I1,I36I2
10、,I37I1,I38I2, I1,I3,I59I2, I1,I32021/3/922FP-GROWTH算法原理-实例2-创建根结点和频繁项目表Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNull2021/3/923FP-GROWTH算法原理-实例2-加入第一个事务(I2,I1,I5)2021/3/924FP-GROWTH算法原理-实例2-加入第二个事务(I2,I4)2021/3/925FP-GROWTH算法原理-实例2-加入第三个事务(I2,I3)2021/3/926FP-GROWTH算法原理-实例2-加入第四个事务(I2,I1,I4)202
11、1/3/927FP-GROWTH算法原理-实例2-加入第五个事务(I1,I3)2021/3/928FP-GROWTH算法原理-实例2-加入第六个事务(I2,I3)2021/3/929FP-GROWTH算法原理-实例2-加入第七个事务(I1,I3)2021/3/930FP-GROWTH算法原理-实例2-加入第八个事务(I2,I1,I3,I5)2021/3/931FP-GROWTH算法原理-实例2-加入第九个事务(I2,I1,I3)2021/3/932FP-GROWTH算法原理-实例2-挖掘频繁项集首先考虑I5,得到条件模式基: 、构造条件FP-Tree得到I5频繁项集:I2,I5,I1,I5,I
12、2,I1,I52021/3/933FP-GROWTH算法原理-实例2-挖掘频繁项集接着考虑I4,得到条件模式基: 、构造条件FP-Tree得到I4频繁项集:I2,I42021/3/934FP-GROWTH算法原理-实例2-挖掘频繁项集然后考虑I3,得到条件模式基: 、 构造条件FP-Tree由于此树不是单分支路径,因此需要递归挖掘I32021/3/935FP-GROWTH算法原理-实例2-挖掘频繁项集 递归考虑I3,此时得到I1条件模式基,即I1, I3的条件模式基为 构造条件FP-Tree得到I3的频繁项目集I2,I3,I1,I3,I2,I1,I32021/3/936FP-GROWTH算法原
13、理-实例2-挖掘频繁项集 最后考虑I1,得到条件模式基: 构造条件FP-Tree得到I1的频繁项目集:I2,I12021/3/937FP-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格式化处理2021/3/938代码实现-FP树数据结构2021/3/939代码实现-构造FP树步骤2021/3/940代码实现-构造FP树2021/3/941代码实现-构造FP树2021/3/942代码实现-构造FP树(updateTree函数)2021/3/943代码实现-构造FP树(updateH
14、eader函数)2021/3/944代码实现-构造FP树(验证)2021/3/945代码实现-挖掘频繁项集步骤从构建好的FP树中抽取频繁项集的步骤如下:(1)从FP树中获取条件模式基;(2)利用条件模式基,构建一个条件FP树;(3)迭代重复(1)(2),直到树包含一个元素项为止。2021/3/946条件模式基定义 条件模式基是以所查找元素项为结尾的路径集合所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径前缀路径。简而言之,一条前缀路径就是介于所查找元素项与树根节点之间的所有内容。 每一个频繁项的所有前缀路径(条件模式基):2021/3/947代码实现-抽取条件模式基eg:t的第1条前缀路径prefixPath=t,s,y,x,z;2021/3/948代码实现-抽取条件模式基2021/3/949代码实现-抽取条件模式基(验证)2021/3/950代码实现-创建条件FP树2021/3/951代码实现-创建条件FP树2021/3/952代
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 农村简易征地合同模板
- 餐饮单位原料购销合同模板
- 杀虫消毒合同模板
- 黄埔区叉车租赁合同模板
- 藏品转让项目合同模板
- 无产权房屋合同模板
- 小区安置房合同模板
- 金器抵押合同模板
- 青蛙收购合同模板
- 借款合同合同模板
- 阴茎损伤的护理课件
- 皮肤科住院医师规范化培训内容与标准
- 苏教版六年级上册数学认识百分数(课件)
- 抗美援朝抗美援朝
- 【自考复习资料】00510秘书实务(实用便携笔记)
- GB 29436-2023甲醇、乙二醇和二甲醚单位产品能源消耗限额
- 人教PEP版六年级英语上册期中试卷(含听力音频和答案)
- 如何建立良好的人际关系主题班会课件
- 事故油池基坑开挖专项施工方案
- 2023年10月自考00600高级英语试题及答案含评分标准
- 2023年高考全国乙卷物理真题分析
评论
0/150
提交评论