数据挖掘进阶之序列模式挖掘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个对象:个类:
GSP类:算法核心类,GSP算法的核心操作:连接和剪枝操作都在这里实现。在使用该算法时,也是需要通过使用该类的方法来实现GSP算法。
Sequence类:序列类,该类封装了序列的基本信息和基本操作,实现了对序列间的比较以及序列中的项目集操作。
Element类:元素类,在序列模式中元素也就是项目集,项目集中包含了项目。在本算法实现中,元素类中含有一个项目集属性,用于表示项目集,在使用时也是使用该属性来表示项目集,另外,在该类中还封装了对项目的操作以及一些其他操作。
SeqDB类:该类用于从数据库中扫描获取序列,本算法主要用于模拟实现,所以在程序中已经初始化了序列。
GSPTest类:测试类,使用JUnit对算法进行单元测试,本文附的代码只含有对于实现GSP算法的方法测试。
具体源码请参考博文“序列模式分析算法GSP的实现”。