数据仓库与数据挖掘第10章.ppt

第十章 序列模式挖掘 一、序列的概念及定义 二、序列模式挖掘 第一节 序列的概念及定义 1. 什么是序列 设数据库表：顾客交易（顾客id，交易时间，顾客购买项） 同一时间不存在一个顾客进行 两个以上的交易 交易中不考虑顾客购买多少物 品，而只考虑一项物品有没有 被购买 事务发生时间 客户ID 购买项 2004.12.10 2004.12.12 2004.12.15 2004.12.20 2004.12.25 2004.12.25 2004.12.25 2004.12.30 2004.12.30 2004.12.31 2 5 2 2 4 3 1 1 4 4 A，B H C D，F，G C C，E，G C H D，G H 第一节 序列的概念及定义 1. 什么是序列 项目 顾客购买的商品就是项目 项目集 一个项目集是一个非空的项目的集合 序列（Sequence） 一个项目集有序的若干子项目集所构成的排列 第一节 序列的概念及定义 1. 什么是序列 一个顾客的所有事务放在一起就可以看作是一个序列，可以对顾客的事务按时间进行排序 序列模式的数据挖掘就是在所有在一个用户指定的最小支持度的序列中发现最大的序列 第一节 序列的概念及定义 1. 什么是序列 一个顾客的所有事务放在一起就可以看作是一个序列，可以对顾客的事务按时间进行排序 序列模式的数据挖掘就是在所有在一个用户指定的最小支持度的序列中发现最大的序列 第一节 序列的概念及定义 2. 概念及定义 给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值。 序列模式的概念最早是由Agrawal和Srikant 提出的 第一节 序列的概念及定义 2. 概念及定义 项目集(Itemset) 是各种项目组成的集合 序列(Sequence) 是不同项目集(ItemSet)的有序排列，序列s可以表示为s = s1 s2 … sl，sj(1 = j = l)为项目集(Itemset)，也称为序列s的元素 序列的元素(Element) 可表示为(x1 x2 … xm)， xk(1 = k = m)为不同的项目，如果一个序列只有一个项目，则括号可以省略 一个序列包含的所有项目的个数称为序列的长度。长度为l的序列记为l-序列 第一节 序列的概念及定义 2. 概念及定义 设? = a1 a2 …a n，? = b1 b2 … bm，如果存在整数1 = j1 j2 … jn = m，使得a1 ? bj1，a2 ? bj2，…， an ? bjn，则称序列?为序列?的子序列，又称序列?包含序列?，记为? ? ? 序列?在序列数据库S中的支持数为序列数据库S中包含序列?的序列个数，记为Support(?) 给定支持度阈值?，如果序列?在序列数据库中的支持数不低于?，则称序列?为序列模式 长度为l的序列模式记为l-模式 第一节 序列的概念及定义 2. 概念及定义 序列数据库SDB(Sequence Database)是元组(Sid，S)的集合，其中，Sid是对应序列的序号，元组的个数称为序列数据库的大小，记为|SDB| 一个序列Sa在序列数据库SDB中的绝对支持度，即SDB中包含Sa的元组数目，极为sup(Sa )；相对支持度为SDB中包含Sa的元组在整体数据库元组中所占的百分比，即sup(Sa )/ |SDB| 第一节 序列的概念及定义 2. 概念及定义 示例：设序列数据库如下图所示，并设用户指定的最小支持度min-support = 2 序列a(bc)df是序列a(abc)(ac)d(cf)的子序列 序列(ab)c是长度为3的序列模式 Sequence_id Sequence 10 a(abc)(ac)d(cf) 20 (ad)c(bc)(ae) 30 (ef)(ab)(df)cb 40 eg(af)cbc 第一节 序列的概念及定义 3. 序列模式挖掘应用领域 顾客购买行为分析 网络访问模式分析 科学实验分析 疾病治疗早期诊断 自然灾害预测 DNA序列模式分析 第二节 序列模式挖掘 1. 序列模式挖掘 排序阶段 发现频繁项集阶段 转换阶段 序列阶段 最大阶段 第二节 序列模式挖掘 1. 序列模式挖掘 事务发生时间 客户ID 购买项 2004.12.10 2004.12.12 2004.12.15 2004.12.20 2004.12.25 2004.12.25 2004.12.25 2004.12.30 2004.12.30 2004.12.31 2 5 2 2