挖掘关联规则之Apriori算法

主要是用来挖掘关联规则，即从一个事务数据集中发现频繁项集并推出关联规则，其名字是因为算法基于先验知识(prior knowledge).根据前一次找到的频繁项来生成本次的频繁项。Apriori是关联分析中核心的算法。

Apriori算法的特点：

只能处理分类变量，无法处理数值型变量；

数据存储可以是交易数据格式（事务表），或者是事实表方式（表格数据）。

算法核心在于提升关联规则产生的效率而设计的。

2. 新概念：

项集：

（例如所有的商品）为一个项集，则每一个事务t（例如购买小票上的商品）都是一个项集。

支持度： 项集的支持度是指包含该项集的事务所占所有事务的比例。

频繁项集：就是指满足给定的最小支持度的项集。

关联规则：X->Y 是指由X能推出Y

置信度： 对于X->Y的置信度表示p(X,Y)/p(X); 即项集X事务中也包含项集Y的事务所占的比例

3. Apriori的思想：

我们希望置信度和支持度要满足我们的阈值范围才算是有效的规则，实际过程中我们往往会面临大量的数据，如果只是简单的搜索，会出现很多的规则，相当大的一部分是无效的规则，效率很低，那么Apriori就是通过产生频繁项集，然后再依据频繁项集产生规则，进而提升效率。

以上所说的代表了Apriori算法的两个步骤：产生频繁项集和依据频繁项集产生规则。

为什么确定频繁项集？

刚才说了，必须支持度大于我们指定的支持度，这也就是说能够确定后面生成的规则是在普遍代表性上的项目集生成的，因为支持度本身的高低就代表了我们关联分析结果是否具有普遍性。

怎么寻找频繁项集？

这里不再讲述，直接说一个例子大家就都明白了。例子来源于Fast Algorithms for Mining Association Rules

如下：

Apriori寻找频繁项集的过程是一个不断迭代的过程，每次都是两个步骤，产生候选集Ck（可能成为频繁项集的项目组合）；基于候选集Ck计算支持度，确定Lk。

Apriori的寻找策略就是从包含少量的项目开始逐渐向多个项目的项目集搜索。

数据如下：

我们看到，数据库存储的数据格式，会员100购买了 1 3 4三种商品，那么对应的集合形式如右边的图所示。那么基于候选集C1，我们得到频繁项集L1，如下图所示，在此表格中{4}的支持度为1，而我们设定的支持度为2。支持度大于或者等于指定的支持度的最小阈值就成为L1了，这里{4}没有成为L1的一员。因此，我们认定包含4的其他项集都不可能是频繁项集，后续就不再对其进行判断了。

此时我们看到L1是符合最低支持度的标准的，那么下一次迭代我们依据L1产生C2（4就不再被考虑了），此时的候选集如右图所示C2（依据L1*L1的组合方式）确立。C2的每个集合得到的支持度对应在我们原始数据组合的计数，如下图左所示。

此时，第二次迭代发现了{1 2} {1 5}的支持度只有1，低于阈值，故而舍弃，那么在随后的迭代中，如果出现{1 2} {1 5}的组合形式将不被考虑。

如上图，由L2得到候选集C3，那么这次迭代中的{1 2 3} { 1 3 5}哪去了？如刚才所言，{1 2} {1 5}的组合形式将不被考虑，因为这两个项集不可能成为频繁项集L3，此时L4不能构成候选集L4，即停止。

如果用一句化解释上述的过程，就是不断通过Lk的自身连接，形成候选集，然后在进行剪枝，除掉无用的部分。根据频繁项集产生简单关联规则。

Apriori的关联规则是在频繁项集基础上产生的，进而这可以保证这些规则的支持度达到指定的水平，具有普遍性和令人信服的水平。

以上就是Apriori的算法基本原理，下面以一个具体的实例进行说明下。

算法作用：Apriori算法主要是用来挖掘关联规则，即从一个事务数据集中发现频繁项集并推出关联规则

4. 算法应用：

应用数据集：Groceries（一个购物蓝的数据集）

应用目的：分析出购物蓝数据集中那些物品常存在与一个购物蓝中，并推出关联规则。

运行代码：

代码解释：第六行代码中设置支持度为1%，置信度为0.5

运行结果分析：

通过上代码运行出的结果见上图，该结果第一列为lhs(left-hand side)，代表关联规则中的X，第二列rhs(right-hand side)，代表关联规则中的Y，第三列为支持度，以第一项为例表示有1.006609%的人购买了lhs+rhs，第四列为置信度表示购买lhs的顾客中会有58.24%的人去买rhs，计算公式为confidence=P(lhs+rhs)/P(lhs). 最后一列lift是一个类似相关系数的指标。lift=1 时表示lhs和rhs独立，该值越大表明lhs和rhs存在一个购物蓝中并不是偶然的，计算公式为lift=P(lhs+rhs)/P(lhs)*P(rhs).

从此，我们分析下第一条关联规则：有1%的人同时购买了curd,yogurt,whole milk这三种商品，其中在购买curt和yogurt的客户中，共有58.23%的人买了whole milk。lift=2.28表示这两个（lhs和rhs）并不是独立的。

参考资料：

http://zhan.renren.com/dmeryuyang?gid=3602888498023976650&checked=true

http://rakesh.agrawal-family.com/papers/vldb94apriori.pdf

回复数字或算法名称即可查看相关文章：

1. 决策树算法之一C4.5

2. 数据挖掘之Apriori算法

3. 网页排序算法之PageRank