基于Apriori算法的降低数据库扫描记录数的挖掘算法研究

安颖 马桂真

（北京联合大学旅游学院 北京市 100101）

在数据挖掘的知识模式中，关联规则用于表示数据库中一组对象之间某种关联关系的规则。关联规则的挖掘就是要找出支持度大于等于指定的最小支持度阀值这样的一些规则，挖掘过程分两步完成：

步骤一：找出所有支持度大于事先给定的最小支持度的频繁项集；

步骤二：从找出的频繁项集中产生强关联规则，即产生那些支持度大于等于预先给定的最小支持度的关联规则。

关联规则挖掘的特点是数据量庞大，所以算法的总体性能主要取决于第一步，因此高效率地找出所有频繁项目集是衡量关联规则挖掘算法性能的重要指标。在传统的算法中，往往通过多次扫描数据库来实现，算法的主要时间将花费在扫描数据库和I/O 操作上，因此算法运行效率较低，也是各种改进算法需要解决的核心问题。

1 经典关联规则算法

1.1 经典Apriori算法

关联规则挖掘的经典算法是Agrawal 等人在1994年提出的Apriori 算法。随后，围绕着如何提高这个算法的性能问题，研究人员进行了大量的改进工作。

Apriori 算法发现关联规则的过程首先要找出所有支持度大于等于预先给定的最小支持度阀值的所有属性的组合，称为频繁项集，记为Lk，这一步是算法性能高低的关键步骤。然后利用频繁项集产生满足最小支持度阀值的所有规则。为了找到Lk，Apriori 算法使用一种称为逐层搜索的迭代方法，即首先通过Lk-1 与自己连接产生候选K-项集，记为Ck，然后通过剪枝，剔除Ck 中非频繁项集，得到Lk。

1.2 影响Apriori算法性能的主要问题

基于频繁项集的Apriori 算法采用了逐层搜索的迭代的方法，即利用候选项集和频繁项集得到全部频繁项集，并通过对候选项集的剪枝，大幅度降低了候选项集的大小，得到了预期的结果。然而，Apriori 算法在性能上仍存在着一些问题：

该算法需要重复扫描数据库来计算侯选项集的支持度计数，从而严重影响了算法的运行效率。

2 Apriori算法改进

针对Apriori 算法瓶颈问题，本文提出了一种改进算法，即通过减少数据库扫描次数的方法提高Apriori 算法的效率。

2.1 BTA算法思想

图1：两种算法在不同支持度阀值下的时间开销

在经典的Apriori 算法中，计算侯选项集的支持度计数是通过重复扫描数据库来实现的。为了改善这个问题，提高算法性能，本文提出一种基于事务标号集的关联规则算法BTA(Based on Tid_set Apriori)。

BTA 算法只在第一次扫描数据库得到频繁项集各项的事务标识号后，就无需再对数据库进行扫描，由频繁n 项集在生成候选n+1项集时，对相关项的Tid 集进行交运算，生成新的Tid 集，通过Tid 集中包含的事务数计算候选集中相关项的支持度。将大于支持度阀值的记录组成频繁n+1 项集，如此反复，直到产出最终所需要的频繁项集为止。区别于经典的Apriori 算法，BTA 算法只需要在产生侯选1-项集时扫描一次数据库，计算剩余的侯选项集支持度计数时只统计相应Tid 集合元素的个数即可。这样就不用重复扫描数据库，降低了访问数据库的I/O 操作时间，提高了Apriori 算法的效率。

BTA 算法基本步骤为：

（1）首先，逐个扫描事务数据库，产生1-项候选集合Cl，在扫描每个事务时，除了对每个项计数外，还要记录包含该项的事务标识符Tid。这样扫描完一遍数据库后，我们得到的候选集Cl中，每个项集都包含一个相应的事务标识符列表。Cl的结构如下：

(项集Item_set，支持度计数support，事务标识符集Tid_set)

（2）从Cl中删除不满足最小支持度计数的项集，得到Ll。

（3）Lk-1进行自连接，生成Ck，其中Ck的事务标识符集等于生成它的两个Lk-1的事务标识符集的交集。计算Ck中项集所对应的事务标识符集中的Tid 个数，就得到了Ck中每一个项集的计数。

2.2 BTA算法描述

下面是BTA 算法的描述：

输入：事务数据库D；最小支持度阀值minsup。

输出：D 中的频繁项集L。

Cl=create_candidaet_1(D) ；//创建1-项侯选集

Ll={cand∈Clcand.support)>= minsup}；//选出1-项频繁集

For (K=2；Lk-1<>φ；k++)

｛apriori_generate (Lk-1，minsup)；// 调用apriori_generate 生成候选集Ck

Lk= Ck.Item_set；/选出频繁项集Lk

｝

Answer：L=∪kLk；/合并所有的Lk

Procedure apriori_generate (Lk-1: frequence _item;minsup:int)

//产生最小支持度为minsup 的候选集Ck

{for each Item_set li∈Lk-1

for each Item_set lj∈Lk-1

if (li[1]= lj[1]∧li[2]=lj[2]∧……∧li[k-2]= lj[k-2]∧li[k-1]< lj[k-1]) then

{cand= li∪lj//连接频繁项集Lk-1，得到一个候选项集C

If has_inftequence_subset(cand, Lk-1) then // 利 用Apriori 性质剪枝

Delete cand；

Else

{cand.Tid_set=li.Tid_set ∩lj.Tid_set；//计算该项集的事务标识集的交集

cand.support=length(cand.Tid_set) ；//计算该项集的支持度计数if cand.support

delete cand；

else

add cand to Ck

}

}

Return Ck；

}

Procedure has_infrequence_subset(cand:candidate_k_itemset；Lk-1:frequence(k-1)_itemset)

//判断候选项集的子集是否为频繁项集

For each(k-1)_subset s of cand

If s ! ∈ Lk-1 then

Return true；

Return flase；

2.3 实验验证BTA算法与Apriori算法的性能

通过上述算法描述可以看出，BTA 算法只有在第一步生成侯选1-项集Cl的时候扫描了一遍数据库，从而获得了每个项集的Tid 列表；计算其他侯选项集支持度计数时，只需统计侯选项集中相应事务标识符列表中的Tid 个数即可。假设侯选项集Cl的数目为|Cl|，数据库中的记录数为n，每条记录的平均容量为v，则计算侯选集C1 所需的时间为O(|Cl|nv)，由于只扫描一遍数据库，因此BTA 算法总时间开销为O(|Cl|nv)(此处忽略内存运行时间)。与Apriori 经典算法的总时间开销O(∑k|Ck|nv)相比，BTA 算法大大节省了时间开销。

为了便于比较，我们利用模拟实验数据集测试两种算法的运行时间。实验环境：计算机硬件配置是Intel Core CPU 2.5GHZ/4GB/100GB，操作系统是Windows7，在VC++6.0 编程环境中分别实现Apriori 和BTA 算法。

实验数据集为：Mushroom，含8124 个事务，该数据库由蘑菇的颜色、气味、形状、生长环境、……、类别等23 个属性组成。每种属性有2～12 个枚举值，共128 个不同项。数据集取自UCI Machine Learning Repositoty。在不同的支持度阀值下，两种算法执行时间如图1 所示。

3 结论

综上所述，针对不同的支持度，BTA 算法的执行效率要比Apriori 算法高。而且BTA 算法的执行效率优势在支持度较小时更加明显，其原因是随着支持度的减小，候选项目集逐渐增多，Apriori 算法进行数据库扫描计算支持度所需时间迅速增加。而BTA 算法只需扫描一次数据库，通过事务标识符集的交集计算支持度，算法运行时间得到很大的缩减。