6.2　Apriori算法

6.2.1　Apriori算法的基本思想

关联规则的挖掘分为两步：第一步，找出所有频繁项集；第二步，由频繁项集产生强关联规则。而其总体性能由第一步决定。在搜索频繁项集时，最简单、基本的算法就是Apriori算法。算法的名称源于这样一个事实：算法使用频繁项集性质的先验知识。Apriori使用一种称为逐层搜索的迭代方法，k-项集用于探索（k+1）-项集。首先，通过扫描数据库，累积每个项目的计数，并收集满足最小支持度的项目，找出频繁1-项集的集合。该集合记作L1。然后，L1用于找频繁2-项集的集合L2，L2用于找L3，如此下去，直到不能再找到频繁k项集。找每个Lk需要进行一次数据库全扫描。

Apriori的核心算法思想简要描述如下：该算法中有两个关键步骤——连接步和剪枝步。

（1）连接步：为找出Lk（频繁k-项集），通过L(k-1)与自身连接，产生候选k-项集，该候选项集记作Ck；其中L(k-1)的元素是可连接的。

（2）剪枝步：Ck是Lk的超集，即它的成员可以是频繁的也可以不是频繁的，但所有的频繁项集都包含在Ck中。扫描数据库，确定Ck中每一个候选的计数，从而确定Lk（计数值不小于最小支持度计数的所有候选项集是频繁的，从而属于Lk）。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，使用Apriori性质：任何非频繁的（k-1）-项集都不可能是频繁k-项集的子集。因此，如果一个候选k-项集的（k-1）-项集不在Lk中，则该候选项集也不可能是频繁的，从而可以由Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。

6.2.2　Apriori算法的步骤

Apriori算法的主要步骤如下：

（1）扫描全部数据，产生候选1-项集的集合C1。

（2）根据最小支持度，由候选1-项集的集合C1产生频繁1-项集的集合L1。

（3）对k>1，重复执行步骤（4）～（6）。

（4）由Lk执行连接和剪枝操作，产生候选（k+l）-项集的集合C(k+1)。

（5）根据最小支持度，由候选（k+l）-项集的集合C(k+1)，产生频繁（k+1）-项集的集合L(k+1)。

（6）若L≠ø，则k=k+1，跳往步骤（4）；否则，跳往步骤（7）。

（7）根据最小置信度，由频繁项集产生强关联规则，结束。

6.2.3　Apriori算法的实例

表6-2为数据库事务列表示例，在数据库中有9笔交易。每笔交易都用不同的事务代表，交易中的项目按字典顺序存放。下面介绍Apriori算法寻找数据库D中频繁项集的过程。

设最小支持度计数为2，即min_sup=2，利用Apriori算法产生候选项集及频繁项集的过程如下。

1）第一次扫描

扫描数据库D获得每个候选项的支持度计数：

由于最小事务支持度计数为2，没有删除任何项目，可以确定频繁1-项集的集合L1由具有最小支持度的候选1-项集组成。

2）第二次扫描

为发现频繁2-项集的集合L2，算法使用L1∞L1产生候选2-项集的集合C2。在剪枝步没有候选项从C2中删除，因为这些候选的每个子集也是频繁的。

3）第三次扫描

L2∞L2产生候选3-项集的集合C3。

候选3-项集C3的产生过程如下。

（1）连接C3=L2∞L2。

（2）使用Apriori性质剪枝：频繁项集的所有非空子集也必须是频繁的。例如，{I1，I3，I5}的2-项子集是{I1，I3}、{I1，I5}和{I3，I5}。{I3，I5}不是L2的元素，因而不是频繁的。因此，从C3中删除{I1，I3，I5}。

（3）这样，剪枝C3={{I1，I2，I3}，{I1，I2，I5}}。

算法使用L3∞L3产生候选4-项集的集合C4。L3∞L3={I1，I2，I3，I5}，根据Apriori的性质，因为它的子集{I2，I3，I5}不是频繁的，所以这个项集被删除。这样C4=ø，因此算法终止，找出了所有的频繁项集。

6.2.4　Apriori算法的程序实现

在实践中，事务记录通常有上万条，这时就要借助程序找出所有的频繁项集。下面将介绍一种用程序实现Apriori算法的方法。

为了便于对数据进行处理，首先对数据库中的事务进行映射。映射的方法是看每条事务中是否包含项集中的所有元素，如果包含对应的元素，则标记为1，否则为0，这样就可以得到由所有事务组成的0-1矩阵。以表6-2为例，对该表的事务进行映射后，可得到如表6-3所示的新的事务矩阵。

当进行这样的处理后，用程序进行处理就会更容易。接下来，按照Apriori算法的步骤，编写如P6-1所示的程序，则很快得到表6-3对应的频繁项集的0-1映射矩阵。

上述矩阵的最后一列是频繁项集的支持度。通过比较可以发现，用程序得到的结果与6.2.3节的结果是一致的，但用程序寻找频繁项集的效率要高得多，尤其是当事务记录增多后。

6.2.5　Apriori算法的优缺点

Apriori算法的最大的优点是算法思路比较简单，它以递归统计为基础，生成频繁项集，易于实现。Apriori算法作为经典的频繁项集生成算法，在数据挖掘技术中占有很重要的地位。但通过上述分析发现，为了生成Ck，连接步需要进行大量的比较，而且由连接产生的项集即使后来由Apriori的性质确定了它不是候选项集，在确定之前仍然需要对它生成子项集，并判断子项集是否都在L(k-1)中。这些步骤浪费了大量的时间，如果可以保证由连接步生成的项集都是候选项集，那么可以省掉不必要的连接步和剪枝步。