GSP算法在数据挖掘中的应用

一：基本概念介绍

序列模式挖掘：指挖掘相对时间或其他模式出现频率高的模式

序列模式挖掘的动机：大型连锁超市的交易数据有一系列的用户事物数据库。每一条记录包括用户的ID，事物发生的时间和事物涉及的项目。如果能够在其中挖掘涉及事物间关联关系的模式，即用户几次购买行为间的联系，可以采用更有针对性的营销措施。

序列：(sequence) 以SID表示，一个序列即是一个完整的信息流

序列符号化表示：序列是不同项目集的有序排列。序列s可以表示为s = <s1,s2,s3,…,sl>, sj(1<= j <= l)为项目集（itemset），也称为序列s的元素

序列的长度：序列的元素可以表示为（x1,x2,x3,…,xm）,xk (1<= k <= m)为不同的项目。一个序列中所包含的所有项的个数称为序列的长度

项目：(item) 序列中最小组成单位的集合。e g: {A,B,C}.

事件：（event）通常用时间戳标志，标识事件的前后关系，又叫itemset.是item的集合

项目集：（itemset）是各种项目组成的集合

k-频繁序列：如果频繁序列项目个数为K,称为k频繁序列。eg:<（面包，苹果）> 为2频繁序列

序列模式：一个用户在不同时间点的交易记录就构成了一个购买序列

【注意：易错之处】
【注意一：】：k频繁序列：频繁序列中项目的个数为k;（是项目的个数，不是项目集）eg:<（面包，苹果）> 为2频繁序列

【注意二：】：序列的长度：频繁序列中项目集的个数为k;（是项目的个数，不是项目集）eg:<（面包，苹果）> 长度为1

【注意三：】：序列的大小：序列中物品的个数

【注意四：】：易错点：挖掘过程中的k-频繁集（Lk）或者候选k-集(Ck)指的都是【注意一和注意三】中的序列大小。

二：从一个样例入手

2.1.按照常规整理为序列
C1:<(Ringworld) (Foundation) (Ringworld Engineers , Second Foundation)>

C2:<(Foundation , Ringworld) (Foundation and Empire) (Ringworld Engineers)>

2.2.我们学习GSP算法论文中摘要提出的关键新奇的思路
First, we add time constraints that specify a minimum and/or maximum time period between adjacent elements in a pattern.

      Second, we relax the restriction that the items in an element of a sequential pattern must come from the same transaction, instead allowing the items to be presentin a set of transactions whose transaction-times are within a user-specifed time window.              Third, given a user-defined taxonomy(is-a hierarchy) on items, we allow sequential patterns to include items across all levels of the taxonomy

2.3.结合我们实际的例子来解释我们摘要中的思路
【1】第一条：我们添加时间限制，指定模式中相邻元素一个最小和最大的时间段。

   【2】第二条：我们放松了序列中一个项集的定义限制，只要序列中不同项集的交易时间在我们用户指定的一个滑动时间窗口。

   【3】第三条：给物品一个用户指定的分类，允许序列模式中包含分类法中所有级别的项。

 样例解释：

 2.3.1最大/最小时间间隔，例如设定max-gap = 30

虽然C2:<(Foundation , Ringworld) (Foundation and Empire) (Ringworld Engineers)>中的(Foundation , Ringworld) 和 (Ringworld Engineers)是属于同一个序列，但是他们的交易时间一个是1，一个是50，显然超过了最大的max-gap（换到实际上面理解就是：我们只关心一个顾客在一个星期里面的购物记录，不关心一个顾客十年前的购物记录，因为时间太长没有连续性，不存在研究意义）

也就是说“人在心不在”即看似这两个项集在同一个序列里面，但是频繁模式挖掘的时候不当做一个序列里面了。

2.3.2 滑动时间窗口。例如我们设置7天的时间窗口。

原始对应的序列为：

C1:<(Ringworld) (Foundation) (Ringworld Engineers , Second Foundation)>

但是当我们考虑滑动时间窗口为7之后，(Ringworld) 和 （Foundation）这两个项集就可以合并为一个项集了，即（Ringworld , Foundation）。这样一来，在挖掘的结果上序列中项集的形式和意义都会有所改变了。

2.3.3 添加分类限制。
例如我们挖掘到的频繁序列要属于同一类别，多了一个限制条件

<(Foundation) (Asimov)>

论文中的例子：引入分类后，支持就向上扩展了。

三 论文中定义的一些细节

GSP: 翻译过来的意思是广义的序列模式。

论文中提到的元素指的就是一个项集。

3.1 子序列的定义：

3.2 邻接子序列：
3.2.1 邻接子序列出现的原因

    最大跨度影响序列模式发现算法的支持度计数，施加最大时间跨度约束之后，有些数据序列就不再支持候选模式。也就是说使用最大间隔约束可能违反先验原理，以图2.1为例，无约束情形下，<{2} {5}>和<{2}{3}{5}>的支持度都是60%，若施加约束mingap=0，maxgap=1，<{2} {5}>的支持度下降至40%（缺少D的支持），而<{2}{3}{5}>的支持度仍是60%，即超集的支持度比原集要高——与先验原理违背。使用邻接子序列的概念可避免这一问题。

  还是因为同一个序列中有些时间相隔太远的项集不能去参与频繁模式挖掘。

3.2.2 邻接子序列的定义：

3.2.3 邻接子序列举例

注意：以前的子序列中，<(1,2) (3, 4) (6) >属于s的子序列，但不属于邻接子序列。

3.3 滑动窗口的定义

3.4 最大最小时间限制

3.5 序列模式与广义序列模式的关系
GSP算法中提出的想法，如果将其中的一些变量设置为特定的值，则广义化序列模式挖掘就变成传统的序列模式挖掘了

四：GSP算法

论文中主要从这三个方面来进行讲解：1） Candidate Generation ， 2）Counting Candidates ，3）Taxonomies

4.1 候选集产生
添加阶段：

一对频繁（k-1）序列合并，产生候选k-序列。为不重复产生，合并原则如下：

序列S1与序列S2合并，仅当从S1中去掉第一个事件得到的子序列与从S2中去掉最后一个事件得到的子序列相同，合并结果为S1与S2最后一个事件的连接，连接方式有两种：

1）若S2的最后两个事件属于相同的元素，则S2的最后一个事件在合并后的序列中是S1的最后一个元素的一部分；

2）若S2的最后两个事件属于不同的元素，则S2的最后一个事件在合并后的序列中成为连接到S1的尾部的单独元素

4.2 修剪阶段
与apriori算法一样：对于k-序列模式，只要存在一个（k-1）邻接子序列，则表面k-序列是不频繁的。

4.2.1 首先介绍两种技巧：

4.2.2 其次介绍在有时间限制后如何判断一个数据序列是否包含一个特定的序列
对事物数据库中的每个数据序列的每一项进行哈希，从而确定应该考察哈希树哪些叶子节点中的候选K序列；对于叶子节点中的每个候选K序列，须考察其是否包含在该数据序列中，对每个包含在该数据序列中的候选序列，其计数值加1。

如何考察数据序列d是否包含某个候选K序列s？分两步（使用“向前阶段”和“向后阶段”来判断是否包含）

1）论文中关于两个阶段的定义：

2）翻译过来就是

【1】注意d是数据库中的序列，s是候选序列，s将要被判断是否是频繁的。

【2】向前阶段：向前往后找，要是d中找不到s中的某个元素，则s不是d的子序列；找呀找呀，要是能够找到那就分情况呀。没有超过时间限制一切好说；如果超过来时间限制，则进入“向后阶段”。

【3】向后阶段：由于时间限制超过了Max-gap。故应该从新时间值后重新搜索。若找到了，则进入“向前阶段”。

3）举例来讲

4.3 加入分类
其实就是在序列中的项集后面填入一个类别。例如书籍的后面加上作者名字和书籍所属类别。

五.算法

六 源代码及数据集等总结

6.1数据说明一：
算法说明请见开源平台上面的http://www.philippe-fournier-viger.com/spmf/GSP.php

算法的输入数据集，输出结果等请见我的博客 https://blog.csdn.net/yezonghui/article/details/105556854

6.2 数据样例1
输入数据集：

最终结果

产生过程

6.3 数据样例2
输入数据集

最终结果

结果产生过程：

七. 参考文章

https://www.cnblogs.com/beaver-sea/p/4743167.html （序列模式）

https://www.cnblogs.com/liuqing910/p/8964863.html (文月煮刀GSP算法讲解)

论文：《Mining Sequential Patterns: Generalizations：Generalizations and Performance Improvements 》

http://www.philippe-fournier-viger.com/spmf/GSP.php （spmf平台）

https://blog.csdn.net/yezonghui/article/details/105556854 （自己的博客）

本文参考文章：https://blog.csdn.net/yezonghui/article/details/105887249?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522170481742616800197078305%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=170481742616800197078305&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_allsobaiduend~default-1-105887249-null-null.142^v99pc_search_result_base3&utm_term=%E5%BA%8F%E5%88%97%E6%8C%96%E6%8E%98GSP&spm=1018.2226.3001.4449