GSP（Generalized Sequential Pattern Mining）算法

Generalized Sequential Pattern (GSP) Mining

数据预处理

根据Id将item 根据时间排序 得到如下的序列，一个项集里面如果有多个项，说明这个项集里面项s是属于同一个时间点的，内部不分先后顺序，一般按照字典序排列。

GSP算法

找出频繁一项集

找出所有满足支持度的频繁一项集，支持度的计算是按照用户粒度的，比如一个用户ID下A出现了三次，那么A的计数只会加1

找出所有长度为2的sequence

长度为2表示包含两个item,这就要分成两种情况：

这两个item在不同的项集中，比如<A,B>这两个item在相同的项集中，比如<(A,B)>

找<A,B>

对于所有满足条件的频繁一项集进行组合，得到如下表

找<(A,B)>

同样的方法，但是因为不区分顺序也并且同一时刻出现两个相同的item只记作一次，所以我们可以得到一个不包括对角线的上三角矩阵 这样就有6*6 + 15 = 51个候选2-sequence,对于每一个2-sequence，遍历sequence 数据库，计算其支持度，并且筛选出所有满足条件的2-sequence. 从原数据中进行匹配] 计算支持度 得到所有满足最小支持度的2-sequence， 这个表在后面有用处

由2-sequence 找3-sequence

定义：

-1st,表示sequence去掉第一个元素之后的序列-Last表示sequence去掉最后一个元素之后的序列

注意：如果fist 或者last元素是个多项集，那么就要枚举所有的可能性。

对所有的2-sequence 进行-1st 和 -Last操作得到下面的表

join操作

如果sequence X进行-1st操作后得到a(X-a=x),sequence Y进行-Last操作后得到y(y+z=Y)，并且x==y, 那么我们可以对X, Y进行join操作得axz。

这里有个小trick就是，如果az没有出现在之前提到的2-sequence表里，那么我们join之后就不用进行支持度的统计，因为az不满足最小值度，那么它的超集也肯定不满足。 这样我们就能得到所有满足条件的3-sequence 同理可以由3-seq到4-seq

按照这样的方法直到找不到满足条件的sequence,这样我们就能找出所有满足支持度的序列

限制条件

可以在挖掘中加上一定的限制条件，使得挖掘出的结果更符合业务场景

Window Size:限制序列的时间跨度，比如要挖掘一个孕妇怀孕期间的购物pattern,那么时间跨度肯定要限制在10个月之内Max-gap：如果两个相邻事件的事件间隔过大，那么我们可以不认为他们属于同一个patternMin-Gap: 如果相邻两个事件之间的时间间隔过小，那么可以认为他们呢属于同一个项集合，比如<A,B>如果A,B间的时间小于某个阈值，那么可以将<A,B>变为<(A,B)>

参考资料

https://simpledatamining.blogspot.com/2015/03/generalized-sequential-pattern-gsp.html?showComment=1563432640616#c5070656676430360295 The best article about GSP