1.1.3 实例说明

以事务数据库D为例，数据库有9个事务，即|D|=9，见表1-1。使用Apriori算法发现D中的频繁项集。

（1）在算法的第一次迭代时，每个项都是候选1-项集的集合C1的成员。算法简单地扫描所有事务，计算每个项出现的次数。

C1：

（2） 假设最小支持度计数为2，即min_sup=2（这里谈论的是绝对支持度，因为使用的是支持度计数，对应的相对支持度为2/9=22％）。可以确定频繁1-项集的集合L1，它由满足最小支持度的候选1-项集组成。本例中，C1中的所有候选都满足最小支持度。

L1：

（3）为了发现频繁2-项集的集合L2，算法使用连接L1L1（等价于L1×L1，因为L1L1的定义要求进行两个连接的项集共享k−1=0个项）产生候选2-项集的集合C2。C2由个2-项集组成。注意，在剪枝步，没有候选项集从C2中删除，因为这些候选的每个子集也是频繁的。

C2：

（4）扫描D中的事务，累计C2中每个候选项集的支持度计数。

C2:

（5） 确定频繁2-项集的集合L2，它由L2中满足最小支持度的候选2-项集组成。

L2:

（6）候选3-项集的集合C3的产生详细过程如下。在连接步，首先令C3=L2L2=｛｛I1,I2,I3｝, ｛I1,I2,I5｝, ｛I1,I3,I5｝, ｛I2,I3,I4｝, ｛I2,I3,I5｝, ｛I2,I4,I5｝｝。根据先验性质，频繁项集的所有子集必须是频繁的，可以确定后4个候选子集不可能是频繁的。因此，把它们从C3中删除，这样，在此后扫描D确定L3时就不必再求它们的计算数值。注意，由于Apriori算法使用逐层搜索技术，给定一个候选k-项集，只需要检查它们的（k−1）项子集是否频繁即可。

（a）连接：C3=L2L2=｛｛I1,I2｝, ｛I1,I3｝, ｛I1,I5｝, ｛I2,I3｝, ｛I2,I4｝, ｛I2,I5｝｝｛｛I1,I2｝, ｛I1,I3｝, ｛I1,I5｝, ｛I2,I3｝, ｛I2,I4｝, ｛I2,I5｝｝=｛｛I1,I2,I3｝, ｛I1,I2,I5｝, ｛I1,I3,I5｝,｛I2,I3,I4｝, ｛I2,I3,I5｝, ｛I2,I4,I5｝｝。

（b）使用先验性质剪枝：频繁项集的所有非空子集必须是频繁的。

● ｛I1,I2,I3｝的2-项子集是｛I1,I2｝,｛I1,I3｝和｛I2,I3｝。｛I1,I2,I3｝的所有2-项子集都是L2的成员。因此，｛I1,I2,I3｝保留在C3中。

● ｛I1,I2,I5｝的2-项子集是｛I1,I2｝,｛I1,I5｝和｛I2,I5｝。｛I1,I2,I5｝的所有2-项子集都是L2的成员。因此，｛I1,I2,I5｝保留在C3中。

● ｛I1,I3,I5｝的2-项子集是｛I1,I2｝,｛I1,I5｝和｛I3,I5｝。｛I3,I5｝不是L2的成员，因而不是频繁的。因此，从C3中删除｛I1,I3,I5｝。

● ｛I2,I3,I4｝的2-项子集是｛I2,I3｝,｛I2,I4｝和｛I3,I4｝。｛I3,I4｝不是L2的成员，因而不是频繁的。因此，从C3中删除｛I2,I3,I4｝。

● ｛I2,I3,I5｝的2-项子集是｛I2,I3｝,｛I2,I5｝和｛I3,I5｝。｛I3,I5｝不是L2的成员，因而不是频繁的。因此，从C3中删除｛I2,I3,I5｝。

● ｛I2,I4,I5｝的2-项子集是｛I2,I4｝,｛I2,I5｝和｛I4,I5｝。｛I4,I5｝不是L2的成员，因而不是频繁的。因此，从C3中删除｛I2,I3,I5｝。

（c）剪枝后C3=｛I1,I2,I3｝,｛I1,I2,I5｝。

C3剪枝后的版本：

（7）扫描D中事务以确定L3，它由C3中满足最小支持度的候选3-项集组成。

L3：

（8）算法使用L3L3产生候选4-项集的集合C4。尽管连接产生结果｛｛I1,I2,I3,I5｝｝，但是这个项集被删去，因为它的子集｛I2,I3,I5｝不是频繁的。这样，C4=∅，因此算法终止。

下面给出了Apriori算法和它的相关过程的伪代码[2]。Apriori算法的第1步是找出频繁1-项集的集合L1。在第2～10步，针对候选集Ck进行计数，以便找出Lk。apriori-gen函数产生候选集，然后使用先验性质删除那些具有非频繁子集的候选项（步骤3），该过程在下面介绍。一旦产生了所有的候选项，就扫描数据库（步骤4）。对于每个事务，使用subset函数找出该事务中是候选项的所有子集（步骤5），并对每个这样的候选项累加计数（步骤6和步骤7）。最后，所有满足最小支持度的候选项（步骤9）形成频繁项集的集合L（步骤11）。

如上所述，apriori_gen函数实现两个功能：连接和剪枝。在连接部分，Lk-1与Lk-1连接，产生可能的候选集。剪枝部分使用先验性质删除具有非频繁子集的候选项。非频繁子集的测试过程在has_infrequent_subset函数中实现。

表1-1中，包含频繁项集X=｛I1,I2,I5｝。X的非空子集是｛I1,I2｝、｛I1,I5｝、｛I2,I5｝、｛I1｝、｛I2｝和｛I5｝。将Apriori算法应用于频繁项集X产生关联规则，结果如下，每个规则都列出了置信度。

①｛I1,I2｝⇒I5, 可信度= 2 /4 = 50％。

②｛I1,I5｝⇒I2, 可信度= 2 /2 = 100％。

③｛I2,I5｝⇒I1, 可信度= 2 /2 = 100％。

④I1⇒｛I2,I5｝, 可信度= 2 /6 = 33％。

⑤I2⇒｛I1,I5｝, 可信度= 2 /7 = 29％。

⑥I5⇒｛I1,I2｝, 可信度= 2 /2 = 100％。

如果最小置信度阈值为70％，则只有①②⑥是强规则。此处应注意，与传统的分类规则不同，关联规则的右端可能包含多个合取项。