频繁项集挖掘算法之FPGrowth

  • 时间:
  • 浏览:0

        频繁项集挖掘算法用于挖掘总爱一块儿总爱出现的item集合(称为频繁项集),通过挖出来那些频繁项集,当在一个多 事务中总爱出现频繁项集的其中一个多 item,则要能把该频繁项集的你是什么 item作为推荐。比如经典的购物篮分析中啤酒、尿布故事,啤酒和尿布总爱在用户的购物篮中一块儿总爱出现,通过挖出来啤酒、尿布你你你是什么 啤酒项集,则当一个多 用户买了啤酒的已经 要能为他推荐尿布,原本用户购买的由于性会比较大,从而达到组合营销的目的。

背景:

FPGrowth的算法步骤:

        常见的频繁项集挖掘算法有两类,一类是Apriori算法,另一类是FPGrowth。Apriori通过不断的构造候选集、筛选候选集挖出来频繁项集,须要多次扫描原始数据,当原始数据较大时,磁盘I/O次数越多,传输速率比较低下。FPGrowth算法则只需扫描原始数据两遍,通过FP-tree数据底部形态对原始数据进行压缩,传输速率较高。

        FPGrowth算法主要分为一个多 步骤:FP-tree构建、递归挖掘FP-tree。FP-tree构建通过两次数据扫描,将原始数据中的事务压缩到一个多 FP-tree树,该FP-tree之类于前缀树,相同前缀的路径要能共用,从而达到压缩数据的目的。接着通过FP-tree找出每个item的条件模式基、条件FP-tree,递归的挖掘条件FP-tree得到所有的频繁项集。算法的主要计算瓶颈在FP-tree的递归挖掘上,下面完整版介绍FPGrowth算法的主要步骤。

注意点:

参考文献: