|
前言 前面讲到频繁项集挖掘的关联算法Apriori（机器学习(22)之Apriori算法原理总结）和FP Tree（机器学习(31)之频繁集挖掘FP Tree详解），这两个算法都是挖掘频繁项集的。而今天要介绍的PrefixSpan（PrefixSpan算法的全称是Prefix-Projected Pattern Growth，即前缀投影的模式挖掘）算法也是关联算法，但是它是挖掘频繁序列模式的，因此要解决的问题目标稍有不同。 项集数据和序列数据 首先看看项集数据和序列数据有什么不同，如下图所示。  左边的数据集就是项集数据，在Apriori和FP Tree算法中已经看到过，每个项集数据由若干项组成，这些项没有时间上的先后关系。而右边的序列数据则不一样，它是由若干数据项集组成的序列。比如第一个序列 子序列和频繁序列 子序列和数学上的子集的概念很类似，也就是说，如果某个序列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=  PrefixSpan算法思想 PrefixSpan算法的目标是挖掘出满足最小支持度的频繁序列。那么怎么去挖掘出所有满足要求的频繁序列呢？回忆Aprior算法（机器学习(22)之Apriori算法原理总结），它是从频繁1项集出发，一步步的挖掘2项集，直到最大的K项集。PrefixSpan算法也类似，它从长度为1的前缀开始挖掘序列模式，搜索对应的投影数据库得到长度为1的前缀对应的频繁序列，然后递归的挖掘长度为2的前缀所对应的频繁序列，。。。以此类推，一直递归到不能挖掘到更长的前缀挖掘为止。 比如对应于上面的例子，支持度阈值为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项频繁序列为  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算法。 不过scikit-learn始终不太重视关联算法，一直都不包括这一块的算法集成，这就有点落伍了。 欢迎分享给他人让更多的人受益  参考：
|
|
|
