(2)关联规则X]Y的支持度s是数据库中包含X∪Y的事务占库中所有事务的百分比;(3)关联规则X]Y的置信度c是包含X∪Y的事务数与包含X的事务数的比值。因此给定一个数据库,挖掘关联规则的问题就是在数据库中找出满足用户指定的最小支持度和最小置信度的所有关联规则。
2 Apriori算法的简介
查找频繁项集是整个关联规则挖掘过程中最消耗时间和计算成本的过程,Apriori算法则用一种称
收稿日期:2008-05-12
作者简介:郭云峰(1978-),男,浙江嘉兴人,在读研究生,数据挖掘.
第2期 郭云峰等:对关联规则挖掘中Apriori算法的一种改进 61为逐层搜索的迭代方法,从k项集搜索(k+1)项集。其性质是:如果当项集I不满足最小支持度阀值,则I不是频繁的;任何非频繁的(k-1)项集都不可能是频繁k项集的子集。
Apriori算法搜索频繁项集的过程可描述为:
(1)扫描所有事务,统计每项出现次数,如果满足最小支持度阀值,则为频繁1项集L1;
(2)由频繁1项集L1∞L1生成的C2是L2的超集,如果C2中每个候选项集在所有事务中出现的次数满足最小支持度,则该项集必定是频繁的,最终生成频繁2项集L2;(3)由频繁2项集L2∞L2生成的C3是L3的超集,如果C3中一个候选项集的(k-1)子集都存在于L2中,而该候选项集在所有事务中出现次数满足最小支持度阀值的要求,则该项集属于频繁3项集L3。同理查找L4,L5,…,直到能找不到更高维的频繁项集为止。
由于Apriori算法需要反复扫描数据库,候选项集多,影响了运行的效率。
3 Apriori算法的改进
3.1 事务项目的布尔化
扫描一次数据库,将事务数据库映射成为布尔向量矩阵。各个项目的向量长度等于事务数,若项在第n个事务中出现,则该项的布尔向量的第n位设置“1”,否则设置“0”。项的向量中“1”的个数表示该项在数据库中出现的次数。以文献1给的一个事务数据库D为例,如表1所示,可以映射成为如表2所示的布尔向量矩阵。
表1 事务数据库D
TIDT100T200T300T400T500T600T700T800T900
ItemsetA,B,EB,DB,CA,B,DA,CB,CA,CA,B,C,EA,B,C
表2 数据库D对应的布尔向量矩阵
Item1234567
A100110111
B111101011
C001011111
D010100000
E100000010
3.2 逻辑“与”运算
根据候选项集对应的布尔向量,进行逻辑“与”运算,判断得出频繁项集。而布尔向量的逻辑“与”运算则是指任意的两个布尔向量中相同位置只有都为“1”时,结果才能为“1”。例如,设向量A为BV1=
100110111,向量B为BV2=111101011,所以A与B的逻辑“与”运算就等于BV1∧BV2=(100100011)。3.3 连接步和剪枝步的优化
在传统的Apriori算法中,要生成频繁项集Lk+1,就要执行连接步和剪枝步操作。而连接步每操作一次,相应的剪枝步中要生成Ck经过进一步的研究和分析,可以发现连接步和剪枝步k+1个候选子集。操作带有一些机诫性,会有大量多余的候选集生成。
设有任意两个符合要求的频繁k项集Lk1={i1,i2,…,ia}和Lk2={i2,i2,…,ik-1,ib},不难发现每次连接步生成{i1,i2,…,ik-1,ib}中的ia和ib都不相同,如果ia和ib对应的布尔向量逻辑“与”运算的结果
k不符合最小支持度阀值的要求,则无需进行进一步的剪枝,相应的可减少生成C因此,k+1个候选项集。
通过优化连接和剪枝,候选项集数目可得到较大幅度的减少。
62 杭州电子科技大学学报 2009年3.4 算法描述
改进算法的思想可描述为:扫描一次数据库,将事务数据库映射为布尔向量矩阵。对各个项目中“1”的个数进行统计,满足支持度阀值,该项目就属于频繁1项集。从频繁1项集中任选2个向量进行逻辑“与”运算,其结果中如果“1”的个数满足支持度阀值,则这2个向量的组合属于频繁2项集。从已存在的频繁k-1(k≥3)项集中任选2个符合连接条件的项集进行连接,在连接生成的k项集中判断最后2位项目的“与”运算,结果符合支持度阀值的则可继续进行剪枝。如果剪枝生成的所有k-1项子集都存在于频繁Lk-1中,那么只需要对i1,i2,…,ik各个项目一起进行“与”操作,所得结果符合支持度阀值要求的,该k项集为频繁k项集。以此类推,最终得出所有频繁项集。过程如图1所示:
图1 改进算法过程图
3.5 算法的示例
为了直观地说明上述算法过程,以表1所示的事务数据库为例,具体介绍该改进算法的各个步骤。
表1所示的一个事务数据库D。这里不妨设最小支持度的阀值为2(即minsup=2/9=22%),要求找出D中所有的频繁项集。
扫描数据库D一遍,为每个项目建立一个布尔向量,表1中事务的个数为9,即向量的长度为9。设事务数据库D中的项目A,B,C,D,E对应的向量分别为BV1,BV2,BV3,BV4,BV5,扫描结果如表2所示:BV1=100110111,BV2=111101011,BV3=001011111,BV4=010100000,BV5=100000010。统计各个项目“1”的个数,项目A,B,C,D,E均符合满足最小阀值的要求,频繁1项集L1={{A},{B},{C},{D},{E}}。
搜索频繁2项集。在L1中任选两个项集进行“与”操作,只有BV1∧BV2,BV1∧BV3,BV1∧BV5,BV2∧BV3,BV2∧BV4,BV2∧BV5满足最小阀值的要求,频繁2项集L2={{A,B},{A,C},{A,E},{B,C},{B,D},{B,E}}。
推导频繁3项集。在频繁2项集L2中,查找起点相同的频繁2项集:项集{A,B}和{A,C},终点B和C的“与”运算符合支持度阀值要求,且{A,B,C}的所有2项子集都存在于中。将A,B,C这3个项目进行“与”操作,得BV1∧BV2∧BV3=(000000011),符合频繁项集的条件。同理,{A,B,E}也是频繁3项集;而{A,C},{A,E}的起点也相同,但终点C和E的“与”运算不符合支持度阀值的要求,{A,C,E}不用考虑。同理,其他频繁2项集的组合也都不符合要求,因此频繁3项集L3={{A,B,C},{A,B,E}}。
依此类推,根据搜索推导频繁4项集。根据算法要求,L4不存在,推导结束。
第2期 郭云峰等:对关联规则挖掘中Apriori算法的一种改进 63至此所有的频繁项集都已经找到,L={{A},{B},{C},{D},{E},{A,B},{A,C},{A,E},{B,C},{B,D},{B,E},{A,B,C},{A,B,E}}。3.6 实验结果
为了进一步测试该改进算法的性能,在主频为P4,2.4GHz,512MB内存和Windowsxp操作系统的PC机上对该算法进行了测试,所有的程序代码由DevC++编写。采用的数据库是来自UCIrvineMachineLearningDatabaseReposi2tory的一个实验数据库mushroom。运行结果如图2所示。图2显示了该改进算法和Apriori算法的运行时间,对mush2room这个非常稠密,项集之间的相关性很强的数据库,改进算法要比原始算法要快2倍以上。
图2 算法的运行时间
4 结束语
改进算法在构建向量矩阵的基础上,通过优化连接和
剪枝,对Apriori算法进行了改进。只需要扫描一次事务数据库,减少了候选项集,通过矩阵行向量之间的“与”运算,克服了原始算法需多次扫描数据库、生成候选项集多和运算效率低等不足。实验结果表明,改进算法是有效且可行的,具有较高的挖掘效率,实用性较好。
参考文献
[1] JiaweiHan,MichelineKamber.数据挖掘概念与技术[M].北京:机械工业出版社,2001:149-172.[2] MargaretHDunham.数据挖掘教程[M].北京:清华大学出版社,2005:141-1.
[3] 陈明,史忠植,王文杰.一种有效的基于图的关联规则挖掘算法[J].计算机应用,2006,26(11):2654-2656.[4] 李杰,徐勇,王云峰,等.最简关联规则及其挖掘算法[J].计算机工程,2007,33(13):46-48.
[5] 刘独玉,杨晋浩,钟守铭,等.基于图的关联规则挖掘高效算法研究[J].计算机工程与设计,2006,27(23):4475-4478.
AnImprovedAprioriAlgorithminMiningAssociationRules
GUOYun2feng,ZHANGJi2xiang
(InstituteofGraphicsandImage,HangzhouDianziUniversity,HangzhouZhejiang310018,China)
Abstract:AsApriorialgorithmforfindingfrequentitemsetrequirestoscandatabasesrepeatedly,anenhanced
ApriorialgorithmwhichusedtherowvectorsofBooleanmatrixfortransactiondatabases,optimizedtheconnectionandpruning,canfindthefrequentitemsetquickly.Itusestheoptimizationtoreducetheitemsetwithcandidate,combinestheinnerofBoolean-vectortoproductthefrequentitemset.Studiesandexperimentsshowsthatthealgo2rithmnotonlyscansthedatabaseonlyonce,butalsosearchtheresultquickly,occupiesthememorylessandhan2dleswithitemsetdimensionslargely.
Keywords:associationrules;Boolean-vector;frequentitemset
