}
张伟科
(沈阳理工大学 理学院， 沈阳 110159)
摘 要：针对经典Apriori算法多次扫描数据库产生I/O负载影响运行效率等问题，在对Apriori算法的原理及其相关改进算法研究的基础上，提出了一种基于压缩集的改进Apriori算法，即AprioriTid_M算法.通过有效的裁剪方法减少无效项集的产生，减少候选项集的数量，从而提高算法的效率.仿真实验表明，在支持度相同但数据量不同，以及数据量相同但支持度不同这两种条件下，AprioriTid_M算法在性能上和运算时间上都比Apriori算法有很大程度的改善.
关 键 词：Apriori算法； AprioriTid算法； AprioriTid_M算法； 关联规则； 置信度； 项集； 支持度； 性能
数据挖掘关联规则中相当经典的算法就是Apriori算法，该算法具有反单调性的特点.Apriori算法首先生成候选项集判断是否为频繁项集 [1]，所生成的频繁项集的任一子集均是频繁的，含有非频繁项集的任意子集的项集一定是非频繁的.运用迭代的思想，首先发现频繁1项集，由频繁 k-1项集生成 k候选项集，逐层扫描数据库后从候选 k项集中筛选出频繁 k项集，直到最终剩下的候选项集为空时算法结束 [2].
Apriori算法生成频繁项集的算法描述如下.
输入：数据集 D，设置最小支持度min_sup的阈值.
输出： D中的频繁项集 L.
L 1=find_frequent_1-itemset( D)；
for( k=2； L k-1 ≠ φ； k++){
C k =apriori_gen( L k-1 )；
//产生候选项集
for all transaction t∈ D{
C t =subset( C k ， t)；
//识别 t包含的所有候项集
for all candidates c∈ C t {
c.count++；
//支持度计算增值
}
}
L
k
={
}
//提取频繁 k项集
}
return L=∪ k L k ；
procedure apriori_gen( L k-1 )
for eachitemset l 1∈ L k-1
for eachitemset l 2∈ L k-1
if( l 1[1]= l 2[1])∧…∧( l 1[ k-2]= l 2[ k-2])∧( l 1[ k-1]< l 2[ k-2])then{
c=join( l 1， l 2)；
//连接：产生候选项集
if has_infrequent_subset( c， L k-1 )then
delete c
//剪枝：移除非频繁的候选项集
else
add cto C k
}
return C k
procedure has_infrequent_subset( c， L k-1 )
//使用先验知识判断候选项集是否频繁
for each( k-1)-subset sof c
if s∉ L k-1 then
return TRUE；
return FALSE
算法的具体步骤如下.
1) 单遍扫描数据集，得到每个项的支持度以及所有频繁1项集的集合 L 1.
2) 通过调用apriori_gen [3]函数对前一次扫描得到的频繁 k-1项集再次扫描，依据每项的支持度使判断阈值得到新的候选 k项集.apriori_gen函数由频繁 k-1项集生成候选 k项集，经过连接和剪枝，其两个步骤如下所示.
① 连接.连接频繁
k-1项集的集合
L
k-1
中每个项集的各个元素，并按照字典的顺序排列，任意的
k-1项集
k-1和
F″
k-1
，如果其所包含的前面
k-2个项是完全相同的，则连接成为一个候选
k项集
F
k
[4].
② 剪枝.由has_infrequent_subset函数完成 [5]，判定候选项集中的 k项集是否含有 k-1非频繁项集，若含有 k-1项集是非频繁的，则要将该候选项集删除以此完成剪枝.图1为Apriori算法挖掘事物数据的关联规则流程图.
图1 关联规则流程图
Fig.1 Flow chart of association rule
虽然Apriori算法能够实现对数据项的关联规则挖掘，但是随着数据库存储量的增加和对算法的迭代应用及研究，表明Apriori算法主要有两方面运行性能瓶颈 [6].
1) 反复多次扫描事物的数据库，增加了I/O的负载.Apriori算法每次进行 k循环都要完整地扫描数据库，判定候选项集 C k 中的每一个元素是否能够成为项集 L k .例如，一个最大频繁项集中有15个项，就需要至少扫描事物数据库15遍才能完成任务.对于海量数据挖掘来说，I/O负载量非常大.
2) 海量数据会产生异常庞大的候选项集.项集 L k-1 候选项集 C k 是呈指数增长的，数量庞大.例如，10 4个频繁1项集会产生大约10 7个元素的候选2项集 [7].庞大的候选项集浪费了存储空间，同时降低了运行效率，因此，算法的运行性能方面需加以优化.
2.1 AprioriTid算法
AprioriTid算法主要是通过减少扫描事物数据量来实现性能优化.一个事物中如果不包含 k阶大项集，则一定不含有 k+1阶的大项集.因此，忽略大项集事务后，可减少后续循环扫描事物的次数，并且不会影响到候选项集的支持度.
AprioriTid算法首先基于Apriori算法思想
[8]使用apriori_gen函数运算产生候选项集后，构造一个用来记录每条事物包含的候选项集Tid表.
k阶候选项集的Tid表记为
k
，其形式为〈
t，TID，{
}〉，其中，TID是事物
t的标识，
C是事物
t中包含的
k阶候选项集.如果一个事物不包含任何
k阶候选项集，那么这条事物就不会出现在
k
中.因为1阶候选项集
L
1就是所有的项，所以与
D完全相同.当
k>1时，
k
由
k-1
产生.如果第一事物包含了一个
k阶候选项集
C，那么也必然包括这个候选项集.因此，产生
k
的方法为对任一
k阶候选项集
C，如果
C的两个子集均包含在
k-1
里的某条记录中，那么就添加
C到
k
的相应记录中去.
k阶候选项集的支持数可从Tid表中获得，因而避免了事物包含的候选项集量过少的问题.随着循环次数的增加，扫描的数据量会越来越少，从而减少后续循环扫描事物的次数，提高执行效率.
AprioriTid算法的过程描述如下：
L 1={large 1-itemsets}；
//计算1阶大项集
；
for( k=2； L k-1 ≠ φ； k= k+1)；
C k =apriori_gen( L k-1 )；
//构造候选项集
φ；
for all transaction
k-1
do
C
t
={
C[
k-2]
C[
k]∈
t}；
// t包含的候选项集
for all C∈ C t do C.sup= C.sup+1；end for
φ
{<
t.
；
end if
//构造 k阶候选项集的Tid表
end for
L
k
={
}；
//计算 k阶大项集
end for
L=∪ k L k
2.2 AprioriTid_M算法
AprioriTid算法只在计算1项集的支持度时对数据库 D进行了扫描，减少了运行时间，但是过于庞大的候选项集还是会影响运行时间，因此，本文提出一种基于压缩集的AprioriTid_M改进算法.根据原理，频繁项集的所有非空子集一定是频繁项集 [9]，可得频繁 k项集的所有 k-1项集一定也是频繁的，以此为基础进一步地优化Tid表.
性质1 如果频繁 k项集可以产生频繁 k+1项集，那么频繁 k项集中的项集个数一定大于 k.
证明 由一切频繁项集的非空子集一定是频繁的，推出 L k+1 任何项集的 k+1个不同 k项子集一定在频繁 k项集中，证明完毕.
性质2 若 M k 是数据库 D中的频繁 k项集 [10]，那么 M k 中包含的任何一项在全部 k-1项集 M k-1 里出现的次数一定大于等于 k-1次.
证明 假设 N k ={ x 1， x 2， x 3，…， x k }， x i ∈ L k ，频繁项集 N k ∈ L k ， x i ∈ I， i=1，2，…， k，其中， I={ I 1， I 2，…， I m }是数据项的集合，则 N k 中任何一个含有 k-1个项的子集也一定是频繁项集，且它们都属于 L k-1 .设 N k-1， i = N k -{ x i }，则推出 x i ∈ N k -{ x j }， j≠ i， j=1，2，…， k，即 x i 一定在其他的 k-1项集集合中，因此，频繁 k项集 L k 中任意的 x i 项在 L k-1 里面至少出现 k-1次，证明完毕.
改进的AprioriTid_M算法生成
k
时，可依据
L
k-1
中每一项出现的频数，删除
k-1
里面频数小于
k-1项的项集.Tid表存储的是事物项所有可能的组合，若直接扫描已经剪枝后Tid表所得到的频繁项集，可以节省运行时间，提高算法的执行效率.因此，本文提出了改进的AprioriTid_M算法，具体改进方法为：与AprioriTid算法相同，首先产生
L
1和Tid表
1；当执行第
k步时，
k>1，调用A_prune函数删除掉
k-1
中的
k-1非频繁项集和包含在
L
k-1
中的频数小于
k-1次项的项集，同时删除事务中只有一个项集的项集.使用
k-1
里的每个事务项集组合得出
k
，通过统计
k
中每个项的频数产生
L
k
且直到
=0停止运算.改进的AprioriTid_M算法的伪代码如下.
L 1={频繁1项集}；
数据库
D；
for( k=2； L k-1 ≠ φ； k++)do begin；
//产生全部的频繁项集
L k-1 =A_prune( C k-1 )；
for所有条目
；
for每一个项目 T 1∈ t.set-itemsets；
for每一个项目 T 2∈ t.set-itemsets；
for所有候选 c∈ C t do；
if(( T 1[1]= T 2[1])∧( T 1[2]= T 2[2])∧…∧( T 1[ k-2]= T 2[ k-2])∧( T 1[ k-1]< T 2[ k-1])) then
{ c= T 1；
add cto C t ；
c.count++}；
if
c.
〈
t.TID，
C
t
〉；
end；
Answer= U k L k
应用改进的AprioriTid_M算法挖掘频繁项集，最小支持数设定为2.先对数据库
D进行扫描，生成
1和
L
1，统计每一项的支持数，根据最小支持数阈值，对
1中的非频繁项集
D进行剪枝，得到
1并对其中的每一个事物进行组合处理，得到
2，并统计
2中的2项集的支持数，符合设定支持数阈值的项集组成
L
2，统计
L
2每一个项的计数，进行剪枝处理，删除含有
A的项集，因为事务T4000只有一个项集进行剪枝，得到
2表.对组合
2表中的事物得到
3表，统计
3表得到
L
3，因为仅剩下{
B，
C，
E}，不能再得到
4，则运算结束，整个过程如图2所示.
图2 改进的AprioriTid_M算法示例
Fig.2 Example for improved AprioriTid_M algorithm
为了验证改进后的AprioriTid_M算法的性能，分别采用AprioriTid算法和改进的AprioriTid_M算法对相同的数据进行挖掘，测试出在不同的支持度下两种算法执行所需要的时间，和不同的数据规模下两种算法运行所需要的时间.操作系统采用Windows XP Professional，利用SQL 2005对实验数据进行预处理.
图3为设置不同支持度时，数据集量为1 000条时，使用AprioriTid算法和AprioriTid_M算法生成频繁项集所消耗的时间对比图.当数据量相同时，AprioriTid产生频繁项集的时间随着支持度的增加变化幅度比较大，性能不够稳定.改进的AprioriTid_M算法对于相同的数据进行运算时，时间变化幅度相对较小，且运算时间明显少于没有改进时所使用的时间，说明AprioriTid_M算法在计算时间和性能上比AprioriTid算法有很大程度的提高.
图3 支持度不同时产生频繁项集所需的时间
Fig.3 Time to generate frequent item sets
under different support degree
图4为分别选取事务数据量为2 000、3 000、4 000、5 000、6 000和7 000，支持度为0.5时两种算法运行所消耗的时间对比图.由图4可以看出，两种算法在数据量增加时，消耗的时间越来越多.但是在处理等量数据时，AprioriTid_M算法运行的时间明显小于改进前的算法消耗时间，且当数据量增加时，运行时间的增值幅度是趋于平稳的，而AprioriTid算法随事务总量增加时，消耗时间增长幅度比较大，性能不够稳定.
图4 支持度为0.5时两种算法的运行时间
Fig.4 Running time of two algorithms
with support degree of 0.5
图5为支持度为0.7时两种算法的运行时间.由图5可知，当支持度为0.7时，改进后的AprioriTid_M算法用时较少，且随着事务量的增长，运行时间平稳增长，而AprioriTid算法运行时间随事务量增加而急剧增长，性能不如改进后的算法稳定.
图5 支持度为0.7时两种算法的运行时间
Fig.5 Running time of two algorithms
with support degree of 0.7
综上可知，改进后的AprioriTid_M算法在性能上和运行效率上有所提高，稳定性比较好.
本文研究了经典Apriori算法的核心思想，分析了该算法性能上的缺点和不足，在此基础上研究了AprioriTid算法，并提出一种基于事务集压缩的AprioriTid_M算法.通过对这两种算法在等量事务数据、不同支持度下的运行时间比较和某一设定支持度下不同事务数据量的运行时间比较分析，证明了AprioriTid_M算法在性能和效率上均高于AprioriTid算法.
参考文献(References)：
[1]张春燕，孟志青，袁沛.文本挖掘的时态文本关联规则算法研究 [J].计算机科学，2013，40(6)：219-224.
(ZHANG Chun-yan，MENG Zhi-qing，YUAN Pei.Mining algorithm for temporal text association rules in text mining [J].Computer Science，2013，40(6)：219-224.)
[2]Silverstri C，Orlando S.Approximate mining of frequent patterns on streams [J].Intelligent Data Analysis，2007，11(1)：49-73.
[3]于孝美，陈贞翔，彭立志.基于决策树的网络流量分类方法 [J].济南大学学报(自然科学版)，2012，26(3)：291-295.
(YU Xiao-mei，CHEN Zhen-xiang，PENG Li-zhi.Traffic classification based on decision tree [J].Journal of University of Jinan(Science and Technology)，2012，26(3)：291-295.)
[4]Tsang S，Kao B，Kevin Y Y，et al.Decision trees for uncertain data [J].IEEE Transations on Knowledge and Date Engineering，2011，23(1)：64-78.
[5]Kohavi R，Provost F.Applications of data mining to electronic commerce [J].Data Mining and Knowldege Discovery，2011，5(1)：5-10.
[6]焉晓贞，谢红，王桐.一种基于相关分析的多元回归数据估计方法 [J].沈阳工业大学学报，2013，35(2)：212-217.
(YAN Xiao-zhen，XIE Hong，WANG Tong.Data evaluation method using multiple regression based on correlation analysis [J].Journal of Shenyang University of Technology，2013，35(2)：212-217.)
[7]翟云，杨炳儒，曲武，等.基于新型集成分类器的非平衡数据分类关键问题研究 [J].系统工程与电子技术，2011，33(1)：196-201.
(ZHAI Yun，YANG Bing-ru，QU Wu，et al.Study on source of classification in imbalanced datasets based on new ensemble classifier [J].Systems Engineering and Electronics，2011，33(1)：196-201.)
[8]向程冠，熊世桓，王东.基于关联规则的社交网络好友推荐算法 [J].中国科技论文，2014，9(1)：87-91.
(XIANG Cheng-guan，XIONG Shi-huan，WANG Dong.Social network friends recommendation algorithm based on association rules [J].China Sciencepaper，2014，9(1)：87-91.)
[9]章志刚，吉根林.一种基于FP-Growth的频繁项目集并行挖掘算法 [J].计算机工程与应用，2014，50(2)：103-106.
(ZHANG Zhi-gang，JI Gen-lin.Parallel algorithm for mining frequent item sets based on FP-Growth [J].Computer Engineering and Applications，2014，50(2)：103-106.)
[10]胡维华，冯伟.基于分解事务矩阵的关联规则挖掘算法 [J].计算机应用，2014，34(增刊2)：113-116.
(HU Wei-hua，FENG Wei.Improved Apriori algorithm based on decomposed transaction matrix [J].Journal of Computer Applications，2014，34(Sup2)：113-116.)
(责任编辑：钟 媛 英文审校：尹淑英)
ZHANG Wei-ke
(School of Science, Shenyang Ligong University, Shenyang 110159, China)
Abstract：In order to solve the problem that the I/O load generated in the repeated scanning database for the classic Apriori algorithm will affect the running efficiency, an improved AprioriTid algorithm based on the compression set, namely the AprioriTid_M algorithm, was proposed on the basis of the research on the principle of Apriori algorithm and its related improved algorithms. Through the effective pruning methods, the generation of invalid item sets was reduced, and the number of candidate item sets was decreased. Therefore, the efficiency of the algorithm was improved. The results of simulation experiments show that under such conditions as the same support degree but different data amount or the same data amount but different support degree, the performance and running time of AprioriTid_M algorithm get greatly improved compared with those of Apriori algorithm.
Key words：Apriori algorithm; AprioriTid algorithm; AprioriTid_M algorithm; association rule; confidence degree; item set; support degree; performance
收稿日期：2015-12-03.
基金项目：辽宁省科学技术计划项目(2012217005)； 辽宁省科学事业公益研究基金资助项目(2012004002).
作者简介：张伟科(1965-)，男，河北秦皇岛人，讲师，硕士，主要从事计算机视觉、智能检测与控制等方面的研究.
doi：10.7688/j.issn.1000-1646.2016.03.14
中图分类号：TP 311
文献标志码：A
文章编号：1000-1646(2016)03-0314-05
*本文已于2016-04-22 15∶41在中国知网优先数字出版. 网络出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20160422.1541.006.html