二关联规则挖掘-- Apriori 算法 _关联规则

本文首先介绍了算法的原理，进行了简单的示例推导，而后运用R语言中的包对数据集进行关联规则挖掘实战。
一、概述
算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，这种算法所针对的关联规则是单维、单层、布尔关联规则。
在前一篇文章中写到关联规则挖掘算法的总体性能取决于寻找频繁项集，而后由频繁项集产生强关联规则就很容易了。那么如何寻找频繁项集呢？自然的想法是对于数据集D ，遍历它的每一条记录T ，得到T的所有子集，然后计算每一个子集的支持度，最后的结果再与最小支持度比较。此种方法的计算量非常巨大，显然是不可取的。因此，算法提出了逐层搜索的迭代方法：
1.自连接获取候选集。第一轮的候选集就是数据集D中的项，而其他轮次的候选集则是由前一轮次频繁集自连接得到（频繁集由候选集剪枝得到）。
2.对候选集进行剪枝。剪枝规则1：如果某条候选集的支持度小于最小支持度，那么就会被剪掉；剪枝规则2：如果某条候选集的子集中存在非频繁集，该候选集也会被剪掉。
值得注意的是，为了提高频繁项集逐层产生的效率，进一步减少计算量，一种称作性质的重要性质被用于压缩搜索空间，即：频繁项集的所有非空子集都必须也是频繁的（对应剪枝规则2）。
二、示例推导
该示例基于某事务数据库，数据库中有9个事务，如下图所示：
如何使用算法寻找频繁项集呢？具体如下：
1.在算法的第一次迭代，每个项都是候选 1-项集的集合C1的成员。算法简单地扫描所有的事务，对每个项的出现次数计数。
2.假定最小事务支持计数为 2（即， = 2/9 = 22%）。可以确定频繁 1-项集的集合 L1。它由具有最小支持度的候选 1-项集组成。
3.为发现频繁 2-项集的集合L2 ，算法使用 L1 与 L1 自连接产生候选 2-项集的集合 C2。
4.下一步，扫描 D 中事务，计算 C2 中每个候选项集的支持计数，如下图的第二行的中间表所示。
5.将候选集支持度计数与最小支持度比较，产生频繁 2-项集的集合 L2。
6.产生候选 3-项集的集合 C3。首先， L2 与 L2 自连接得到 {I1,I2,I3},{I1,I2,I5},{I1,I3,I5},{I2,I3,I4},{I2,I3,I5},{I2,I4,I5}。根据性质，频繁项集的所有子集必须是频繁的，我们可以确定后 4 个候选不可能是频繁的。因此，我们把它们由 C3 删除，这样，在此后扫描 D 确定 L3 时就不必再求它们的计数值。值得注意的是，算法使用逐层搜索技术，给定 k-项集，我们只需要检查它们的(k-1)-子集是否频繁。
7.扫描 D 中事务，以确定 L3 ，它由具有最小支持度的 C3 中的候选 3-项集组成。
8.产生候选 4-项集的集合 C4。L3 与 L3 自连接得到 {I1,I2,I3,I5} ，由于其子集 {I1,I3,I5} 不是频繁的，所以 C4 为空，算法终止。

文章插图
三、实例 1.R语言函数介绍
R语言中包可以实现算法。
(data,=list(=0.1,=0.8,=1,=10))
其中参数是一个列表，包含支持度，置信度，和，即规则包含的元素个数（LHS+RHS），默认的 = 1 ，意味着{}=>beer 是合法的规则，我们往往不需要这种规则，所以一般设定 = 2 。

二 关联规则挖掘-- Apriori 算法

二关联规则挖掘-- Apriori 算法