机器学习(十五)— Apriori算法、FP Growth算法

1、Apriori算法

  Apriori算法是常用的用于挖掘出数据关联规则的算法,它用来找出数据值中频繁出现的数据集合,找出这些集合的模式有助于我们做一些决策。

  Apriori算法采用了迭代的方法,先搜索出候选1项集及对应的支持度,剪枝去掉低于支持度的1项集,得到频繁1项集。然后对剩下的频繁1项集进行连接,得到候选的频繁2项集,筛选去掉低于支持度的候选频繁2项集,得到真正的频繁二项集,以此类推,迭代下去,直到无法找到频繁k+1项集为止,对应的频繁k项集的集合即为算法的输出结果。

  可见这个算法还是很简洁的,第i次的迭代过程包括扫描计算候选频繁i项集的支持度,剪枝得到真正频繁i项集和连接生成候选频繁i+1项集三步。

  一个项集的支持度(support)被定义为数据集中包含该项集的记录所占的比例。比如,图2中{豆奶}的支持度为4/5。支持度是针对项集来说的,因此可以定义一个最小支持度,而只保留满足最小支持度的项集。可信度或置信度(confidence)是针对一条诸如{尿布}->{葡萄酒}的关联关系来定义的。这条规则的可信度被定义为“支持度({尿布,葡萄酒})/支持度({尿布})”

  机器学习(十五)— Apriori算法、FP Growth算法

  机器学习(十五)— Apriori算法、FP Growth算法

   算法步骤:

      输入:数据集合D,支持度阈值αα

   输出:最大的频繁k项集

   1)扫描整个数据集,得到所有出现过的数据,作为候选频繁1项集。k=1,频繁0项集为空集。

   2)挖掘频繁k项集

     a) 扫描数据计算候选频繁k项集的支持度

     b) 去除候选频繁k项集中支持度低于阈值的数据集,得到频繁k项集。如果得到的频繁k项集为空,则直接返回频繁k-1项集的集合作为算法结果,算法结束。如果得到的频繁k项集只有一项,则直接返回频繁k项集的集合作为算法结果,算法结束。

     c) 基于频繁k项集,连接生成候选频繁k+1项集。

   3) 令k=k+1,转入步骤2。

   从算法的步骤可以看出,Aprior算法每轮迭代都要扫描数据集,因此在数据集很大,数据种类很多的时候,算法效率很低。

2、FP Growth算法

  作为一个挖掘频繁项集的算法,Apriori算法需要多次扫描数据,I/O是很大的瓶颈。为了解决这个问题,FP Tree算法(也称FP Growth算法)采用了一些技巧,无论多少数据,只需要扫描两次数据集,因此提高了算法运行的效率。

  参考:http://www.cnblogs.com/pinard/p/6307064.html

上一篇:posix 匿名信号量与互斥锁 示例生产者--消费者问题


下一篇:Frequent Pattern 挖掘之二(FP Growth算法)