序列模式数据挖掘算法研究

摘 要： 序列模式的发现是数据挖掘领域一个活跃的研究分支，即在序列数据库中找出所有的频繁子序列。本文先介绍序列模式挖掘中的一些基本概念，然后详细描述FreeSpan和PrefixSpan2个基于投影、分治的模式增长的重要算法。

关键词：序列模式；算法

一、基本术语和定义

设I= {i1，i2，……，in}是一个项目集合，项目集或者项集（items） 就是各种项目组成的集合，即I 的所有子集。一个序列就是若干项集的有序列表，一个序列S可表示为〈s1，s2，……，sn〉，其中sj为项集，也称作S的元素。元素由不同的项组成，可表示为（x1，x2，……，xn）。当元素只包含一项时， 一般省去括号，如（x2）一般表示为x2。元素之间是有顺序的，但元素内的项是无序的，一般定义为词典序。序列包含项的个数称为序列的长度， 长度为L的序列记为L- 序列. 序列数据库就是元组（tuples）〈sid， s 〉的集合， 其中s是序列，sid 是该序列的序列号，元组的个数称为序列数据库的大小， 记作|SDB|。

1、 FreeSpan算法思想

FreeSpan ，即频繁模式投影的序列模式挖掘，其基本思想为：利用频繁项递归地将序列数据库投影到更小的投影数据库集中，在每个投影数据库中生成子序列片段.这一过程对数据和待检验的频繁模式集进行了分割，并且将每一次检验限制在与其相符合的更小的投影数据库中.

2、FreeSpan 算法分析：

它将频繁序列和频繁模式的挖掘统一起来，把挖掘工作限制在投影数据库中，还能限制序列分片的增长.它能有效地发现完整的序列模式，同时大大减少产生候选序列所需的开销，比基于Apriori 的GSP算法快很多.不足之处，它可能会产生许多投影数据库，如果一个模式在数据库中的每个序列中出现，该模式的投影数据库将不会缩减；另外，一个长度为k 的序列可能在任何位置增长，那么长度为k + 1的候选序列必须对每个可能的组合情况进行考察，这样所需的开销是比较大的. 对FreeSpan 中频繁项矩阵F占用存储空间的定量分析如下：设序列数据库中有m个频繁项，频繁项矩阵共需要|M|= m +32×（m-1）×（m-2） 个计数单元。例如，m=1000，|M|=1.5×106=3Mb（假设每个计数单元占用2b 的空间） ，目前一般的计算机就很容易满足这个要求[4]。

3、PrefixSpan算法的提出

在许多应用中，如DNA分析和股市序列分析等，数据库常包含大量的序列模式，而且许多模式很长，此时有必要重新审视序列模式挖掘问题，以探索一些更加有效、易于扩展的方法.通过观察发现，基于Apriori算法的瓶颈在于每一步的候选集生成和测试，能否找到一种方法，既能吸取Apriori的灵魂又能避免或者充分减少昂贵的候选集生成和测试.顺着这个思路， PeiJian ，Han Jiawei 及Wang Jianyong 等人基于分治和模式扩展的原理提出了模式扩展方法，代表性的算法有FreeSpan 和PrefixSpan ，其中PrefixSpan改进法采用了伪投影技术，性能比FreeSpan 好.下面描述并分析PrefixSpan 算法.

4、 PrefixSpan 算法思想及描述

该算法就是通过前缀投影来挖掘序列模式， 进行投影时， 并不考虑所有出现的频繁子序列， 而是找出前缀序列， 把相应的后缀投影成为一系列的投影数据库. 对于每一个投影数据库， 只须找出局部频繁模式， 且不产生候选码， 它的主要步骤如下：

① 扫描数据库一次，找出频繁L2序列， 假设为k个；

② 划分研究空间： 把完整的序列模式划分为k个研究空间， 分别以频繁L2序列为前缀；

③ 构造相应的数据库，也就是对应前缀的后缀集合；

④ 在这些后缀集合中递归地发现频繁模式的子集.

算法形式化描述如下：

输入： 序列数据库S 和最小支持度min sup.

输出： 所有的序列模式.

方法：调用子程序PrefixSpan（ < > ， 0 ， S ）

其中子程序PrefixSpan（ α， L ， S|α） 描述如下：

（1） 扫描S|α，找到满足下述要求的长度为1 的序列模式b ：

1） b可以添加到α的最后一个元素中并为序列模式；

2） b可以作为α的最后一个元素并为序列模式.

（2） 对每个生成的序列模式b ，将b添加到α形成序列模式α′，并输出α′；

（3） 对每个α′，构造α′的投影数据库S|α′，并调用子程序PrefixSpan （α′，L + 1，S|α′） .子程序参数说明：α为一个序列模式； L 为序列模式α的长度； S|α为α的投影数据库（当α为空时， S|α就是S） .

5、PrefixSpan算法的主要改进：

（1）逐层投影：使用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数.

（2）伪投影：当序列数据库可以直接放入内存时，可以使用伪投影操作代替实际的投影数据库，从而可以有效减少构造投影数据库的开销. 其主要思想就是用指针指向对应序列， 用偏移量表示后缀起始位置， 这样就可用指针和偏移量代替真实投影， 从而在投影数据库中不重复出现后缀， 节省不少的空间. 例如： 序列数据库只有序列〈a（abc）（ac）d （cf） 〉， 关于〈ab〉的投影数据库为〈（- c）（ac） d （cf） 〉， 这时可以用（e ，4） 代替S |〈ab〉， 指针指向对应的序列， 而4表示后缀从第4 位置开始， 即从字符c 开始. 可见利用虚拟投影节省了空间， 进一步提高了该类算法的性能[6].

6、 PrefixSpan 算法与Apriori算法的比较

经过测试比较，PrefixSpan 算法性能比基于Apriori的算法（GSP 和SPADE） 明显要好，原因在于：

1） 模式扩展方式不生成候选序列。PrefixSpan 是一个基于模式扩展的方法，就象FP - growth 一样。用传统的候选集生成- 测试方法来处理一个比较小的数据库（例如只有10k 的序列） ，需要相当多的时间来生成和测试大量的候选序列模式。

2） 基于投影的分治是数据缩减（ reduction） 的有效方法。序列模式α的投影数据库包含且仅包含用来挖掘那些由α扩展得到的模式的必需信息， 投影数据库的大小随着挖掘过程向更长的序列模式进行而迅速缩减。

3） PrefixSpan 需要的内存空间相对稳定。原因在于它采用分治的方法，不生成候选集。而GSP 和SPADE ，当支持度阈值（support threshold） 降低时，由于需要容纳大量候选序列，需要相当数量的内存。基于模式扩展的方法，可以应用到多层次、多维数的序列模式中，也可以挖掘其他结构化的模式。