数据挖掘与商务智能 Data Mining & Business Intelligence

Slides:



Advertisements
Similar presentations
阻塞操作. 在 linux 里,一个等待队列由一个 wait_queue_head_t 类型的结构来描述 等待队列的初始化: static wait_queue_head_t testqueue; init_waitqueue_head(&testqueue);
Advertisements

第六 章数据库访问页 6.1 数据访问页视图 6.2 创建数据访问页 6.3 编辑数据访问页 6.4 查看数据访问页 退出.
Some Knowledge of Machine Learning(1)
频繁模式与关联规则挖掘 林琛 博士、副教授.
CH3 關聯規則 授課老師:簡禎富 講座教授 簡禎富、許嘉裕©2014 著作權所有.
关联.
小学生游戏.
初中数学八年级下册 (苏科版) 10.4 探索三角形 相似的条件(2).
在PHP和MYSQL中实现完美的中文显示
第三章 关联规则挖掘 Association Rule Mining
Advanced Topics in Data Mining: Sequential Patterns
序列模式挖掘算法简介 报告人:邓爱林
Hadoop I/O By ShiChaojie.
强连通分量 无向图 1、任意两顶点连通称该图为连通图 2、否则将其中的极大连通子图称为连通分量 A D C B E 有向图
第8章 關聯分析 王海.
SOA – Experiment 3: Web Services Composition Challenge
李杰 首都经济贸易大学 安全与环境工程学院 个人主页:
数据挖掘: 概念和技术 — Chapter 6 — ©张晓辉 复旦大学 (国际)数据库研究中心
辅导课程六.
元素替换法 ——行列式按行(列)展开(推论)
第十章 IDL访问数据库 10.1 数据库与数据库访问 1、数据库 数据库中数据的组织由低到高分为四级:字段、记录、表、数据库四种。
以ISI平台为例,为您演示一下如何在Endnote文献中查看该文献的References
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
数据挖掘工具性能比较.
动态规划(Dynamic Programming)
基于类关联规则的分类 Classification Based on Class-Association Rules
用event class 从input的root文件中,由DmpDataBuffer::ReadObject读取数据的问题
使用矩阵表示 最小生成树算法.
SOA – Experiment 2: Query Classification Web Service
第4章 非线性规划 4.5 约束最优化方法 2019/4/6 山东大学 软件学院.
数列.
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
第二十二章 曲面积分 §1 第一型曲面积分 §2 第二型曲面积分 §3 高斯公式与斯托克斯公式.
顺序表的删除.
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
VB与Access数据库的连接.
Lightweight Data-flow Analysis for Execution-driven Constraint Solving
实体描述呈现方法的研究 实验评估 2019/5/1.
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
第4章 Excel电子表格制作软件 4.4 函数(一).
正切函数的图象和性质 周期函数定义: 一般地,对于函数 (x),如果存在一个非零常数T,使得当x取定义域内的每一个值时,都有
iSIGHT 基本培训 使用 Excel的栅栏问题
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
3.1.2 空间向量的数量积运算 1.了解空间向量夹角的概念及表示方法. 2.掌握空间向量数量积的计算方法及应用.
3.16 枚举算法及其程序实现 ——数组的作用.
《手把手教你学STM32-STemWin》 主讲人 :正点原子团队 硬件平台:正点原子STM32开发板 版权所有:广州市星翼电子科技有限公司
1.2 子集、补集、全集习题课.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
Visual Basic程序设计 第13章 访问数据库
第七、八次实验要求.
基于Apriori性质的多维关联规则数据挖掘
《工程制图基础》 第五讲 投影变换.
分数再认识三 真假带分数的练习课.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
生 物 信 息 学 Bioinformatics 巩晶 癌症研究中心 山东大学 医学院
第六章 Excel的应用 五、EXCEL的数据库功能 1、Excel的数据库及其结构 2、Excel下的数据排序 (1)Excel的字段名行
基于列存储的RDF数据管理 朱敏
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
第十七讲 密码执行(1).
创建、启动和关闭Activity 本讲大纲: 1、创建Activity 2、配置Activity 3、启动和关闭Activity
使用Fragment 本讲大纲: 1、创建Fragment 2、在Activity中添加Fragment
§4.5 最大公因式的矩阵求法( Ⅱ ).
RefWorks使用指南 归档、管理个人参考文献.
培训课件 AB 变频器的接线、操作及参数的备份 设备动力科.
最小生成树 最优二叉树.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
《手把手教你学STM32-STemWin》 主讲人 :正点原子团队 硬件平台:正点原子STM32开发板 版权所有:广州市星翼电子科技有限公司
9.3多项式乘多项式.
Presentation transcript:

数据挖掘与商务智能 Data Mining & Business Intelligence 第六章 序列模式挖掘 西安电子科技大学 软件学院 主讲人:黄健斌

内容提纲 序列模式挖掘简介 序列模式挖掘的应用背景 序列模式挖掘算法概述 GSP算法 SPADE算法 PrefixSpan算法 CloSpan算法 利用SPSS软件挖掘频繁序列模式

序列模式挖掘简介 序列模式的概念最早是由Agrawal和Srikant 提出的。 动机:大型连锁超市的交易数据有一系列的用户事务数据库,每一条记录包括用户的ID,事务发生的时间和事务涉及的项目。如果能在其中挖掘涉及事务间关联关系的模式,即用户几次购买行为间的联系,可以采取更有针对性的营销措施。

序列模式挖掘的应用背景 应用领域: 客户购买行为模式预测 Web访问模式预测 疾病诊断 · · · · · ·

应用案例1:客户购买行为模式分析 B2C电子商务网站可以根据客户购买纪录来分析客户购买行为模式,从而进行有针对性的营销策略。 ID User transaction sequence 1 ………………………………………………………….. 2 ……………………………………………… 3 …………………………………………………….. 4 …………………………………. 图书交易网站将用户购物纪录整合成用户购物序列集合 相关商品推荐:如果用户购买了书籍“UML语言”, 则推荐“Visio2003实用技巧” 得到用户购物行为序列模式 <(“UML语言”)(“Visio2003实用技巧”)>

应用案例2:Web访问模式分析 大型网站的网站地图(site map)往往具有复杂的拓扑结构。用户访问序列模式的挖掘有助于改进网站地图的拓扑结构。比如用户经常访问网页web1然后访问web2,而在网站地图中二者距离较远,就有必要调整网站地图,缩短它们的距离,甚至直接增加一条链接。 Index 网站入口 web1 web2

应用案例3:疾病诊断 医疗领域的专家系统可以作为疾病诊断的辅助决策手段。对应特定的疾病,众多该类病人的症状按时间顺序被记录。自动分析该纪录可以发现对应此类疾病普适的症状模式。每种疾病和对应的一系列症状模式被加入到知识库后,专家系统就可以依此来辅助人类专家进行疾病诊断。 例: 通过分析大量曾患A类疾病的病人发病纪录,发现以下症状发生的序列模式:<(眩晕) (两天后低烧37-38度) > 如果病人具有以上症状,则有可能患A类疾病

事务数据库实例 例:一个事务数据库,一个事务代表一笔交易,一个单项代表交易的商品,单项属性中的数字记录的是商品ID

序列数据库 一般为了方便处理,需要把事务数据库转化为序列数据库。方法是把用户ID相同的记录合并,有时每个事务的发生时间可以忽略,仅保持事务间的顺序关系。

基本概念 项集(Itemset)是所有在序列数据库出现过的单项组成的集合 例:对一个用户购买记录的序列数据库来说,项集包含用户购买的所有商品,一种商品就是一个单项。通常每个单项有一个唯一的ID,在数据库中记录的是单项的ID。

基本概念 元素(Element)可表示为(x1x2…xm), xk(1 <= k <= m)为不同的单项。元素内的单项不考虑顺序关系,一般默认按照ID的字典序排列. 在用户事务数据库里,一个事务就是一个元素

基本概念 序列(Sequence)是不同元素(Element)的有序排列,序列s可以表示为s = <s1s2…sl>,sj(1 <= j <= l)为序列s的元素 一个序列包含的所有单项的个数称为序列的长度。长度为l的序列记为l-序列

举例 例:一条序列<(10,20)30(40,60,70)>有3个元素,分别是(10 20),30,(40 60 70 ); 例:一条序列<(10,20)30(40,60,70)>有3个元素,分别是(10 20),30,(40 60 70 ); 3个事务的发生时间是由前到后。这条序列是一个6-序列。

基本概念 序列在序列数据库S中的支持度为序列数据库S中包含序列的序列个数,记为Support() 设序列 = <a1a2…an>,序列 = <b1b2…bm>,ai 和bi都是元素。如果存在整数1 <= j1 < j2 <…< jn <= m,使得a1  bj1,a2  bj2,…, an  bjn,则称序列为序列的子序列,又称序列包含序列,记为  。 序列在序列数据库S中的支持度为序列数据库S中包含序列的序列个数,记为Support() 给定支持度阈值,如果序列在序列数据库中的支持度不低于,则称序列为序列模式 长度为l的序列模式记为l-模式

例子 例子:设序列数据库如下图所示,并设用户指定的最小支持度 min-support = 2。 Sid Sequence 10 <a(abc)(ac)d(cf)> 20 <(ad)c(bc)(ae)> 30 <(ef)(ab)(df)cb> 40 <(af)cbc> 序列<a(bc)df>是序列<a(abc)(ac)d(cf)>的子序列 序列<(ab)c>是长度为3的序列模式

序列模式先验特性 Apriori (Agrawal & Sirkant’94) 特性 min_sup =2 如果序列s是非频繁序列,则s的所有超集序列都是非频繁的 <a(bd)bcb(ade)> 50 <(be)(ce)d> 40 <(ah)(bf)abf> 30 <(bf)(ce)b(fg)> 20 <(bd)cb(ac)> 10 Sequence Seq. ID min_sup =2 <hb> 非频繁 则: <hab> 非频繁 <(ah)b> 非频繁

序列模式 VS 关联规则 问题 序列模式挖掘 关联规则挖掘 数据集 序列数据库 事务数据库 关注点 单项间在同一事务内以及事务间的关系 单项间在同一事务内的关系

序列模式挖掘算法概述 类Apriori算法 该类算法基于Apriori理论,即序列模式的任一子序列也是序列模式。算法首先自底向上的根据较短的序列模式生成较长的候选序列模式,然后计算候选序列模式的支持度。典型的代表有GSP算法, spade算法等 基于划分的模式生长算法 该类算法基于分治的思想,迭代的将原始数据集进行划分,减少数据规模,同时在划分的过程中动态的挖掘序列模式,并将新发现的序列模式作为新的划分元。典型的代表有FreeSpan算法和prefixSpan算法

知识回顾 基本概念 支持度计数:包含特定项集的事务的个数: 关联规则:形如 的蕴涵表达式 支持度:同时包含X,Y的事务在所有事务中所占的比例 关联规则:形如 的蕴涵表达式 支持度:同时包含X,Y的事务在所有事务中所占的比例 置信度:事务X出现时Y出现的频繁程度 频繁项集:满足最小支持的项集

知识回顾 定理 关联规则挖掘的任务划分: 先验原理:如果一个项集是频繁的,那它的所有子集一定都是 频繁的 先验原理:如果一个项集是频繁的,那它的所有子集一定都是 频繁的 定理1:如果规则 不满足置信度阈值,则形如 的规则一定也不满足置信度阈值,其中 X'是 X的子集 关联规则挖掘的任务划分: 频繁项集的产生(候选( 产生 ),剪枝(基于先验原理)) 规则的产生(逐层方法来产生关联规则,定理1剪枝)

知识回顾 Apriori算法伪代码: Ck: Candidate itemset of size k Fk : frequent itemset of size k F1 = {frequent items}; for (k = 1; Fk !=; k++) do begin Ck+1 = candidates generated from Fk ; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t Fk+1 = candidates in Ck+1 with min_support end return k Fk;

如果关联规则产生自同一项集,则置信度满足单调性 知识回顾 支持度度量满足单调性(X'为X的子集) 置信度一般不满足单调性(X'为X的子集) 如果关联规则产生自同一项集,则置信度满足单调性

知识回顾 Pruned supersets 基于支持度的候选项集剪枝

知识回顾 基于置信度的候选规则剪枝 Pruned Rules Low Confidence Rule

GSP算法 算法思想(候选产生测试法): 类似于Apriori算法,采用冗余候选模式的剪除策略和特殊的数据结构-----哈希树来实现候选模式的快速访存。

GSP算法描述 F1 C2  F2  C3  F3  C4  F4  …… 根据长度为i 的种子集Fi ,通过连接操作和修剪操作生成长度为i+1的候选序列模式Ci+1;扫描序列数据库,计算每个候选序列模式的支持度,产生长度为i+1的序列模式Fi+1,并将Fi+1作为新的种子集 重复第二步,直到没有新的序列模式或新的候选序列模式产生为止 F1 C2  F2  C3  F3  C4  F4  ……

GSP算法伪代码 输入:大项集阶段转换后的序列数据库DT。 输出:最大序列 (1) L1 = {large 1-sequences}; (2) FOR (k = 2;Lk-1  ;k++) DO BEGIN (3) Ck = GSPgenerate(Lk-1); (4) FOR each customer-sequence c in the database DT DO (5) Increment the count of all candidates in Ck that are contained in c; (6) Lk = Candidates in Ck with minimum support; (7) END; (8) Answer = Maximal Sequences in ∪kLk;

GSP算法 产生候选序列模式主要分两步: 连接阶段:如果去掉序列模式s1的第一个元素与去掉序列模式s2的最后一个元素所得到的序列相同,则可以将s1与s2进行连接,即将s2的最后一个元素添加到s1中 剪枝阶段:若某候选序列模式的某个子序列不是序列模式,则此候选序列模式不可能是序列模式,将它从候选序列模式中删除 L1 C2  L2  C3  L3  C4  L4  ……

GSP算法 序列合并过程 序列s1与另一个序列s2合并,s2的最后一个单项可以作为最后一个单项合并到s1的最后一个元素中,也可以作为一个单独的元素。取决于以下条件: 如果s2的最后两个单项属于相同的元素,则s2的最后一个单项在合并后的序列中是s1的最后一个元素的一部分。 如果s2的最后两个单项属于不同的元素,则s2的最后一个单项在合并后的序列中成为连接到s1尾部的元素。

GSP算法 候选序列模式的支持度计算:对于给定的候选序列模式集合C,扫描序列数据库,对于其中的每一条序列s,找出集合C中被s所包含的所有候选序列模式,并增加其支持度计数

举例

哈希树 GSP采用哈希树存储候选序列模式。哈希树的节点分为三类: 根节点 内部节点 叶子节点

哈希树 根节点和内部节点中存放的是一个哈希表,每个哈希表项指向其它的节点。而叶子节点内存放的是一组候选序列模式。 例:

添加候选序列模式 从根节点开始,用哈希函数对序列的第一个元素做映射来决定从哪个分支向下,依次在第n层对序列的第n个单项作映射来决定从哪个分支向下,直到到达一个叶子节点。将序列储存在此叶子节点。 初始时所有节点都是叶子节点,当一个叶子节点所存放的序列数目达到一个阈值,它将转化为一个内部节点。

计算候选序列模式的支持度 给定一个序列s是序列数据库的一个记录: 对于内部节点,如果s是通过对单项x做哈希映射来到此节点的,则对s中每一个和x在一个元素中的单项以及在x所在元素之后第一个元素的第一个单项做哈希映射,然后从相应的表项向下迭代做操作 2)或 3)。 对一个叶子节点,检查每个候选序列模式c是不是s的子序列.如果是相应的候选序列模式支持度加一。

计算候选序列模式的支持度 hash树存储的优点 这种计算候选序列的支持度的方法避免了大量无用的扫描,对于一条序列,仅检验那些最有可能成为它子序列的候选序列模式。扫描的时间复杂度由O(n*m)降为O(n*t),其中n表示序列数量,m表示候选序列模式的数量,t代表哈希树叶子节点的最大容量

GSP算法存在的主要问题 如果序列数据库的规模比较大,则有可能会产生大量的候选序列模式 需要对序列数据库进行循环扫描 对于序列模式的长度比较长的情况,由于其对应的短的序列模式规模太大,本算法很难处理

SPADE算法 SPADE(Sequential PAttern Discovery using Equivalent Class) developed by Zaki 2001 基于Apriori的垂直数据格式的序列模式挖掘算法 通过简单的连接K序列任意长度为(k-1)子序列的ID_list,可以确定任意K序列的支持度。ID_list的长度等于K序列的支持度,即可确定是否是序列模式。 数据库表示形式: < itemset: (sequence_ID,event_ID) >

SPADE算法 minsup =2

SPADE算法总结 优点: 缺点: 垂直数据格式的使用连同ID_list的创建,可以减少对序列数据库的扫描。 同GSP,使用宽度优先和先验剪枝产生很大的候选集。

序列模式挖掘算法概述 基于划分的模式生长算法 该类算法基于分治的思想,迭代的将原始数据集进行划分,减少数据规模,同时在划分的过程中动态的挖掘序列模式,并将新发现的序列模式作为新的划分元。典型的代表有FreeSpan算法和PrefixSpan算法

PrefixSpan算法 算法思想:基于FP-Growth算法 Pei, et al.@ICDE’01 采用分治的思想,不断产生序列数据库的多个更小的投影数据库,然后在各个投影数据库上进行序列模式挖掘

知识回顾 FP-Growth算法 通过逐个读入事务,并把每一个事务映射到FP树中的一条路径的方法构造FP-Tree。

知识回顾 null After reading TID=1: A:1 B:1 After reading TID=2: null B:1 C:1 D:1

Pointers are used to assist frequent itemset generation 知识回顾 Transaction Database null B:3 A:7 B:5 C:3 C:1 D:1 Header table D:1 C:3 E:1 D:1 E:1 D:1 E:1 D:1 Pointers are used to assist frequent itemset generation

基本概念 前缀:设每个元素中的所有单项按照字典序排列。给定序列 = <e1e2…en>, = <e1’ e2’… em’> (m  n) ,如果ei’ = ei (i  m - 1), em’  em,并且(em - em’)中的单项均在em’中单项的后面, 则称是的前缀 例:序列<(ab)> 是序列<(abd)(acd)> 的一个前缀;序列<(ad)>则不是 。

基本概念 投影:给定序列和 ,如果是的子序列,则关于的投影’必须满足: 是’的前缀,’是的满足上述条件的最大子序列 例:对于 序列 =<(ab)(acd)>, 其子序列 = <(b)>的投影是’ = <(b)(acd)>; <(ab)>的投影是原序列<(ab)(acd)>。

基本概念 后缀: 序列关于子序列 = <e1e2… em-1em’>的投影为’ = <e1e2… en> (n >= m),则序列关于子序列的后缀为<em”em+1… en>, 其中em” = (em - em’) 例:对于 序列<(ab)(acd)>,其子序列<(b)>的投影是<(b)(acd)>,则<(ab)(acd)>对于<(b)>的后缀为<(acd)>。 ※ 总结:后缀即是投影去掉它自身;

<(abc)(ac)d(cf)> <(_bc)(ac)d(cf)> <(_c)(ac)d(cf)> 举例 例: <a(abc)(ac)d(cf)> <a> <(abc)(ac)d(cf)> <aa> <(_bc)(ac)d(cf)> <a(ab)> <a(abc)> <ab> <(_c)(ac)d(cf)>

基本概念 投影数据库:设为序列数据库S中的一个序列模式,则的投影数据库为S中所有以为前缀的序列相对于的后缀,记为S|

举例 例:对于如下的序列数据库生成一系列的投影数据库 Sid Sequence 10 <a(abc)(ac)d(cf)> 20 <(ad)c(bc)(ae)> 30 <(ef)(ab)(df)cb> 40 <(af)cbc>

举例 扫描序列数据库S,产生长度为1的序列模式有:<a> : 4, <b>:4, <c> : 4, <d> : 3, <e> : 3, <f> : 3 序列模式的全集必然可以分为分别以<a>,<b>,<c>,<d>,<e>和<f>为前缀的序列模式的集合,构造不同前缀所对应的投影数据库,结果如下页图所示

举例 Prefix Project Database <a> <(abc)(ac)d(cf)> <(_d)c(bc)(ae)> <(_b)(df)cb> <(_f)cbc> <b> <(_c)(ac)d(cf)> <(_c)(ae)> <(df)cb> <c> <c> <(ac)d(cf)> <(bc)(ae)> <b> <bc> <d> <(cf)> <c(bc)(ae)> <(_f)cb> <e> <(_f)(ab)(df)cb> <(af)cbc> <f> <(ab)(df)cb> <cbc>

Prefix-Span算法描述 扫描序列数据库,生成所有长度为1的序列模式 根据长度为1的序列模式,生成相应的投影数据库 在相应的投影数据库上重复上述步骤,直到在相应的投影数据库上不能产生长度为1的序列模式为止 分别对不同的投影数据库重复上述过程,直到没有新的长度为1的序列模式产生为止 S11 …… … S1 … S S1n …… Sm Sm1 …… … Smp ……

算法伪码 PrefixSpan算法 输入:序列数据库S及最小支持度阈值min_sup 输出:所有的序列模式

算法伪码 子程序PrefixSpan(, L, S|) 参数: : 一个序列模式 ; L:序列模式的长度 ; S| :如果为空,则为S,否则为的投影数据库 扫描S|,找到满足下述要求的长度为1的序列模式b: b可以添加到的最后一个元素中并为序列模式 <b>可以作为的最后一个元素并为序列模式 对每个生成的序列模式b,将b添加到形成序列模式’,并输出’ 对每个’,构造’的投影数据库S|’ ,并调用子程序PrefixSpan(’, L + 1, S|’)

PrefixSpan算法 序列合并过程 序列s1与另一个序列s2合并,s2的最后一个单项可以作为最后一个单项合并到s1的最后一个单项中,也可以作为一个单独的单项。取决于以下条件: 如果s2的最后两个单项属于相同的元素,则s2的最后一个单项在合并后的序列中是s1的最后一个元素的一部分。 如果s2的最后两个单项属于不同的元素,则s2的最后一个单项在合并后的序列中成为连接到s1尾部的元素。

举例 minsup = 2 <(1, 2) (1,3)> <(3,4) (5, 6, 7)> 给定如下的序列数据库: Sid sequence 1 <(1, 2) (1,3)> 2 <(3,4) (5, 6, 7)> 3 <(1,3) (8) (7)> 4 <(8)>

举例 找出频繁单项:1,3,7,8;然后除去非频繁的单项: <(1) (1,3)> <(3)(7)> Sid sequence 1 <(1) (1,3)> 2 <(3)(7)> 3 <(1,3)(8)(7)> 4 <(8)>

举例 为频繁1序列(频繁单项)生成投影数据库: <(1) (1,3)> <(3)(7)> Sid sequence 1 <(1) (1,3)> 2 <(3)(7)> 3 <(1,3)(8)(7)> 4 <(8)> Sid Suffix for prefix <(1)> 1 <(1,3)> 3 <(_3)(8)(7)>

举例 为频繁1序列(频繁单项)生成投影数据库: <(1) (1,3)> <(3)(7)> Sid sequence 1 <(1) (1,3)> 2 <(3)(7)> 3 <(1,3)(8)(7)> 4 <(8)> Sid Suffix for prefix <(3)> 1 <> 2 <(7)> 3 <(8)(7)>

举例 Suffix for prefix <(7)> 2 3 Suffix for prefix <(8)> 3 Sid Suffix for prefix <(7)> 2 <> 3 Sid Suffix for prefix <(8)> 3 <(7)> 4 <>

举例 在上面的投影数据库中,前缀<(1)>的投影数据库中还有频繁单项_3,前缀<(3)>的投影数据库中还有频繁单项7. 生成频繁2序列<(1,3)>,<(3)(7)>, 然后为其生成投影数据库.其中没有频繁项目,算法终止。 Sid Suffix for prefix <(1,3)> 1 <> 3 <(8)(7)> Sid Suffix for prefix <(3)(7)> 2 <> 3

PrefixSpan算法分析 PrefixSpan算法不需要产生候选序列模式,从而大大缩减了检索空间 相对于原始的序列数据库而言,投影数据库的规模不断减小 PrefixSpan算法的主要开销在于投影数据库的构造。可以通过伪投影技术进行效率提升。

伪投影 当数据库可以直接放入内存时,并不需要构造所有的序列模式对应的投影数据库,我们可以使用指向数据库中序列的指针及其偏移量作为伪投影 例子:假设上述序列数据库可以放入内存,在构造a投影数据库时,序列 S1 = <a(abc)(ac)d(cf)>所对应的伪投影为:一个指向S1的指针,指针偏移设定为2。同样的,序列S1的<ab>投影数据库对应的伪投影为:一个指向S1的指针,指针偏移设定为4

伪投影与物理投影对比 伪投影避免了物理投影拷贝后缀的过程 但是当数据库不可以放入内存中时,伪投影技术是非常低效的 建议策略: 当数据库可以存放入主内存中,伪投影在时间和空间上都是很高效的 但是当数据库不可以放入内存中时,伪投影技术是非常低效的 硬盘随机访问时很低效的 建议策略: 集成伪投影和物理投影技术 当数据集可以放入内存时候,使用伪投影技术

算法效率比较

伪投影与物理投影比较

闭序列模式挖掘 闭序列模式:如果不存在序列s',其中s'是s的真超序列,并且s'与s具有相同的支持度,那么称s为闭序列模式 例子:以下序列哪一个为闭序列模式? <abc>: 20, <abcd>:20, <abcde>: 15 CloSpan:Mining Closed Sequential Patterns in Large Datasets Xifeng Yan. Jiawei Han

序列扩展 项集扩展: ,同时 序列扩展:

字典序树 字典序: ,同时 ,如果满足下列条件之一,则t<t' 举例:(a,f)<(b,f),(a,b)<(a,b,c)

字典序树 字典序序列 如果s'=s◊p,则s<s';(序列大于它的前缀序列) 如果s=a◊ip,同时s'=a◊sp',无论p与p'之间的序列关系都有s<s';(项集扩展小于序列扩展) 如果s=a◊ip,s'=a◊ip',p<p'则有s<s';(同种扩展与后缀大小相关) 如果s=a◊sp,同时s'=a◊sp',p<p'则s<s'; 举例:<(ab)> < <(ab)(a)>,<(ab)> < <(a)(b)>

字典序序列树构造 字典序序列树构造

示例

示例

PrefixSpan算法

PrefixSpan算法 特点:在前缀搜索树上搜索所有的频繁项集 终止条件:序列s的投影数据库中序列的个数小于min_sup

优化策略 引理1:给定一个子序列s和它的投影数据库Ds. 如果存在a,a是Ds中所有具有相同扩展类型序列的公共前缀。那么对于任意的b,如果s◊b是闭的,a肯定是b的前缀。 即我们只需要搜索分支s◊a,而不用搜索分支s◊b。 举例:Ds={<(d)(e)(af)>,<(d)(e)(fg)>},因为<(d)(e)>是Ds中的所有序列的公共前缀,因此D中以s为前缀但不包含序列<(d)(e)>的序列都不可能是闭序列。因此我们不需要构造序列s◊e

优化策略 引理2:给定一个序列s和它的投影数据库Ds. 如果存在a,对Ds中所有序列项a总是出现在项b之前(无论他们是在同一个元素中还是不同元素中),那么Ds◊a◊b=Ds◊b。因此对于任意的r,s◊b◊r不可能是闭序列。则不需要搜索分支s◊b

优化策略 投影数据库等价性

优化策略 引理3:给定两个序列s和s',同时s是s'的子序列,且L(Ds)=L(Ds'),那么对于任意的r,support(s◊r)=supprot(s'◊r)

优化策略 推论1:如果一个序列s<s'并且 .如果有L(Ds) =L(Ds'),那么就不需要在继续搜索s'在前缀搜索树上的分支。称s'是s的一个向后子模式 举例:对于如下序列数据库有L(D<(f)>)=L(D<(af)>),则可以得出D<(f)>=D<(af)>.即:不需要一一比较D<(f)>和D<(af)>z中的所有序列是否相等,而只需要比较这两个集合的大小即可

优化策略 推论2:如果一个序列s<s'并且 .如果有L(Ds) =L(Ds'),那么就可以利用s分支代替搜索s'在前缀搜索树上的分支。称s'是s的一个向后超模式 举例:对于如下序列数据库有L(D<(b)>)=L(D<(e)(b)>),则可以得出D<(b)>=D<(e)(b)>.即:不需要增长序列<(e)(b)>,因为<(e)(b)>的投影数据库与<(b)>的投影数据相同

CloSpan算法

CloSpan算法

Prefix-Span与Clospan的比较

利用SPSS软件挖掘频繁序列模式

利用SPSS软件挖掘频繁序列模式 实验主题 实验任务 应用序列模式挖掘购物篮,建立聪明的 营销策略 应用序列模式挖掘购物篮,建立聪明的 营销策略 实验任务 利用IBM SPSS Modeler软件提供的序列模式挖掘功能对购物篮进行序列模式挖掘,更深入的挖掘超市购物记录,建模后分析实验结果,并完成实验报告。

案例分析 案例分析 实验将采用购物篮作为实验案例,输入数据如下表所示,给出了五个用户的购物清单: <a(bd)bcb(ade)> 5 <(be)(ce)d> 4 <(ah)(bf)abf> 3 <(bf)(ce)b(fg)> 2 <(bd)cb(ac)> 1 Sequence Seq. ID

实验步骤 1. 打开软件Clementine 12.0后如下图所示:

实验步骤 2.首先我们要将需要分析的购物篮数据输入到软件中,这里我们采用手动输入的方式 在“选项板区”找到“源”中的“手动输入”,双击“手动输入”,将其添加到数据流区域,如下图:

实验步骤 双击数据流区域的“用户输入”,得到如下对话框:

实验步骤 选中“生成数据”的方式为“状况良好”,并输入数据如下: id代表用户id,time标识购物的先后顺序,a-h代表商品,F代表未购买,T代表已购买。值区域每一列代表一个购物项。如第一列的含义为:用户1第1次购买的商品为b和d。

实验步骤 点击上图中的“类型”,修改“方向”栏如下:

实验步骤 3.要分析的数据输入完毕后,我们需要选择分析数据的模型,这里我们选择“序列”模型对数据进行分析。 单击选中数据流区域的“用户输入”,再双击“选项板区”中“建模”下的“序列”,将其添加至数据流区域,它将自动与“用户输入”连接,如下:

实验步骤 双击数据流区域的“无目标”,得到对话框如下:

实验步骤 将对话框填写如下,点击“执行” 注:点击 可以看到可选字段。

实验步骤 你将在右上角看到分析结果节点,如右图: 双击“id”将其添加到数据流区域,如下:

实验步骤 双击数据流区域中的“id”,得到分析结果如下:

实验步骤 点击上图中的“ ”,选择“显示全部”,则实验结果如下:

实验结果分析

实验结果分析 下面我们以 为例,对实验结果进行分析。第一栏为前项,其有两行构成,表示先购买c,再购买b。后项为d。实例为1,表示先购买了c,再购买了b,则之后购买了d的个体个数。规则支持为20%,即实例与样本总体的比值,即1/5。出现前项的个体个数,即先购买了c,再购买了b的个体个数,为3个,故置信度为实例/前项的个体个数,即1/3,为33.333%。而支持度与时间先后无关,则它表示购买了b、c、d三件商品的个体个数与样本总体的比值,而购买了b、c、d三件商品的个体个数为3个,则3/5等于60%。

Thank you!