PrefixSpan算法原理总结
参考：http://www.cnblogs.com/pinard/p/6323182.html
基本概念
项集数据和序列数据：
左边的数据集就是项集数据，每个项集数据由若干项组成，这些项没有时间上的先后关系。而右边的序列数据则不一样，它是由若干数据项集组成的序列。比如第一个序列<a(abc)(ac)d(cf)>,它由a,abc,ac,d,cf共5个项集数据组成，并且这些项有时间上的先后关系。对于多于一个项的项集我们要加上括号，以便和其他的项集分开。同时由于项集内部是不区分先后顺序的，为了方便数据处理，我们一般将序列数据内所有的项集内部按字母顺序排序。
子序列与频繁序列：
了解了序列数据的概念，我们再来看看上面是子序列。子序列和我们数学上的子集的概念很类似，也就是说，如果某个序列A所有的项集在序列B中的项集都可以找到，则A就是B的子序列。当然，如果用严格的数学描述，子序列是这样的： 对于序列A={a1,a2,…ana1,a2,…an}和序列B={b1,b2,…bmb1,b2,…bm},n≤mn≤m，如果存在数字序列1≤j1≤j2≤…≤jn≤m1≤j1≤j2≤…≤jn≤m, 满足a1⊆bj1,a2⊆bj2…an⊆bjn，则称A是B的子序列。当然反过来说， B就是A的超序列。 而频繁序列则和我们的频繁项集很类似，也就是频繁出现的子序列。比如对于下图，支持度阈值定义为50%，也就是需要出现两次的子序列才是频繁序列。而子序列<(ab)c>是频繁序列，因为它是图中的第一条数据和第三条序列数据的子序列，对应的位置用蓝色标示: 
前缀与前缀投影：
在PrefixSpan算法中的前缀prefix通俗意义讲就是序列数据前面部分的子序列。比如对于序列数据B=<a(abc)(ac)d(cf)>，A=<a(abc)a>,则A是B的前缀。当然B的前缀不止一个，比如, 
算法流程
PrefixSpan算法类似Aprior，它从长度为1的前缀开始挖掘序列模式，搜索对应的投影数据库得到长度为1的前缀对应的频繁序列，然后递归的挖掘长度为2的前缀所对应的频繁序列，以此类推，一直递归到不能挖掘到更长的前缀挖掘为止。流程如下： 1）找出所有长度为1的前缀和对应的投影数据库 2）对长度为1的前缀进行计数，将支持度低于阈值αα的前缀对应的项从数据集S删除，同时得到所有的频繁1项序列，i=1. 3）对于每个长度为i满足支持度要求的前缀进行递归挖掘：
- 找出前缀所对应的投影数据库。如果投影数据库为空，则递归返回。
- 统计对应投影数据库中各项的支持度计数。如果所有项的支持度计数都低于阈值αα，则递归返回。
- 将满足支持度计数的各个单项和当前的前缀进行合并，得到若干新的前缀。
- 令i=i+1，前缀为合并单项后的各个前缀，分别递归执行第3步。
实例：
设支持度阈值为50%。下图长度为1的前缀包括, , 
现在我们开始挖掘频繁序列,分别从长度为1的前缀开始。这里我们以d为例子来递归挖掘，其他的节点递归挖掘方法和Ｄ一样。方法如下图，首先我们对ｄ的后缀进行计数，得到{a:1, b:2, c:3, d:0, e:1, f:1，_f:1}。注意f和_f是不一样的，因为前者是在和前缀d不同的项集，而后者是和前缀d同项集。由于此时a,d,e,f,_f都达不到支持度阈值，因此我们递归得到的前缀为d的2项频繁序列为