序列模式挖掘算法简介

1、2001-8-151报告人：报告人：邓爱林邓爱林2001-8-152l序列模式简介序列模式简介lGSP算法算法lPrefixSpan算法算法2001-8-153l序列模式的概念最早是由序列模式的概念最早是由Agrawal和和Srikant 提出的提出的l序列模式定义：给定一个由不同序列组成的集合，其序列模式定义：给定一个由不同序列组成的集合，其中，每个中，每个序列序列由不同的元素按顺序有序排列，每个由不同的元素按顺序有序排列，每个元元素素由不同由不同项目项目组成，同时给定一个用户指定的最小支组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，持度阈值，序列模式挖掘

2、就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值最小支持度阈值2001-8-154l例子例子1：在两年前购买了：在两年前购买了Ford 牌轿车的顾客，很有可牌轿车的顾客，很有可能在今年采取贴旧换新的购车行动能在今年采取贴旧换新的购车行动l例子例子2：在购买了自行车和购物篮的所有客户中，有：在购买了自行车和购物篮的所有客户中，有70%的客户会在两个月后购买打气筒的客户会在两个月后购买打气筒2001-8-155l应用领域：应用领域： 客户购买行为模式预测客户购买行为模式预测 Web访问模式预测访问模式预测 疾病诊断

3、疾病诊断 自然灾害预测自然灾害预测 DNA序列分析序列分析2001-8-156l符号化表示：符号化表示： 项目集项目集(Itemset)是各种项目组成的集合是各种项目组成的集合 序列序列(Sequence)是不同项目集是不同项目集(ItemSet)的有序排列，的有序排列，序列序列s可以表示为可以表示为s = ，sj(1 = j = l)为项为项目集目集(Itemset)，也称为序列，也称为序列s的元素的元素 序列的元素序列的元素(Element)可表示为可表示为(x1x2xm)， xk(1 = k = m)为不同的项目，如果一个序列只有一个项目，为不同的项目，如果一个序列只有一个项目，则括号可

4、以省略则括号可以省略 一个序列包含的所有项目的个数称为序列的长度。一个序列包含的所有项目的个数称为序列的长度。长度为长度为l的序列记为的序列记为l-序列序列2001-8-157l符号化表示：符号化表示： 设设 = ， = ，如果存在整数，如果存在整数1 = j1 j2 jn = m，使得，使得a1 bj1，a2 bj2， an bjn，则称序列，则称序列 为序列为序列 的的子序列子序列，又称序列，又称序列 包含序列包含序列 ，记为，记为 序列序列 在序列数据库在序列数据库S中的中的支持数支持数为序列数据库为序列数据库S中中包含序列包含序列 的序列个数，记为的序列个数，记为Support( )

5、给定支持度阈值给定支持度阈值 ，如果序列，如果序列 在序列数据库中的支在序列数据库中的支持数不低于持数不低于 ，则称序列，则称序列 为为序列模式序列模式 长度为长度为l的序列模式记为的序列模式记为l-模式模式2001-8-158l例子：设序列数据库如下图所示，并设用户指定的最例子：设序列数据库如下图所示，并设用户指定的最小支持度小支持度min-support = 2。Sequence_idSequence10203040l序列序列是序列是序列的子序列的子序列l序列序列是长度为是长度为3的序列模式的序列模式2001-8-159l问题描述：给定序列数据库和最小支持度阈值，序列问题描述：给定序列数据

6、库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式模式挖掘就是要找出序列数据库中所有的序列模式l系统规定：由于同一个元素中的项目之间排列没有顺系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列同项目按照字典顺序排列2001-8-1510l序列模式挖掘的主要算法序列模式挖掘的主要算法 GSP(Generalized Sequential Patterns)算法算法：类似于：类似于Apriori算法算法 PrefixSpan(Prefix-project Sequenti

7、al Pattern mining)算法算法：采用分治的思想，不断产生序列数据库的多个：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘列模式挖掘2001-8-1511l上述算法存在的主要问题：上述算法存在的主要问题： 缺少时间限制缺少时间限制：用户可能需要指定序列模式的相邻：用户可能需要指定序列模式的相邻元素之间的时间间隔。例如，一个序列模式可能会元素之间的时间间隔。例如，一个序列模式可能会发现客户在购买了物品发现客户在购买了物品A后的第三年购买物品后的第三年购买物品B。我们需要的却是给定时间间隔内

8、用户的购买意向我们需要的却是给定时间间隔内用户的购买意向 事务的定义过于严格事务的定义过于严格：一个事务中包含在客户的一：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务的所有的购买行为均作为一个事务 缺少分类层次缺少分类层次：只能在项目的原始级别上进行挖掘：只能在项目的原始级别上进行挖掘2001-8-1512lGSP算法描述：算法描述： 扫描序列数据库，得到长度为扫描序列数据库，得到长度为1的序列模式的序列模式L

9、1，作，作为初始的种子集为初始的种子集 根据长度为根据长度为i 的种子集的种子集Li 通过连接操作和剪切操作通过连接操作和剪切操作生成长度为生成长度为i+1的候选序列模式的候选序列模式Ci+1；然后扫描序列；然后扫描序列数据库，计算每个候选序列模式的支持数，产生长数据库，计算每个候选序列模式的支持数，产生长度为度为i+1的序列模式的序列模式Li+1，并将，并将Li+1作为新的种子集作为新的种子集 重复第二步，直到没有新的序列模式或新的候选序重复第二步，直到没有新的序列模式或新的候选序列模式产生为止列模式产生为止L1 C2 L2 C3 L3 C4 L4 2001-8-1513l产生候选序列模式主

10、要分两步：产生候选序列模式主要分两步： 连接阶段连接阶段：如果去掉序列模式：如果去掉序列模式s1的第一个项目与去的第一个项目与去掉序列模式掉序列模式s2的最后一个项目所得到的序列相同，的最后一个项目所得到的序列相同，则可以将则可以将s1于于s2进行连接，即将进行连接，即将s2的最后一个项目添的最后一个项目添加到加到s1中中 剪切阶段剪切阶段：若某候选序列模式的某个子序列不是序：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除它从候选序列模式中删除L1 C2 L2 C3 L3 C4 L4 2001-8

11、-1514l例子：下图演示了如何从长度为例子：下图演示了如何从长度为3的序列模式产生长度的序列模式产生长度为为4的候选序列模式的候选序列模式Sequential patternsWith length 3Candidate 4-SequencesAfter JoinAfter Pruning2001-8-1515l候选序列模式的支持度计算：对于给定的候选序列模候选序列模式的支持度计算：对于给定的候选序列模式集合式集合C，扫描序列数据库，对于其中的每一条序列，扫描序列数据库，对于其中的每一条序列d,找出集合找出集合C中被中被d所包含的所有候选序列模式，并增加所包含的所有候选序列模式，并增加其支持

12、度计数其支持度计数L1 C2 L2 C3 L3 2001-8-1516lGSP算法存在的主要问题：算法存在的主要问题： 如果序列数据库的规模比较大，则有可能会产生大如果序列数据库的规模比较大，则有可能会产生大量的候选序列模式量的候选序列模式 需要对序列数据库进行循环扫描需要对序列数据库进行循环扫描 对于序列模式的长度比较长的情况，由于其对应的对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太大，本算法很难处理短的序列模式规模太大，本算法很难处理2001-8-1517l相关定义相关定义 前缀前缀：设每个元素中的所有项目按照字典序排列。：设每个元素中的所有项目按照字典序排列。给定序列给

13、定序列 = ， = (m n) ，如果如果ei = ei (i m - 1)， em em，并且，并且(em - em)中的中的项目均在项目均在em中项目的后面，中项目的后面， 则称则称 是是 的前缀的前缀 投影投影：给定序列：给定序列 和和 ，如果，如果 是是 的子序列，则的子序列，则 关关于于 的投影的投影 必须满足：必须满足： 是是 的前缀，的前缀， 是是 的满的满足上述条件的最大子序列足上述条件的最大子序列 后缀后缀： 序列序列 关于子序列关于子序列 = 的投影的投影为为 = (n = m)，则序列，则序列 关于子序列关于子序列 的后缀为的后缀为， 其中其中em” = (em - em

14、)2001-8-1518l例子：例子： a(ab)a(abc)2001-8-1519l算法描述：算法描述： 扫描序列数据库，生成所有长度为扫描序列数据库，生成所有长度为1的序列模式的序列模式 根据长度为根据长度为1的序列模式，生成相应的投影数据库的序列模式，生成相应的投影数据库 在相应的投影数据库上重复上述步骤，直到在相应在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为的投影数据库上不能产生长度为1的序列模式为止的序列模式为止SS1SmS11 S1n Sm1 Smp 2001-8-1520l扫描序列数据库扫描序列数据库S，产生长度为，产生长度为1的序列模式有：的序列模式

15、有： : 4, :4, : 4, : 3, : 3, : 3l序列模式的全集必然可以分为分别以序列模式的全集必然可以分为分别以，和和为前缀的序列模式的集合，构造不同为前缀的序列模式的集合，构造不同前缀所对应的投影数据库，结果如下页图所示前缀所对应的投影数据库，结果如下页图所示l分别对不同的投影数据库重复上述过程，直到没有新分别对不同的投影数据库重复上述过程，直到没有新的长度为的长度为1的序列模式产生为止的序列模式产生为止Sequence_idSequence102030402001-8-1521PrefixProject Database Sequence_idSequence10203040

16、2001-8-1522l定义定义1. 投影数据库投影数据库：设：设 为序列数据库为序列数据库S中的一个序列中的一个序列模式，则模式，则 的投影数据库为的投影数据库为S中所有以中所有以 为前缀的序列为前缀的序列相对于相对于 的后缀，记为的后缀，记为S| l定义定义2. 投影数据库中的支持数投影数据库中的支持数：设设 为序列数据库为序列数据库S中中的一个序列模式，序列的一个序列模式，序列 以以 为前缀，则为前缀，则 在在 的投影数的投影数据库据库S| 中的支持数为中的支持数为S| 中满足条件中满足条件 . 的序列的序列 的的个数个数2001-8-1523lPrefixSpan算法算法 输入：序列数

17、据库输入：序列数据库S及最小支持度阈值及最小支持度阈值min_sup 输出：所有的序列模式输出：所有的序列模式 方法：调用子程序方法：调用子程序PrefixSpan(, 0, S)2001-8-1524l子程序子程序PrefixSpan( , L, S| )参数：参数： . 一个序列模式一个序列模式 L. 序列模式序列模式 的长度的长度 S| . 如果如果 为空，则为为空，则为S，否则为，否则为 的投影数据库的投影数据库扫描扫描S| ，找到满足下述要求的长度为，找到满足下述要求的长度为1的序列模式的序列模式b： b可以添加到可以添加到 的最后一个元素中并为序列模式的最后一个元素中并为序列模式

18、可以作为可以作为 的最后一个元素并为序列模式的最后一个元素并为序列模式对每个生成的序列模式对每个生成的序列模式b，将，将b添加到添加到 形成序列模形成序列模式式 ，并输出，并输出 对每个对每个 ,构造构造 的投影数据库的投影数据库S| ,并调用子程序并调用子程序PrefixSpan( , L + 1, S| )2001-8-1525lPrefixSpan算法分析：算法分析： PrefixSpan算法不需要产生候选序列模式，从而大算法不需要产生候选序列模式，从而大大缩减了检索空间大缩减了检索空间 相对于原始的序列数据库而言，投影数据库的规模相对于原始的序列数据库而言，投影数据库的规模不断减小不断

19、减小 PrefixSpan算法的主要开销在于投影数据库的构造算法的主要开销在于投影数据库的构造2001-8-1526lPrefixSpan算法的主要改进：算法的主要改进： 逐层投影逐层投影：使用隔层投影代替逐层投影，从而可以：使用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数有效减小投影数据库的个数 伪投影伪投影：当序列数据库可以直接放入内存时，可以：当序列数据库可以直接放入内存时，可以使用伪投影操作代替实际的投影数据库，从而可以使用伪投影操作代替实际的投影数据库，从而可以有效减少构造投影数据库的开销有效减少构造投影数据库的开销2001-8-1527l隔层投影的例子：隔层投影的例子： 扫描序列数据库，产生所有长度为扫描序列数据库，产生所有长度为1的序列模式的序列模式 再次扫描序列数据库，构造如下图所示的下三角矩阵，得到所有再次扫描序列