数据挖掘进阶之关联规则挖掘FP-Growth算法与序列模式挖掘GSP算法

近期在写论文方面涉及到了数据挖掘，需要通过数据挖掘方法实现软件与用户间交互模式的获取、分析与分类研究。主要涉及到关联规则与序列模式挖掘两块。关联规则挖掘使用基于有趣性度量标准的FP-Growth算法，序列模式挖掘使用基于有趣性度量标准的GSP算法。若想实现以上优化算法，首先必须了解其基本算法，并编程实现。关键点还是在于理解算法思想，只有懂得了算法思想，对其进行优化操作易如反掌。源代码方面，其实是自己从网络中查找并进行阅读，在理解的基础上进行优化。下面首先介绍一下基本的FP-Growth算法的实现过程:

原理介绍
基本思路：不断地迭代FP-tree的构造和投影过程。

对于每个频繁项，构造它的条件投影数据库和投影FP-tree。对每个新构建的FP-tree重复这个过程，直到构造的新FP-tree为空，或者只包含一条路径。当构造的FP-tree为空时，其前缀即为频繁模式；当只包含一条路径时，通过枚举所有可能组合并与此树的前缀连接即可得到频繁模式。

算法实现
本算法采用Java实现，主要根据序列模式的情况，算法共有2个类：

MyFptree类：算法核心类。FP-Growth算法的核心操作：建树和挖掘频繁项操作都在这里实现。在使用该算法时，也是需要通过使用该类的方法来实现GSP算法。

TreeNode2类：元素类。在本算法实现中，元素类中含有元素属性集，在使用时也是使用该属性。另外，在该类中还封装了对元素的操作以及一些其他操作。

继续数据挖掘方面算法的讲解，前面讲解了数据挖掘中关联规则算法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算法的方法测试。