序列模式挖掘——GSP算法

序列模式挖掘的基本概念
项目全集I、项集X和事务集合T的概念和文章关联规则挖掘——Apriori算法 中定义的一致。一个序列(Sequence)是一个有序的项集列表，这个有序通常是指时间有序。我们将序列s表示为：

<a1a2...ar>

其中，
ai
是一个项集，也称为s的一个元素。序列元素
ai
用

{x1,x2,...,xk}

表示，其中
xj∈I
，并且，
ai
中的元素是按字典序排列的。一个项目在一个序列的某个元素中只能出现一次，但是可以出现在序列的多个元素中。一个序列中元素的个数成为序列的基数；一个序列中项目的个数成为序列的长度，长度为k的序列成为k-序列。这里有一个关于序列的例子，如下表：

其中，每一个用户每一次购买的项目集合，是一个事务，也是一个项目集合，每一个用户所有次购买事务按时间排序就组成了一个序列，比如，对应于用户2的序列位：
<(10,20)(30)(10,40,60,70)>
。注意到，序列元素中的的项目是有序的。
子序列超虚列：对于两个序列
s1=<a1a2...ar>
和序列
s2=<b1b2...bv>
，如果存在整数
1≤j1<j2<...<jr?1<jr≤v
使得
a1?bj1,a2?bj2,...,ar?bjr
， 那么
s1
就是
s2
的字序列，
s2
就是
s1
的超序列。比如，
<(10)(30)(10,40,60,70)>
就是
<(10,20)(30)(10,40,60,70)>
的字序列。
序列模式挖掘，就是从一个数据序列(Data Sequence)集合S中找出所有满足用户指定最小支持度的序列。每个这样的序列称为一个频繁序列，或者序列模式。可以看出，序列模式挖掘类似于Apriori算法中的频繁项目集挖掘是类似的，而且你接下来就会发现，帮助我们实现序列模式挖掘的GSP算法和频繁项目集挖掘的算法十分接近，如果你已经理解了频繁项目集挖掘算法，那么就可以很容理解GSP算法。
GSP算法
直接给出算法伪代码：

candidate?gen?SPM(Fk?1)
的伪代码如下：

其中，
Ck
表示候选k-频繁序列模式，
Fk
表示k-频繁序列模式，
UkFk
表示所有k-频繁序列模式的并集。 关于GSP算法更详细的介绍，可以阅读论文[2]。 参考资料： 1. Bing Liu. 《Web Data Exploring Hyperlinks,Contents,and Usage Data》Second Edition. 2. R. Srikant and R. Agrawal. Mining Sequential Patterns: Generalizations and Performance Improvements.