资源描述：
《机器学习-FPGROWTH算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、机器学习-FP-GROWTH算法李家豪目录2Apriori算法和FP-GROWTH算法的比较FP-GROWTH算法原理FP-GROWTH代码实现（python）示例：从新闻网站点击流中挖掘新闻报道回忆Apriori算法3项集：项的集合称为项集，即商品的组合。k项集：k件商品的组合，不关心商品件数，仅商品的种类。频繁项集：如果项集的相对支持度满足给定的最小支持度阈值，则该项集是频繁项集。强关联规则:满足给定支持度和置信度阈值的关联规则支持度：support(A->B)=P(AB)置信度：confidence(
2、A->B)=P(A
3、B)回忆Apriori算法4回忆Apriori算法5Apriori算法的挑战6挑战多次数据库扫描巨大数量的候补项集繁琐的支持度计算改善Apriori:基本想法减少扫描数据库的次数减少候选项集的数量简化候选项集的支持度计算FP-GROWTH算法优点相比Apriori算法需要多次扫描数据库，FPGrowth只需要对数据库扫描2次。第1次扫描事务数据库获得频繁1项集。第2次扫描建立一颗FP-Tree树。7FP-GROWTH算法原理-实例1要找总是一起购买的商品，比如[薯片，鸡蛋]就是一条频繁模
4、式(规律)。8IDItems1牛奶，鸡蛋，面包，薯片2鸡蛋，爆米花，薯片，啤酒3牛奶，面包，啤酒4牛奶，鸡蛋，面包，爆米花，薯片，啤酒5鸡蛋，面包，薯片6鸡蛋，面包，啤酒7牛奶，面包，薯片8牛奶，鸡蛋，面包，黄油，薯片9牛奶，鸡蛋，黄油，薯片FP-GROWTH算法原理-实例1-统计频次Step1:先扫描数据库，统计所有商品的出现次数(频数)，然后按照频数递减排序，删除频数小于最小支持度的商品。设最小支持度数为：minsup=4统计频数：牛奶6，鸡蛋7，面包7，薯片7，爆米花2，啤酒4，黄油2.降序排序：薯片
5、7,鸡蛋7,面包7,牛奶6,啤酒4（删除小于minsup的商品）9IDItems1牛奶，鸡蛋，面包，薯片2鸡蛋，爆米花，薯片，啤酒3牛奶，面包，啤酒4牛奶，鸡蛋，面包，爆米花，薯片，啤酒5鸡蛋，面包，薯片6鸡蛋，面包，啤酒7牛奶，面包，薯片8牛奶，鸡蛋，面包，黄油，薯片9牛奶，鸡蛋，黄油，薯片频繁1项集，记为F1FP-GROWTH算法原理-实例1-重新排序10IDItems1牛奶，鸡蛋，面包，薯片2鸡蛋，爆米花，薯片，啤酒3牛奶，面包，啤酒4牛奶，鸡蛋，面包，爆米花，薯片，啤酒5鸡蛋，面包，薯片6鸡蛋，面包
6、，啤酒7牛奶，面包，薯片8牛奶，鸡蛋，面包，黄油，薯片9牛奶，鸡蛋，黄油，薯片IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step2:对每一条数据记录，按照F1重新排序。FP-GROWTH算法原理-实例1-建立FP树11IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,
7、啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step3：把第二步重新排序后的记录，插入到fp-tree中Step3.1：插入第一条（第一步有一个虚的根节点）FP-GROWTH算法原理-实例1-建立FP树12IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step3.2：插入第二条。根结点不管，然后插入薯片，在step3.1的基础上+1，则
8、记为2；同理鸡蛋记为2；啤酒在step3.1的树上是没有的，那么就开一个分支。FP-GROWTH算法原理-实例1-建立FP树13IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step3.3：插入第三条FP-GROWTH算法原理-实例1-建立FP树14IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯
9、片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶同理，剩余记录依次插入fp-tree中。FP-GROWTH算法原理-实例1-建立FP树15图中左边的一列叫做头指针表，树中相同名称的节点要链接起来，链表的第一个元素就是头指针表里的元素。虚线连接起来的表示同一个商品，各个连接的数字加起来就是该商品出现的总次数。FP-GROWTH算法原理-实例1-挖掘频繁项集Step4：从F
