分析：PrefixSpan算法
首先看看项集数据和序列数据有什么不一样，以下图所示。算法
左边的数据集就是项集数据，在Apriori和FP Tree算法中已经看到过，每一个项集数据由若干项组成，这些项没有时间上的前后关系。而右边的序列数据则不同，它是由若干数据项集组成的序列。好比第一个序列<a(abc)(ac)d(cf)>,它由a,abc,ac,d,cf共5个项集数据组成，而且这些项有时间上的前后关系。对于多于一个项的项集要加上括号，以便和其余的项集分开。同时因为项集内部是不区分前后顺序的，为了方便数据处理，通常将序列数据内全部的项集内部按字母顺序排序。数据库
子序列和频繁序列api
子序列和数学上的子集的概念很相似，也就是说，若是某个序列A全部的项集在序列B中的项集均可以找到，则A就是B的子序列。固然，若是用严格的数学描述，子序列是这样的：机器学习
对于序列A={a1,a2,...an}和序列B={b1,b2,...bm},n≤m，若是存在数字序列1≤j1≤j2≤...≤jn≤m, 知足a1⊆bj1,a2⊆bj2...an⊆bjn，则称A是B的子序列。固然反过来讲， B就是A的超序列。分布式
而频繁序列则与频繁项集很相似，也就是频繁出现的子序列。好比对于下图，支持度阈值定义为50%，也就是须要出现两次的子序列才是频繁序列。而子序列<(ab)c>是频繁序列，由于它是图中的第一条数据和第三条序列数据的子序列，对应的位置用蓝色标示。学习
PrefixSpan的一些基本概念大数据
PrefixSpan算法的全称是Prefix-Projected Pattern Growth，即前缀投影的模式挖掘，里面有前缀和投影两个词。那么首先看看什么是PrefixSpan算法中的前缀prefix。优化
在PrefixSpan中的前缀prefix通俗意义讲就是序列数据前面部分的子序列。若是用严格的数学描述，前缀是这样的：对于序列A={a1,a2,...an}和序列B={b1,b2,...bm},n≤m，知足a1=b1,a2=b2...an−1=bn−1,而an⊆bn，则称A是B的前缀。好比对于序列数据B=<a(abc)(ac)d(cf)>，而A=<a(abc)a>,则A是B的前缀。固然B的前缀不止一个，好比<a>, <aa>, <a(ab)> 也都是B的前缀。ui
接下来再看看前缀投影，其实前缀投影就是这儿的后缀，前缀加上后缀就能够构成一个咱们的序列。下面给出前缀和后缀的例子。对于某一个前缀，序列里前缀后面剩下的子序列即为咱们的后缀。若是前缀最后的项是项集的一部分，则用一个“_”来占位表示。spa
下面这个例子展现了序列<a(abc)(ac)d(cf)>的一些前缀和后缀，仍是比较直观的。要注意的是，若是前缀的末尾不是一个彻底的项集，则须要加一个占位符。在PrefixSpan算法中，相同前缀对应的全部后缀的结合称为前缀对应的投影数据库。
PrefixSpan算法思想
PrefixSpan算法的目标是挖掘出知足最小支持度的频繁序列。那么怎么去挖掘出全部知足要求的频繁序列呢？回忆Aprior算法（机器学习(22)之Apriori算法原理总结），它是从频繁1项集出发，一步步的挖掘2项集，直到最大的K项集。PrefixSpan算法也相似，它从长度为1的前缀开始挖掘序列模式，搜索对应的投影数据库获得长度为1的前缀对应的频繁序列，而后递归的挖掘长度为2的前缀所对应的频繁序列，。。。以此类推，一直递归到不能挖掘到更长的前缀挖掘为止。
好比对应于上面的例子，支持度阈值为50%。里面长度为1的前缀包括<a>, <b>, <c>, <d>, <e>, <f>,<g>，须要对这6个前缀分别递归搜索找各个前缀对应的频繁序列。以下图所示，每一个前缀对应的后缀也标出来了。因为g只在序列4出现，支持度计数只有1，所以没法继续挖掘。咱们的长度为1的频繁序列为<a>, <b>, <c>, <d>, <e>，<f>。去除全部序列中的g，即第4条记录变成<e(af)cbc>。
如今开始挖掘频繁序列,分别从长度为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项频繁序列为<db>和<dc>。接着分别递归db和dc为前缀所对应的投影序列。首先看db前缀，此时对应的投影后缀只有<_c(ae)>,此时_c,a,e支持度均达不到阈值，所以没法找到以db为前缀的频繁序列。如今来递归另一个前缀dc。以dc为前缀的投影序列为<_f>, <(bc)(ae)>, <b>，此时进行支持度计数，结果为{b:2, a:1, c:1, e:1, _f:1}，只有b知足支持度阈值，所以获得前缀为dc的三项频繁序列为<dcb>。继续递归以<dcb>为前缀的频繁序列。因为前缀<dcb>对应的投影序列<(_c)ae>支持度所有不达标，所以不能产生4项频繁序列。至此以d为前缀的频繁序列挖掘结束，产生的频繁序列为<d><db><dc><dcb>。一样的方法能够获得其余以<a>, <b>, <c>, <e>, <f>为前缀的频繁序列。
PrefixSpan算法流程
下面对PrefixSpan算法的流程作一个概括总结。
输入：序列数据集S和支持度阈值α
输出：全部知足支持度要求的频繁序列集
1）找出全部长度为1的前缀和对应的投影数据库
2）对长度为1的前缀进行计数，将支持度低于阈值α的前缀对应的项从数据集S删除，同时获得全部的频繁1项序列，i=1.
3）对于每一个长度为i知足支持度要求的前缀进行递归挖掘：
a) 找出前缀所对应的投影数据库。若是投影数据库为空，则递归返回。
b) 统计对应投影数据库中各项的支持度计数。若是全部项的支持度计数都低于阈值α，则递归返回。
c)将知足支持度计数的各个单项和当前的前缀进行合并，获得若干新的前缀。
d) 令i=i+1，前缀为合并单项后的各个前缀，分别递归执行第3步。
PrefixS算法总结
PrefixSpan算法因为不用产生候选序列，且投影数据库缩小的很快，内存消耗比较稳定，做频繁序列模式挖掘的时候效果很高。比起其余的序列挖掘算法好比GSP,FreeSpan有较大优点，所以是在生产环境经常使用的算法。
PrefixSpan运行时最大的消耗在递归的构造投影数据库。若是序列数据集较大，项数种类较多时，算法运行速度会有明显降低。所以有一些PrefixSpan的改进版算法都是在优化构造投影数据库这一块。好比使用伪投影计数。固然使用大数据平台的分布式计算能力也是加快PrefixSpan运行速度一个好办法。好比Spark的MLlib就内置了PrefixSpan算法。
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------