并行序列模式挖掘

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

1、并行序列模式挖掘研究概况1序列模式挖掘问题R.Agrawal等人在1995年首先提出了序列模式挖掘的概念[1]，其问题描述如下。在由多个交易组成的交易数据库中，某个交易描述了某个顾客在某时间购买物品的集合。物品的集合叫做项集。相同顾客在不同交易中包含的项集的子集，按时间先后关系排列称为一个序列。每个子集称为一个元素(element)。并且给定由用户确定的最小支持度阈值(min_supportthreshold)，序列模式挖掘就是去发现所有子序列的出现频率不小于给定的最小支持度的频繁子序列。2序列模式挖掘研究概况在序列模式挖掘的问题被提出以后，人们开始在时间序列数据库中挖掘序列模式和其他频繁

2、模式的算法方面不断地进行研究和改进。现有的序列模式挖掘算法主要可以分为两类:第一类是基于Apriori特性的算法[2]。它是由R.Agrawal和R.srikant在1994年提出的。其基本思想是任一个频繁模式的子模式必定是频繁的。基于这一特性，人们提出了一系列类APriori的序列模式挖掘算法，这些算法中有采用水平数据格式(horizontaldataformat)的算法，如AprioriAll算法[1]、GSP算法[3]、PSP算法[4]等;有采取垂直数据格式(verticadataformat)的算法，如SPADE算法[5]、SPAM算法[6]等。第二类是J.Han等人提出的基于模式

3、增长(pattern-growth)策略的算法，如Freespan算法[7]、Prefixspan算法[8],[9]等。另外，C.Antunes等人提出了SPARSE算法[10]。在很多序列模式挖掘任务中，用户不需要找出数据库中所有可能存在的序列模式，而是加入一定的约束，找出用户感兴趣的序列模式[11],[12]，Agrawal等人将序列模式挖掘问题加以泛化，引入了时间约束、滑动时间窗口(slidingtimewindow)和分类约束，并提出了GSP算法[3]。上述序列模式挖掘算法都是在一维信息中挖掘序列模式。在多维序列模式方面，H.Pint等人提出的UniSeq算法[13]能有效地挖掘多

4、维序列模式，但在维度较高时其挖掘性能会有所下降。当前国内外学者研究方向还包括增量式(Incermental)序列模式挖掘[14]、闭合(Closed)序列模式挖掘[15]、周期性(Peirodic)模式挖掘[16]、结构(Strueture)模式挖掘[17]、近似(Approximate)序列模式挖掘[18]等。3并行序列模式挖掘研究概况由于并行关联规则挖掘方面的研究起步较早，出现了许多优秀的算法[19]～[24]。而序列模式是关联规则的扩展，并行序列模式挖掘也很快被人们重视起来。当前大多数并行序列模式挖掘算法都是对串行算法并行化的结果。随着研究的深入与问题的需要，序列模式挖掘的经典算法G

5、SP的思想也逐渐被扩展到了并行序列模式挖掘中。Shintani等人提出了基于GSP算法的三种并行策略NPSPM、SPSPM、HPSPM[25]。在算法NPSPM中，将候选序列复制到所有处理器中，每个处理器利用本地数据库计算其本地支持度，并在每次迭代之后执行一个归约操作，最后得到其全局支持度。NPSPM在每个节点上都复制完整的候选集，在处理大型数据库时常常会导致内存溢出；SPSPM策略将候选集划分成大小相等的块后分别置于各个处理器中。但是SPSPM利用系统的聚合内存，容易引起额外的通信开销，因为为了得到序列的全局支持度，每个处理器的本地数据库必须广播到其他所有的处理器上；HPSPM采用了一个

6、更加智能的策略，一方面基于Hash机制对候选序列进行划分，另一方面，它减少了所需的通信时间。相比前面两个并行策略，HPSPM的性能最好。Guralnik等人提出了一类基于树投影技术的并行序列模式算法[26],[27]。根据并行策略，算法可被分为两种。一种是数据并行模式DPF：原始数据库被划分成p个大小相等的块存于p个处理器上，每个处理器拥有一个相同的字典树，各处理器计算本地支持度然后通过通信和归约操作得到各候选序列的支持度，然后将全局支持度发送到各处理器，并求出第k层的频繁序列；另外一种形式是任务并行模式TPF：利用数据并行算法扩展树直到某一层k+1(k>0);然后将第k层不同节点划分到各

7、处理器上，一旦初始分配完成，每个处理器继续产生子树(子森林)，这样可以获得比DPF更好的扩展性。Zaki等人提出了PSPADE算法[28]处理共享内存计算机上的序列模式挖掘问题。该算法采用了如下技术:(l)使用垂直数据库的数据格式，通过简单时态连接列举出所有频繁序列;(2)利用格理论，将原始搜索空间分解成基于后缀的类，这些类可在主存中被单独处理。这种分解过程在下一层被递归地应用到各个父类上以产生更小的类;.(3)提出了异