一种基于逆序编码性质的Apriori算法改进

张华飞，董黎刚，王 盛

(浙江工商大学信息与电子工程学院，浙江杭州310018)

0 引言

随着关联规则［1］挖掘概念的提出，经典的Apriori算法［2］逐渐在该领域被广泛的应用。为应付日益膨胀的数据量，当前挖掘算法结合多种策略进行改进，如基于剪枝技术的Apriori改进算法［3］，采用HAPPI结构的算法［4］，采用PLT结构的算法［5］，DMFIA算法及UMFIA算法［6］。这些算法改进预处理技术以提高挖掘效率但较大幅度增大了系统开销，预处理后的数据，无法对原始数据进行很好的回溯，对于新增加的项目，转换后的数据对新数据无法兼容，必须整体重新扫描生成数据，这种特性降低了数据分析的效率，也增加了系统的开销。同时，这些算法对当前基于网络的分布式数据库系统的数据分析兼容性存在不足。再如结合压缩事物信息技术的算法［7］，这些算法改进幅度较小，性能提升有限。另外，位向量以其运算简单，存储容量要求相对较低的优点为算法的改进方向提供了一些思路［8］。一种基于位向量的BF-Apriori算法［9］较好地克服了以上算法适用性范围狭窄的问题，但其性能方面依然存在问题。为此，本文将针对该算法性能上的不足，做进一步的改进，提出BF_Advanced-Apriori算法。

1 主要定义和性质

为了描述BF_Advanced-Apriori算法，根据B-Apriori算法描述给出定义1，定义2［8］，根据BF-Apriori给出性质1［9］，并增补两条性质，性质2及性质3。

定义1 事务－位向量(项目集－位向量)的编码关系。给定I={I1，I2，…，Im}(项目按其支持度大小逆序排列，m为数据库包含的项目总数，限于篇幅，下面将不再说明)。事务数据库表示为D，事物T∈D(项目集X)，并且T⊆I(X⊆I)，规定f:T ×I(X ×I)→b1b2b3…bk(1≤k≤m，k值为事务T(项目集X)中存在项目的逆序位置序号最大值)，并称b=b1b2b3…bk为事务T(项目集X)所对应的位向量，记为 Bt(Bx)，其中 bj∈{0，1}，若事务中包含 Ij，则 bj=1，否则 bj=0，j=1，2，…，k。

定义2 长度Length。给定I={I1，I2，…，Im}及位向量Bt(Bx)。将Bt(Bx)包含位值1的数目称为Bt(Bx)的长度，记为Length(Bt(Bx))。

性质1 若项目Ix在频繁项集Lk－1中出现的次数小于k－1次，那么Ix就不可能是频繁项集Lk的元素。

证明 由频繁项集的定义可知，频繁项集的任一子集都是频繁的。频繁项集Lk的k－1维子集意味着在k个项中去掉一个，那么每一项目在Lk的k－1维子集中出现的次数等于k－1次，所以若某一项目在频繁项集Lk－1中出现的次数小于k－1次，那么它就不可能是频繁项集Lk的项，性质1得证。

性质2 给定 I={I1，I2，…，Im}，对于 k 项集 X1，X2，对应位向量分别为 Bx1，Bx2，Length(Bx1)=Length(Bx2)=k，当且仅当Length(Bx1xor Bx2)=2时，项集X1与X2有且只有k－1个元素相同。

证明 因为Length(b1xor b2)=2，根据逻辑“异或”的定义，项目集X1，X2必有两个位值相异，相异的情况是{(0，1)，(1，0)}，{(1，0)，(0，1)}，{(1，0)，(1，0)}，{(0，1)，(0，1)}，而当 Length(b1)=Length(b2)=k 时，相异的的情况只能是{(0，1)，(1，0)}或{(1，0)，(0，1)}，所以项集 X1 与 X2 有且只有k－1个元素相同，性质2得证。

性质3 给定I={I1，I2，…，Im}，I中前k个项目的支持度计数大于最小支持度minsup。那么候选频繁项集在匹配时，仅需匹配前k项。

证明 根据Apriori算法的原理，候选频繁项集的组成项目来源于频繁的项(项支持度计数大于阈值的项)，所以，在逆序编码情况下，匹配过程仅需匹配前k项，性质3得证。

2 数据处理及规则挖掘

假设I={I1，I2，…，Im}是m个项的集合(m为数据库所涉及项目的总数且项目按项目支持度(概率)从大到小排列)，事物T构成数据库D。T⊆I，T⊆D，项的集合X同样满足X⊆I，X⊆D，minsup表示最小支持度阈值，X.sup表示项集X在事务数据库D中所对应的支持度计数。

图1 RC算法示例

2.1 数据预处理算法

算法1 逆序编码算法RC

根据定义1给出的事务－位向量编码定义和规则，本文给出了的RC算法示例，如图1所示。

显然，RC算法空间效率提升的具体程度要根据具体的项目支持度的分布情况而定。

而RC算法的理论平均时间复杂度为O(n)，此处n代表事物数。空间复杂度为S(1)。

2.2 规则生成频繁k－项目集算法

算法2 候选频繁项集生成算法CFIG

输入:频繁k－1项目集Lk－1输出:候选频繁k项目集Ck

☆ BL(k－1)={Bx|X∈Lk－1};//BL(k－1)为 Lk－1对应的位向量集合

☆BC(k)={Bx|X∈Ck};//BC(k)为Ck对应的位向量集合

☆ For all Ik－1∈ Lk－1do begin // 遍询 Lk－1的项目 Ik－1

☆ If(IFrek－1＜ k －1)then Ij=Ik－1and Lk－1=Lk－1－ Lk－1(Ij);//IFrek－1为项目 Ik－1在 Lk－1中出现的频率。删除包含项目Ij的Lk－1元素，见性质1

☆End

☆ For all Mb∈ BL(k－1)，Nb∈ BL(k－1)do begin //Mb，Nb 分别为集合 BL(k－1)中任意两个元素

☆MN=Mbxor Nb;

☆If(Length(MN)=2＆＆MN∉BC(k))then BC(k)=BC(k)∪ MN;//MN包含位值1的个数为2，则MN加入BC(k)，见性质2

3）存储管理。利用Qt的文件类QFile和数据库SQL模块等，进行自动存储管理，如记录ROV状态信息、清理临时文件等。

☆End

显然，CFIG算法减少了频繁项集拼接时产生的部分候选项集。CFIG算法的理论平均时间复杂度为O(n2)，此处n代表k－1频繁项集数目。空间复杂度为S(1)。

算法3 基于逆序编码的模式匹配算法PMRC

输入:候选频繁k项目集Ck输出:频繁k项集Lk

☆BC(k)={Bx|X∈Ck}; //BC(k)为Ck对应的位向量集合

☆BL(k)={Bx|X∈Lk}; //BL(k)为Lk对应的位向量集合

☆ BL(k)=Φ; //BL(k)初始为空集

☆BT={Bx|X∈T};//BT为事物T对应的位向量集合

☆ For all Pb∈ BTdo begin//遍询事物集

☆For all Qb∈ BC(k)do begin //遍询候选频繁项集

☆If(Qb=Pband Qb)then Qb.sup++;//匹配，该过程仅在位向量包含频繁项目的一端m位(m为频繁一项集L1的数目)进行，见性质3

☆End //Ck的匹配计数结束

☆For all Qb∈ BC(k)do begin//遍询候选频繁项集

☆ If(Qb.sup＞minsup)BL(k)=BL(k)∪ Qb;//筛选大于最小频繁支持度的Ck作为Lk

☆End

PMRC算法性能分析:假设数据库包含M条事物，N个项目，在支持度minsup下有s项频繁项，且以1位运算为基本运算量单位(其他定义同上)。那么模式匹配过程，PMRC算法所需匹配的模式长度为:

运算量为:

仅基于位向量的模式匹配算法所需匹配的模式长度为:

运算量为:

使用PMRC算法而减少的运算量占比:

由分析结果可以看出，最小支持度minsup取值越大，s越小，PMRC算法的性能也就提升越明显。PMRC算法的理论平均时间复杂度为O(n*m)，此处n代表事物数，m为候选频繁项集数目，且m＜＜n。空间复杂度为S(1)。

2.3 BF_Advanced-Apriori算法的性能验证

为了验证算法性能，本文在电脑上实现了BF_Advanced-Apriori算法和B-Apriori算法(同属于一类算法)［8］生成3 － 频繁项集。实验采用由 Tom Brijs提供的 retail数据集(http://fimi.cs.helsinki.fi/data/)，在支持度阈值为1 000的情况下，撷取不同大小的数据集(单位:条)10 000，20 000，…，80 000，88 162分别进行3－频繁项集的挖掘，算法执行时间如图2所示。

从图2可以看出，BF_Advanced-Apriori算法的执行效率明显优于B-Apriori算法，并且随着数据集的增大，BF_Advanced-Apriori算法和 B-Apriori算法的性能差距在逐步扩大。

图2 3－频繁项集挖掘的算法执行时间

3 结束语

本文以B-Apriori的位向量数据结构为前提，设计完成了基于BF-Apriori逆序编码技术的Apriori改进算法BF_Advanced-Apriori.该算法保留了位向量易于转换，运算简单的优点，并有效克服了其空间性能不足的缺陷，同时，所涉及技术大幅度提升了算法的时间效率。改进算法能令新数据兼容已转换的数据，其所具有数据高可压缩性和可分割性，为大幅提升分布式系统间的交互效率提供了条件。可见，BF_Advanced-Apriori算法在海量数据的知识挖掘中将更加有效快速。

［1］ Agrawal R，Imielinske T，Swami A.Mining association rules between sets of items in large databases［C］.New York:ACM Press，1993:207 －216.

［2］ Agrawal R，Srikant R.Fast algorithms for mining association rules in large databases［C］.San Francisco:Morgan Kaufmann，1994:487－499.

［3］ 何海涛，吕士勇，田海燕.基于改进 Apriori算法的数据库入侵检测［J］.计算机工程，2009，35(16):154－158.

［4］ Wen Yinghsiang，Huang Jenwei，Chen Mingsyan.Hardware.Hardware-enhanced association rule mining with hashing and pipelining［J］.IEEE Trans on Knowledge and Data Engineering，2008，20(6):784－795.

［5］ Boukerche A，Samarah S.A novel algorithm for mining association rules in wireless ad hoc sensor networks［J］.IEEE Trans on Parallel and Distributed Systems，2008，19(7):865－877.

［6］ 宋余庆，朱玉全，孙志挥，等.基于FP-tree的最大频繁项目集挖掘及更新算法［J］.软件学报，2003，14(9):1 586－1 592.

［7］ RathinasabapathyR，Bhaskaran R.Performance comparison of hashing algorithm with Apriori［C］.Washington:IEEE Computer Society，2009:729 －733.

［8］ 陈耿，朱玉全，杨鹤标，等.关联规则挖掘中若干关键技术的研究［J］.计算机研究与发展，2005，42(10):1 785－1 789.

［9］ 王盛，董黎刚，李群.一种基于逆序编码的关联规则挖掘研究［J］.杭州电子科技大学学报，2010，30(5):169－172.