一、序列模式分析的概念
序列模式挖掘（Sequential Pattern Mining，SPM）是指从序列数据库中寻找频繁子序列作为模式的知识发现过程，它是数据挖掘的一个重要的研究课题，在很多领域都有实际的应用价值，如在DNA分析等尖端科学研究领域、Web访问等新型应用。通过对这些领域的数据开展序列模式挖掘，可以发现隐藏的知识，从而帮助决策者做出更好的决策，以获得巨大的社会价值和经济价值。
与关联规则挖掘不同，序列模式挖掘的对象以及结果都是有序的，即序列数据库中每个序列的事件在时间或空间上是有序的，序列模式的输出结果也是有序的。例如，<{1},{2}>和<{2},{1}>是两个不同的序列。
二、序列模式分析的分类
迄今为止，出现了大量的序列模式挖掘算法，主要包括以下4种类型。
（1）基于Apriori特性的算法。
早期的序列模式挖掘算法都是基于Apriori特性发展起来的。Rakesh Agrawal和Ramakrishnan Srikan在1995年最早提出了序列模式挖掘的概念，并且提出了3个基于Apriori特性的算法：AprioriAll、AprioriSome和Dynamic-Some。在此基础上，研究者又提出了广义序列模式（Generalized Sequential Patterns，GSP）算法，它对AprioriAll算法的效率进行了改进，并且加入了时间限制，放宽了交易的定义，加入了分类等条件，使序列模式挖掘更符合实际需要。GSP算法是最典型的类Apriori算法，后来又提出了MFS算法和PSP算法以改进GSP算法的执行效率。
基于Apriori特性的算法思想来源于经典的关联规则挖掘算法Apriori，使用了Apriori算法中的先验知识。这类算法可以有效地发现事务数据库中所有频繁序列，但是与Apriori算法相同，这类算法最大的缺点是需要多次扫描数据库并且会产生大量的候选集，当支持度阈值较小或者序列模式较长时这个问题会更加突出。
（2）基于垂直格式的算法。
最典型的基于垂直格式的算法是SPADE算法，它的基本思想是：首先把序列数据库转换成垂直数据库格式，然后利用格理论和简单的连接方法挖掘频繁序列模式。SPADE算法最大的优点是大大减少了扫描数据库的次数，整个挖掘过程仅需要扫描3次数据库，比GSP算法更优越。然而，SPADE算法需要额外的计算时间和存储空间，用以把水平格式的数据库转换成垂直格式，并且它的基本遍历方法仍然是广度优先遍历，需要付出候选码巨大的代价。另一个典型的算法是SPAM算法，它实施了有效支持度计数与数据库垂直数位映象的表示方法相结合的搜索策略，提高了挖掘长序列模式时的效率。
（3）基于投影数据库的算法。
类Apriori算法会产生大量的候选集并且需要多次扫描数据库，因此在挖掘长序列模式时效率很低。为了克服以上缺点，一些研究者开始另辟蹊径，提出了基于投影数据库的算法。此类算法采取了分而治之的思想，利用投影数据库减小了搜索空间，提高了算法的性能。比较典型的算法有FreeSpan和PrefixSpan。
FreeSpan算法的基本思想是：利用当前挖掘的频繁序列集将数据库递归地投影到一组更小的投影数据库上，分别在每个投影数据库上增长子序列。FreeSpan算法的优点在于它能够有效地发现完整的序列模式，同时大大减少产生候选序列所需的开销，与典型的类Apriori算法GSP算法相比性能更优越。然而利用FreeSpan可能会产生很多投影数据库，如果一个模式在数据库中的每个序列中都出现，该模式的投影数据库将不会缩减；另外，由于长度为 k 的子序列可能在任何位置增长，搜索长度为( k +1)的候选序列需要检查每一个可能的组合，这是相当费时的。
针对FreeSpan的缺点，人们提出了PrefixSpan算法。它的基本思想是：在对数据库进行投影时，不考虑所有可能的频繁子序列，而只是基于频繁前缀来构造投影数据库，因为频繁子序列总可以通过增长频繁前缀而被发现。PrefixSpan算法使得投影数据库逐步缩减，比FreeSpan效率更高，并且它还采用了双层投影和伪投影两种优化技术以减少投影数据库的数量。PrefixSpan算法的主要代价是构造投影数据库。在最坏的情况下，PrefixSpan需要为每个序列模式构造投影数据库，如果序列模式数量巨大，那么代价也是不可忽视的。
（4）基于内存索引的算法。
典型的基于内存索引的算法是MEMISP。MEMISP算法整个过程只需要扫描数据库一次，并且不产生候选序列也不产生投影数据库，大大地提高了CPU和内存的利用率。实验表明，MEMISP比GSP和PrefixSpan更高效，而且对于数据库的大小和数据序列的数量也有较好的线性可伸缩性。
