一、 算法简介
序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的元素
按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持
度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出
现频率不低于用户指定的最小支持度阈值。
产生候选序列模式主要分两步
连接阶段：如果去掉序列模式 s1 的第一个项目与去掉序列模式 s2 的最后
一个项目所得到的序列相同，则可以将 s1 于 s2 进行连接，即将 s2 的最后一个
项目添加到 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
输入的序列集合为：
[<(1,5) 2 3 4>, <1 3 4 (3,5)>, <1 2 3 4>, <1 3 5>, <4 (4,5)>]
序列模式 L(1) 为：[<2>, <4>, <1>, <3>, <5>]
评论1