数据挖掘进阶之序列模式挖掘GSP算法

绪

继续数据挖掘方面算法的讲解，前面讲解了数据挖掘中关联规则算法FP-Growth的实现。此篇博文主要讲解基于有趣性度量标准的GSP序列模式挖掘算法。有关论文后期进行补充。实现思路与前面优化的FP-Growth算法一致，首先实现简单的GSP算法，通过认真阅读源码，在理解的基础之上进行优化。优化后的算法将在性能方面与原算法进行对比，以此突出此算法的优良性能。下面进行简要介绍:

原理介绍

GSP算法是一种非常有效的序列模式挖掘算法，该算法使用一种称作为逐层搜索的迭代方法，首先找出频繁1-序列模式的集合F1，F1用于寻找频繁2-序列模式F2，F2用于寻找频繁3-序列模式、F3...，如此下去，直到不能找到频繁序列模式为止。

???F1?=?the?set?of?frequent?1-sequence

???k=2,

???do?while?F(k-1)!=?Null;

???????Generate?candidate?sets?Ck?(set?of?candidate?k-sequences);

???????????For?all?input?sequences?s?in?the?database?D

???????????????do

???????????Increment?count?of?all?a?in?Ck?if?s?supports?a

???????????Fk?=?{a?∈?Ck?such?that?its?frequency?exceeds?the?threshold}

???????????????k=?k+1;

???????????Result?=?Set?of?all?frequent?sequences?is?the?union?of?all?Fks

???????????????End?do

???End?do

GSP需要多次扫描序列数据库，在第一次扫描中，对所有的单个项目(1—序列模式)进行计数。利用频繁1—序列模式生成候选频繁2—序列模式，进行第二次扫描并求候选频繁2—序列模式的支持数。使用频繁2—序列模式生成候选频繁3—序列模式，重复以上过程，直到找出所有的频繁序列模式。

?算法实现

本算法采用Java实现，主要根据序列模式的情况，序列模式挖掘中共涉及到3个对象：序列、元素和项目。算法共有5个类：

GSP类：算法核心类，GSP算法的核心操作：连接和剪枝操作都在这里实现。在使用该算法时，也是需要通过使用该类的方法来实现GSP算法。

Sequence类：序列类，该类封装了序列的基本信息和基本操作，实现了对序列间的比较以及序列中的项目集操作。

Element类：元素类，在序列模式中元素也就是项目集，项目集中包含了项目。在本算法实现中，元素类中含有一个项目集属性，用于表示项目集，在使用时也是使用该属性来表示项目集，另外，在该类中还封装了对项目的操作以及一些其他操作。

SeqDB类：该类用于从数据库中扫描获取序列，本算法主要用于模拟实现，所以在程序中已经初始化了序列。

GSPTest类：测试类，使用JUnit对算法进行单元测试，本文附的代码只含有对于实现GSP算法的方法测试。

具体源码请参考博文“序列模式分析算法GSP的实现”。