资源描述：
《关联规则挖掘的apriori算法改进综述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、关联规则挖掘的Apriori算法改进综述1引言数据挖掘是一种半自动地从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取出隐含在其中潜在有用的信息和知识的过程。数据挖掘从数据中提取人们感兴趣的可用信息和知识，并将提取出来的信息和知识表示成概念、规则、规律和模式。数据挖掘，又称数据库中的知识发现(KnowledgeDiscoveryinDatabase,KDD)，指的是从大型数据库的数据仓库中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用信息，换言之，数据挖掘是一个利用各种分析工具在海量数据
2、中，发现模型和数据间关系的过程，这些模型和关系可以用来作出预测。对于数据挖掘技术的研究已引起了国际人工智能和数据库等领域专家与学者的广泛关注，这其中在事务数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的研究课题。关联规则是美国IBMAlmadenresearchcenter的RabeshAgrawal等人于1993年首先提出的，最近几年在数据挖掘研究领域对关联规则挖掘的研究开展得比较积极和深入[1]。关联规则挖掘是发现大量数据中项集之间有趣的关联或相关关系。随着大量数据不停被地收集和存储，许多业界人士
3、对于从数据库中挖掘关联规则越来越感兴趣。2Apriori算法2.1关联规则挖掘问题的形式化描述对于经常使用的数据，同一文件的不同版本之间的内容往往会有重复，因此数据冗余比较多，如果采用增量式压缩就可以大大节省磁盘空间。但是这样的数据是压缩的，一旦用户需要查询/恢复数据就需要解压过程，因此这会使系统性能降低。设I={i1，i2，…，im}是由m个不同的项目组成的集合，给定一个事务数据库D，其中的每一个事务T是I中一组项目的集合，即T⊆I，T有一个唯一的标识符TID。若项集X⊆I且X⊆T，则事务T包含项集X。
4、一条相联规则就是形如X⇒Y的蕴涵式，其中X⊆I，Y⊆I，x∩Y=Φ。相联规则X⇒Y成立的条件是:(l)它具有支持度s，即事务数据库D中至少有s%的事务包含XY∪；(2)它具有置信度c，即在事务数据库D中包含X的事务至少有c%同时也包含Y。关联规则的挖掘问题就是在事务数据库D中找出具有用户给定的最小支持度minsup和最小置信度minconf的关联规则。2.2Apriori算法简介1994年，RakeshAgrawalRama和KrishnanSkrikant首先提出了Apriori算法[2]，它是一种最有
5、影响的挖掘布尔关联规则频繁项集的算法。Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法，其核心是使用候选项集找频繁项集。Apriori算法使用一种称作逐层搜索的迭代方法k-项集用于搜索以(k+l)-项集。首先，找出频繁1-项集的集合，该集合记作L1，L1用于找频繁2-项集的集合L2，L2从用于找L3.如此下去，直到不能找到频繁项集。3Apriori算法的改进3.1DDApriori算法[3]从Apriori算法可以看出,对每一Ci均对数据库扫描一次,而这时有些事务已经对频繁项集的生成不产生
6、作用,减少数据库D内不起作用的事务对于算法来说是很有必要的,本算法的基本思想就基于此。该算法是在每次计算Ci支持记数的过程中,给不包含Ci中的任何项集的事务打上删除标记,在以后的扫描计数中不加考虑。其实在Ci扫描过数据库后,与Ci中某一项集相同的事务t,如果其支持记数小于Vminsup,这一事务对后面的频繁项集将不产生作用,因此它也可以从数据库中删去。本算法通过增加这一事实,得出的算法比[3]中算法更有效。随着i值的增大,删除的事务也不断增大,因而有效降低了候选项集的计数速度,提高了整个算法的效率。算法:
7、DDApriori使用根据候选生成的逐行迭代找出频繁项集输入:事务数据库D;最小支持记数阈值Vminsup输出:D中的频繁项集L方法:10)L1=findfrequent1-itemsets(D);/20)for(i=2;Li-1≠;i++){30)Ck=aproiri_gen(Li-1,Vminsup);//产生新的候选项集,此函数同于Apriori算法中的函数40)foreachtransactiont∈D{//扫描D并计数41)ift.delete=0thendobe
8、gin50)Ct=subset(Ci,t);//获取t的子集作为候选51)ifCt=then52)t.delete=1//打上删除标志53)else//对每一个Ct进行计数并记录内容54)ifCt=cthent.count++,t.text=c60)foreachcandidatec∈Ct.70)c.count++;71)end80)}81)if
