生产管理知识_序列及apriori生成候选算法

序列 报告人 熊赟 内容概要 基本概念 其他 类Apriori生成候选算法 相似性搜索 FreeSpan算法 PrefixSpan算法 第6章序列 6 1基本概念6 2原理6 3核心算法6 4其他 序列是不同项集的有序排列 定义1 序列 I i1i2 im 是项集 ik 1 其中sj 1 j n 为项集 也称序列S的元素 即sj I 每个元素由不同项组成 序列的元素可表示为 i1i2 ik 若一个序列只有一个项 则括号可以省略 序列包含的所有项的个数称为序列的长度 长度为l的序列记为l 序列 序列 定义2 子序列 序列T 是另一个序列S 的子序列 满足下面条件 对于每一个j 1 j m 1 有ij ij 1且对于每一个j 1 j m 存在1 k n 使得tij sk 即序列S包含序列T 用符号 表示 被包含于 序列T是序列S的子序列可记为T S 称T为S的子序列 S为T的超序列 若一个序列S不包含在任何其他的序列之中 则称序列S是最大的 子序列 定义3 支持度 序列数据库D是元组的集合 sid为序列标识号 如果序列T是S的子序列 即T S 称元组包含序列T 则序列T在序列数据库D中的支持度是数据库中包含T的元组数 即supportD T D T S 记作support T 序列支持度 定义4 频繁序列模式 给定正整数 为支持度阈值 如果数据库中最少有 个元组包含序列S 即support S 则称序列S为序列数据库D中的一个 频繁 序列模式 长度为l的序列模式称为l 模式 序列模式挖掘的任务就是找出数据库中所有的序列模式 即那些在序列集合中出现频率超过最小支持度 用户指定最小支持度阈值 的子序列 频繁序列模式 定义5 序列关联规则 对于给定的项集I i1i2 im 以及序列S T 形如S T的表达式称为序列关联规则 序列关联规则 置信度 支持度 序列关联规则 序列关联规则S T的支持度是支持序列S和T的顾客数占总顾客数之比 序列关联规则S T的置信度记为 是支持序列S和T的顾客数与仅支持S的顾客数之比 序列模式挖掘阶段 排序阶段发现频繁项集阶段转换阶段序列阶段最大阶段 由客户标识及交易发生的时间为关键字所排序的数据库 排序阶段 客户序列描述数据库 频繁项集分别是 C D G D G 和 H 发现频繁项集阶段 转换后的数据库 客户序列 转换阶段 核心算法 AprioriAll AprioriSome算法FreeSpan PrefixSpan算法 序列阶段最大阶段 AprioriAll算法 基本思想 AprioriAll算法 AprioriAll算法 L1 L2 AprioriAll算法 L3 L4 AprioriAll算法 最大的频繁序列 AprioriSome算法 基本思想 算法分为两个阶段 前阶段 只对一定长度的序列计数 next k 函数即Ck生成Lk后阶段 对前阶段已确定的Lk确定为最大序列对前阶段没有生成Lk 先删除所有在Ck中包含在Li中的序列 再对Ck计数生成Lk AprioriSome算法 L1 L2 next last 2k AprioriSome算法 C3 C4 修剪 AprioriSome算法 C5为空结束前阶段进入回溯阶段 删除了L4的子序列后的C3再计数发现是最大3序列 L4 AprioriSome算法 最大的频繁序列 除以外L2中所有的序列都被删除L1中所有的序列都被删除 类Apriori算法有以下缺点 有可能生成庞大众多的候选序列 多遍扫描数据库 不易发生长度较大的序列模式 序列模式越长 所需要生成的序列就越多 FreeSpan算法频繁模式投影的序列模式挖掘Frequentpattern projectedSequentialpatternmining 基本思想 基于数据库投影和分片技术 利用频繁项递归地将序列数据库投影到更小的投影数据库集中 在每个投影数据库中生成子序列片段 FreeSpan算法 序列数据库最小支持度设为2 FreeSpan算法 1 找到频繁项集L1频繁项按支持度降序排列形成频繁项列表 f list 根据f list 序列模式集被分为不相交的六个子集 1 只包含项f 分而自治策略 FreeSpan算法 2 A 构造频繁项矩阵F用于生成长度为2的序列模式 投影数据库集用于生成长度为3及更长的序列模式F是一个三角矩阵F j k 1 j m 1 k j 其中F j j 1 j m 仅有一个计数值 而其他每个F j k 1 j m 1 k j 有三个计数值 A B C 序列模式 的投影数据库是含有 的序列集的子序列 非频繁项及 后的项也被删除 F矩阵图 1b 2c 3a 4d 5e 6f 1b 2c 3a 4d 5e 6f F j j 仅有一个计数值 F j k 有三个计数值 A B C 序列 FreeSpan算法 2 B 生成长度为2的序列模式标记循环项模式和投影数据库 循环项模式标记形如 i j 其中 表示两种形式 投影数据库标记形如 i j bp bq bp bq 表示在子序列挖掘过程中与 i j 合在一起生成长度更长的序列模式的频繁项集 FreeSpan算法 FreeSpan算法 2 C 再次扫描数据库S 生成循环项模式和投影数据库 b f b d 2 2 2 2 2 2 2 2 2 2 2 四个投影数据库如下图 FreeSpan算法 2 D 对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式 FreeSpan算法 给定序列数据库S及最小支持度阈值 1 扫描序列数据库S 找到S中的频繁项集 并以降序排列生成f list列表 2 执行下面步骤 a 第一遍扫描数据库S 构造频繁项矩阵 b 生成长度为2的序列模式及标记循环项模式和投影数据库 c 再次扫描数据库S 生成循环项模式和投影数据库 d 对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式 PrefixSpan算法 通过前缀投影挖掘序列模式 Prefix projectedSequentialpatternmining 基本思想 序列数据库投影时 并不考虑所有可能出现的频繁子序列 而只检验前缀序列 然后把相应的后缀序列投影成投影数据库 每个投影数据库中 只检查局部频繁模式 不需要生成候选序列 例 前缀 给定序列 m n 如果ei ei i m 1 em em 并且 em em 中的项目均在em 中项目的后面 则称 是 的前缀 投影 给定序列 和 其中 是 的子序列 即 的子序列 被称为 关于前缀 的投影 当且仅当1 是 的前缀2 不存在 的超集 即 使得 是 的子序列并且 是 的前缀 后缀 序列 关于子序列 的投影为 n m 则序列 关于子序列 的后缀为 其中em em em 算法描述 扫描序列数据库 生成所有长度为1的序列模式根据长度为1的序列模式 生成相应的投影数据库在相应的投影数据库上重复上述步骤 直到在相应的投影数据库上不能产生序列模式为止 S S1 Sm S11 S1n Sm1 Smp PrefixSpan算法 PrefixSpan算法 定义1 投影数据库 设 为序列数据库S中的一个序列模式 则 的投影数据库为S中所有以 为前缀的序列相对于 的后缀 记为S 例 投影数据库 由4个后缀序列组成 投影数据库 PrefixSpan算法 PrefixSpan算法 查找长度为1的序列模式 4 4 4 3 3 3分割搜索空间序列模式集可按6个前缀被划分为六个子集 1 包含前缀的子集 6 包含前缀的子集 寻找序列模式的子集 构建并递归挖掘投影数据库 PrefixSpan算法 寻找具有前缀的序列模式 投影数据库 由4个后缀序列组成 扫描 投影数据库一遍 找到含有前缀的长度为2的序列模式 包括 2 4 2 4 2 2 递归 所有具有前缀的序列划分为6个子集 1 包含前缀的子集 6 包含前缀的子集 投影数据库 不产生任何频繁子序列 结束 投影数据库 包含前缀的序列模式有 即 投影数据库 序列模式 即 投影数据库 投影数据库 投影数据库 包含前缀的序列模式有 找到含有前缀的序列模式 包括 子程序PrefixSpan L S 参数 一个序列模式 L 序列模式 的长度S 如果 不为空时 为 投影数据库 否则为投影数据库S 1扫描S 找到频繁项b b满足 a b可以作为 的最后一个元素 形成一个序列模式 或者b 可以追加到 上 形成一个序列模式 2