Apriori算法

Apriori 算法是数据挖掘中一种挖掘关联规则的频繁项集算法。其核心是基于两阶段频集思想的递推算法。

先来了解下关联规则挖掘：

发现事务数据库，关系数据 ,  或其它信息库中项或数据对象集合间的频繁模式。关联，相关，或因果关系结构。

频繁模式：在数据库中频繁出现的模式 ( 项集 ,  序列 ,  等 ) 。

动机是发现数据中的规律性。

如：

购物篮分析：哪些产品更经常一起购买 ?   啤酒 和 尿布 ?!

购买了 PC 后 ,  哪些将相继购买 ?

什么类型的  DNA  对新药敏感 ?

我们能自动地对 Web 文档分类吗 ?

再来看看几个概念：

支持度 ：s (support) ，事 务包含  X ∪ Y  的 概率。

置信度 ：c (confidence) ， 事务含  X  也包含  Y  的 条件概率p(Y|X)。

频繁项集 ： I, 项集 I 的相对支持度满足预定义的最小支持度阈值

Apriori 算法 :

Apriori 算法的核心是使用候选项集寻找频繁项集。 Apriori 使用一种称为逐层搜索的迭代方法， k- 项集用于搜索（ k+1 ） – 项集。首先，找出所有频繁 1- 项集 L1 ，然后用 L1 寻找 L2 ，用 L2 寻找 L3, 如此，直至不能找到频繁 k- 项集为止。

Apriori 性质 ：

频繁项集的所有非空子集肯定也是频繁的。

如 :

每个包含  {beer, diaper, nuts} 的事务 也包含  {beer, diaper}

如果  {beer, diaper, nuts}  是频繁的 , {beer, diaper} 也是

转换一下思维，如果一个子集是非频繁的，那么它的超集也一定是非频繁的。这在Apriori 算法里面很重要。

利用 Apriori 性质，我们在使用频繁 (k-1)- 项集 L(k-1) 寻找频繁 k- 项集 L(k) 时分两个过程：连接步和剪枝步。

连接步 ：

L(k-1) 与其自身进行连接，产生候选项集 C(k) 。 L(k-1) 中某个元素与其中另一个元素可以执行连接操作的前提是它们中游 (k-2) 个项是相同的。也就是只有一个项是不同的。

如：项集 {I1,I2} 与 {I1,I5} 连接之后产生的项集是 {I1,I2,I5} ，而项集 {I1,I2} 与 {I3,I4}不能进行连接操作。

剪枝步 ：

候选集 C(k) 中的元素可以是频繁项集，也可以不是。但所有的频繁 k- 项集一定包含在 C(k) 中，所以， C(k) 是 L(k) 的超集。扫描事物集 D ，计算 C(k) 中每个候选项出现的次数，出现次数大于等于最小支持度与事务集 D 中事务总数乘积的项集便是频繁项集（这里的最小支持度指的是概率，实际中我们经常直接将最小支持度看成乘积后的结果），如此便可确定频繁 k- 项集 L(k) 了。

但是，由于 C(k) 很大，所以计算量也会很大。为此，需要进行剪枝。即压缩 C(k)，删除其中肯定不是频繁项集的元素，依据就是前面提到的 Apriori 性质：如果一个子集是非频繁的，那么它的超集也一定是非频繁的。这在 Apriori 算法里面很重要。如此，如果一个候选 (k-1)- 子集不在 L(k-1) 中，那么该候选 k- 项集也不可能是频繁的，可以直接从 C(k) 中删除。

这里看一个例子就可以理解了：

所以，满足条件的所有频繁项集有 {A} 、 {B} 、 {C} 、 {E} 、 {A 、 C} 、 {B 、 C}、 {B 、 E} 、 {C 、 E} 、 {B 、 C 、 E}

算法伪代码 :

C[k]: 长度为 k的候选项集
L[k] : 长度为k的频繁项集

L[1] = {频繁项};
for (k = 1; L[k] !=∅; k++) do begin
    C[k+1] = 由 L[k]产生的候选;
    for each 数据库中的事务t  do
      增加包含在t 中的所有候选C[k+1]的计数
    L[k+1] = C[k+1]中满足 min_support的候选
    end
return   L[1..k];

原文：http://blog.csdn.net/epluguo/article/details/27800625