序列模式挖掘算法

1、2020/6/25,1,第4章 序列模式挖掘算法,2020/6/25,2,主要内容,序列模式挖掘简介 序列模式挖掘的应用背景 序列模式挖掘算法概述 GSP算法 PrefixSpan算法 Disc-all算法 支持约束的序列模式挖掘,2020/6/25,3,一、序列模式挖掘简介,序列模式的概念最早是由Agrawal和Srikant 提出的。 动机：大型连锁超市的交易数据有一系列的用户事务数据库，每一条记录包括用户的ID，事务发生的时间和事务涉及的项目。如果能在其中挖掘涉及事务间关联关系的模式，即用户几次购买行为间的联系，可以采取更有针对性的营销措施。,2020/6/25,4,事务数据库实例,例：

2、一个事务数据库，一个事务代表一笔交易，一个单项代表交易的商品，单项属性中的数字记录的是商品ID,2020/6/25,5,序列数据库,一般为了方便处理，需要把数据库转化为序列数据库。方法是把用户ID相同的记录合并，有时每个事务的发生时间可以忽略，仅保持事务间的偏序关系。,2020/6/25,6,问题定义,项集(Itemset)是所有在序列数据库出现过的单项组成的集合 例：对一个用户购买记录的序列数据库来说，项集包含用户购买的所有商品，一种商品就是一个单项。通常每个单项有一个唯一的ID，在数据库中记录的是单项的ID。,2020/6/25,7,问题定义,元素(Element)可表示为(x1x2xm)

3、， xk(1 = k = m)为不同的单项。元素内的单项不考虑顺序关系，一般默认按照ID的字典序排列 在用户事务数据库里，一个事务就是一个元素。,2020/6/25,8,问题定义,序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示为s = ，sj(1 = j = l)为序列s的元素 一个序列包含的所有单项的个数称为序列的长度。长度为l的序列记为l-序列,2020/6/25,9,例：一条序列有3个元素，分别是（10 20），30，（40 60 70 ）； 3个事务的发生时间是由前到后。这条 序列是一个6-序列。,2020/6/25,10,问题定义,设序列 = ，序列

4、= ，ai 和bi都是元素。如果存在整数1 = j1 j2 ，那么下列条件必满足其一： 1） , 的第m项 的第m项且与 在其第m项 之前的部分完全相同 2） , 的第m项 = 的第m项但 的第m项和第m-1项不在同一元素中而 的第m项则相反，并且与 在其第m项 之前的部分完全相同,2020/6/25,62,例： 小于 因为条件1), 小于 因为条件2). 定义序列的大小关系只是为了给序列排序，这种大小度量是相对的，没有真正的物理意义,2020/6/25,63,相关定义,一条l-序列序列所有长度为k的子序列（1 k l)中最小的一条叫做这条序列的k-最小序列. 给定k-序列c为条件序列，一条l

5、-序列序列所有大于c的长度为k的子序列（1 k l)中最小的一条叫做这条序列的k-条件最小序列.,2020/6/25,64,Disc-all算法概述,该算法首先划分数据库，然后在划分数据库上执行迭代的执行Disc策略，即基于序列比较的序列模式枚举过程：首先通过适当的枚举找到所有的k-序列模式，然后根据k-序列模式找到所有的k+1序列模式。,2020/6/25,65,数据库划分,Disc-all算法对原始序列数据库进行两层划分： 一层划分：首先找到所有的频繁单项并删除所有的非频繁单项，然后进行一级划分，即对于每个频繁单项i，找到所有包含它的序列组成i划分。 二层划分：找到所有的2-序列模式并删除

6、所有的非频繁2-序列，然后进行二级划分，即对于每个2-序列模式，找到所有包含它的序列。,2020/6/25,66,例：对如下数据库进行两层划分，给定最小支持度2，首先找到所有的频繁单项：a,b,c,d,e,f,2020/6/25,67,生成一层划分数据库,下面给出了每个频繁单项的一层划分数据库：,2020/6/25,68,在a-划分数据库里找到所有第一项为a的2-序列模式：，并删除非频繁的以a开头的2-序列。删除规则为： 1）如果单项i和a在同一元素内且是2-序列模式; 2）如果单项i和a不在同一元素内且是2-序列模式; 当条件1), 2)全都不满足时删除i.,2020/6/25,69,生成二

7、层划分数据库,下面只给出根据a-划分找到的2-序列模式及其二层划分数据库，注意所有的非频繁2-序列已经被删除。,2020/6/25,70,Disc策略,对于每一个划分数据库，给定一组k-序列模式集合S，Disc策略通过枚举找到所有的k+1-序列模式。枚举过程如下： 1) 对于每个序列s,找到s的最小的k+1-子序列s,且s的k前缀 S，将s加入k+1序列集，记录s的源序列s,2020/6/25,71,Disc策略,2) 对k+1序列集排序，设最小支持度为，排序后第个序列称为条件序列。 3) 如果第一个序列和条件序列相等，则输出条件序列为一个k+1-序列模式，并且将所有k+1序列替换为它们源序列

8、的条件最小k+1-序列。否则尽可能将所有k+1序列替换为条件序列，对于源序列中不含条件序列的k+1序列则替换为条件最小k+1-序列,2020/6/25,72,Disc策略,4）重复上述步骤直到k+1序列集包含的序列数目小于。 Disc策略迭代的根据k-序列模式集找到k+1-序列模式集，然后递增k. 直到没有k+1-序列模式集为空，算法终止。Disc-all算法从从k=2时开始采用Disc策略。,2020/6/25,73,Disc策略,由于Disc-all算法是在划分数据库上采用Disc策略，对于一个的划分，Disc策略只寻找所有以为前缀的序列模式。 回忆之前讨论的prefixSpan算法，可以

9、发现在这一点上二者非常相似。都是基于前缀生长的思想。不同的是prefixSpan采用递归而Disc-all算法采用迭代。,2020/6/25,74,考虑前面的序列数据库，对于右侧的一个基于二层划分，仍然给定最小支持度为2，下面的例子展示了Disc策略是如何找到以3-序列模式的,2020/6/25,75,初始化3-序列集,可以看出是一条3序列模式。Sid为30的序列没有产生初始3-序列因为其不包含以为前缀的3-子序列,为条件序列，将所有3-序列替换为源序列的条件3-最小序列并重新排序，又发现一条3-序列模式,2020/6/25,76,用新的条件最小3-序列替换各3-序列并排序，3-序列数据集如右

10、侧所示。这一次没有新的3-序列模式被发现。,用新的条件序列替换各3-序列并排序，3-序列数据集如右侧所示。发现新的3-序列模式.注意Sid为10的序列不含,所以用条件最小3-序列替换。,2020/6/25,77,重复上面的步骤，可以发现新的3-序列模式. 这时只有Sid为10的序列含有比更大的3-序列，所以算法停止。,2020/6/25,78,Disc-all算法分析,Disc-all算法同样不生成候选序列模式，减少了计算开销。同时采用划分技术, 减少了搜索空间。应用Disc策略，解决了划分效率随划分层次增加而下降的问题。 Disc-all采用的划分技术不如prefixSpan高效，而且Dis

11、c策略较为复杂耗时，算法效率往往不及prefixSpan，但在处理长序列数据集时，因为Disc策略没有迭代开销同时投影技术效率有所下降， Disc-all表现反而更好。,2020/6/25,79,Disc-all和prefixSpan的性能比较,平均序列长度为20时，Disc-all和prefixSpan的性能比较,2020/6/25,80,Disc-all和prefixSpan的性能比较,平均序列长度为80时，Disc-all和prefixSpan的性能比较,2020/6/25,81,用户需要的往往是满足特定条件的序列模式，而传统的序列模式挖掘没有考虑用户的特殊要求，做了大量无效的挖掘。比如

12、对于购买记录的事务数据库，用户希望得到的序列模式事务之间的时间差不能太大。,七、支持约束的序列模式挖掘,2020/6/25,82,解决办法,引入约束的概念。在约束条件下做符合用户要求的序列模式挖掘。一方面利用特定约束本身的性质节省了挖掘的时间和空间，另一方面避免用户陷入大量的无用信息。,2020/6/25,83,约束的分类,单调约束：如果一个序列满足，那么这个序列的所有超序列也满足的约束； 反单调约束：如果一个序列满足，那么这个序列 的任意子序列也满足的约束； 简洁约束：用特定规则挖掘的约束； 还有一些无法归为以上三类的约束，一般被称为强约束（tough constraints.）比如时间性约

13、束。,2020/6/25,84,一些常用的约束,2020/6/25,85,支持约束的序列模式挖掘算法,在支持约束的模式序列挖掘领域内产生了大量的成果。主要有两类，一类是针对特定的约束，如针对单调性约束的ExAnte,针对Gap约束的CCSM,另一类是提出一个通用的框架，可以针对不同的约束采用不同的策略，如PrefixGrowth.,2020/6/25,86,ExAnte算法,ExAnte实际上是一种数据预处理方法，它首先删除所有不满足约束条件的序列，然后删除所有在新的序列数据库中非频繁的单项。处理后的数据集可以应用任何序列模式挖掘方法。,2020/6/25,87,例：给定最小支持度2和约束 Sum(P)4，（目标序列模式的总值大于4），考虑右侧的序列数据库,单项后的数字代表权值。,2020/6/25,88,从表中可以看出，Sid为20，40的序列不满足给定的约束，可以被删除。删除后频繁单项为c,b,d.a被删除。得到如下的数据集： 同原数据集相比，数据规模大大减少,2020/6/25,89,PrefixGrowth算法,PrefixGrowth算法以prefixSpan算法为框架，将约束处理机制整合到前缀增长的过程中。在为前缀构造投影数据库之前，首先启用相应的约束机制检查前缀是否有可能扩展为满足约束条件的序列模式。,2020/