并行序列模式挖掘

《并行序列模式挖掘》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

并行序列模式挖掘研究概况1序列模式挖掘问题R.Agrawal等人在1995年首先提出了序列模式挖掘的概念[1]，其问题描述如下。在由多个交易组成的交易数据库中，某个交易描述了某个顾客在某时间购买物品的集合。物品的集合叫做项集。相同顾客在不同交易中包含的项集的子集，按时间先后关系排列称为一个序列。每个子集称为一个元素(element)。并且给定由用户确定的最小支持度阈值(min_supportthreshold)，序列模式挖掘就是去发现所有子序列的出现频率不小于给定的最小支持度的频繁子序列。2序列模式挖掘研究概况在序列模式挖掘的问题被提出以后，人们开始在时间序列数据库中挖掘序列模式和其他频繁模式的算法方面不断地进行研究和改进。现有的序列模式挖掘算法主要可以分为两类:第一类是基于Apriori特性的算法[2]。它是由R.Agrawal和R.srikant在1994年提出的。其基本思想是任一个频繁模式的子模式必定是频繁的。基于这一特性，人们提出了一系列类APriori的序列模式挖掘算法，这些算法中有采用水平数据格式(horizontaldataformat)的算法，如AprioriAll算法[1]、GSP算法[3]、PSP算法[4]等;有采取垂直数据格式(verticadataformat)的算法，如SPADE算法[5]、SPAM算法[6]等。第二类是J.Han等人提出的基于模式增长(pattern-growth)策略的算法，如Freespan算法[7]、Prefixspan算法[8],[9]等。另外，C.Antunes等人提出了SPARSE算法[10]。在很多序列模式挖掘任务中，用户不需要找出数据库中所有可能存在的序列模式，而是加入一定的约束，找出用户感兴趣的序列模式[11],[12]，Agrawal等人将序列模式挖掘问题加以泛化，引入了时间约束、滑动时间窗口(slidingtimewindow)和分类约束，并提出了GSP算法[3]。上述序列模式挖掘算法都是在一维信息中挖掘序列模式。在多维序列模式方面，H.Pint等人提出的UniSeq算法[13]能有效地挖掘多维序列模式，但在维度较高时其挖掘性能会有所下降。当前国内外学者研究方向还包括增量式(Incermental)序列模式挖掘[14]、闭合(Closed)序列模式挖掘[15]、周期性(Peirodic)模式挖掘[16]、结构(Strueture)模式挖掘[17]、近似(Approximate)序列模式挖掘[18]等。3并行序列模式挖掘研究概况由于并行关联规则挖掘方面的研究起步较早，出现了许多优秀的算法[19]～[24]。而序列模式是关联规则的扩展，并行序列模式挖掘也很快被人们重视起来。当前大多数并行序列模式挖掘算法都是对串行算法并行化的结果。随着研究的深入与问题的需要，序列模式挖掘的经典算法GSP的思想也逐渐被扩展到了并行序列模式挖掘中。Shintani等人提出了基于GSP算法的三种并行策略NPSPM、SPSPM、HPSPM[25]。在算法NPSPM中，将候选序列复制到所有处理器中，每个处理器利用本地数据库计算其本地支持度，并在每次迭代之后执行一个归约操作，最后得到其全局支持度。NPSPM在每个节点上都复制完整的候选集，在处理大型数据库时常常会导致内存溢出；SPSPM策略将候选集划分成大小相等的块后分别置于各个处理器中。但是SPSPM利用系统的聚合内存，容易引起额外的通信开销，因为为了得到序列的全局支持度，每个处理器的本地数据库必须广播到其他所有的处理器上；HPSPM采用了一个更加智能的策略，一方面基于Hash机制对候选序列进行划分，另一方面，它减少了所需的通信时间。相比前面两个并行策略，HPSPM的性能最好。Guralnik等人提出了一类基于树投影技术的并行序列模式算法[26],[27]。根据并行策略，算法可被分为两种。一种是数据并行模式DPF：原始数据库被划分成p个大小相等的块存于p个处理器上，每个处理器拥有一个相同的字典树， 各处理器计算本地支持度然后通过通信和归约操作得到各候选序列的支持度，然后将全局支持度发送到各处理器，并求出第k层的频繁序列；另外一种形式是任务并行模式TPF：利用数据并行算法扩展树直到某一层k+1(k>0);然后将第k层不同节点划分到各处理器上，一旦初始分配完成，每个处理器继续产生子树(子森林)，这样可以获得比DPF更好的扩展性。Zaki等人提出了PSPADE算法[28]处理共享内存计算机上的序列模式挖掘问题。该算法采用了如下技术:(l)使用垂直数据库的数据格式，通过简单时态连接列举出所有频繁序列;(2)利用格理论，将原始搜索空间分解成基于后缀的类，这些类可在主存中被单独处理。这种分解过程在下一层被递归地应用到各个父类上以产生更小的类;.(3)提出了异步机制，使得处理器工作在不同的类上，处理器之间无须共享或同步;(4)为了保证各处理器上的负载均衡，提出了动态负载均衡机制，即任何一个空闲处理器将加入到一个忙碌的处理器上以处理在更高层形成的类。通过这些技术，算法在减小I/O开销和实现负载均衡方面取得了较好的效果。近年来，科研人员开始把并行化技术引入到闭合序列模式挖掘中去，如韩家炜等人提出的算法Par-CSP[29]，通过将伪投影分配给不同的处理器以实现并行化。同时在我国，越来越多的学者也已经涉足并行序列模式挖掘邻域，邹翔等人提出了分布式序列模式挖掘算法FDMSP[30]，其采用一种异步的方式进行计算，指定站点统计不同序列的全局支持计数。马传香等人提出了并行序列模式挖掘算法PMSP[31]，该算法基于改进的DSG图，通过剪枝候选集及数据的合理分布，有效地解决了I/O代价问题。此外文献[32]，「33]，[34]也都提出了一系列有效的并行挖掘序列模式的算法。4挑战与总结在对海量数据进行挖掘时，随着内存支持和I/O开销的增长，算法的效率也受到严重影响，单机处理远远满足不了需要。开发并行和分布式序列模式挖掘算法是十分必要的。近年来，越来越多的研究人员针对不同并行计算机体系结构提出了许多优秀的并行算法，在很大程度上提高了大规模序列模式挖掘的效率。但是随着并行计算的规模越来越大、参与计算的处理器数目越来越多，并行序列模式挖掘算法的并行效率提高得越来越有限，其原因归根结底是不能很好地解决如下的几个问题:(l)计算负载均衡并行序列模式挖掘过程主要是将挖掘的工作量进行划分，然后交给不同的处理器处理。由于整体工作量在挖掘前是未知的，因此如何进行平均地分配是非常棘手的问题，往往会由于工作量分配不均造成某些处理器在工作时其他一些处理器处于空闲状态，浪费了系统资源。(2)通讯开销并行计算需要各计算单元之间的信息交互，因此通讯开销是必须要考虑的问题，过大的通讯开销会降低整体的挖掘效率。如何减小通讯量和通讯次数是并行序列模式挖掘面临的一大难题。(3)并行空间搜索策略针对串行序列模式挖掘，已有大量简化搜索空间的策略被提出。这些策略可以有效地降低挖掘的工作量，大大提高挖掘的效率。然而，由于受通讯、同步等多方面因素的限制，这些策略并不能直接应用于并行序列模式挖掘。虽然，现有的并行序列模式挖掘算法提出了一些优化策略，但并没有很好地解决效率提高的问题。(4)同步次数并行序列模式的挖掘过程中，当计算进行到某个阶段，每个计算单元可能需要其他计算单元提供的信息才能继续完成后面的计算，此时所有计算单元停止计算，同时进行信息交互，这就是同步。同步次数的增多很大程度上会降低并行序列模式挖掘的效率，在某些基于apriori特性的算法中这种现象尤为突出。(5)I/O开销 序列模式挖掘涉及大规模数据库的多次扫描，受内存限制等条件的影响，并行计算时必然会花费不小的1/0开销。(6)数据偏移在分布存储的并行计算机体系结构下挖掘序列模式，往往全局序列数据库会被划分为大小相等的分块提交给各计算节点并行处理。各计算单元的本地数据库里蕴含的信息量可能有较大差异，这样会造成计算单元之间的负载不均，这就是数据偏移问题。此外，针对特定的计算机体系结构，并行序列模式挖掘还面临着其他一些关键问题，如共享存储环境下数据库互斥访问等。如何针对不同的体系结构设计这些问题的解决方案已经成为并行序列模式挖掘的重要内容。参考文献[1]R.Agrawal，R.Srikant.MiningsequentialPatterns.Procofthe1lthInt'1ConfonDataEngineering(ICDE95).LosAla-mitos，CA:IEEEComputerSocietyPress，1995，3-14.[2]R.Agrawal，R.Srikant.FastAlgorithmsforMiningAssociationRules.In:Proc.ofthe20thInt.Conf.onVeryLargeDatabases，Santiago，Chile，September1994.487-499.[3]Srikant，RandAgTawal，RMiningsequentialpatterns：GeneralizationsandperformanceimprovementsSpringer-Verlag[J]：InProc5thInt．Conf.ExtendingDatabaseTechnology．EDBT，P．M．G．Apers，M．Bouzeghoub，andG．Gardarin，Eds．Vo1．1057．，1996：3-17[4]F.Masseglia，F.Cathala，P.Yoneelet.ThePSPApproachforMiningSequentialPatterns.Proc.ofthe2ndEuropeansymposiumonPrinciplesofdataMiningandKnowledgeDiscovery，Nantes，France，1998:176-184.[5]M.J.Zaki(1998).SPADE:AnEfficientAlgorithmforMiningFrequentSequences.In:ProceedingofMachineLearningJournal，specialissueonUnsupervisedLearning，Vol.42Nos.l/2，pp.31-60.[6]J.Ayres，J.Gehrke，T.Yiu，etal.SequentialPatternMiningUsingaBitmapRepresentation.Proc.Ofthe8thACMSIGKDDInt.Conf.OnKnowledgeDiscoveryandDataMining，Edmonton，Alberta，Canada，2002.NewYork，ACMPress:429-435.[7]J.Han，J.Pei，B.Mortazavi-Asl，Q.Chen，U.DayalandM-C.Hsu.FreeSPan:FrequentPattern-ProjectedSequentialPatternMining.In:Proc.2000Int.Conf.KnowledgeDiscoveryandDataMining(KDD'00)，355-359，Boston，MA，Aug.2000.[8]J.Pei，J.Han，B.Mortazavi-Asl，H.Pinto，Q.Chen，U.DayalandM-C.Hsu.prefixspan:MiningsequentialPatternsefficientlybyPrefix-ProjectedPatterngrowth.In:Proc.2001Int.Conf.DataEngineering(ICDE'01)，Pages:215-224，Heidelberg，Germany，April2001.[9]J.pei，J.Han，B.Mortazavi-Asl，H.pinto，Q.Chen，U.DayalandM-C.Hsu.prefixspan:MiningsequentialPatternsefficientlybyPrefix-ProjectedPatterngrowth[C].IEEETransactionsonKnowledgeandDataEngineering，2004，16(11)，1424-1440.[10]C.Antunes，A.Oliveira.SequentialPatternMiningAlgorithms:Trade-offsbetweenSpeedandMemory.Proc.Ofthe2ndInt.WorkshoponMiningGraphs，TreesandSequences，Pisa，Italy，2004.UniversityofPisa:l-12.[11]J.Pei，J.Han.CanWePushMoreConstraintsintoFrequentPatternMining?Proc.ofthe6thACMSIGKDDInt.Conf.OnKnowledgeDiscoveryandDataMining，Boston，MA，2000.NewYork，ACMPress:350-354.[12]J.Pei，J.Han，W.Wang.MiningSequentialPatternswithConstraintsinLargeDatabases. Proc.ofthe1lthInt.Conf，onInformationandKnowledgeManagement，McLean，Virginia，2002.NewYork，ACMPress:18-25.[13]H.Pinto，J.Han，J.Pei，etal.Multi-dimensionalSequentialPatternMining.Proc.ofthe10thInt.Conf.OnInformationandKnowledgeManagement，Atlanta，Georgia，2001.NewYork，ACMPress:81-88.[14]F.Masseglia，P.Poncelet，M.Teisseire.IncrementalMiningofSequentialPatternsinLargeDatabases.DataandKnowledgeEngineering，2003，46(1):97-121.[15]X.Yan，J.Han，andR.Afshar.ClosPan:MiningclosedsequentialPatternsinlargeDatabases.InSDM'03，2003.[16]J.Yang，W.Wang，P.Yu.MiningAsynchronousPeriodicPatternsinTimeSeriesData.R.Ramakrislman，S.Stolfo，R.Bayardo，I.Parsa.Proc.ofthe6thACMSIGKDDInt.Conf.onKnowledgeDiscoveryandDataMining，Boston，MA，USA，2000.NewYork，ACMPress:275-279.[17]X.Yan，J.Han.gSPan:Graph-basedSubstructurePatternMining.V.Kumar，S.Tsumoto，P.Yu，N.Zhong.Proc.ofthe2002IEEEInt.Conf.onDataMining，Maebashi，Japan，2002.LosAlamitos，CA，IEEEComputerSocietyPress:721-724.[18]J.Yang，W.Wang，P.Yu，etal.MiningLongSequentialPatternsinaNoisyEnvironment.M.Franklin，B.Moon，A.Ailamaki.Proc.ofthe2002ACMSIGMODInt.Conf.OnManagementofData，Madison，WI，2002.NewYork，ACMPress:406-417.[19]R.Agrawal，J.Sharfer.ParallelMIntngofAssociationRules[J].IEEETrans.onKnowledgeandDaraEngg.，1996，8(6)，962-969.[20]J.s.park，M-S.Chenandp.S.Yu.Efficientparalleldataminningforassociationrules.InProc.ofthe4thConfonInformationandKnowledgeManagement，pages31-36，November1995.[21]D.Cheung，J.Han，VT.Ng，AW.Fu，FuYJ.AfastdistributealgorithmformIntngassociationrules.In:Proc.oftheInt'1Conf.onParallelandDistributedInformationSystems.1996.31-44.[22]E.H.Han，G.Karypis，V.Kumar.ScalableparalleldataminingforAssociationrules.IEEETransactionsonKnowledgeandDataEngineering，12(3)，(2000)，337-352.[23]A.Schuster，R.Wolff.CommunicationEfficientdistributedminingofAssociationrules[A].In:ProcoftheACMSIGMODInt'1ConferenceonManagementofData[C]，SantaBarbara，California，2001-05:473-484.[24]0.R.Zaiane，M.EI-Hajj，P.Lu.FastParallelAssociationRuleMiningWithoutCandidacyGeneration[A].TechnicalReportTR01-12，DepartmentofComputingScience[C]，UniversityofAlberta，Canada，2001，665-668.[25]T.Shintani，M.Kitsuregawa.MiningAlgorithmsforSequentialPatternsinparallelHashBasedApproach[C]//InResearchandDevelopmentinKnowledgeDiscoveryandDataMining:SecondPacific-AsiaConference(PAKDD’98).Melboume，Australia，1998:283-294.[26]V.Guralnik，N.Garg，G.Karpis.paralleltreeprojectionalgorithmforsequencemining[C]//EuroPar2001.Manehester:Springer-Verlag2001:310-320.[27]V.Guralnik，G.Karypis.paralleltree-projeetion-basedsequenceminingalgorithm.ParallelComputing，30(4):443-472，2004.[28]M.J.Zaki.Parallelsequenceminingonshared-memorymachines.JournalofparallelandDistributedComputing，2001，61:401-426.[29]S.Cong，J.HanandD.Padua.ParallelMiningofClosedSequentialPatterns.InACM'05，Pages562-567. [30]邹翔，张巍，刘洋，等.分布式序列模式发现算法的研究[J].软件学报.2005，16(7):1262-1269.[31]马传香，简钟.序列模式挖掘的并行算法研究，计算机工程.2005，31(6).[32]赵峰，李庆华.并行序列挖掘的一种改进算法.华中科技大学学报(自然科学版).2003，31(10):38-40.[33]李庆华，马传香.挖掘频繁闭序列的并行算法研究.中国模糊逻辑与计算智能联合学术会议论文集，2005:450-454.[34]T.ZHU，S.BAI.Aparallelminingalgorithmforclosedsequentialpatterns[C].Proceedingsof21stInternationalConferenceonAdvancedInformationNetworkingandApplicationsWorkshops，2007.