序列模式挖掘综述

1、序 列 报告人：熊 赟 内容概要 基本概念基本概念 其他其他 类类AprioriApriori生成候选算法生成候选算法 相似性搜索相似性搜索 FreeSpanFreeSpan算法算法,PrefixSpan,PrefixSpan算法算法 第第6 6章章 序序 列列 w6.1 基本概念w6.2 原 理w6.3 核心算法w6.4 其 他 n序列是不同项集的有序排列。序列是不同项集的有序排列。 n定义定义1(1(序列序列) )：I=I=i i1 1i i2 2iim m是项集，是项集，i ik k（1=k=m1=k=m）是一个项，序列）是一个项，序列S S记为记为S Ss ，其中其中s sj j（1=

2、j=n1=j=n）为项集（也称序列）为项集（也称序列S S的元素），的元素），即即s sj j I I。每个元素由不同项组成。序列的元素可。每个元素由不同项组成。序列的元素可表示为（表示为（i i1 1i i2 2iik k），若一个序列只有一个项，则），若一个序列只有一个项，则括号可以省略。括号可以省略。 n序列包含的所有项的个数称为序列包含的所有项的个数称为序列的长度。序列的长度。长度长度为为l l 的序列记为的序列记为l l - -序列。序列。 序序 列列n定义定义2(2(子序列子序列) )：序列：序列T Tt 是另一个是另一个序列序列S Ss 的子序列，满足下面条件：的子序列，满足下面

3、条件：对于每一个对于每一个j j，1=j=m-11=j=m-1，有，有i ij jiij+1j+1 且且 对于对于每一个每一个j j，1=j=m1=j=m，存在，存在1=k=n1=k=n，使得，使得t tijij s sk k。即序列即序列S S包含序列包含序列T T。用符号。用符号“ ”表示表示“被包被包含于含于”，序列，序列T T是序列是序列S S的子序列可记为的子序列可记为T T S S。称称T T为为S S的子序列，的子序列，S S为为T T的超序列。的超序列。n若一个序列若一个序列S S不包含在任何其他的序列之中，则不包含在任何其他的序列之中，则称序列称序列S S是最大的。是最大的。

4、 子子 序序 列列定义定义3 3（支持度）：序列数据库（支持度）：序列数据库D D是元组是元组sidS的集合，的集合，sidsid为序列标识号，如果序列为序列标识号，如果序列T T是是S S的子序列（即的子序列（即T T S S）称元组）称元组包含序包含序列列T T；则序列；则序列T T在序列数据库在序列数据库D D中的支持度是中的支持度是数据库中包含数据库中包含T T的元组数，即的元组数，即supportsupportD D(T)(T)| D D T T S |S |记作记作supportsupport（T T）。 序列支持度序列支持度n定义定义4 4（频繁序列模式）：给定正整数（频繁序列模

5、式）：给定正整数 为支持为支持度阈值，如果数据库中最少有度阈值，如果数据库中最少有 个元组包含序个元组包含序列列S S，即，即supportsupport（S S）= ，则称序列，则称序列S S为序列为序列数据库数据库D D中的一个（频繁）序列模式。中的一个（频繁）序列模式。n长度为长度为l l 的序列模式称为的序列模式称为l l 模式。模式。 频繁序列模式频繁序列模式 序列关联规则序列关联规则置信度置信度支持度支持度 序列关联规则序列关联规则序列关联规则ST的支持度是支持序列S和T的顾客数占总顾客数之比。序列关联规则ST的置信度记为（），是支持序列S和T的顾客数与仅支持S的顾客数之比。 交易

6、发生的时间客户标识购买项June 1004June 1204June 1504June 2004June 2504June 2504June 2504June 3004June 3004July 25042522431144A，BHCD，F，GCC，E，GCHD，GH客户标识客户标识交易时间交易时间购买项购买项11June 2504June 3004CH222June 1004June 1504June 2004A,BCD,F,G3June 2504C,E,G444June 2504June 3004July 2504CD,GH5June 1204H由客户标识及交易发生的时间为关键字所排序的数

7、据库客户客户号号客户序列客户序列12345客户序列描述数据库频繁项频繁项集集映射映射(C)(D)(G)(DG)(H)12345频繁项集分别是(C)、(D)、(G)、(D,G)和(H)客户标识客户标识原始客户序列原始客户序列转换后客户序列转换后客户序列映射后序列映射后序列12345转换后的数据库（客户序列） 核心算法核心算法 客户号客户号客户序列客户序列12345 AprioriAllAprioriAll算法算法 1-1-序列序列支持度支持度42444L12-2-序列序列支持度支持度243322322L23-3-序列序列支持度支持度22322AprioriAllAprioriAll算法算法 4-

8、4-序列序列支持度支持度2L3L4序列序列支持度支持度222AprioriAllAprioriAll算法算法 最大的频繁序列AprioriSomeAprioriSome算法算法 AprioriSomeAprioriSome算法算法 1-1-序列序列支持度支持度42444L12-2-序列序列支持度支持度243322322L2next(last)=2k不计数AprioriSomeAprioriSome算法算法 C3C4修剪修剪AprioriSomeAprioriSome算法算法 C5为空结束前阶段进入回溯阶段删除了L4的子序列后的C3再计数发现是最大3序列L44-4-序列序列支持度支持度2序列序列

9、支持度支持度222AprioriSomeAprioriSome算法算法 最大的频繁序列除以外L2中所有的序列都被删除 L1中所有的序列都被删除 FreeSpanFreeSpan算法算法频繁模式投影的序列模式挖掘频繁模式投影的序列模式挖掘 Frequent pattern-projected Sequential pattern miningFreeSpanFreeSpan算法算法 序列序列idid序列序列项项10a,b,c,d20b,c,e,f,g30a,b,f,h40b,c,d,e50a,b,c,d,e序列数据库序列数据库 最小支持度设为2 FreeSpanFreeSpan算法算法 Free

10、SpanFreeSpan算法算法4(4,3,0)1(3,2,0) (2,1,1) 2(2,2,2) (2,2,0)(1,2,1)1(3,1,1) (1,1,2)(1,0,1)(1,1,1)1(2,2,2) (1,1,0)(1,1,0)(0,0,0) (1,1,0)21b2c3a4d5e6f1b2c3a4d5e6f序列 FreeSpanFreeSpan算法算法 FreeSpanFreeSpan算法算法项长度为2的序列模式循环项标记投影数据库标记f:2,:2,:2b+ f+ e:3,:2:bd:2, :2, :2:2, :2, :2b+ d : bccd: bacb:4 FreeSpanFreeS

11、pan算法算法 b+ + d FreeSpanFreeSpan算法算法标记:b : bccd: b: b投影数据库,序列模式:2:2:2:2:2:2:2:2。PrefixSpanPrefixSpan算法算法（通过前缀投影挖掘序列模式）（通过前缀投影挖掘序列模式）Prefix-projected Sequential pattern mining 例： 前缀：给定序列前缀：给定序列 = ， = (m n) ，如果，如果ei = ei (i m - 1)， em em，并且并且(em - em)中的项目均在中的项目均在em中项目的后面，中项目的后面， 则称则称 是是 的前缀的前缀.投影：投影：给定

12、序列给定序列 和和 ，其中，其中 是是 的子序列，即的子序列，即。 的子序列的子序列 （ ），）， 被称为被称为 关于前缀关于前缀 的投影，当且仅当的投影，当且仅当1 1） 是是 的前缀的前缀2 2）不存在不存在 的超集的超集 /（即（即 /， /），使得），使得 /是是 的子序列并且的子序列并且 是是 /的前缀。的前缀。 后缀：后缀： 序列序列 关于子序列关于子序列 = 的投的投影为影为 = (n = m)，则序列，则序列 关于子关于子序列序列 的后缀为的后缀为， 其中其中em” = (em - em)算法描述：扫描序列数据库，生成所有长度为1的序列模式根据长度为1的序列模式，生成相应的投影

13、数据库在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生序列模式为止SS1SmS11 S1n Sm1 Smp PrefixSpanPrefixSpan算法算法 PrefixSpanPrefixSpan算法算法序列号序列号序列序列10203040n定义1. 投影数据库：设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S|n例： n投影数据库,PrefixSpanPrefixSpan算法算法 PrefixSpanPrefixSpan算法算法 PrefixSpanPrefixSpan算法算法 n子程序子程序PrefixSpan( , L, S

14、| ) 参数：参数： ：一个序列模式：一个序列模式 ；L：序列模式：序列模式 的长度的长度 S| ： 如果如果 不为空时，为不为空时，为 投影数据库，否则投影数据库，否则为投影数据库为投影数据库S，1 1 扫描扫描S|S| ，找到频繁项，找到频繁项b b，b b满足：满足：a)ba)b可以作为可以作为 的最后一个元素，形成一个序列模的最后一个元素，形成一个序列模式；或者式；或者b)b) 可以追加到可以追加到 上，形成一个序列模式。上，形成一个序列模式。2 2）对于每个频繁项）对于每个频繁项b b，追加到，追加到 上，形成一个序列上，形成一个序列模式模式 ，输出，输出 ；3 3）对于每个）对于每个 ，构建，构建 投影数据库投影数据库S|S| ，调，调用用PrefixSpan(PrefixSpan( ,l+1,S|,l+1,S| ) )。 前缀前缀投影（后缀）数据库投影（后缀）数据库序列模式序列模式,(_d)c(b,c)(ae),aba,ad,c,(_c)(ae),b,c,