《序列模式挖掘算法.pdf》由会员分享，可在线阅读，更多相关《序列模式挖掘算法.pdf（35页珍藏版）》请在三一文库上搜索。
1、2015-1-51 序列模式挖掘算法序列模式挖掘算法 桂林电子科技大学研究生院 桂林电子科技大学研究生院 2015-1-52 讲课讲课的主要内容的主要内容 序列模式简介序列模式简介 GSP算法 （1）有关概念 （2）GSP算法实现步骤 （3）举例说明 （4）缺陷 算法 （1）有关概念 （2）GSP算法实现步骤 （3）举例说明 （4）缺陷 2015-1-53 一、序列模式简介一、序列模式简介 应用领域：应用领域： 客户购买行为模式预测客户购买行为模式预测 Web访问模式预测访问模式预测 疾病诊断疾病诊断 自然灾害预测自然灾害预测 DNA序列分析序列分析 2015-1-54 一、序列模式简介一、序
2、列模式简介 序列模式的概念最早是由序列模式的概念最早是由Agrawal和和Srikant 提出的提出的 序列模式定义：给定一个由不同序列组成的集合，其 中，每个 序列模式定义：给定一个由不同序列组成的集合，其 中，每个序列序列由不同的元素按顺序有序排列，每个由不同的元素按顺序有序排列，每个元 素 元 素由不同由不同项目项目组成，同时给定一个用户指定的最小支 持度阈值，序列模式挖掘就是找出所有的频繁子序列， 即该子序列在序列集中的出现频率不低于用户指定的 最小支持度阈值 组成，同时给定一个用户指定的最小支 持度阈值，序列模式挖掘就是找出所有的频繁子序列， 即该子序列在序列集中的出现频率不低于用户
3、指定的 最小支持度阈值 2015-1-55 一、序列模式简介一、序列模式简介 符号化表示：符号化表示： 项目集项目集(Itemset)是各种项目组成的集合是各种项目组成的集合 序列序列(Sequence)是不同项目集是不同项目集(ItemSet)的有序排列， 序列 的有序排列， 序列s可以表示为可以表示为s = ，sj(1 ， = ，如果存在整数，如果存在整数1 40 30 20 10 SequenceSequence_id 序列序列是序列是序列的子序列的子序列 序列序列是长度为是长度为3的序列模式的序列模式 2015-1-58 一、序列模式简介一、序列模式简介 问题描述：给定序列数据库和最小
4、支持度阈值，序列 模式挖掘就是要找出序列数据库中所有的序列模式 问题描述：给定序列数据库和最小支持度阈值，序列 模式挖掘就是要找出序列数据库中所有的序列模式 系统规定：由于同一个元素中的项目之间排列没有顺 序，为了表达的唯一性，我们将同一个元素内部的不 同项目按照字典顺序排列 系统规定：由于同一个元素中的项目之间排列没有顺 序，为了表达的唯一性，我们将同一个元素内部的不 同项目按照字典顺序排列 2015-1-59 序列模式挖掘的一般步骤序列模式挖掘的一般步骤 排序阶段排序阶段 大项集阶段大项集阶段 转换阶段转换阶段 序列阶段序列阶段 选最大阶段选最大阶段 2015-1-510 一、序列模式简介
5、一、序列模式简介 序列模式挖掘的主要算法序列模式挖掘的主要算法 GSP(Generalized Sequential Patterns)算法算法：类似于：类似于 Apriori算法算法 PrefixSpan(Prefix-project Sequential Pattern mining) 算法算法：采用分治的思想，不断产生序列数据库的多个 更小的投影数据库，然后在各个投影数据库上进行序 列模式挖掘 ：采用分治的思想，不断产生序列数据库的多个 更小的投影数据库，然后在各个投影数据库上进行序 列模式挖掘 2015-1-511 二、二、GSPGSP算法算法 GSP算法描述：算法描述： 扫描序列数据
6、库，得到长度为扫描序列数据库，得到长度为1的序列模式的序列模式L1，作 为初始的种子集 ，作 为初始的种子集 根据长度为根据长度为i 的种子集的种子集Li 通过连接操作和剪切操作 生成长度为 通过连接操作和剪切操作 生成长度为i+1的候选序列模式的候选序列模式Ci+1；然后扫描序列 数据库，计算每个候选序列模式的支持数，产生长 度为 ；然后扫描序列 数据库，计算每个候选序列模式的支持数，产生长 度为i+1的序列模式的序列模式Li+1，并将，并将Li+1作为新的种子集作为新的种子集 重复第二步，直到没有新的序列模式或新的候选序 列模式产生为止 重复第二步，直到没有新的序列模式或新的候选序 列模式
7、产生为止 L1 C2 L2 C3 L3 C4 L4 2015-1-512 二、二、GSPGSP算法算法 产生候选序列模式主要分两步：产生候选序列模式主要分两步： 连接阶段连接阶段：如果去掉序列模式：如果去掉序列模式s1的第一个项目与去 掉序列模式 的第一个项目与去 掉序列模式s2的最后一个项目所得到的的最后一个项目所得到的序列序列相同， 则可以将 相同， 则可以将s1于于s2进行连接，即将进行连接，即将s2的最后一个的最后一个项目项目添 加到 添 加到s1中中 剪切阶段剪切阶段：若某候选序列模式的某个子序列不是序 列模式，则此候选序列模式不可能是序列模式，将 它从候选序列模式中删除 ：若某候选
8、序列模式的某个子序列不是序 列模式，则此候选序列模式不可能是序列模式，将 它从候选序列模式中删除 L1 C2 L2 C3 L3 C4 L4 2015-1-513 二、二、GSPGSP算法算法 例子：下图演示了如何从长度为例子：下图演示了如何从长度为3的序列模式产生长度 为 的序列模式产生长度 为4的候选序列模式的候选序列模式 After PruningAfter Join Candidate 4-SequencesSequential patterns With length 3 2015-1-514 二、二、GSPGSP算法算法 候选序列模式的支持度计算：对于给定的候选序列模 式集合 候选序
9、列模式的支持度计算：对于给定的候选序列模 式集合C，扫描序列数据库，对于其中的每一条序列，扫描序列数据库，对于其中的每一条序列d, 找出集合找出集合C中被中被d所包含的所有候选序列模式，并增加 其支持度计数 所包含的所有候选序列模式，并增加 其支持度计数 L1 C2 L2 C3 L3 2015-1-515 带交易时间的交易数据源带交易时间的交易数据源 客户号交易时间物品客户号交易时间物品 1June 259930 1June309990 2June109910,20 2June159930 2June209940,60,70 3June259930,50,70 4June259930 4Jun
10、e309940,70 4July259990 5June129990 2015-1-516 GSPGSP算法举例算法举例 客户号 （ 客户号 （ Cust_id） 顾客序列（ ） 顾客序列（Customer Sequence） 1 2 3 4 5 2015-1-517 第一步产生第一步产生L1L1 （10） （20） （30） （40） （50） （60） （70） （90） 2015-1-518 第二步产生第二步产生C2C2 C2 支持 数 支持 数 C2 支持 数 支持 数 C2 支持 数 支持 数 C2 支持 数 支持 数 C2 支持 数 支持 数 （10,20）1（10）（60） 1（
11、20,50）0（30）（40） 2（40,50）0 （10）（20） 0（10,70） 0（20）（50） 0（30,50）1（40）（50） 0 （10,30）0（10）（70） 1（20,60）0（30）（50） 0（40,60）1 （10）（30） 1（10,90） 0（20）（60） 1（30,60）0（40）（60） 0 （10,40）0（10）（90） 0（20,70）0（30）（60） 1（40，70）2 （10）（40） 1（20,30） 0（20）（70） 1（30,70）1（40）（70） 0 （10,50）0（20）（30） 1（20,90）0（30）（70） 2（40,
12、90）0 （10）（50） 0（20，40） 0（20）（90） 0（30,90）0（40）（90） 1 （10,60）0（20）（40） 1（30,40）0（30）（90） 2（50,60）0 2015-1-519 第二步产生第二步产生C2C2 C2 支持 数 支持 数 C2 支持 数 支持 数 C2 支 持 数 支 持 数 C2 支 持 数 支 持 数 C2 支持 数 支持 数 （50）（60）0（50,90）0（60）（70）0（70,90）0 （50,70）1（50）（90）0（60,90）0（70）（90）1 （50）（70）0（60,70）1（60）（90）0 2015-1-520
13、 第三步产生第三步产生L2L2 （30）（）（40） （30）（70） （30）（90） （40,70） 2015-1-521 第四步产生第四步产生C3C3 （30）（）（40,70） 2015-1-522 二、二、GSPGSP算法算法 GSP算法存在的主要问题：算法存在的主要问题： 如果序列数据库的规模比较大，则有可能会产生大 量的候选序列模式 如果序列数据库的规模比较大，则有可能会产生大 量的候选序列模式 需要对序列数据库进行循环扫描需要对序列数据库进行循环扫描 对于序列模式的长度比较长的情况，由于其对应的 短的序列模式规模太大，本算法很难处理 对于序列模式的长度比较长的情况，由于其对应的
14、 短的序列模式规模太大，本算法很难处理 2015-1-523 一、序列模式简介一、序列模式简介 上述算法存在的主要问题：上述算法存在的主要问题： 缺少时间限制缺少时间限制：用户可能需要指定序列模式的相邻 元素之间的时间间隔。例如，一个序列模式可能会 发现客户在购买了物品 ：用户可能需要指定序列模式的相邻 元素之间的时间间隔。例如，一个序列模式可能会 发现客户在购买了物品A后的第三年购买物品后的第三年购买物品B。我 们需要的却是给定时间间隔内用户的购买意向 。我 们需要的却是给定时间间隔内用户的购买意向 事务的定义过于严格事务的定义过于严格：一个事务中包含在客户的一 次购买行为中所购买的所有物品
15、。可能需要指定一 个滑动时间窗口，客户在滑动时间窗口的时间段内 的所有的购买行为均作为一个事务 ：一个事务中包含在客户的一 次购买行为中所购买的所有物品。可能需要指定一 个滑动时间窗口，客户在滑动时间窗口的时间段内 的所有的购买行为均作为一个事务 缺少分类层次缺少分类层次：只能在项目的原始级别上进行挖掘：只能在项目的原始级别上进行挖掘 2015-1-524 三、三、PrefixSpanPrefixSpan算法算法 相关定义相关定义 前缀前缀：设每个元素中的所有项目按照字典序排列。 给定序列 ：设每个元素中的所有项目按照字典序排列。 给定序列 = ， = (m n) ， 如果 ， 如果ei =
16、ei (i m - 1)， em em，并且，并且(em - em)中的 项目均在 中的 项目均在em中项目的后面，中项目的后面， 则称是的前缀则称是的前缀 投影投影：给定序列和：给定序列和 ，如果是的子序列，则关 于的投影 ，如果是的子序列，则关 于的投影必须满足：必须满足： 是是的前缀，的前缀，是的满 足上述条件的最大子序列 是的满 足上述条件的最大子序列 后缀后缀： 序列关于子序列序列关于子序列 = 的投影 为 的投影 为 = (n = m)，则序列关于子序列 的后缀为 ，则序列关于子序列 的后缀为， 其中其中em” = (em - em) 2015-1-525 三、三、PrefixSp
17、anPrefixSpan算法算法 例子：例子： a(ab) a(abc) 2015-1-526 三、三、PrefixSpanPrefixSpan算法算法 算法描述：算法描述： 扫描序列数据库，生成所有长度为扫描序列数据库，生成所有长度为1的序列模式的序列模式 根据长度为根据长度为1的序列模式，生成相应的投影数据库的序列模式，生成相应的投影数据库 在相应的投影数据库上重复上述步骤，直到在相应 的投影数据库上不能产生长度为 在相应的投影数据库上重复上述步骤，直到在相应 的投影数据库上不能产生长度为1的序列模式为止的序列模式为止 S S1 Sm S11 S1n Sm1 Smp 2015-1-527
18、三、三、PrefixSpanPrefixSpan算法算法 扫描序列数据库扫描序列数据库S，产生长度为，产生长度为1的序列模式有：的序列模式有： : 4, :4, : 4, : 3, : 3, : 3 序列模式的全集必然可以分为分别以序列模式的全集必然可以分为分别以， ，和和为前缀的序列模式的集合，构造不同前 缀所对应的投影数据库，结果如下页图所示 为前缀的序列模式的集合，构造不同前 缀所对应的投影数据库，结果如下页图所示 分别对不同的投影数据库重复上述过程，直到没有新 的长度为 分别对不同的投影数据库重复上述过程，直到没有新 的长度为1的序列模式产生为止的序列模式产生为止 40 30 20 1
19、0 SequenceSequence_id 2015-1-528 三、三、PrefixSpanPrefixSpan算法算法 Project DatabasePrefix 40 30 20 10 SequenceSequence_id 2015-1-529 三、三、PrefixSpanPrefixSpan算法算法 定义定义1. 投影数据库投影数据库：设为序列数据库：设为序列数据库S中的一个序列 模式，则的投影数据库为 中的一个序列 模式，则的投影数据库为S中所有以为前缀的序列 相对于的后缀，记为 中所有以为前缀的序列 相对于的后缀，记为S| 定义定义2. 投影数据库中的支持数投影数据库中的支持数
20、：设为序列数据库：设为序列数据库S中 的一个序列模式，序列以为前缀，则在的投影数 据库 中 的一个序列模式，序列以为前缀，则在的投影数 据库S| 中的支持数为中的支持数为S| 中满足条件中满足条件 .的序列的 个数 的序列的 个数 2015-1-530 三、三、PrefixSpanPrefixSpan算法算法 PrefixSpan算法算法 输入：序列数据库输入：序列数据库S及最小支持度阈值及最小支持度阈值min_sup 输出：所有的序列模式输出：所有的序列模式 方法：调用子程序方法：调用子程序PrefixSpan(, 0, S) 2015-1-531 三、三、PrefixSpanPrefixS
21、pan算法算法 子程序子程序PrefixSpan( , L, S| ) 参数：参数： . 一个序列模式一个序列模式 L. 序列模式的长度序列模式的长度 S| . 如果为空，则为如果为空，则为S，否则为的投影数据库，否则为的投影数据库 扫描扫描S| ，找到满足下述要求的长度为，找到满足下述要求的长度为1的序列模式的序列模式b： b可以添加到的最后一个元素中并为序列模式可以添加到的最后一个元素中并为序列模式 可以作为的最后一个元素并为序列模式可以作为的最后一个元素并为序列模式 对每个生成的序列模式对每个生成的序列模式b，将，将b添加到形成序列模 式 添加到形成序列模 式，并输出，并输出 对每个对每
22、个,构造构造的投影数据库的投影数据库S| ,并调用子程序并调用子程序 PrefixSpan( , L + 1, S| ) 2015-1-532 三、三、PrefixSpanPrefixSpan算法算法 PrefixSpan算法分析：算法分析： PrefixSpan算法不需要产生候选序列模式，从而大 大缩减了检索空间 算法不需要产生候选序列模式，从而大 大缩减了检索空间 相对于原始的序列数据库而言，投影数据库的规模 不断减小 相对于原始的序列数据库而言，投影数据库的规模 不断减小 PrefixSpan算法的主要开销在于投影数据库的构造算法的主要开销在于投影数据库的构造 2015-1-533 三、
23、三、PrefixSpanPrefixSpan算法算法 PrefixSpan算法的主要改进：算法的主要改进： 逐层投影逐层投影：使用隔层投影代替逐层投影，从而可以 有效减小投影数据库的个数 ：使用隔层投影代替逐层投影，从而可以 有效减小投影数据库的个数 伪投影伪投影：当序列数据库可以直接放入内存时，可以 使用伪投影操作代替实际的投影数据库，从而可以 有效减少构造投影数据库的开销 ：当序列数据库可以直接放入内存时，可以 使用伪投影操作代替实际的投影数据库，从而可以 有效减少构造投影数据库的开销 2015-1-534 三、三、PrefixSpanPrefixSpan算法算法 隔层投影的例子：隔层投影
24、的例子： 扫描序列数据库，产生所有长度为扫描序列数据库，产生所有长度为1的序列模式的序列模式 再次扫描序列数据库，构造如下图所示的下三角矩阵，得到所有 长度为 再次扫描序列数据库，构造如下图所示的下三角矩阵，得到所有 长度为2的序列模式的序列模式 构造长度为构造长度为2的序列模式所对应的扫描数据库，然后对每个投影数的序列模式所对应的扫描数据库，然后对每个投影数 据库，重复上面的操作，直到没有新的序列模式产生为止据库，重复上面的操作，直到没有新的序列模式产生为止 40 30 20 10 SequenceSequence_id fedcba 1(2,0,1)(1,1,1)(1,2,1)(2,2,0
25、)(2,1,1)f 0(1,1,0)(1,2,0)(1,2,0)(1,2,1)e 0(1,3,0)(2,2,0)(2,1,1)d 3(3,3,2)(4,2,1)c 1(4,2,2)b 2a 2015-1-535 三、三、PrefixSpanPrefixSpan算法算法 伪投影：当数据库可以直接放入内层时，并不需要构 造所有的序列模式对应的投影数据库，我们可以使用 指向数据库中序列的指针及其偏移量作为伪投影 伪投影：当数据库可以直接放入内层时，并不需要构 造所有的序列模式对应的投影数据库，我们可以使用 指向数据库中序列的指针及其偏移量作为伪投影 例子：假设上述序列数据库可以放入内层，在构造例子：假设上述序列数据库可以放入内层，在构造a投 影数据库时，序列 投 影数据库时，序列 S1 = 所对应的伪投 影为：一个指向 所对应的伪投 影为：一个指向S1的指针，指针偏移设定为的指针，指针偏移设定为2。同样的， 序列 。同样的， 序列S1的的投影数据库对应的伪投影为：一个指向投影数据库对应的伪投影为：一个指向 S1的指针，指针偏移设定为的指针，指针偏移设定为4