关联规则并行研究综述

-1-综述报告报告题目：_关联规则的并算法研究综述学生姓名：__李艺_______________入学年份：__2009年9月____________专业：__计算机应用技术__________研究方向：__生物信息学______________导师：__蔡应繁周应华___________时间：__2014年3月__导师审查意见1.是否和开题内容一致：2.从综述广度、写作水平、文献阅读量等方面给出简要评价：总分(百分制，60分以下为不合格)：签字：日期：-2-说明研究生论文选题是研究生进行学位论文工作的开端，也是对研究生进行科研训练的重要一环。选题时要把握开拓性、先进性、成果的必要性、成果的可能性等原则。选题要在导师指导下，由研究生独立进行。课题还应尽可能符合研究生的素质特点和兴趣，尽可能结合已有的科研任务，尽可能纳入我院的科研计划。研究生开题是在第四学期末进行，无论是参加导师课题或自选课题的研究生，一律要求从第三学期开始进行选题调研，充分学习了解某领域的国内外研究现状，保证必要的前期研究积累。开题前两周必须提交一篇10－15页（统一的技术报告格式）的综述报告给导师审阅，由导师签字认可，作为必要材料附在开题申请表后，否则不允许进行开题。该综述报告必须保证20篇以上的文献阅读量（记录在参考文献中），其中英文文章篇数不少于50％。导师要给学生充分的开题建议。重庆邮电大学计算机学院2014年3月-3-关联规则的并行算法研究综述李艺重庆邮电大学计算机科学与技术学院重庆400065E-mail:[e-mail]:18223980008摘要：关联规则挖掘是近年来数据挖掘研究中一个相当活跃的领域。本文详细介绍了关联规则及相关术语的定义,对关联规则的分类进行了评述，着重介绍了关联规则的算法以及关联规则的并行挖掘算法，重点对一些算法进行了分析，并对未来的发展进行了预测和展望。关键词：数据挖掘关联规则并行分布式ASurveyofResearchonAlgorithmofparallelofassociationrulesAbstract：Associationrulesminingisaveryactivefieldofdataminingresearchinrecentyears.Thispaperintroducesindetailtherelevantregulationsandrelateddefinitions,astheclassificationofassociationrulesareintroduced,withtheemphasisontheimportanceofseveralparallelalgorithmsofassociationrulesexcavationalgorithmofassociationrulesandalgorithmanalysisandpredictionofthefuturedevelopmentprospects.Keywords:DataminingAssociationrulesParallelDistributed-4-1.引言近年来，随着计算机存储与数据库等技术的飞速发展，特别是云储存的出现及发展，使得人们所拥有的数据信息量大幅增加，如何从海量的数据中挖掘出有价值的信息已经成为国内外相关专家研究的课题。传统数据库系统无法发现隐藏在海量数据背后的关系，也无法使用已知的数据去预测未来的数据发展趋势与方向，从而导致“数据海量而信息缺乏”现象。[1]人工智能（ArtificialIntelligence）[2]和机器学习（MachineLearning）[3]的出现为人们对海量数据的分析提供了便利，而且直接促使数据挖掘(DataMining)[4]的产生，并得到迅速发展。数据挖掘具有重要的理论及应用价值，因为它不仅能用来描述过去数据的发展过程，而且可以发现先前未知的有用模式，具有预测未来观测结果的能力，已成为一个具有广阔应用前景的热门研究方向。目前，数据挖掘已经被成功地应用在信息管理、科学研究、工程设计、过程控制、决策支持等许多方面。数据挖掘可采用分类、聚类、关联分析、预测、序列分析等多种技术对数据进行分析处理，其中与关联分析对应的关联规则挖掘是数据挖掘研究的一个重要分支。关联规则（AssociationRule）是在1993年被Agrawal等[5]首次通过分析购物篮问题而提出的。1998年Cai等[6]提出了加权关联规则挖掘算法，引入了项目权重，之后大量学者专家进行了加权关联规则研究，提出了许多垂直加权、水平加权、混合加权的关联规则算法和相应扩展及应用，加权关联规则不断得到发展并受到重视。许多专家学者对其进行了大量的研究和探索，并对原有的算法进行了优化改进和扩展，使得关联规则挖掘得到广泛应用，目前，在科学研究、通信与安全、金融、零售、医疗保健等行业和领域发挥着巨大作用，成为数据挖掘最最重要、最热门的研究内容之一。2.关联规则2.1关联规则的定义定义：设I={i1,i2,…,im}是项的集合,事务数据库DB=T1,T2,…,Tn,其中的每个事务T是项的集合,T⊆I,并且每个事务T都有一个唯一的标识符TID.如果X⊆T,则称X是一个项集(itemset),如果X中有k个元素,则称X为k-项集。关联规则是形如A⇒B的蕴含式,其中,A⊂I,B⊂I且A∩B=∅。规则A⇒B在事务数据库DB中的支持度(support),是DB中包含A∪B的事务占事务总数的百分比,即概率P(A∪B)。一个项集X的支持度一般用sup(X)表示。规则A⇒B在DB中的可信度(confidence),是在DB中的那些包含A的事务中,B也同时出现的概率,即条件-5-概率P(B|A)。对于一个项集X,如果其支持度大于等于用户给定的阈值MinSup,则称X为频繁项集(FI:FrequentItemset)或频繁模式。[5]关联规则的挖掘一般可分成两个步骤:(1)找出所有支持度大于等于最小支持度阈值的频繁项集。(2)由频繁模式生成满足可信度阈值的关联规则。第(1)步的工作是相当费时的,而第(2)步在第(1)步的基础上很容易实现,因此关联规则挖掘算法的性能主要由第(1)步决定。频繁项集的挖掘问题可以用图形象地表示.所有项集能够构成的组合可以用如图1所示的集合枚举树(set-enumerationtree)来表示。集合枚举树是一棵排序树,树中每个结点表示一种项集组合.树的根是空集,以下依次为1-项集,2-项集,……。频繁项集的挖掘问题实际上就是从集合枚举树中找一条分割线(cut),使得在线以上的项集是频繁的,而线以下的项集是非频繁的。为了找出这一分割线,我们需要以一定的策略遍历集合枚举树,以计算结点的支持度。图1由项集abcde构成的集合枚举树(按照次序abcde）2.2关联规则分类传统关联规则挖掘主要是用于购物篮分析的布尔型关联规则，但在实际应用中关联规则有多种类型，根据不同的标准，可以分为不同的类型。[7]2.2.1根据规则中所处理的项对应属性的数据类型分类可以分为布尔型关联规则和数值型关联规则。[8]布尔型关联规则考虑的是项的存在与不存在，处理的是种类化的、离散的数据，显示了变量之间的关系；而数值型关联规则是对数值型字段进行处理的关联规则，规则所描述的是量化的项或属性之间的关联，项或属性的量化值被划分为区间，涉及动态离散化的数值属-6-性，当然，数值型关联规则中也可以包含种类变量。2.2.2根据规则中涉及的数据维数分类可以分为单维关联规则和多维关联规则。单维关联规则中的项或属性只涉及到数据的一个维，或称为维内关联规则，如用户在商场购买的商品；而多维关联规则中的项或属性涉及两个或多个数据维。[9]2.2.3根据规则中数据的抽象层分类可以分为单层关联规则和多层关联规则。单层关联规则不考虑现实数据所具有的层次性，规则挖掘只涉及相同抽象层的项和属性；多层的关联规则已经充分的考虑了数据的层次性，规则涉及数据不同抽象层的项或属性。当然还有其它的分类标准，如根据对关联规则的不同扩充分类，[10]有相关分析、添加约束、最大模式、频繁闭项集等类型。2.3几种常见的关联规则算法2.3.1经典Apriori算法Apriori算法[5]是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递推的方法。可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。2.3.2基于划分的算法Savasere等[11]设计了一个基于划分的算法。这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把-7-产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。该算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。2.3.3FP-树频集算法针对Apriori算法的固有缺陷，J.Han等[12]提出了不产生候选挖掘频繁项集的方法：FP-树频集算法。采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树（FP-tree），同时依然保留其中的关联信息，随后再将FP-tree分化成一些条件库，每个库和一个长度为1的频集相关，然后再对这些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之Apriori算法有巨大的提高。3.关联规则的并行算法3.1并行的算法概念并行算法[13]是一些可同时执行的进程的集合,这些进程相互作用和协调,以完成对一个问题的求解设计，并行算法的目的是让并行机的众多处理机充分发挥作用,以达到对问题的快速有效求解。并行算法对并行机的依赖性很强,在一台并行机上有效的算法在别的不同结构的并行机上可能效果并不好,因此,设计者必须了解并行机的结构才能设计出好的并行算法。并行算法的目标是尽可能减少时间复杂性,为达到这个目的,要尽量使每个时刻可独立执行的计算任务增加,使整个算法的计算步数尽量减少,或者说,通过增加每个时刻步的算复杂性来减少整体的时间复杂性,适当增加空间复杂性来减少时间复杂性。3.2CD算法CD(CountDistribution)算法[5]是对Apriori算法的简单并行化,在目前诸多并行关联规则挖掘算法中,CD算法经过实践证明,具有较好的性能,其响应时间是随事务数量增加而呈线性增加。CD算法的基本思想是由各个处理器首先独-8-立地生成全局候选项集和频繁项集,其次需要将其生成的局部候选项集计数发送至其它处理器后再进行同步处理,这样一来就需要很大的1/0通信量并存在计算上的冗余情况，故CD算法可以进行很多的改进，国内很多学者都对CD算法进行了改进。3.3DD算法DD(DataDistribution)算法[5]将候选项集在各个结点之间进行均匀分布，这样处理可以通过增加结点来减少每遍扫描的候选项集数目，从而提高算法的并行效率其缺点是需要在各个结点之间进行数据传递