一种改进的Apriori算法的研究

王平

摘要：本文对关联规则数据挖掘经典算法Apriori算法需要重复扫描数据库的不足提出了一种新算法。该算法在连接两个频繁（k-1）-项集时，对其事务标识符进行交计算，得到新的候选k-项集。避免了对数据库的频繁扫描，大大提高了算法效率。

关键词：Apriori 关联规则 数据挖掘

中图分类号：TP311.13 文献标识码：A 文章编号：1007-9416（2014）12-0132-02

1 Apriori算法简介

在已经提出的所有关联规则的算法中，最经典的算法是Agrawal和Srikant的Apriori算法（1993）[1]。Apriori算法的具体执行步骤如下：

先产生频繁1-项集L1。首先扫描数据库，识别所有单个项（1-项集），记为C1。统计数据库中有多少个事务包含该项，这些事务的计数叫做1-项集的支持度。删除支持度低于用户所规定的最小支持度的1-项集，得到频繁1-项集，记为L1。

对于k=2，3，…，产生过程按如下方法由频繁（k-1）-项集得到频繁k-项集。在频繁（k-1）-项集列表上进行（k-1）-项集对的连接运算，创建候选k-项集列表。当且仅当两个项集的前（k-2）项相同，一对（k-1）-项集被连接在一起。如果条件满足，则该对能连接成一个k-项集，它包括前（k-2）个公共项和两个非公共项，两个非公项分别来自两个（k-1）-项的成员。

根据Apriori的性质，一个项集是频繁的，则它的所有非空子集都必须频繁的。换句话说，如果一个项集不是频繁的，则它的所有超集都不可能是频繁的。

推广到一般情况，在Lk-1中通过与自身项集的连接得到候选k-项集。为压缩Ck，结合Apriori性质，若一个候选k-项集Ck的（k-1）项子集不在Lk中，则该候选也不可能是频繁的，从而将其从Ck中删除。选择不小于最小支持度的候选项集，得到Lk。重复以上过程，直到不再有候选（或频繁）项集为止。

2 Apriori算法缺陷分析

（1）对于每次生成的候选项集Ck的每一个候选项集，都必须扫描数据库进行其支持度计数。扫描过程需要数据频繁地进出，因此算法效率很低。

（2）产生了大量的候选项集，候选2-项集尤为多。Ck是Lk的超集，呈指数级增长。

3 Apriori算法的改进

针对Apriori算法的两个致命的缺陷，国内外专家学者提出以Apriori算法为基础的一些改进算法。Savasere等[2]提出了基于数据分割的算法，将数据库中的事务划分成多个互不相交的块，在不同的块上产生局部频繁项集，通过对原数据库的两次扫描完成频繁项集的挖掘。Brin等[3]提出了基于动态项集计数的DIC算法，其与Apriori算法的区别在于，将事务数据库划分成多个区段，在搜索数据库时，利用各区段的特性，动态产生候选集的同时也能计算出其支持度。

对各种算法进行了分析与研究，发现影响算法效率的主要缺陷是频繁地扫描数据库，为减少扫描次数而提出了一种新的算法。算法步骤如下：

（1）扫描所有事务，对每个项计数，产生候选项集C1。C1不只是数据项集和计数的集合，而同时为产生的每个候选项集添加一个属性：事务标识符。将小于最小支持度计数的候选项删除，得到频繁1-项集L1。

（2）Lk-1自身进行连接操作，生成k-项集Ck。此过程需生成Ck的事务标识符，即把两个满足连接条件的Lk-1标识符进行求交计算。再统计Ck各项集中事务标识符的计数，即Ck各项集的计数（如表1）。

具体执行过程：

（1）扫描数据库，产生候选集C1，如表2所示。

（2）由C1确定频繁项集L1（如表3）。

（3）对L1进行连接，生成C2。每生成一个新的候选项集，通过计算两个项的事务标识符的交，然后统计新的事务标识个数，并与最小支持度进行比较，如果新的事务标识符的计数小于最小支持度，则将该项从C2中删除。

{A，B}.LIST=A.list∩B.list={S1，S4，S8，S9}≥min_sup

{A，C}.LIST=A.list∩C.list={S5，S7，S8，S9}≥min_sup

{A，D}.LIST=A.list∩D.list={S4}≤min_sup（删除）

{A，E}.LIST=A.list∩E.list={S1，S8}≥min_sup

{B，C}.LIST=B.list∩C.list={S3，S6，S8，S9}≥min_sup

{B，D}.LIST=B.list∩D.list={S2，S4}≥min_sup

{B，E}.LIST=B.list∩E.list={S1，S8}≥min_sup

{C，D}.LIST=C.list∩D.list=≤min_sup（删除）

{C，E}.LIST=C.list∩E.list={S8}≥min_sup

{D，E}.LIST=D.list∩E.list=≤min_sup（删除）

通过以上计算得出带有事务标识符属性的候选项集C2，如表4所示。

（4）根据上表生成频繁2-项集L2，如表5所示。

（5）重复步骤3，生成C3。

根据其Apriori性质可得，{A，C，E}，{B，C，D}，{B，C，E}，{B，D，E}均被剪枝。

只剩项集{A，B，C}.list={S8，S9}

{A，B，E}.list={S1，S8}

由此结果生成候选项集C3，如表6所示。

（6）生成频繁项集L3，如表7所示。

（7）生成C4。

{A，B，C，E}.list={S8}≤min_sup，因此L4=。

至此不再产生新的候选项集，算法终止，找到了全部的频繁项集。

从以上可以看出，Apriori改进算法相比未改进的Apriori算法的优势在于：在整个数据挖掘过程只对数据库扫描一次。改进算法只在第一步产生1-候选项集C1时需要对数据库扫描一次，以便获取当前所有项集的事务标识符。之后不需要扫描事务数据库去确定每个项集的支持度，只需统计Ck中事务标识符的个数。新算法在时间上具有明显优势，尤其数据量比较庞大时，这种优势更加显著。

参考文献

[1]（印度）K.P.Soman Shyam Diwakar.数据挖掘基础教程[M].范明，牛常勇译.北京：机械工业出版社，2012.120-129.

[2]Savasere A，Omiecinski E，Navathe S.An efficient algorithm for mining association rules inlarge databases[C].Morgan Kaufmann Publisher，1995.432-443.

[3]Brin S，Motwani R，Ullman J D，et al. Dynamic itemset counting and implication rules for market basket data[C].ACM Publisher Press 1997.255-264.endprint