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

数据挖掘进阶之序列模式挖掘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的实现”。

上一篇:如何通过JavaFX应用程序将变量传递给控制器​​?


下一篇:从jar运行时无法加载javafx资源