序列模式分析算法GSP的实现

GSP是序列模式挖掘的一种算法。其主要描述如下：



l 根据长度为i 的种子集Li 通过连接操作和剪切操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持数，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集。







l 重复第二步，直到没有新的序列模式或新的候选序列模式产生为止。







l 扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集



L1Þ C2 Þ L2 Þ C3 Þ L3 Þ C4 Þ L4 Þ ……



产生候选序列模式主要分两步



l 连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1于s2进行连接，即将s2的最后一个项目添加到s1中。



l 剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除。



候选序列模式的支持度计算：对于给定的候选序列模式集合C，扫描序列数据库，对于其中的每一条序列d,找出集合C中被d所包含的所有候选序列模式，并增加其支持度计数。