数据挖掘中常用关联规则挖掘算法

《数据挖掘中常用关联规则挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第2。期计算机技术与发展V01．2ONo．42010年4月COⅣI丌RTEa阉10GYANDDEVEU]l’MENTApr．2010数据挖掘中常用关联规则挖掘算法王爱平，王占凤，陶嗣干，燕飞飞(安徽大学计算智能与信号处理教育部重点实验室，安徽合肥230039)摘要：文中首先介绍了数据挖掘中关联规则的经典算法——A州算法。再从宽度、深度、划分、采样、增量式更新等几个角度对关联规则挖掘进行了分类讨论。然后运用文献查询和比较分析的方法对常见的关联规则挖掘算法进行了概述，主要包括FP—growth算法、DHP算法、Partition

2、算法、兀JP算法、CD算法等算法。最后对关联规则挖掘的发展远景进行了展望。关键词：数据挖掘；关联规则；频繁项集；挖掘算法中图分类号：TP311文献标识码：A文章编号：1673—629X(2010)04—0105—04CommonAlgorithmsofAssociationRulesMininginDataMiningWANGAi．ping，WANGZhan-feng，TAOSi．gan，YANFei—fei(MinistryofEducationKeyLaboratoryofInteligentComputing&Si1a

3、1Processing，AnhuiUniversity，I-hfei230039，China)A：rStintroducestheclassicalalgorithmofassociationrulemining—Apriori．Thenclassifieddiscussestheassociationruleminingfromseveralanglessuchaswidth，depth，partition，samplingandi~mnentalupdating．ItslmfⅡnazestheo01rnmo~algori

4、thmsofassocia·tionrulenn．mgtJghqueryingdoctmaentsandcomparativeanalysis．ItmainlyincludesFP—Growth~onthm，DHPalgorithm，Patti-tionalgorithm。FUPalgorithm，CDalgorithmand80on．Atlastprospecttheassociationrulemining．Keymints：datamining；associationrule；frequentitemsets；mini

5、ng~gorithmO引言法，其中以Agawal提出的Apri~算法[】最为著名，大数据挖掘(DataMining)，又称数据库中的知识发多数挖掘算法都是建立在Apriori算法基础之上，但是现(KnowledgeDiscoveryinDatabase)，是从大量的、不Apriori算法无论在时间效率还是空间伸缩性上都面完整的、有噪声的、模糊的、随机的大型数据中提取隐临着挑战，因此研究人员探索出很多新的挖掘方法，并含在其中的、人们事先未知的、具有潜在价值的信息和拓展了关联规则概念及应用范围。知识的过程_1J。简单的说，数据挖

6、掘就是从大量数据中提取或“挖掘”出人们有用的知识。面对当前“海量1关联规则的基本概念数据，微量信息”的现状，数据挖掘的重要研究分支设集合J={i1，i2，⋯，i}，其中ik(k=1，2，⋯，——关联规则，作为一种高级和智能的数据处理和分m)表示项。如果xcj，集合x被称为项集。当lx析技术的研究正方兴未艾。I=k，则X被称为k一项集。事务二元组T=(tid，X)，通过关联规则挖掘，可以得到隐含于海量数据中tid是事务唯一的标识符称为事务号。数据集D={t1，具有潜在价值的有用信息。关联规则的目标是以有效t2，⋯，t}是由t1

7、，t2，⋯，t事务组成的集合。的方式提取最有趣的模式。关联规则可以描述为：形如AB的蕴涵式，其中迄今为止已提出了许多高效的关联规则挖掘算AJ，BcJ，并且AnB=。项集X的支持度s是D中包含X的事务数占所有事务数的百分比，记为(x)=户(x)：。项集x的置信度f是D中同收稿日期：2009—08—15；修回日期：2009一Il一21基金项目：国家自然科学基金项目(60472065)时包含xUy的事务数占包含x的所有事务数的百作者简介：王爱平(1956一)，女，甘肃庆阳人，教授，从事计算机教学分比，记为f(x)=P(XIy)=。

8、至于与研究。·106·计算机技术与发展第20卷最小支持度minsup和最小置信度mineonf都是由用户，由连接得到候选k一项集，直到没有新的候所给定，如果项集x的sup(X)>minsup，那么项集X选集产生为止。被称为频繁项集，其中生成的关联规则中所有支持度Apriori算法需扫描数据