频繁序列模式挖掘
1.频繁序列模式挖掘序列模式是频繁模式的一种特殊情况，它们的应用范围完全不一样！如：
上述购物清单是两个用户的购物清单，根据上面的清单，我们可以发现尿布和啤酒组合起来一起购买的情况较多，因此超市可以根据这样的频繁项集分析，将尿布和啤酒放在较近的地方，或者将尿布和啤酒同时促销等增加销量。 而序列模式如：
上述购物清单是两个用户不同时间前后两次的购物清单，可以发现高清机顶盒往往在某个用户购买电视机以后的某次购物中出现在下次的购物清单中，但往往很少出现机顶盒在购买电视机之前出现，这是因为电视机的购买历史带来了（促进了）机顶盒的销售，因此超市可以根据这样的频繁序列模式分析，将机顶盒推荐给购买了电视的用户，或者在电视热卖以后增加机顶盒的促销来增加销量。 很常见的是，我们可以用许多算法挖掘频繁模式如Apriori和FPGrowth等，而为了对含有时间顺序的数据集进行频繁模式的挖掘，就有了GSP和SPADE算法。 定义：序列模式挖掘，假定数据集D，有n个序列（Seq），每个Seq由多个事件（Event）组成，所有Event都是时间有序的。 若有一个Seq，它是数据集D的部分序列的子序列，那么它的支持度的计算方式为： support(s) = s在n个序列中出现的次数 如果spport(s)>min_support，则我们可以把它称为频繁序列，或者序列模式。下面是两个常用的挖掘算法：
| |||||||||||||||||||||
| SID | EID | 项 | |||||||||||||||||||
| 1 | 1 | I1，I2 | |||||||||||||||||||
| 1 | 2 | I3 | |||||||||||||||||||
| 1 | 3 | I4 |
| SID | EID | 项 |
| 3 | 1 | I2 |
| 3 | 2 | I4 |
我们首先得到的候选序列为（接下来的表述中，尖括号<>表示里面的项有序，而圆括号()表示里面的项是出现在一个event中）：
<I1>,<I2>,<I3>,<I4>
可以得到它们的支持度分别为：
<I1>:1
<I2>:3
<I3>:2
<I4>:2
进行剪枝，可以得到的序列模式为：
然后再用前一步得到的序列模式，进行自连接，我们可以得到候选序列：
<I2,I2>:0
<I3,I2>:0
<I4,I4>:0
(I2,I3):0
(I3,I4):0
进行剪枝，得到的序列模式为：
由于<I2,I3>去掉第一项得到<I3>，与<I2,I4>去掉最后一项得到<I2>，序列并不相同。所以它们是不能进行连接的，此时算法终止。最终得到的序列模式即为：
即如果用户购买了I2，则很有可能再购买I3;如果用户购买了I2，则很有可能再购买I4。
GSP算法很直白，但是也有缺点，就是每次计算序列的支持度时，都需要全表扫描数据集D。我们简单估计一下，假设数据集D的里面含有m个不同的项。假设第一步得到的单个序列候选集无需进行剪枝，那么由那个单个序列集合再进行自连接时，得到的序列个数为：m*m+m(m-1)/2个。（m*m个为有序的序列，m(m-1)/2为同时出现在某一个event的序列个数），那么此时需要进行的数据集D的扫描次数=（m*m+m(m-1)/2）*数据集D的记录数。一次候选集剪枝的全数据集D的扫描次数都非常之大。
针对上面的问题，就有了SPADE算法的提出。
3.SPADE算法
SPADE算法在GSP算法的基础上，提出了ID_LIST的概念，来规避多次对数据集D进行全表扫描的问题。ID_LIST是一个（SID，EID）组成的集合。
我们用上面一个例子来推导一下，了解SPADE算法是如何做的。
第一轮的候选序列<I1>,<I4>，我们得到它们的ID_LIST：
I1
| SID | EID |
| 1 | 1 |
I2
| SID | EID |
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
I3
I4
这样我们可以很快的知道它们的支持度：
<I4>:2
然后，我们再根据序列模式自连接得到本轮的候选集，以及候选集对应的ID_LIST（此时的ID_LIST可以由上一轮的ID_LIST得到），因为候选集包括：
针对其中的<I2,I3>的ID_LIST进行举例子：
I2的ID_LIST含有3项（1,1），（2,1），（3,1）；
而I3的ID_LIST有2项（1,2），（2,2）；
那么我们可以知道，序列号相同，且I3在I2之后出现的有两项：
（1,1）（1,2）
（2.1）（2,51); font-family:Arial; font-size:13.63636302948px; line-height:26px">即可以得到<I2,I3>的ID_LIST：
同理得到<l2,l4>的ID_LIST：
| SID | EID | EID |
| 1 | 1 | 3 |
| 3 | 1 | 2 |
所以，可以得到<I2,I3>的支持度为2。同样的第二轮会进行剪枝，得到序列模式：
由于<I2,I4>去掉最后一项得到<I2>，序列并不相同。所以它们是不能进行连接的，此时算法终止。最终得到的序列模式即为：
（补充：如果能够连起来，则按照二的方法，假设<l2,l3>,<l3,l4>相连，则计算SID相同，且<l2,l3>中l3与<l3,l4>中l3的SID和EID同时相同的次数作为support）
（再补充：如果进入下一轮，即存在<l2,l3,l4>和<l3,l4,l5>序列，则连接的时候，第一个去掉头元素，第二个去掉尾元素，计算<l2,l3,l4>和<l3,l4,l5>中，l3和l4的SID和EID分别同时相同的次数作为support）
其实可以看到，SPADE与GSP算法大体相同，只不过由于它多了一个ID_LIST记录，使得每一次的ID_LIST根据上一次的ID_LIST得到（从而得到支持度），而ID_LIST的规模是随着剪枝的不断进行，而规模逐渐缩小的。所以也就解决了GSP算法多次扫描数据集D问题。
但是，最后提醒大家用户一句话！这个算法的实现虽然并不复杂，但是考虑到要处理的数据量的时候就需要非常小心谨慎，因为算法过程会产生大量的中间候选结果，不管是计算量上还是从空间存储效率上都会存在很大的挑战，并且从序列模式的应用上来说，如果不是需要严格按照顺序得到频繁规则，个人建议使用关联规则挖掘，其中FPG算法是一个不错的选择！
（参考：http://blog.csdn.net/rongyongfeikai2/article/details/40478335）
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!