序列模式挖掘.ppt

知识背景 序列模式是神马 1 顾客购买产品X 很可能在一段时间内购买购买产品Y 时间序列模型 2 在某个点发现了现象X 很可能在下一个点发现现象Y 空间序列模型 知识背景 序列模型VS关联规则 关联规则 序列模型 序列模型 关联规则 时间 空间 维度 知识背景 序列模型VS时间序列模型 时间序列模型 序列模型 序列模型 一系列研究对象在某段时间内的行为模式分析 如顾客购买序列模式的发现 时间序列模型 一个特定对象 变量 在某段时间内的变化趋势 具有时间自相关性 如股票分析 知识框架 1 1概念 定性 序列模式挖掘是挖掘频繁出现的有序事件或子序列 定量 给定一个正整数min sup 表示最小支持度阈值 如果序列 在序列数据库S中存在support S min sup 则序列 是频繁序列 也叫做序列模式 1 2 定义 序列 将与对象A有关的所有事务按时间戳增序排序 就得到对象A的一个序列s 事务 序列是事务的有序列表 可以记作s 项 事务e是一个项集 可以记作e x1 x2 x3 xn 当只有1项时直接记作x1 序列包含的项的数量记作序列的长度 长度为L的序列记作L序列 序列数据库 包含一个或多个序列数据的数据集 子序列 设序列 序列 ai和bi都是元素 如果存在整数1 j1 j2 jn m 使得a1 bj1 a2 bj2 an bjn则称序列 为序列 的子序列 又称序列 包含序列 记为 包含3个序列 S1 S2 S3 假设有S4 S1包含3个事务 8个项 长度即为8 成为8序列 S2以及S3都为S1的子序列 S4则不是S1的子序列 2 1GSP算法和SPADE算法 算法介绍 属于类Apriori算法 基于原理 序列模式的每个非空子集都是序列模式 基于 候选产生 测试 模式进行挖掘 主要步骤 1 扫描序列数据库 得到长度为1的序列模式L1 作为初始的种子集 2 根据长度为i的种子集Li 通过连接操作和修剪操作生成长度为i 1的候选序列模式Ci 1 然后扫描序列数据库 计算每个候选序列模式的支持度 产生长度为i 1的序列模式Li 1 并将Li 1作为新的种子集 3 重复第二步 直到没有新的序列模式或新的候选序列模式产生为止 L1 C2 L2 C3 L3 C4 L4 2 1GSP算法和SPADE算法 连接操作 如果去掉序列模式S1的第一个项与去掉序列模式S2的最后一个项所得到的序列相同 则可以将S1于S2进行连接 即将S2的最后一个项目添加到S1中 其中 1 若S2的最后两个项本来属于同一个事务 则合并后与S1序列的最后一个项合并为同一个同一个事务 2 否则 S2最后一项则单独成为一个事务 剪切阶段 若某候选序列模式的某个子序列不是序列模式 则此候选序列模式不可能是序列模式 将它从候选序列模式中删除 频繁3序列 候选产生 候选剪枝 2 1GSP算法和SPADE算法 GSPVSSPADE 区别在于数据库中存储数据的结构不一样 因此扫描数据库的效率不一样 2 1GSP算法和SPADE算法 如果序列数据库的规模比较大 则有可能会产生大量的候选序列模式需要对序列数据库进行循环扫描对于序列模式的长度比较长的情况 由于其对应的短的序列模式规模太大 本算法很难处理 类Apriori算法存在的问题 2 2PrefixSpan算法 算法介绍 基于FP增长算法采用分治的思想 不断产生序列数据库的多个更小的投影数据库 然后在各个投影数据库上进行序列模式挖掘 前缀与后缀 假定序列S 则序列 等都是S的前缀 S关于的后缀为 S关于的后缀为 S关于的后缀为 2 2PrefixSpan算法 投影数据库 设 为序列数据库S中的一个序列模式 则 的投影数据库为S中所有以 为前缀的序列相对于 的后缀 记为S 例 序列模式的投影数据库为 2 2PrefixSpan算法 主要步骤 1 得到长度为1的序列模型 2 划分搜索空间 3 找出序列模式的子集 a 找出序列数据库D关于的投影数据库 b 扫描投影数据库 得到局部频繁项 c 递归过程 4 汇集 S S1 Sm S11 S1n Sm1 Smp 2 2PrefixSpan算法 1 1序列模型为 4次 4次 4次 3次 3次 3次 2 划分搜索空间 根据 1 中的结果划分前缀为的子集 前缀为的子集 前缀为的子集等 2 2PrefixSpan算法 3 找出序列模型的子集 a 建立的投影数据库 b 扫描上述投影数据库 找出局部频繁项 分别为 c 递归地寻找以 为前缀的序列模型 4 汇总以上挖掘的序列模型子集 2 2PrefixSpan算法 PrefixSpan算法分析 PrefixSpan算法不需要产生候选序列模式 从而大大缩减了检索空间相对于原始的序列数据库而言 投影数据库的规模不断减小PrefixSpan算法的主要开销在于投影数据库的构造 3 1多维 多层次的序列模式挖掘 购买数码相机的退休顾客很可能在一个月内购买彩色打印机 购买笔记本的年轻人很可能在两周内购买打印机 这些例子的序列模式挖掘都是多维 多层次的 多维体现在 年轻人 与 老人 多层次体现在 彩色打印机 与 打印机 3 2基于约束的序列模式挖掘 1 序列的长度例 顾客在1周内购买的商品序列 2 序列间事务的最大间隔例 用户的Web页面浏