文档介绍：序列模式挖掘的并行算法研究
摘 要
序列模式挖掘是指从序列数据库中发现相对于时间或者其它顺序的高频
率序列。其最初动机是想通过在带有交易时间属性的交易数据库中发现频繁
项目序列以发现一个时间段内的客户购买行为规律。近年来序列模式挖掘已
经成为数据挖掘的一个重要方向，其应用范围已不局限于交易数据库，在
DNA 分析等尖端科学研究领域、Web 访问等新型应用数据源等众多方面都
得到了针对性研究。
文中结合 和 提出的序列模式挖掘的有关定义和
提出的概念格理论，提出了频繁概念的定义；根据序列模式并行挖
掘的需要提出了搜索空间划分理论，其中包括搜索空间、子搜索空间、等价
子搜索空间和最大子搜索空间的定义。
序列模式挖掘的数据有如下特点：数据量大，数据分布存储。已有的大
部分序列模式挖掘算法没有综合考虑到数据的上述特点。本文针对序列模式
挖掘数据的这些特点，结合并行理论，提出了一个分布式并行算法
SPP(Sequential Pattern Parallel)。本算法遵循模式缩减的原则，利用分治策
略实现并行操作，在每台处理器上运用搜索空间划分理论和频繁概念构造频
繁项集，运用图深度优先搜索方法构造频繁序列。算法只需扫描数据库两
遍，不需要生成候选序列，大大减少了数据库访问时间，提高了序列模式挖
掘的效率。不过本文采用是静态负载平衡，还有待改进。
基于自己设计的随机数据生成程序和不同的消息结构，本文在具体的并
行环境中模拟了算法 SPP，并在单机中实现了 AprioriAll 算法。实验证明，
相比于 AprioriAll，SPP 算法具有良好的加速比和效率。
关键词 序列模式；并行；概念格；搜索空间
- I -
Research on Parallel Algorithm for Sequential
Pattern Mining
Abstract
Sequential pattern mining is the mining of frequent seqences related to time
or other orders from the sequence database. Its initial motivation is to discover
the laws of customer purchasing in a time section by finding the frequent
sequences. In recent years, sequential pattern mining has become an important
direction of data mining, and its application field has not been confined to the
transanction database and has extended to new data sources such as Web and
advanced science fields such as DNA analysis.
Combining with the relevant definitions put forward by and
and Concept Lattice Theory brought forward by , this paper
proposes the term of frequent concept. To fulfill the needs of sequential pattern
parallel mining, there proposes search space partition theory which includes the
definitions of search space, sub search space, equivalence sub search space and
maxi