文档介绍：机器学****FP-GROWTH算法李家豪目录2回忆Apriori算法项集:项的集合称为项集,即商品的组合。k项集:k件商品的组合,不关心商品件数,仅商品的种类。频繁项集:如果项集的相对支持度满足给定的最小支持度阈值,则该项集是频繁项集。强关联规则:满足给定支持度和置信度阈值的关联规则支持度:support(A->B)=P(AB)置信度:confidence(A->B)=P(A|B)3回忆Apriori算法4回忆Apriori算法5Apriori算法的挑战挑战多次数据库扫描巨大数量的候补项集繁琐的支持度计算改善Apriori:基本想法减少扫描数据库的次数减少候选项集的数量简化候选项集的支持度计算6FP-GROWTH算法优点相比Apriori算法需要多次扫描数据库,FPGrowth只需要对数据库扫描2次。第1次扫描事务数据库获得频繁1项集。第2次扫描建立一颗FP-Tree树。7FP-GROWTH算法原理-实例1要找总是一起购买的商品,比如[薯片,鸡蛋]就是一条频繁模式(规律)。IDItems1牛奶,鸡蛋,面包,薯片2鸡蛋,爆米花,薯片,啤酒3牛奶,面包,啤酒4牛奶,鸡蛋,面包,爆米花,薯片,啤酒5鸡蛋,面包,薯片6鸡蛋,面包,啤酒7牛奶,面包,薯片8牛奶,鸡蛋,面包,黄油,薯片9牛奶,鸡蛋,黄油,薯片8FP-GROWTH算法原理-实例1-统计频次Step1:先扫描数据库,统计所有商品的出现次数(频数),然后按照频数递减排序,删除频数小于最小支持度的商品。设最小支持度数为:minsup=4统计频数:牛奶6,鸡蛋7,面包7,薯片7,爆米花2,啤酒4,:薯片7,鸡蛋7,面包7,牛奶6,啤酒4(删除小于minsup的商品)IDItems1牛奶,鸡蛋,面包,薯片2鸡蛋,爆米花,薯片,啤酒3牛奶,面包,啤酒4牛奶,鸡蛋,面包,爆米花,薯片,啤酒5鸡蛋,面包,薯片6鸡蛋,面包,啤酒7牛奶,面包,薯片8牛奶,鸡蛋,面包,黄油,薯片9牛奶,鸡蛋,黄油,薯片频繁1项集,记为F19FP-GROWTH算法原理-实例1-重新排序IDItems1牛奶,鸡蛋,面包,薯片2鸡蛋,爆米花,薯片,啤酒3牛奶,面包,啤酒4牛奶,鸡蛋,面包,爆米花,薯片,啤酒5鸡蛋,面包,薯片6鸡蛋,面包,啤酒7牛奶,面包,薯片8牛奶,鸡蛋,面包,黄油,薯片9牛奶,鸡蛋,黄油,薯片IDItems1薯片,鸡蛋,面包,牛奶2薯片,鸡蛋,啤酒3面包,牛奶,啤酒4薯片,鸡蛋,面包,牛奶,啤酒5薯片,鸡蛋,面包6鸡蛋,面包,啤酒7薯片,面包,牛奶8薯片,鸡蛋,面包,牛奶9薯片,鸡蛋,牛奶Step2:对每一条数据记录,按照F1重新排序。10