数据挖掘中的序列模式

数据挖掘的任务是从数据中发现模式，模式时空一个用语言L来表示的一个表达式E，它可用来描述数据集F中数据的特性，E所描述的数据时机和F的一个子集FE。E作为一个模式要求它比数据子集FE中所有元素的描述方法简单，在实际应用中，往往根据模式的实际作用细分为分类模式、回归模式、时间序列模式、聚类模式、关联模式和序列模式6种。给定一个由客户交易之城的数据库DB，挖掘序列模式的问题就是在那些具有客户指定最小支持度（minimum support）的序列中找出最大序列（maximal sequence），而每个这样的最大序列就代表了一个序列模式（sequence pattern）

一、序列模式挖掘参数

1.时间序列T的时间长度

可以讲数据库中的整个序列或用户所选择的序列（如2003你那）作为时间序列的长度，序列模式（挖掘）将仅限于在之一序列长度之内进行。

2.时间窗口W

一系列在时间内发生的事件在特定的分析中可以看成是一起发生的。如果一个时间窗口W呗设置为同序列T一样长，那就会发现对时间不敏感的频繁模式，也就是基本关联模式。如：“2000年，一个购买电脑的顾客也买了数码相机”其中不再关系哪个先买哪个后买）；若一个事件窗口W被设置为0，那就会发现一个序列事件是作为单个时间发生（来处理的）如：“一个顾客购买了电脑，然后又购买了內存，最后悔购买CD-ROM”。若一个事件窗口W被设置为上述两者之间的某个值（即0与T总长度之间），如：若W设为一个月，那么在同一月发生的交易事务，将被认为是同一时间发生的，而被合在一起进行分析。

3.发现模式中事件发生的时间间隔int。

若将int设为0，就意味着没有间隔，也就是发现严格连续时间序列。这里也可以将参数W考虑进来。若W设为一周，也就是要发现连续各周频繁模式。DNA分析经常需要发现无间隔的连续序列。而min_interval int大多挖掘频繁序列模式的研究都是针对不同的参数设置，以及采用Aprior启发知识和与Apriori类似。但做了相应改动的挖掘方法。

二、序列模式发现算法

1.基于Apriori性质的逐层发现方法

Apriori性质是指频繁项集的所有非空子集必须也是频繁的。即在交易数据库中，如果某一长度为K的序列不是频繁的，那么它的任何长度为k+1的超序列也不可能是频繁的。这种基于Apriori[8]性质的逐层搜索的迭代方法，主要包括AprioriAll算法和GSP算法等。此类算法的思想是在已经生成频繁序列中搜寻更长的频繁序列，并在此过程中对待检查的序列集进行有效的修建。

（1）AprioriAll算法。AprioriAll算法将序列模式发现的过程分为以下五个阶段：排序阶段：数据库中的元组按照“顾客号”为主键，“交易时间”为次主键排序。频繁项集发现阶段：用频繁集合发现算法，求出所有频繁项集，以灭个频繁项集为唯一元素的序列即为频繁1-序列。转化阶段：每个事务被该事务中所有频繁项集所替代，经过转化，事务序列呗表示成由频繁项集的集合构成的有序表。序列阶段：这是算法的主要阶段。在算法执行中，需要多趟扫描原序列数据库。最大序列阶段：从频繁序列中找出最大序列，在实现上，这一阶段可以与上一阶段合并。

（2）GSP算法。基本的序列模式模型研究的是在同一字段上的序列模式即单维的序列模式。实践应用中的数据集是一个多维的空间。基本序列模型存在缺少时间约束、对交易的定义死板、缺少分类层次等局限，因此为客服上述局限文献7的作者将序列模式的基本模型进行了扩展，加入了时间约束、滑动窗口和分类层次，提出了泛化序列模式发现问题并给出了相应的GSP算法。GSP算法是一个迭代的过程，在每一次迭代中，首先生成候选序列，然后扫描序列数据库计算候选序列的支持度以确定频繁徐立。其中候选序列的生成阶段包括连接阶段和修剪阶段。

2.基于序列模式增长的发现方法

基于序列模式增长（sequential patterns growth）方法，包括FreeSpan，PrefixSpan算法等。这类方法采取了一种分而治之（devide-and-conquer）的思想，挖掘过程中无需生成候选序列。其主要特征有：算法不生成大量的候选序列，而是以某种压缩的形式保留了原数据库的基本的数据分组。随后的分析可以聚焦于计算相关数据集而非候选序列的频率。算法的每一次迭代不是扫描完整的原数据库来匹配相应的全部候选序列，而是通过数据库投影来对将要检查的数据集和序列模式进行划分，这样分而治之的方法将减小搜索空间，提高算法性能。FreeSpan算法是在基于任何频繁子序列对数据库投影，并在子序列的任何位置上增长；而PrefixSpan算法仅仅基于频繁前缀子序列投影并通过在其后添加后缀来实现序列的增长。PrefixSpan算法因包含更少的投影库和子序列连接而比FreeSpan算法性能更优。

本文主要讲述了序列模式的挖掘问题，并对序列模式挖掘的经典算法进行描述。肃立恶魔是与管理模式相仿，只不过把数据之间的关联性与时间联系起来。为了发现序列模式，不仅需要知道事件是否发生，而且需要确定事件发生的时间。由此看出，序列模式挖掘是很有价值的，他在网络通信、气象分析、商业零售、金融证劵等领域有广阔的应用前景。同时对于一般的大型数据库，序列模式挖掘算法的时空开销往往都很大，这就要求我们在经典算法的基础上设计出高校挖掘算法。

作者简介：

孙冬梅（（1978—），女，长春市房产档案馆，学士，研究方向：人工智能。

（作者单位：长春市房产档案馆）