Question

一、Apriori 算法概述
Apriori 算法是一种最有影响力的挖掘布尔关联规则的频繁项集的 算法，它是由 Rakesh Agrawal 和 RamakrishnanSkrikant 提出的。它使用一种称作逐层搜索的迭代方法，k- 项集用于探索（k+1）- 项集。首先，找出频繁 1- 项集的集合。该集合记作 L1。L1 用于找频繁 2- 项集的集合 L2，而 L2 用于找 L2，如此下去，直到不能找到 k- 项集。每找一个 Lk 需要一次数据库扫描。为提高频繁项集逐层产生的效率，一种称作 Apriori 性质的重 要性质 用于压缩搜索空间。其运行定理在于一是频繁项集的所有非空子集都必须也是频繁的，二是非频繁项集的所有父集都是非频繁的。

二、问题的引入

购物篮分析：引发性例子

Question：哪组商品顾客可能会在一次购物时同时购买？

关联分析
Solutions：
1：经常同时购买的商品可以摆近一点，以便进一步刺激这些商品一起销售。
2：规划哪些附属商品可以降价销售，以便刺激主体商品的捆绑销售。

三、关联分析的基本概念

1、支持度

关联规则 A->B 的支持度 support=P(AB)，指的是事件 A 和事件 B 同时发生的概率。

2、置信度

置信度 confidence=P(B|A)=P(AB)/P(A),指的是发生事件 A 的基础上发生事件 B 的概率。比如说在规则 Computer => antivirus_software , 其中 support=2%, confidence=60%中，就表示的意思是所有的商品交易中有 2%的顾客同时买了电脑和杀毒软件，并且购买电脑的顾客中有 60%也购买了杀毒软件。

3、k 项集

如果事件 A 中包含 k 个元素，那么称这个事件 A 为 k 项集，并且事件 A 满足最小支持度阈值的事件称为频繁 k 项集。

4、由频繁项集产生强关联规则

1）K 维数据项集 LK 是频繁项集的必要条件是它所有 K-1 维子项集也为频繁项集，记为 LK-1　

2）如果 K 维数据项集 LK 的任意一个 K-1 维子集 Lk-1，不是频繁项集，则 K 维数据项集 LK 本身也不是最大数据项集。

3）Lk 是 K 维频繁项集，如果所有 K-1 维频繁项集合 Lk-1 中包含 LK 的 K-1 维子项集的个数小于 K，则 Lk 不可能是 K 维最大频繁数据项集。

4）同时满足最小支持度阀值和最小置信度阀值的规则称为强规则。

例如：用一个简单的例子说明。表 1 是顾客购买记录的数据库 D，包含 6 个事务。项集 I={网球拍，网球，运动鞋，羽毛球}。考虑关联规则：网球拍网球，事务 1,2,3,4,6 包含网球拍，事务 1,2,6 同时包含网球拍和网球，支持度，置信度。若给定最小支持度，最小置信度，关联规则网球拍网球是有趣的，认为购买网球拍和购买网球之间存在强关联。

四、Apriori 算法的基本思想：

Apriori 算法过程分为两个步骤：

第一步通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；

第二步利用频繁项集构造出满足用户最小信任度的规则。

具体做法就是：

首先找出频繁 1-项集，记为 L₁；然后利用 L₁来产生候选项集 C₂，对 C₂中的项进行判定挖掘出 L₂，即频繁 2-项集；不断如此循环下去直到无法发现更多的频繁 k-项集为止。每挖掘一层 L_k就需要扫描整个数据库一遍。算法利用了一个性质：

Apriori 性质 ：任一频繁项集的所有非空子集也必须是频繁的。意思就是说，生成一个 k-itemset 的候选项时，如果这个候选项有子集不在(k-1)-itemset(已经确定是 frequent 的) 中时，那么这个候选项就不用拿去和支持度判断了，直接删除。具体而言：

1） 连接步

为找出 L_k（所有的频繁 k 项集的集合），通过将 L_k-1（所有的频繁 k-1 项集的集合）与自身连接产生候选 k 项集的集合。候选集合记作 C_k。设 l₁和 l₂是 L_k-1中的成员。记 l_i[j]表示 l_i中的第 j 项。假设 Apriori 算法对事务或项集中的项按字典次序排序，即对于（k-1）项集 l_i，l_i[1]i</sub>[2]<……….i</sub>[k-1]。将 L_k-1与自身连接，如果(l₁[1]=l₂[1])&&( l₁[2]=l₂[2])&&……..&& (l₁[k-2]=l₂[k-2])&&(l₁[k-1]2</sub>[k-1])，那认为 l₁和 l₂是可连接。连接 l₁和 l₂ 产生的结果是{l₁[1],l₁[2],……,l₁[k-1],l₂[k-1]}。

2） 剪枝步

C_K是 L_K的超集，也就是说，C_K的成员可能是也可能不是频繁的。通过扫描所有的事务（交易），确定 C_K中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。为了压缩 C_k,可以利用 Apriori 性质：任一频繁项集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从 C_K中删除。

五、实例说明

实例一：下面以图例的方式说明该算法的运行过程： 假设有一个数据库 D，其中有 4 个事务记录，分别表示为：

这里预定最小支持度 minSupport=2,下面用图例说明算法运行的过程：

1、扫描 D，对每个候选项进行支持度计数得到表 C1:

2、比较候选项支持度计数与最小支持度 minSupport，产生 1 维最大项目集 L1：

3、由 L1 产生候选项集 C2：

4、扫描 D，对每个候选项集进行支持度计数:

5、比较候选项支持度计数与最小支持度 minSupport，产生 2 维最大项目集 L2：

6、由 L2 产生候选项集 C3：

7、比较候选项支持度计数与最小支持度 minSupport，产生 3 维最大项目集 L3：

算法终止。

实例二：下图从整体同样的能说明此过程：

此例的分析如下：

1 . 连接：C3=L2 L2= {{A,C},{B,C},{B,E}{C,E}} {{A,C},{B,C},{B,E}{C,E}} = {{A,B,C},{A,C,E},{B,C,E}}

2．使用 Apriori 性质剪枝：频繁项集的所有子集必须是频繁的，对候选项 C3，我们可以删除其子集为非频繁的选项：

{A,B,C}的 2 项子集是{A,B},{A,C},{B,C}，其中{A,B}不是 L2 的元素，所以删除这个选项；

{A,C,E}的 2 项子集是{A,C},{A,E},{C,E}，其中{A,E} 不是 L2 的元素，所以删除这个选项；

{B,C,E}的 2 项子集是{B,C},{B,E},{C,E}，它的所有 2－项子集都是 L2 的元素，因此保留这个选项。

3．这样，剪枝后得到 C3={{B,C,E}}

PS

从算法的运行过程，我们可以看出该 Apriori 算法的优点：简单、易理解、数据要求低，然而我们也可以看到 Apriori 算法的缺点：

(1) 在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;

(2) 每次计算项集的支持度时，都对数据库 D 中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的 I/O 开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法。

六、改进 Apriori 算法的方法

方法 1：基于 hash 表的项集计数

将每个项集通过相应的 hash 函数映射到 hash 表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。

方法 2：事务压缩（压缩进一步迭代的事务数）

不包含任何 k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除

方法 3：划分

挖掘频繁项集只需要两次数据扫描

D 中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。

第一次扫描：将数据划分为多个部分并找到局部频繁项集

第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集。

方法 4：选样（在给定数据的一个子集挖掘）

基本思想：选择原始数据的一个样本，在这个样本上用 Apriori 算法挖掘频繁模式

通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式

可以通过一次全局扫描来验证从样本中发现的模式

可以通过第二此全局扫描来找到遗漏的模式

方法 5：动态项集计数

在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不必在这次扫描的以后对比中继续计算。

PS：Apriori 算法的优化思路

1、在逐层搜索循环过程的第 k 步中，根据 k-1 步生成的 k-1 维频繁项目集来产生 k 维候选项目集，由于在产生 k-1 维频繁项目集时，我们可以实现对该集中出现元素的个数进行计数处理，因此对某元素而言，若它的计数个数不到 k-1 的话，可以事先删除该元素，从而排除由该元素将引起的大规格所有组合。

这是因为对某一个元素要成为 K 维项目集的一元素的话，该元素在 k-1 阶频繁项目集中的计数次数必须达到 K-1 个，否则不可能生成 K 维项目集（性质 3)。

2、根据以上思路得到了这个候选项目集后，可以对数据库 D 的每一个事务进行扫描，若该事务中至少含有候选项目集 Ck 中的一员则保留该项事务，否则把该事物记录与数据库末端没有作删除标记的事务记录对换，并对移到数据库末端的事务记录作删除标一记，整个数据库扫描完毕后为新的事务数据库 D’ 中。

因此随着 K 的增大，D’中事务记录量大大地减少，对于下一次事务扫描可以大大节约 I/0 开销。由于顾客一般可能一次只购买几件商品，因此这种虚拟删除的方法可以实现大量的交易记录在以后的挖掘中被剔除出来，在所剩余的不多的记录中再作更高维的数据挖掘是可以大大地节约时间的。

实例过程如下图：

当然还有很多相应的优化算法，比如针对 Apriori 算法的性能瓶颈问题-需要产生大量候选项集和需要重复地扫描数据库，2000 年 Jiawei Han 等人提出了基于 FP 树生成频繁项集的 FP-growth 算法。该算法只进行 2 次数据库扫描且它不使用侯选集，直接压缩数据库成一个频繁模式树，最后通过这棵树生成关联规则。研究表明它比 Apriori 算法大约快一个数量级。