一种基于APRIORI 性质的多维关联规则挖掘算法的研究.doc

文库下载 免费文档下载/本文档下载自文库下载网，内容可能不完整，您可以点击以下网址继续阅读或下载：/doc/13bd41457e21af45b207a82d.html一种基于APRIORI性质的多维关联规则挖掘算法的研究超清晰论文VoI.20ApriINo.22003安徽工业大学学报J.ofAnhuiUniversityofTechnoIogy第20卷第2期2003年4月文章编号：1671-7872(2003)02-0141-04一种基于APRIORI性质的多维关联规则挖掘算法的研究秦锋，杨学兵（安徽工业大学计算机学院，安徽马鞍山243002）摘要：Apriori算法是一种找频繁项集的基本算法，它常常被用于单维关联规则的挖掘，本文在对数据立方体的组织结构以及Apriori算法包括它的一些变形算法进行了深入研究的基础上，给出了一种适用于多维关联规则挖掘的算法，并分别通过理论和实验方法对此算法的性能进行了分析。关键词：数据挖掘；关联规则；多维数据立方体中图分类号：TP312文献标认码：AResearchandanaIysisofmuIti-dimensionaIassociationruIesminingOINFeng，YANGXue-bing(SchooIofComputerScience，AnhuiUniversityofTechnoIogy，Maanshan243002,China)Abstract:AprioriisacIassicaIaIgorithmoffindingfreguentitemsetsinnormaIsingIedimensionaIdatatabIe.ThispaperpresentsanewmuIti-dimensionaIassociationruIesminingaIgorithm.bydeepIyanaIyzingthestructureofdatacubeandAprioriaIgorithm.Attheendofthispaper,theefficiencyanaIysisoftheaIgorithminpracticeandtheoryisgiven.Keywords:datamining;associ/doc/13bd41457e21af45b207a82d.htmlationruIes;muIti-dimensionaIanaIysis引言已经受到KDD(KnowIedgeDiscoverinDatabases)是目前人工智能和数据库相交叉的一个热门研究领域，越来越多的关注。数据挖掘(DataMining,简称DM)是KDD的一个十分重要的步骤，其内容涉及各种知识模式的提取算法。关联规则是数据库中存在的一种十分有用的知识模式，其挖掘算法已得到了较为广泛的重（Muti-DimensionaIDataCube）视和研究，并取得了较大的进展。另外，多维数据分析、多维数据立方体等也是近年来涌现出的一些更有效地对数据进行组织、存贮、分析和处理的新方法。多维关联规则是指在各个属性维之间存在的关联规则。由于每个集中的项目来自不同的维，项目集的出现频次可直接从一个立方体方格中得到，这使得挖掘过程效率大大提高。许多学者对Apriori算Apriori算法是一种找频繁项集的基本算法，（singIe-dimensionaIruIes）的挖掘，法进行改进,大大提高了原算法的效率。这些算法被用于单维关联规则而对于多维关联规则的挖掘并不有效，为此作者提出了一种基于Apriori性质的适用于多维关联规则挖掘的算法。1概念1.1关联规则关联规则概念首先由R.AgrawaI等于1993年提出。所谓关联规则，是指客体之间的相互关系。关联规收稿日期：2002-11-05（2002KJ046）基金项目：安徽省教育厅科研经费资助（1962-），男，安徽和县人，安徽工业大学计算机学院副教授，硕士，主要研究方向为人工智能、机器学作者简介：秦锋习。142安徽工业大学学报2003年则形如：意味着目标数据中客体B1,B2,Bj倾向于同A1/A2/Ai-B1/B2/Bj,（4%，70%）客体A1,A2,Ai一起出现。其中4%为关联规/doc/13bd41457e21af45b207a82d.html则的支持度，70%为关联规则的信任度。1.2Apriori性质需要多遍扫描事务数据库,为了提高频繁项目集的产生效率，可利用一Apriori算法采用的是迭代方法，个重要的Apriori性质来减少项目搜索空间。Apriori性质就是一个频繁项目集的所有非空子集必需也是频繁项目集。这一性质是由Agrawal和Srikant提出并证明的。根据这一性质，进行第 遍扫描之前，可先产生候选集C ,C 可以分两步来产生，设前一步（第 -1步）已生成( -1)-频繁集L -1，则首先可以通过对L -1中的成员进行联接来产生候选，L -1中的两个成员即：必需满足在两个成员的项目中有 -2个项目是相同的这个条件方可联接，C =L -1!L -1=A!BIA,BcL -1,IAnBI= -2接着，再从C 中删除所有包含不是频繁的( -1)-子集的成员项目集即可。1.3数据立方体数据立方体是指含有多维属性的统计实体，设为I维，每维共有IdiI 1个值，其中IdiI是指第I维中共IdiI 1个不同值。互不相同的属性值，每维中再加上一个 Any 值，假设存在一个I维空间，则由每一维中各取一个具体的属性值，则可对应一个I维空间中的点，这个点称之为方格，每个方格内存贮了与其对应的各属性的值同时出现的次数，用count表示。2算法描述给出一个用Apriori改进的算法，它使用Apriori性质进行候选集的生成。（算法1）使用Aprior性质的维间频繁集生成算法输入：?一个I维的数据立方体CBd1,dI?最小支持度：min_sup输出：I维间的频繁项目集L（1） =1;L=!;（2）对于每一维，生成1-itemset候选集C1,di=di维中所有互不相同的取值，C1=Ui=1C/doc/13bd41457e21af45b207a82d.html1,di；I（3）生成1-itemset频繁项目集L1=gen_freguent(1,C1);（4）Repeat= 1;生成 -itemsets候选集C =gen_candidate( ,L -1);生成k-itemsets频繁集Lk=gen_freguent(k,Ck);L=LUL ;UntilL =!;函数gen_freguent( ,C ),从候选集C 中生成频繁项目集L Functiongen_freguent( ,C )L =!;foreachcandidateI=i1,i2,.,i GC dofreguency= 维立方体空间中的方格(i1,i2,.,i )中的count值support=freguency/totalcount;if(supportmin_supp)then/I是一个频繁项目集L =L UI;第2期秦锋等：一种基于APRIORI性质的多维关联规则挖掘算法的研究l43（I-l）函数gen_candidate(I,LI-l)，从频繁项目集中生成I-itemset候选集CIFunctiongen_candidate(I,LI-l)CI=!;foreachitemllGLI-lforeachiteml2GLI-lif(Il与I2有I-2个相同的项目,并且最后一个项目分别来自不同的维)thenc=ll!l2ifc有非频繁的(I-l)子集，then删除celse将c加入到CI中returnCI基本工作原理：根据Apriori性质，算法首先找出所有的l-itemsets频繁项目集Ll，然后陆续找出I-itemsets频繁项目集LI。算法是通过LI-l!LI-l连接/doc/13bd41457e21af45b207a82d.html操作来生成I-itemsets的候选集CI。对于每一个I-检查在I-维立方体中与之相应的方格，根据数据立方体的定义，保存在每个方格中的itemsets候选IGCI，count值是从原始数据中来的一个统计值，所以它能准确反映出这个项目集的出现频次，将它与最小支持度作比较，将符合要求的放入LI中。算法l是使用了Apriori性质来生成和修剪候选集的，其总的连接和检查子集所需时间为：IZ(ILI=2I-l!LI-lIX(I-2)由于每个候选的出现频次只需检查一个方格，所以扫描数据立方体的次数应为:Z(ICI)II=lI由此可以看出，如果数据立方体是稀松的，即只有很少的项目集是频繁的，尤其是当项目集的项目数增因为它可以通过修剪候选集来大大减少候选加时，频繁项目集很少，则使用Apriori性质的算法l较为有效，集的长度，从而降低了支持度的计算时间。但如果数据立方体很密，则连接和修剪所花时间较大，尤其是在数据立方体非常密时，花很长时间进行的连接和修剪却往往不能明显减少候选集的大小，此时用这种方法就会得不偿失。3实验实验的目的是通过对不同大小、不同数据密度以及不同维数的立方体进行实验来对上述算法的性能进行分析。实验以SOLServer7.0作为平台。分别选择2维、3维、4维构建相应维的稀松和密质数据立方体，设I是数据立方体的维数，di是第i维，IdiI指第i维di的长度，即di维中互不相同的取值个数，那么可通过下式来计算数据立方体的大小和密度:立方体大小=HIdiIIi=l立方体密度=非立方体中非空方格数立方体大小根据此式，分别计算并记录了这3种数据立方体的一些信息，具体见表l。根据表l中/doc/13bd41457e21af45b207a82d.html的信息可以看出这3个数据立方体都是稀松的，用算法l对这几个数据立方体进行挖掘，并分别用0.5%，图l中的实线显示了各种情况0.7%，l.0%和l.l%这几种不同的最小支持度来进行实验，144的执行时间。安徽工业大学学报2003年表1实验4中用到的各维的稀松数据立方体信息表立方体2维立方体3维立方体4维立方体立方体大小37532149671251707733立方体密度3.3X10-27.9X10-46.0X10-5下面再看看算法1对密质立方体的执行情况：类似于上述实验，先分别建立2维、3维和4维密质数据立方体，表2是我们计算并记录的几个数据立方体的一些情况。从这张表中可以看出,这3个数据立方体都是非常密质的数据立方体，同样用算法1对这几个数据立方体进行挖掘，并分别用1.1%,1.0%,0.7%和0.5%这几种最小支持度来进行测试，图1中虚线显示了测试结果。实验分析:从图1可以看出,对于2维数据立方体,不同的最小支持度,算法1对稀松和密质2种数据立方体的执行时间几乎没有什么区别，而对于3维和4维数据立方体则存在着明显的区别。从图1中两对曲线可以看出,算法1对稀松数据立方体的挖掘性能明显优于密质数据立方体的挖掘性能。之所以如此是因为当数据立方体很稀松时，使用Apriori性质能修剪掉很多候选，因而减少了计算支持度时所消耗的时间。而对于密质数据立方体，如何设计出更有效的挖掘算法，需要进一步的研究。参考文献：1AgrawalR,ImielinskiT,SwamiA.Miningassociationrules表2实验4用密质数据立方体信息表立方体立方体大小2维立方体1173维立方体510914维立方体296291立方体密度0.710.360.18图1算法1挖掘稀松立方体和密质立方体的性能比较betwe/doc/13bd41457e21af45b207a82d.htmlensetsofitemsinlargedatabasesC.InProc1993ACM-SIGMODIntConfManagementofData,Washington,DC,May1993.207-216.2JoyceBischoff,TedAlexander.数据仓库技术M.成栋，魏立原译. 北京:电子工业出版社，1998.3GrayJ,ChaudhuriS,BosworthA，etal.Datacube:arelationalaggregationoperatorgeneralizinggroup-by,cross-tab,andsub-totalsJ.DataMiningandKnowledgeDiscovery,1997,1(1):29-53.（10）4裴健，柴玮，唐世渭,等,联机分析处理数据立方体代数J.软件学报,1999，6:561-569.5欧阳为民，(10)；蔡庆生.发现广义序贯模式的增量式更新技术J.软件学报，1998，777-780.6Oinfeng,Yangxue-bing.AhighefficientalgorithmofminingseguentialpatternsC.InProc3thWorldCongressonIntelligentControlandAutomation,2000.3750-3752.一种基于APRIORI性质的多维关联规则挖掘算法的研究作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：秦锋， 杨学兵安徽工业大学计算机学院,安徽,马鞍山,243002安徽工业大学学报(自然科学版)JOURNAL OF ANHUI UNIVERSITY OF TECHNOLOGY(NATURAL SCIENCE)2003,20(2)4次 参考文献(6条) 1.Agra/doc/13bd41457e21af45b207a82d.htmlwal R;Imielinski T;Swami A Mining association rulesbetween sets of items in large databases 19932.Joyce Bischoff;Ted Alexander;成栋;魏立原 数据仓库技术 19983.Gray J;Chaudhuri S;Bosworth A Data cube:a relational aggregation operator generalizing group- by,cross-tab,andsub -totals 1997(01)4.裴健;柴玮;唐世渭 联机分析处理数据立方体代数期刊论文-软件学报 1999(06)5.欧阳为民;蔡庆生 发现广义序贯模式的增量式更新技术期刊论文-软件学报 1998(10)6.Qin Feng;Yang xue -bing A high efficient algorithm of mining sequential patterns外文会议 2000 本文读者也读过(10条)1. 杨学兵 一种高效的多维关联规则挖掘算法研究期刊论文-微机发展2002,12(6)2. 吴建兰 基于数据仓库的教学质量监控系统联机分析与主题挖掘算法的研究与实现学位论文20053. 蔡国强 多维关联规则挖掘的研究学位论文20024. 裴芳 基于关联规则的数据挖掘技术在教学管理系统中的应用学位论文20055. 高坚 基于免疫遗传算法的多维关联规则挖掘期刊论文-计算机工程与应用2003,39(32)6. 宋国杰.范明 一种多维关联规则挖掘的模型与算法会议论文-20017. 闫禹.YAN Yu 多维频繁项集计算方法及应用期刊论文-沈阳师范大学学报（自然科学版）2005,23(4)8. 绳英