关联规则中经典的Apriori算法研究

摘 要：本文主要介绍了关联规则中的Apriori算法。通过对该算法的研究，挖掘数据之间的联动关系。

关键词：关联；Apriori

Apriori算法使用了逐层查寻的方式，一遍一遍的扫描事务数据库，得到各层频繁K项集，并利用当层得到的K项集，生成候选的（K+1）项集，直到不能再生成频繁K项集为止。关联挖掘问题被分成如下2个问题：⑴寻找所有的这样的项的集合，它们的支持度不小于用户指定的最小支持度阈值，这样的集合称为频繁项集。⑵利用频繁项集产生规则。一般的想法是，如果B1，B2，B3和B1，B2是频繁项集，那么通过计算置信度，conf=P（B1B2B3）/P（B1B2）来确定{B1，B2，B3}这个规则是否成立，当它不小于最小置信度阈值时，规则成立。为了避免需要算出所有项集的支持度，Apriori引入了候选项集概念，并将候选项集记为Ck。这里需要介绍关联规则两条重要的性质，如下：（1）频繁项集的所有非空子集也必须是频繁的。 （2）非频繁项集的所有超集一定是非频繁的。

例如，如果项集{ B1，B2}是非频繁的，即数据库中同时包含的B1，B2的事务的个数小于min_sup，那么数据库中同时包含B1，B2，B3的事务的个数肯定是小于min_sup的，即{B1，B2，B3}一定是非频繁的。而Apriori算法只运用了性质（1），通过已经找到的频繁项集去构造更大的频繁项集，就是候选项集Ck，它是有可能成为频繁k项集的项集的集合。使用Lk-1生成Lk的详细过程如下：（1）连接步骤：通过Lk-1∞Lk-1来生成Ck：如果Lk-1中两个频繁项集L1和L2的前（k-2）个项相同，但L1的第（k-1）项排在L2的第（k-1）项的前面，那么将它们合在一起可以形成一个k项集。（2）修剪步骤：A.如果Ck中一个候选k项集的某个（k-1）子项集不在Lk-1中，则将该候选项集从Ck中删除。B.对仍在Ck中的没被删除的候选k项集，扫描数据库来计算它们的支持度计数，生成Lk，Lk中包含了Ck中支持度不小于min_sup的所有项集，它们都是k项频繁项集。

1 算法的伪码实现

算法的伪码表示如下：

输入： D：事务数据库；

min_sup：最小支持度计数阈值。

输出：L：所有频繁项集。

方法：

（1） L1={frequent 1-itemsets}；

for（k=2；Lk-1≠，k++）

{ Ck=apriori-gen（Lk-1）； for each transaction t∈D

{Ct=subset（Ck，t）；

for each candidate c∈Ct

c.count++；}

Lk={c∈Ck|c.count≥min_sup}}

return L=kLk

（2） procedure apriori-gen（Lk-1：frequent （k-1）-itemsets）

for each itemset L1∈Lk-1

for each itemset L2∈Lk-1

if （L1[1]^L2[1]）= （L1[2]^L2[2]）=^…^ （L1[k-1]

{

c=L1∞L2；

if has_infrequent_subset（c，Lk-1）then

delete c； else

add c to Ck；

} return Ck；

（3） procedure has_infrequent_subset（c，Lk-1）

for each （k-1）-subset s of c

if sLk-1

return TRUE；

return FALSE；

2 算法的实例

假设数据库中有10个事务，数据库如下：

表2.2 原始数据库

事务TID 项集

TID1 B1，B2，B3

TID2 B2，B3，B5

TID3 B3，B4

TID4 B1，B2，B3

TID5 B1，B3

TID6 B2，B5

TID7 B1，B2

TID8 B2，B3

TID9 B2，B4

TID10 B1，B3，B5

（1）第一次执行，找出项集中所有的项构成候选1项集C1，并对每个项统计出现的次数。如果规定的最小支持度计数min_sup=2（2为绝对支持度），则找出候选1项集中大于min_sup的项，然后构成频繁一项集L1。

（2）第二次执行是为了求的2项集L2，这里需要对L1进行自身连接产生C2。设n=|L1|表示的是L1中项的个数，那么C2产生的2项集的个数则是n（n-1）/2，如果项集太多的话，那么如此多的项集对时间效率和空间容量是个巨大的考验。而本例的项集较小，连接步之后，

再进行剪枝步，由于1项集都是频繁的，所以不用剪枝，都进入C2中。

（3）将各个项集的支持度计数与最小支持度计数阈值进行比较，删除小于min_sup的项集，结果就是L2，即频繁2项集。然后对L2进行自连接，连接完成后进行剪枝，这里需

要根据Apriori算法的性质来删除部分项集，然后产生候选项集C3。根据性质，频繁项集的各个子集都是频繁的，删除C3中不频繁的项集{B1，B2，B5}，{B1，B3， B5}。这样在后面的扫描过程中就不需要计算它们的支持度了。

（4）得到候选项集C3后，再在原始数据库中扫描一次，计算各个项集的支持度，然后

把小于min_sup的项集删除，得到频繁3项集L3。

（5）因为L3中只有一个项集，无法再产生4项集了，因此算法结束，把前面的频繁项集综合起来，构成了全部的频繁项集。这样，运用Apriori算法就求得了所有的频繁项集。

作者简介

朱建斌（1980-），江西南昌人，本科.研究方向：电工电子。