算法简介 算法简介 算法简介算法简介 序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的 元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小 支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中 的出现频率不低于用户指定的最小支持度阈值。 GSP 是序列模式挖掘的一种算法。其主要描述如下：  根据长度为 i 的种子集 Li 通过连接操作和剪 切操作生成长度为 i+1 的候选序列模式 Ci+1； 然后扫描序列数据库，计算每个候选序列模式 的支持数，产生长度为 i+1 的序列模式 Li+1， 并将 Li+1 作为新的种子集。  重复第二步，直到没有新的序列模式或新的 候选序列模式产生为止。  扫描序列数据库，得到长度为 1 的序列模式 L1，作为初始的种子集 L1⇒ C2 ⇒ L2 ⇒ C3 ⇒ L3 ⇒ C4 ⇒ L4 ⇒ …… 产生候选序列模式主要分两步 候选序列模式的支持度计算：对于给定的候选序列模式集合 C，扫描序列数 据库，对于其中的每一条序列 d,找出集合 C 中被 d 所包含的所有候选序列模式， 并增加其支持度计数。 列模式，将它从候选序列模式中删除。 不是序列模式，则此候选序列模式不可能是序  剪切阶段：若某候选序列模式的某个子序列 目与去掉序列模式 s2 的最后一个项目所得到 的序列相同，则可以将 s1 于 s2 进行连接，即 将 s2 的最后一个项目添加到 s1 中。  连接阶段：如果去掉序列模式 s1 的第一个项 二二二二、、、、 算法的设计和实现 本算法采用 Java 实现，主要根据序列模式的情况， 序列模式挖掘中共涉及到这样个 3 对象，序列、元 素和项目，这样算法共有 5 个类： GSP 类：算法核心类，GSP 算法的核心操作：连 接和剪枝操作都在这里实现，在使用该算法时，也 是需要通过使用该类的方法来实现 GSP 算法。 Sequence 类：序列类，该类封装了序列的基本信息 算法的设计和实现 算法的设计和实现 算法的设计和实现 和基本操作，实现了对序列间的比较以及序列中的 项目集操作。 Element 类：元素类，在序列模式中元素也就是项 目集，项目集中包含了项目，在本算法实现中，元 素类中含有一个项目集属性，用于表示项目集，在 使用时也是使用该属性来表示项目集，另外，在该 类中还封装了对项目的操作以及一些其他操作。 

SeqDB 类：该类用于从数据库中扫描获取序列， 本算法主要用于模拟实现，所以在程序中已经初始 化了序列。 GSPTest 类：测试类，使用 JUnit 对算法进行单元 测试，本文附的代码只含有对于实现 GSP 算法的 方法测试。 由于程序中附带了对方法的注释，这里对各个方法 的原理和实现就不作介绍。 三三三三、、、、 实验结果 实验结果 实验结果实验结果 <{1 5}{2}{3}{4}> <{1}{3}{4}{3 5}> <{1}{2}{3}{4}> <{1}{3}{5}> <{4}{5}> （（（（一一一一））））实验数据实验数据实验数据实验数据 （（（（二二二二））））程序输出程序输出程序输出程序输出 2 L(1) 最小支持度计数为： 输入的序列集合为： 序列模式 为： 剪枝前候选集的大小为： 剪枝后候选集的大小为： 序列模式 为： 剪枝前候选集的大小为： 剪枝后候选集的大小为： 序列模式 为： 5>, <3 5>] <1 3 5>] 为： 为： 为： 为： 候选集 候选集 候选集 候选集 [<(1,5) 2 3 4>, <1 3 4 (3,5)>, <1 2 3 4>, <1 3 5>, <4 (4,5)>] ................................................. [<2>, <4>, <1>, <3>, <5>] 40 c [<(2,2)>, <2 2>, <(2,4)>, <2 4>, <4 2>, <(1,2)>, <2 1>, <1 2>, <(2,3)>, <2 3>, <3 2>, <(2,5)>, <2 5>, <5 2>, <(4,4)>, <4 4>, <(1,4)>, <4 1>, <1 4>, <(3,4)>, <4 3>, <3 4>, <(4,5)>, <4 5>, <5 4>, <(1,1)>, <1 1>, <(1,3)>, <1 3>, <3 1>, <(1,5)>, <1 5>, <5 1>, <(3,3)>, <3 3>, <(3,5)>, <3 5>, <5 3>, <(5,5)>, <5 5>] 40 c [<(2,2)>, <2 2>, <(2,4)>, <2 4>, <4 2>, <(1,2)>, <2 1>, <1 2>, <(2,3)>, <2 3>, <3 2>, <(2,5)>, <2 5>, <5 2>, <(4,4)>, <4 4>, <(1,4)>, <4 1>, <1 4>, <(3,4)>, <4 3>, <3 4>, <(4,5)>, <4 5>, <5 4>, <(1,1)>, <1 1>, <(1,3)>, <1 3>, <3 1>, <(1,5)>, <1 5>, <5 1>, <(3,3)>, <3 3>, <(3,5)>, <3 5>, <5 3>, <(5,5)>, <5 5>] L(2) [<2 4>, <1 2>, <2 3>, <1 4>, <3 4>, <4 5>, <1 3>, <1 ................................................. 18 c [<1 (2,4)>, <1 2 4>, <2 (4,5)>, <2 4 5>, <1 (2,3)>, <1 2 3>, <2 (3,4)>, <2 3 4>, <2 (3,5)>, <2 3 5>, <1 (4,5)>, <1 4 5>, <3 (4,5)>, <3 4 5>, <1 (3,4)>, <1 3 4>, <1 (3,5)>, 7 c [<1 2 4>, <1 2 3>, <2 3 4>, <1 4 5>, <3 4 5>, <1 3 4>, <1 3 5>] L(3) [<1 2 4>, <1 2 3>, <2 3 4>, <1 3 4>, <1 3 5>] 

................................................. 2 1 c c [<1 2 (3,4)>, <1 2 3 4>] [<1 2 3 4>] ................................................. [<1 2 3 4>] 候选集 候选集 为： 为： package gsp; ! 60 L(4) 剪枝前候选集的大小为： 剪枝后候选集的大小为： 为： 序列模式 计算花费时间 毫秒 四四四四、、、、程序源代码 程序源代码 程序源代码 程序源代码 （（（（一一一一））））GSP 类类类类 import java.util.ArrayList; import java.util.Map; import java.util.HashMap; /** * * 本类为核心类，在本类中实现了 GSP 算法 * @author guangqingzhong * 列模式 选序列模式 */ public class GSP { private ArrayList c; //长度为 i 的候 private ArrayList l; //长度为 i 的序 private ArrayList result; private SeqDB db; private int support; /** * 构造方法 * 在实例化 GSP 对象时，同时赋值支持度 * 并获取序列集和初始化序列模式结果 * @param support 支持度 */ public GSP(int support) { this.support = support; //赋值支持度 this.db = new SeqDB(); //从 SeqDB 类中获取设置好的序列集