文档介绍：第30卷第11期
2010年11月
文章编号:1001-9081(2010)11-2952-04
计算机应用
JournalofComputerApplications
关联规则挖掘中Apriori算法的研究与改进
崔贯人,副教授,主要研究方向:软件工程; 王柯柯(1977-),女,四川南充人,讲师,硕士,主要研究方向:软件工程; 苟光磊(1980-),男,重庆人,实验师,硕士,主要研究方向:;男,,实验师,
第11期崔贯勋等:关联规则挖掘中Apriori算法的研究与改进 2953
然需要进行模式匹配,也使得算法的提高程度受到限制。
尽管Apriori算法有如上诸多改进方法,但时间效率还不尽理想,为了更进一步提高算法的效率,提出了基于集合的改进Apriori算法,目的就是进一步提高算法的性能。
定理1 设x!Lk,y!Lk,若x1=y1∀x2=y2∀#∀xk-1=yk-1∀xk<yk,则T xl∃
y
=Tx l%Ty l。
证明 对 t!Tx l∃y,由定义1可知,x∃y t,由定义3可知,x t且y t,由定义2可知,t!T xl且t!Ty l,即t!T xl%T yl。
反之,对 t!T xl%T yl,则t!Tx l且t!T yl,由定义2可知,x t且y t,由定义3可知,x∃y t由定义1可知, t!T xl∃y。
所以Tx l∃y=T xl%T yl。证毕。定理2 若k维数据项目集X={x1,x2,#,xk},X中存在一个项目p!X,使得|Lk-1(p)|<k-1,则X不是频繁项目集。其中,|Lk-1(p)|表示(k-1)维频繁项目集的集合Lk-1中包含p的频繁项目集的个数。
证明 用反证法证明。假设X是k维频繁项目集,由性质1可知,它的k个k-1维子集均在Lk-1中。而由X生成的k个k-1维子集中,每一个项目p!X均出现k-1次,故 p!X,均有|Lk-1(p)|&k-1,这与条件矛盾,故x不是频繁项目集。证毕。推论1 若Lk-1中有元素e包含项目p,使得|Lk-1(p)|<k-1,则Lk-1中所有不同于e的元素与e连接而成的候选k维项目集均不可能是频繁项目集。
证明 假设由e生成的一个候选k维数据项目集x是频繁项目集,则e显然是x的一个k-1维子集,由于p!e,因此p!X,由定理2可知|Lk-1(p)|&k-1,与条件矛盾。证毕。
该推论应用于修剪频繁项集方法中将大大减少寻找候选频繁项集的时间开销,示例如下:
例1 假设L3={{a,b,c},{a,b,d},{a,b,e},{a,b,f},{a,b,g},{b,c,d},{b,c,e},{b,c,f},{b,c,g}},求C 4。由定理2可知:|L(a)|=5,|L(b)|=9,|L(c)|=5,|L(d)|=2,|L(e)|=2,|L(f)|=2,|L(g)|=2,由于|L(d)|=|L(e)|=|L(f)|=|L(g)|=2<3,由推论1可知,与项目d、e、f、g连接生成的k(k&4)维项目集均不是频繁项目集,故在连接之前就去掉L3中包含项目d、e、f、g的频繁项目集L ,b,c}}。从而C 3={{a4为空集,显然L4也是空集。
如果用Apriori算法计算,首先要生成候选集C4={{a,b,c,d},{a,b,c,e},{a,