序列模式挖掘---PrefixSpan

很多文章在讲PrefixSpan的时候，不注重基础概念的描述，而只是在乎算法的流程，这样会使得只是照葫芦画瓢，又或者对算法流程某些局部的地方存疑。所以这里重点讲解算法涉及到的所有概念，并且给出经典的Projection过程和理解。

引言：
首先要理解什么是序列模式挖掘问题，然后要清楚算法引出的一些概念前缀、投影、后缀，最后才是整个算法如何通过定义出来的东西来对问题进行求解。并且在这之后会有一些优化。
而PrefixSpan是解决序列模式挖掘问题的，对于这个问题，已经有各种Apriori-based解法，最经典的就是GSP。并且还有不是Apriori-based的FreeSpan。后者虽然比Apriori-based算法会更加快速，但是效率仍旧不是很好，并且在极端的情况下表现力很差。为了能方便之后阅读论文，这里给出的概念定义的语言遵从论文，并且部分给出论文的正文。

序列模式挖掘问题：

基础概念：

给定一个a set of sequences。其中每一个sequence 是 a list of elements 并且每一个 element 是 a set of items。

Sequence_id	Sequence
10	<a(abc)(ac)d(cf)>
20	<(ad)c(bc)(ae)>
30	<(ef)(ab)(df)cb>
40	<eg(af)cbc>

a set of sequences ：就是上面这个表，也就是要处理的数据。
sequence (a list of elements) ：就是 <a(abc)(ac)d(cf)> 这样一条记录
element (a set of items) ：就是如同a或者是(abc)或者是(ac)...其中element的长度为1的话比如a。其实应该是（a）可以简写成a。
item：就是最小的单元，比如(abc)中的a或者b或者c。又或者是第一个element （a）中的a。

并且可以发现的是 sequence是一个elements的列表，这个是有顺序概念的，而element是一个items的集合，这个是无序的概念的。也就是说一个element中的item顺序不同，但是里面的东西都一样，那么其实是等价的。这个就给之后的标准表示给出了正确性的证据。

对于 <a(abc)(ac)d(cf)>这样的一个sequence，里面有5个elements,并且有9个items。规定其长度为9.（以Item为计数）并且可以记为 length-sequence也就是9-sequence

原文：
The number of instances of items in a sequence is called the length of the sequence. A sequence with length l is called an l-sequence.

并且定义子序列（subsequence）和超序列（父序列，super sequence）的概念：
$\alpha = <a_1,a_2,...,a_n> \beta = <b_1,b_2,...b_m>$
$\alpha$ 是 $\beta$ 的subsequence $iff$ 存在 $1\le j_1<j_2<...<j_n\le m$ 使得 $a_1\subseteq b_{j_1},a_2\subseteq b_{j_2},...,a_n\subseteq b_{j_n}.$
此时也可以说 $\beta$ 是 $\alpha$ 的super sequence。

（说白了，就是能在 $\beta$ 上从前往后找依次找出 $\alpha$ 对应的每个element的超集）

这个时候咱们就可以记为： $\alpha \sqsubseteq \beta$ 。

为了能够让问题描述更加科学，咱们定义怎么形容 a set of sequences。叫做 sequence database S。上面那张表就是一个sequence database。一个sequence database 由一项项 <序列ID,序列> 元组(tuple)组成。明显元组之间是无序的。再定义一个sequence $\alpha$ 被S包含就是指 S中某个sequence 是 $\alpha$ 的super sequence。此时就能引入支持度(support)，是指S中有多少个sequence 是 $\alpha$ 的super sequence。

在一边定义概念的时候，其实一边已经在把问题描述得很清楚了。
此时只要对支持度设置一个阈值(support threshold) $\varepsilon$ 。
那么序列模式挖掘问题就是在一个sequence database S 中找出所有支持度满足 $\ge \varepsilon$ 的subsequences 。并且叫这些subsequences 为序列模式（频繁序列模式(frequent)sequential pattern）。同时，可以像对sequence设置长度的概念一样对这些sequential pattern设置长度以里面有多少个item（不是element）可以记为 l-pattern。

小结：
理解概念：
a set of sequences
sequence
a list of elements
element
a set of items
set/list order problem
item
l-sequence
subsequence (super sequence)
sequence database
support
support threshold
(frequent) sequential pattern
the problem of sequential patterns mining

那么引入主角PrefixSpan算法：

1：Sequence的表示。
在上面的时候就讲清楚了，element里面的item的顺序是不会影响结果的。所以就规定按照字典序排列（如果是其他数据类型就按照其他的规则排序）。
<a(bac)(ac)d(cf)> 变成 <a(abc)(ac)d(cf)>。

2：引入概念：前缀(prefix)、投影(projection)、后缀(postfix)。

前缀：

$\alpha = <e_1,e_2,...,e_n>$
$\beta = <e'_1,e'_2,...,e'_m> (m \le n)$
$\beta$ is called a prefix of $\alpha$ $iff$
(1) $e'_i = e_i (1 \le i \le m-1)$
(2) $e'_m \subseteq e_m$
(3)all items in $(e_m-e'_m)$ are alphabetically after those in $e'_m$

投影：

$\alpha = <e_1,e_2,...,e_n>$
$\beta = <e'_1,e'_2,...,e'_m> (m \le n)$
其中 $\beta$ 是 $\alpha$ 的子串。也就是 $\beta \sqsubseteq \alpha$ 。

一个 $\alpha$ 的子串 $\alpha'$ 叫 $\alpha$ 的投影 wrt prefix $\beta$ $iff$
（1） $\beta$ 是 $\alpha'$ 的前缀
（2）不存在 $\alpha'$ 的父串 $\alpha''（\alpha''!=\alpha'）$ 是 $\alpha$ 的子串的同时有前缀 $\beta$

理解什么是投影。
$\alpha$ = <a(abc)d(bc)e>
$\beta$ = <bd>
明显 $\beta$ 是 $\alpha$ 的子串。
构造 $\alpha'$ 是 $\alpha$ 的子串。并且以 $\beta$ 为前缀。
$\alpha'_1$ = <bd(b)>
$\alpha'_2$ = <bd(bc)>
$\alpha'_3$ = <bd(bc)e>
$\alpha'_4$ = <bdbe>
$\alpha'_5$ = <bdce>
...
要满足（2）。条件（2）相当于在上面的备选集中找出了 $\alpha'_3$
明显只有 $\alpha'_3$ 才可以。
可以发现的是投影其实就是以 $\beta$ 为前缀。并且尽可能保留 $\alpha$ 的元素。（从 $\alpha$ 中找有 $\beta$ 的前缀开始后面一直保留下来，这里有两个点，1：一旦找到前缀 $\beta$ 就 2：一直保留到最后，在上述例子中情况1没有体现，其实就是有可能 $\alpha$ 里面有两个地方能和 $\beta$ 子串匹配，那么我们找第一个匹配到的地方。）

后缀：

让 $\alpha'$ 是 $\alpha$ 的投影 wrt prefix $\beta$
$\alpha = <e_1,e_2,...,e_n>$
$\beta = <e_1,e_2,...,e_{m-1},e'_m>$
$\gamma = <e''_m,e_{m+1},...,e_n>$ 是 $\alpha$ 的后缀 wrt prefix $\beta$
表示为 $\gamma = \alpha/\beta$ .
其中 $e''_m = (e_m-e'_m)$
$\alpha = \beta \gamma$

特殊地，当 $\beta$ 不是 $\alpha$ 的子串的时候。投影和后缀都是空的。

举例子：
前缀：
<a> <aa> <a(abc)> 都是 <a(abc)(ac)d(cf)>的前缀。
但是<ab>,<a(bc)>就都不是。
<a(bc)> 不是的原因是不满足前缀的第三个条件。（所以前缀其实是很严格的从前往后数，可以有这样的感觉）

后缀：
<(abc)(ac)d(cf)>是自身的后缀 wrt prefix <a>
<(_bc)(ac)d(cf)>是<(abc)(ac)d(cf)>的后缀 wrt prefix <aa>
<(_c)(ac)d(cf)>是<(abc)(ac)d(cf)>的后缀 wrt prefix <ab>
由于这个第三条可以知道。prefix <ab>不用是原串的前缀。我们也照样能做投影。只需要是子串就行了。而prefixspan的prefix体现在其投影之上。（只是没有显现出来而已。）

其实前缀和后缀的自然连接是投影。也就是说我们之后对于一个原串，并不是说讲其拆分成前缀和后缀。而是说前缀只要是原串的子串，咱们找出投影，然后投影-前缀就是后缀了。（所以在论文上面原串，后缀，前缀关系用的符号是用 / 和乘也就是上面的 $\gamma = \alpha/\beta$ 和 $\alpha = \beta \gamma$ ，并不是单纯的自然连接）

同样和前面部分介绍问题一样，一旦概念清楚了，其实算法自然就出来了。
算法流程很简单：
假设有了sequence databse S 以及阈值 $\varepsilon$
S就用论文上面的。

Sequence_id	Sequence
10	<a(abc)(ac)d(cf)>
20	<(ad)c(bc)(ae)>
30	<(ef)(ab)(df)cb>
40	<eg(af)cbc>

1：
计算1-sequence pattern。其实就是扫一遍sequence database。统计每个item的支持度然后挑出来大于等于阈值的即可。可以找到的是<a>:4 , <b>:4 , <c>:4 , <d>:3 , <e>:3 和 <f>:3。那么在这一步我们就获得了1-sequence pattern了，一共有6个。

2:
考虑将之后的其他的sequence pattern解划分为分别以上述的6个为前缀。
（注意了，这个前缀指的是之后的sequence pattern的前缀，而不是原串的前缀，只要是原串的子串就行了，其实就算不是原串的子串，那么投影后的后缀就是一个空的而已。也就是上面说的特殊情况。）

（1）那些有前缀<a>的sequence pattern
（2）那些有前缀<b>的sequence pattern
（3）那些有前缀<c>的sequence pattern
。。。
明显这个操作是完备的，不会丢失答案的。

但是具体到sequence database S上又是什么样的呢？
其实一开始的前缀，投影，后缀就给出了部分答案。
其实就是分别根据前缀<a>或者<b>或者<c>。。。找出投影，拿出修改后的后缀。构成了一个projection database S'。
（深刻理解这一步！要深刻理解什么是前缀什么是投影什么是后缀，最好多写几个例子。最后后面会解释什么叫做修改后的后缀，以及为什么是这样的。）

具体例子：
处理两个序列：
<a(abc)d(bc)e> 和 <(ef)(ab)(df)cb>
我们在假设在上面的sequence database S中找到了1-sequential pattern <a>了。（其他就先不管了。）
用前缀<a>来做投影：
<a(abc)d(bc)e> 写成 <(a)(abc)(d)(bc)(e)> 。子串型匹配前缀。第一个(a)就有了。
所以投影就是 <(a)(abc)(d)(bc)(e)>，而后缀是<(abc)(d)(bc)(e)>。
并且修改后的后缀也还是<(abc)(d)(bc)(e)>。

<(ef)(ab)(df)cb> 写成 <(ef)(ab)(df)(c)(b)> 。子串型匹配前缀。直到匹配到第两个element(ab)才有前缀<a>。（注意我的描述，子串型匹配是怎么匹配的就不赘述了。我说的是匹配直到第二个。）
所以投影就是 <(ab)(df)cb>。而后缀是<(b)(df)cb>
而修改后的后缀为<(_b)(df)cb>。其中(b)是指这个element，是以我们投影的前缀最后一项来开始的，也就是说指代前缀的最后一个element中的item们。比如这里就是item a。

如果说对< a(abcdefg) > 做前缀为<a(bc)>的投影。那么修改后的后缀就是 <(defg)>。这里的是item b和c。

并且论文中有注释：

if $e''_m$ is not empty, the postfix is also denoted as < (_ items in $e''_m$ ) $e_{m+1},...,e_n$ >

为什么修改后的后缀是这样的呢？
因为这样的话，(ef)(ab)(df)cb 中 (ab)这样的就不会丢失统计了，而且(ab)和ab是不一样的。

（其实我个人认为还有更好理解的方法，先讲完论文的流程，再提我想出来的流程。）

3：
递归求解即可。
第一次找出1-sequence pattern。并且根据这个为前缀来划分sequence pattern。其实就是做投影，取修改后的后缀。在新的sequence database上面找 2-sequence pattern的。

这个时候要分两类，一类是 (前缀的最后一个element的items +item）为一个element。一类是（前缀的最后一个element的items）（item）不为一个element。因为找（length+1） - sequential pattern 其实就是找这两类，并且这样是完备的（以是不是同一个element来划分）。

注意这里的查找并不是看起来那么简单的。
第一类：前缀的最后一个element的items 和item在同一个element下面。
我们在修改后的后缀中，比如前缀是<a> 。有一个修改后的后缀是<(_bc)(abc)(ab)>

明确我们的目的：
我们的目的是在原串上<(abc)(af)(ab)>中找到长度为2，并且前缀是<a>这样的模式串，可能会有的模式串，应该是<ab><(ab)><ac><(ac)><af><(af)>。这里因为是第一类，所以我们找的是(ab) (ac) (af)。并且根据我们的问题，明显这三个都是。而且都是前缀以<a>开头的模式串。

回到上面来，我们已经有了前缀是<a> 以及 < (_bc)(abc)(ab)>。
所以我们要在修改后的后缀中并且配合前缀<a>找出上面说的（ab）、(ac)、(af) 这三个模式串。（在别的地方是找不到了的。）
所以要对每一个element做前缀（严谨一点，应该是前缀的最后一个element）子串匹配。
第一个element是特殊的。（_bc）。只要数一数。有_b 有_c 加入前缀也就是 (ab)、(ac)。
第二个element（abc）。做前缀最后一个element(这里就一个a)做子串匹配。(ab)、（ac）。
第三个element (ab)。就不用说了。

上面的例子不是很刺激，下面来一个刺激一点的。
一个序列是 <a(ab)cd(aefh)(ag)z(aegyz)(abeg)>
前缀是<acae>
咱们找投影<aca(egyz)(abeg)> 注意了投影<ac(aefh)(ag)z(aegyz)(abeg)>的前缀不是<acae>。
获得的修改后的后缀是<(_gyz)(abeg)>
对于第一个element (_gyz)。我们可以有 (_g)、 (_y)、 (_z)。
对于第二个element (abeg) 。子串匹配前缀中最后一个element的item 为e。所以（eg）。

前缀是<ac(ae)>
根据上面说的投影是<ac(aefh)(ag)z(aegyz)(abeg)>。
获得的修改后的后缀是<(_fh)(ag)z(aegyz)(abeg)>。
前缀最后一个element中的items是ae所以
对于第一个element(_fh)。我们可以有(_f)、（_h）。
对于第二个element(ag)。找不到e所以没有。
对于第三个element(z)。不行。
对于第四个element(aegyz)。有 (aeg) (aey) (aez)。
对于第五个element(abeg)。有(aeg)。（连这都是有的哦。子串匹配！）

以上正确性的保证：为啥前缀的最后一个element的items是这样的子串匹配呢？（而不是按照顺序严格匹配下来。又或者XX）
因为我们要找的是只要前缀 + 一个item 是原来串的子串就行了。

第二类：（前缀的最后一个element的items）（item）不为一个element。
这个其实很简单。
如果说修改后的后缀的第一个element 是_开头的。那么就不用管第一个element。
否则就直接对每个element枚举一个item。统计就好了

总之我觉得可以规约一下：
用函数编程的思想来解释：

先写一个函数，传入前缀。
在函数主体中按照上面的规则来查找。并且返回找到的item 和传入的前缀组合成新的前缀。并且返回这些前缀。
记这个函数为find

然后在外面写一个函数来递归就行了。

void func(前缀 A)

调用A = find（A）。获得新的一批sequential pattern 设置为前缀A。
如果A为空就返回。

计入答案中 ANS.add(A)。
递归调用 func(A)

写完函数。调用func({}).一开始前缀为空即可。

这样这个算法就基本上完事了。还有一些优化bi-level projection .pseudo-projection就晚点说。好了。

子串匹配。
字符串
a = "abcdefghijklmn"
b = "aln"
b的元素依次在a上出现了。并且匹配到a的最后一个n上。

a = "ababcdceg"
b = "abc"
b的元素依次在a上出现了。并且最早匹配，匹配完的是a串中的第一个c的位置。
这个就是子串匹配。

需要理解的概念：
前缀（prefix)
投影（projection）
后缀（postfix）
前缀和后缀和原串的关系。
前缀和后缀和投影的关系。
前缀的最后一个element的items。
修改后的后缀。
如何在修改后的后缀中找两类情况。

序列模式挖掘---PrefixSpan

序列模式挖掘问题：

基础概念：

（说白了，就是能在上从前往后找依次找出对应的每个element的超集）

那么引入主角PrefixSpan算法：

前缀：

投影：

后缀：

推荐阅读更多精彩内容

（说白了，就是能在 $\beta$ 上从前往后找依次找出 $\alpha$ 对应的每个element的超集）