基于时间序列的模式挖掘研究

卢海涛

摘 要：论文阐述了基于时间序列的模式挖掘的基本概念，对基于时间序列的模式挖掘经典算法和增量挖掘、时间序列分段线性表示及相似性算法进行了相对全面的介绍，对算法的特征做了详细的论述。

关键词：时间序列 序列模式 增量挖掘 数据挖掘

中图分类号：TP311 文献标识码：A 文章编号：1672-3791（2014）06（b）-0204-01

1993年，Agrawal提出关联规则挖掘算法，但是关联规则挖掘只针对单次事务内部模式，不能挖掘出与时间关联的事务间的联系和趋势。针对这个问题，在1995年，Agrawal和Srikant再次提出序列模式挖掘算法，这是序列模式挖掘算法的第一次提出，算法概要为：给定一个序列集合，由项集构成单一序列，然后给定由用户指定的最小支持度阈值，序列模式挖掘算法发现所有出现频率大于或等于指定的最小支持度阈值的频繁子序列。序列模式挖掘在关联挖掘中加入了时间属性，用以挖掘事务之间在时间上的顺序联系，其作用是能够从数据集中发现可以反映事务间联系和规律的一些模式，进而能够预测事务将来的发展趋势。

序列模式挖掘算法一般可将其大致分为一般算法、增量式序列模式挖掘算法和时间序列分段线性表示及相似性算法等。

1 一般序列模式挖掘算法研究

早期的序列模式挖掘算法大多是基于Apriori算法进行的改进，一般都基于在Agrawal提出的关联规则挖掘中提及的所谓Apriori特性：任一个频繁模式的子模式必须是频繁的。Apriori All[1]、Apriori Some、Dynamic Some、GSP[2]等算法都是基于这个特性而构造出来的。

最早提出的序列模式挖掘算法是Apriori All算法。之后提出的GSP算法改进了Apriori All算法的执行效率，加入了对时间的限制、扩展了交易的定义、考虑了分类的概念，广义化了序列模式挖掘应用领域。之后提出的基于GSP的算法MFS，采用直接连接所有已知频繁序列的方式生成不同长度的候选序列，以期改进算法执行效率。更之后提出的PSP算法，主要是针对存储频繁序列和候选序列的存储数据结构作了改进，将GSP算法中的Hash-tree结构改成了Prefix-tree，这进一步减少了存储序列所需的空间，并且对非序列模式的剪枝过程也更容易进行。

基于所谓Apriori特性的这一类序列挖掘算法是采用分级式方式、通过产生候选序列进行比对的方式进行，其有如下一些局限性：（1）会有大量的候选序列集被产生出来。（2）需要对序列所在数据库进行多次扫描，运行开销过于庞大。（3）对于长序列模式的查找，通过扫描序列数据库的方式也面临诸多困难。

之后有人提出基于数据投影的序列模式挖掘算法，算法采用分而治之，逐步求精的思想，在序列模式挖掘过程中无需生成候选序列，这就减小了搜索空间，提高了算法执行效率。经典的算法包括FreeSpan和PrefixSpan算法等。

而基于垂直格式的SPADE算法，定义了格序列搜索模式，并采用简单连接方式来遍历频繁序列，仅需最多三次序列数据库扫描过程就可以找到所有目标序列。

之后又提出基于内存索引的MEMISP算法，其思想是通过扫描外存数据库将它转换为MDB（内存数据库），跟PrefixSpan算法相比，算法执行过程中不再扫描数据库，也不需要生成候选序列和中间投影数据库，比PrefixSpan得执行效率更高，MEMISP算法的性能与数据库的大小和数据序列的数量呈现线性相关性。

2 增量式序列模式挖掘研究

时间序列是时间相关的，期望挖掘出的目标序列数据也在随时间改变，所以增量式序列模式挖掘在时间序列模式挖掘上更为适合。在这一方面，有如下算法被提出。

GSP+算法基于GSP，其算法的主要改进在于剪枝策略的变化，在对Hash-tree进行剪枝时仅扫描更新部分的数据库以检测候选序列支持度。而基于MFS算法的MFS+也采用了同样的剪枝策略。ISM算法[3]是基于SPADE算法进行改进的，其执行效率有了极大提升，比起大多数序列模式挖掘算法来说，效率提升了几个数量级。ISE算法[4]对ISM算法作了改进，在新序列的插入策略上做了调整。ISE是扩展频繁序列后缀，而IUS算法则是对前缀和后缀都进行了扩展。并且IUS使用了ISM定义的负边界，并新定义了一个最小负边界序列支持数，IUS算法对于内存空间的占用更少。

3 时间序列分段线性表示研究

分段线性表示法主要用来对时间序列进行近似表示，具体方法是对时间序列中进行特征点抽取，将抽取的特征点依次连接，构成的线段序列就称为时间序列的分段线性表示。时间序列分段线性表示研究中最重要的问题就是如何进行特征点抽取，目前主要的方法有PCA（Piecewise Const Approximation）方法、Landmark模型、重要点分段法和PLA（Piecewise Linear Approximation）方法等。

参考文献

[1] AgrawalR，SrikantR.Mining Sequential Patterns，Proceedings of the 1th International Conference on Data Engineering.TaiPei：IEEE Computer Society Press，1995：3-14.

[2] AgrawalR，SrikantR. Mining sequential Pattems：Generalizations and Performance imProvements.In：APers PMG Mokrane B，etal，eds.Proc.of the 5th Int.1Conf.on Extending Database Technology.Heidelberg：Springer-Verlag，1996：3-17.

[3] parthasarathys，Zak1MJ，OgiharaM，etal. Incremental and interactive sequenee mining[C] //Proc.of the 5th International Conference on Information and Knowledge Management.KansasCity，NewYork：ACMPress，1999：251-258.

[4] MassegliaF，PoneeletP，TeisseireM. Incremental mining of sequential Patterns in large databases[J].Data and Knowledge Engineering，2003，46（1）：97-121.endprint