计算机技术与发展.pdf

《计算机技术与发展.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第19卷第5期计算机技术与发展Vo1．19No．52009年5月00M)1rrRTECHN()IoGYANDDEVELJr]lPM旺NTMay2009关联规则算法的研究文拯，梁建武，陈英(中南大学软件学院，湖南长沙410005)摘要：Apriori算法是发现频繁项目集的经典算法，但是该算法需反复扫描数据库，因此效率较低。文中针对传统的Apri．算法需要多次扫描数据库，由此导致的性能瓶颈及效率问题，提出了一种改进的关联规则挖掘算法(算法)。该算法只需一次扫描数据库即可完成所有频繁项集的搜索，极大地提高了算法的效率。关键词：AAC算法；关联规则；数据挖掘；Apriori算法；一次扫描数据库的Apr

2、iori中图分类号：ll文献标识码：A文章编号：1673—629X(2009)05—0056—03ResearchofAssociationRulesAlgorithmWENZheng，LIANGJian—wu，CHENYing(SoftwareCollege，CentralSouthUniversity，Changsha410005，China)Ahstra~：Apriorialgorithmistheclassicmethodwhichusedtodetectfrequentitemsets．Butduetothealgorithmneedtoberepeatedscanningtheda

3、tabase，ithaslessefficiency．ThearticleforthetraditionalApriorialgorithmnecessaryto8Ganthedatabasemanytimesandtheresultingefficiencyandperformancebottlenecks，raising8nimprovedmethodofminingassociationrules(AACalgorithm)，itonlyneedtoscanthedatabaseonetimetofinishallthefrequentitemsetsdetecting，greatlyi

4、mprovetheefficiencyofthealgorithm．Keywords：AACalgorithm；multi—associationrule；datamining；Apriorialgorithm；onetimes^御database’sApronalgorithmO引言1关联规则算法关联规则挖掘就是在海量的数据中发现数据项之1．1基本概念间的关系，是数据挖掘领域中研究的热点问题。1993定义1：事务(transaction)：某个客户在一次交易中年Agrawal等人首先提出了交易数据库中不同商品之发生的所有项目的集合，每个事务都有一个唯一的标间的关联规则挖掘，并逐渐引起了专家、

5、学者的重视。识一tid。关联规则挖掘问题可以分为：发现频繁项gl集和生成定义2：事务数据库(transactiondatabase)关联规则两个子问题，其中发现所有的频繁项目集是D={t1，t2，⋯，t}；由一系列具有唯一标识tid的生成关联规则的基础J。近年来，发现频繁项目集成事务组成，且tid是有序的(tid有序为新算法的要求)。为了关联规则挖掘算法研究的重点，在经典的Apriori定义3：项(item)：事务数据库中的一个属性字段，算法的基础上提出了大量的改进算法。但在这些改时每个字段有一定的取值范围。对超市数据来讲，项是指算法里面，都不可避免地要多次扫描数据库，只是在量交易中的特定商品

6、。的方面提升了算法的效率，却没有得到质的改进口J。定义4：项集(itemset)：包含若干个项的集合。文中首先介绍Apriori算法，然后提出一种新的关定义5：项集维数：把一个项集所包含的项的个数称为此项集的维数或项集的长度。长度为忌的项集，称于关联规则的灵活算法，该算法只需一次扫描数据库，并且在连接时可以同时剪枝，极大地提高了算法的效为k一项集。率。定义6：支持度(support)：假定X是一个项集，D是一个事务集合或事务数据库，称D中包含x的交易收稿日期：2008—09—01的个数与D中总的交易个数之比为X在D中的支持基金项目：国家自然科学基金(60173041)度，记作Support(X

7、)，即作者简介：文拯(1985一)，男，江西萍乡人，硕士研究生，研究方向Support(x)=此为数据库，数据挖掘，网络安全与认证等；梁建武，高级工程师，研究方向为信号处理，网络安全与认证；陈英，硕士，副教授，研究方向定义7：最小支持度(minimumsupport)：由用户定为网络通信与安全技术。义的衡量项集频繁程序的一个阈值，记作minsup。第5期文拯等：关联规则算法的研究·57·定义8：频