Sequential Pattern Mining 序列模式挖掘

序列模式挖掘的任务是:尝试从数据集中发现时间顺序模式。

 

与关联规则挖掘做个类比。

  • 关联规则挖掘发现的是:如果顾客买了尿布,他有较高几率同时会买啤酒。
  • 序列模式挖掘发现的时:如果顾客今天买了尿布,他有较高几率下次会买啤酒。

 

序列模式挖掘与关联规则挖掘之间的主要区别在于:

  • 关联规则挖掘中,“如果—则”的关系出现在同一个数据点中。
  • 序列模式挖掘中,“如果—则”的关系可以是不同的数据点,只要这些不同的数据点对应同一个分析对象(如:这学期修的课和下学期选修的课,都针对同一个学生而言)。

 

序列模式挖掘的方法为:以一定的支持程度作为阀值,在数据集中找出所有满足条件的序列关系。

这里,支持程度的计算方法为:(包含了特定序列关系的组合数量)除以(所有序列组合的数量)

 

常用算法有:GSP (Generalized Sequential Pattern)

见 Srikant & Agrawal, 1996

http://rakesh.agrawal-family.com/papers/icde95seq.pdf

 

数据预处理过程:

将数据处理成分析对象的行为序列,如:

Bob:{瞎蒙且无聊5:05:20,休息且无聊5:05:40,解题且无聊5:06:00,瞎蒙且无聊5:06:20,瞎蒙且崩溃5:06:40,解题且无聊5:07:00}

 

GPS算法:

  1. 选取所有长度为1的序列集合,以特定的阀值进行筛选。
  2. 根据筛选过的长度为1的序列集合,构造长度为2的序列集合,以特定的阀值进行筛选。
  3. 根据筛选过的长度为1的序列集合和长度为2的序列集合,构造长度为3的序列集合,以特定的阀值进行筛选。
  4. 如此直至无法构建、筛选出任何新的序列。
  5. 对于所有筛选出的长度大于1的序列,构建序列关系。

 

例:

设定阀值为0.2

数据:

  • Chuck: a, abc, ac, de, cef
  • Darlene: af, ab, acd, dabc, ef
  • Egoberto: aef, ab, aceh, d, ae
  • Francine: a, bc, acf, d, abeg

 

首先是支持程度的计算,以长度为2的序列为例。

对于Chunk而言,其数据中所有可能的长度为2序列为:

  • (a,abc),(a,ac), (a,de), (a,cef),(abc,ac),(abc,de),(abc,cef),(ac,de),(ac,cef),(de,cef)

共10个。

以Chunk数据中的序列ac为例:

  • (a,abc),(a,ac),(a,cef),(abc,ac),(abc,cef),(ac,cef)

满足该序列,共6个。

(abc,de)不满足序列ac的原因是:abc中的ac是同时间出现的,在同一个数据点中。

因此仅对Chunk而言,序列ac的支持程度为6/10=0.6>0.2。

 

算法:

长度为1的序列:

选取所有长度为1的序列集合,以阀值0.2进行筛选,所有长度为1的序列总数为20,每人5个。

序列有a,b,c,d,e,f,其支持程度分别为:

  • a: 14/20=0.7>0.2
  • b: 6/20=0.2>0.2
  • c: 8/20=0.4>0.2
  • d: 5/20=0.25>0.2
  • e: 7/20=0.35>0.2
  • f: 5/20=0.4>0.2
  • g:1/20=0.05<0.2
  • h:1/20=0.05<0.2

a,b,c,d,e,f超过阀值0.2,可组合成长度为2的序列有:ab,ac,ad,ae,af,bc,bd,be,bf,cd,ce,cf,de,df,ef共15种。

长度为2的序列:

数据中,所有长度为2的序列总数为40,每人(4+3+2+1)=10种。对上一步最后构建的15种长度为2的序列进行检验:

  • 计算ab的支持程度为:9/40 = 0.225 > 0.2
  • 计算ac的支持程度为:15/40 = 0.375 >0.2
  • 计算ad的支持程度为:13/40 = 0.325 >0.2
  • 计算ae的支持程度为:17/40 = 0.425 >0.2
  • 计算af的支持程度为:8/40 = 0.2
  • 如此类推

算出超过阀值的长度为2的序列有:ac,ad,ae等

利用第1步筛选出的中长度为1的序列和刚筛选出长度为2的序列,构造长度为3的序列,如aac,aad,等。

 

长度为3的序列:

数据中,所有长度为3的序列总数为40,每人(4+3+2+1)=10种,对上一步最后构建的长度为3的序列进行检验

  • 计算aac的支持程度为:7/40 = 0.175<0.2
  • 计算aad的支持程度为:8/40 = 0.2
  • 计算aae的支持程度为:17/40 = 0.425>0.2

类似地,计算出超过阀值的长度为3的序列有:aad,aae,ade, etc.

 

如此直至再也无法筛选出更长的序列

 

最后

筛选出的所有长度超过2的序列有:ac,ad,ae,aad,aae,ade,etc等

构造的序列关系有:a->c,a->d,a->e,a->ad,a->ae,a->de等

通过领域知识对这些序列关系进行最后筛选。

 

其他序列挖掘算法还有:

  • Free-Span
  • Prefix-Span

Leave a Reply

Your email address will not be published. Required fields are marked *