基于矩阵的apriori算法的优化

《基于矩阵的apriori算法的优化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机与现代化2008年第l2期JISUANJIYUXIANDAIHUA总第160期文章编号：1006-2475(2008)12-0005-03基于矩阵的Apriori算法的优化梅成，周兴斌(南昌大学计算中心，江西南昌330031)摘要：在数据挖掘中关联规则挖掘是很重要的一个方面，而Aprion算法是进行关联规则挖掘的经典算法。本文首先分析了经典Apd算法，然后利用矩阵的思想对其改进，并利用事务压缩的思想对矩阵进行压缩。改进后的算法明显提高了Apriori算法的效率。关键词：关联规则；Aprio

2、ri算法；事务压缩；矩阵中图分类号：TP311文献标识码：AAnImprovementofAprioriAlgorithmBasedonMatrixMEICheng，ZHOUXing—bin(ComputingCenter，NanchangUIliversity，Nanehang330031，China)Abstract：Miningassociationruleisaveryimportantfacetfordatamining．whileApriorialgorithmisclassical

3、gorithmforassoei—ationrule．ThepaperanalyzestheclassicApriorialgorithmfirst，thenmodifiesitbasedonmarxandcompassesthematrixbasedontransactioncompression．ThemodifedalgorithmobviouslyimprovestheefieeneyofApriorialgorithm．Keywords：associationrule；Aprioria

4、lgorithm；transactioncompression；matrix库D的多次搜索来发现所有的频繁项集在一次扫描0引·言中，就可以得到一种长度的频繁项集集合。首先，找近些年来数据挖掘(DataMining)已被数据库界出频繁1．项集的集合，记作L1。L1用于找频繁2硕所广泛研究。它具体的是指从大型数据库或数据仓集的集合L2，而L2用于找L3，依次类推，直到不能找库中提取人们感兴趣的知识¨】，而数据挖掘中的一到频繁项集为止。个非常重要的方法就是基于关联规则的知识挖掘。Apfiofi算法性质

5、口引：频繁项集的所有非空子集关联规则挖掘是数据库挖掘领域中较早提出的一个都必须也是频繁的。Apfiofi算法性质基于以下观研究方向，目前该领域的新算法、新应用层出不穷，察：根据定义，如果项集I不满足最小支持度min—相关问题定义和背景也不尽相同。在关联规则挖掘sup，则I不是频繁的，即P(I)<(rain—sup)。如果项中Aori算法是比较经典的一个算法，但Apfiofi算A添加到I，则结果项集I即(IuA)不可能比I更频法也存在一些不足之处【2。繁出现。因此，P(IuA)也不是频繁的，即P(

6、IuA)<(min—sup)o1Apriori算法Apfiofi算法的实现过程主要有连接和剪枝两步：Apfiofi算法是1994年由R．Agrawal和R．Srikant(1)连接步。提出的。Apd算法采用一种逐层搜索的迭代方C。=I，I为事务所包含的项目，扫描数据库，得到法，k一项集用于搜索(k+1)一项集。通过对事务数据频繁1一项目集L，执行连接C=L。∞L，产生C，扫收稿日期：2007．11．12基金项目：江西省科技攻关资助项目(S00036)作者简介：梅成(1985．)，男，江西九江人，

7、南昌大学计算中心硕士研究生，研究方向：软件工程；周兴斌(1970-)，男，江西泰和人，副教授，研究方向：软件工程。6计算机与现代化2008年第l2期描数据库，得到L2，执行连接C，=L2∞L2，产生C。。101O110O如此下去，在第k遍扫描中，则是首先利用L一来生11001011成c=L∞Lk一，若C=，则算法结束，否则扫描D=(Dt,D2，⋯，Ds)=11l1O110100100l0数据库得到L。001O0000(2)剪枝步。此矩阵的行表示项(Ij表示第j个项)，列表示事利用Apfiod算法

8、性质，进行对事务的删除，提高务(D；就表示第i个事务)，如果取值为0就表示事扫描的效率。在第k遍扫描中，第一步，利用第(k一务中不含相应的项，为1则表示事务中含有相应的1)次扫描得到的Lk-1来产生C，首先将IJk一中前k-I项。项相同的项集进行连接产生C，接着将连接得到的各个项的最小支持度计数计算如下：项集，若其子集Lk一不是频繁项集，那么任何(k一1)min_eount(I1)=dIl+d2t+⋯+dst=4I>2项集都不可能是频繁项集，则删除，即修剪；第二步，rain_count(I2)=