基于矩阵相乘的Apriori改进算法

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

1、计算机科学2005Vo1.32N4.7(增刊1i)基于矩阵相乘的Apriori改进算法关ImprovedAprioriAlgorithmBasedonMatrixMultiplying高明刘希玉盛立(山东师范大学信息管理学院济南250010AbstractThispaperpresentsanimprovedApriorialgorithm(MM一Apriori)basedonmatrixmultiply.Thenewal-gorithmiscomparedwithApriori切theexperiment,andshowsthatthealgorithmoutperformApriori

2、.KeywordsDatamining,Associationrules,Frequentitems,Matrix由于第二步比较简单，因此关联规则挖掘的研1引言究主要集中在第一步，即从交易数据库中找出符合数据挖掘(DataMining)，也称数据库中知识发指定支持度和置信度条件的所有频繁项集。目前最现KDD(KnowledgeDiscoveryinData-base)，是指有影响的关联规则挖掘算法是Apriori算法D]，后从大量原始数据中挖掘出隐含的、有用的、尚未发现来的研究者也陆续提出了一些新的算法'z,81，但大的信息和知识(如知识规则、限制等)，被认为是目多数算法还是以Aprior

3、i算法为核心，Apriori算法前解决“数据爆炸”和“数据丰富，信息贫乏(Data的思想利用了Apriori性质，即频繁项集的所有非RichandInformationPoo,ar)”的一种有效方法。空子集必须也是频繁的，由k-项频繁集1,*连接得关联规则的挖掘是数据挖掘的重要领域之一。到k+1一项侯选频繁集q十，，然后进行修剪，过滤出随着大型连锁零售商店在零售市场上份额的增加，频繁项集，直到没有频繁项集被发现为止。越来越多的超市或连锁店希望发现其庞大的交易数2Apriori算法据库中隐含的销售信息，这是一种宝贵的信息资源，可以很好地支持人们的决策。关联规则的应用包括Apriori算法是关

4、联规则挖掘的经典算法，算法商场的顾客购物分析、商品广告邮寄分析、网络故障通过多次扫描数据集挖掘频繁项集。第一次扫描，分析等。关联规则的挖掘引起了研究人员与企业界算法对所有数据项进行计数并找出所有频繁1一项人士的共同关注。集。在接下来的每一遍扫描中，算法使用前一遍处关联规则的定义可形式化描述如下:设I={il,理发现的频繁项集生成新的候选频繁项集，并通过i2I...Ii.}是所有项目(item)的集合，令D为一个事扫描数据库对这些候选频繁项集进行计数，然后，使务数据库，其中的每一个事务T都是项目的集合，用支持度阂值对不满足支持度条件的候选频繁项集且T=I。关联规则是形如X=>y的蕊含式，其中

5、进行修剪，过滤出频繁项集，直到没有频繁项集被发X,Y为项目集合，并且Xny=必。定义支持度现为止。Apriori算法描述如下:(support)为D中包含XUY的百分比，置信度算法:Apriori(confidence)为D中包含X的事务同时也包含Y的输人:事务数据库D;最小支持度阑值minsup,百分比。即:sup(X=>Y)=P(XUY);confidence(X输出:D中的频繁集l,o=;>Y)=P(Y}X)。项的集合称为项集。包含k个方法:项的项集称为k一项集。项集满足最小支持度min-1)1,1={large1一itemsets};sup，如果项集的出现频率大于或等于minsup

6、与D2)for(k=2;1-k_1护争;k++)dobegin3)q=Apriori-gen(Lk_1);中事务总数的乘积。如果项集满足最小支持度，则4)foralltransactionsteDdobegin称它为频繁项集(frequentitemset)。频繁项集的集5)C=subset(q，t);6)forallcandidatesc任C,do合记做Lk。7)c.count斗一+;从大型数据库中挖掘关联规则分为两个步骤:8)end9)1,k={CECkIc.count>,minsup二i'1'I}1)找出所有的频繁项集。10)end2)由频繁项集产生强关联规则。11)Answer=U

7、k1"k;，)基金项目:山东省自然科学基金重大项目(Z2004G02)，山东省中青年科学家奖励基金项目2003年(03BS0035),·209·其中，Apriori-gen是以频繁(k-1)项目序列集(2)扫描一遍数据库统计各个项对应的行中ILk-,为自变量的候选项集生成函数。该函数分连接的个数，生成频繁1一项集;和修剪两步执行:(3)删除矩阵A中支持度不满足mirisup的项(1)连接(join)所在的行，生成矩阵M(