数据挖掘-CHAPTER8-序列数据挖掘

1、1Chapter 8. 序列(xli)数据挖掘1共五十四页序列(xli)数据库和序列(xli)模式挖掘事务数据库vs. 序列数据库频繁模式 vs. (频繁) 序列模式序列模式挖掘的应用顾客购物序列: 在3个月内, 先买计算机, 然后买 CD-ROM, 再后买数字照相机.医疗处治(chzh), 自然灾害 (例如, 地震), 科学 和 工程进度, 股票 和市场等.电话呼叫模式, Web日志 点击流DNA 序列和基因结构2共五十四页什么是序列(xli)模式挖掘?给定一个(y )序列的集合, 找出所有的 频繁 子序列序列：事件的有序列表一个 序列数据库 一个 序列 : 一个元素可能包含一个项集.在一个

2、元素中的项是无序的,我们可以用字典序列出它们. 是 的子序列给定 支持度阈值 min_sup =2, 是一个 序列模式SIDsequence102030403共五十四页序列(xli)模式挖掘的挑战大量的 可能的序列模式隐藏在数据库中挖掘算法应当 可能的话, 找出满足最小支持度阈值的模式的完全集高度 有效的, 可伸缩的, 仅涉及不多次数的数据库扫描可以与各种用户指定(zhdng)的约束结合4共五十四页序列(xli)模式挖掘研究概念引进和最初的 类Apriori算法R. Agrawal & R. Srikant. “Mining sequential patterns,” ICDE95GSP一种基

3、于Apriori的, 有影响的算法 (IBM Almaden开发(kif)R. Srikant & R. Agrawal. “Mining sequential patterns: Generalizations and performance improvements,” EDBT96由序列模式到 episodes (类Apriori+ 约束)H. Mannila, H. Toivonen & A.I. Verkamo. “Discovery of frequent episodes in event sequences,” Data Mining and Knowledge Discove

4、ry, 1997挖掘具有约束的序列模式M.N. Garofalakis, R. Rastogi, K. Shim: SPIRIT: Sequential Pattern Mining with Regular Expression Constraints. VLDB 19995共五十四页序列(xli)模式的基本性质: Apriori基本性质: Apriori (Agrawal & Sirkant94) 如果(rgu)序列 S 不是频繁的 则 S 的任何超序列都不是频繁的例, 是非频繁的 和 也是非频繁的5040302010SequenceSeq. ID给定 支持度阈值 min_sup =2 6

5、共五十四页GSP一种拓广的序列(xli)模式挖掘算法GSP (Generalized Sequential Pattern) 挖掘算法Agrawal 和 Srikant提出, EDBT96方法概述初始, 数据库中的每个项都是长度为1的候选(hu xun)for each level (即, 长度为k的序列) do扫描数据库对每个候选序列收集支持度计数使用Apriori , 由长度为k 的频繁序列产生长度为(k+1)的候选序列repeat until 找不到频繁序列或候选主要优点: 根据Apriori对后选剪枝7共五十四页找长度为1的序列(xli)模式使用一个例子(l zi)考查 GSP初始候选

6、: 所有单元素序列, , , , , , , 扫描数据库一次, 对候选进行支持度计数5040302010SequenceSeq. IDmin_sup =2 CandSup354332118共五十四页产生长度(chngd)为2的候选51 个长度为2的候选: 上下两个(lin )表格的组合不使用 Apriori 性质,8*8+8*7/2=92 个候选Apriori 剪裁掉 44.57% 的候选9共五十四页找出长度(chngd)为2的序列模式再扫描数据库一次, 对每个长度为2的候选(hu xun)收集支持度计数有 19 长度为2 的候选, 满足最小支持度阈值 它们是长度为2的序列模式10共五十四页产

7、生长度为3的候选(hu xun)并找出长度为3的模式产生长度为3的候选 长度为2的序列模式自连接根据 Apriori 性质, 和 都是长度为2的序列模式 是一个长度为3的候选, 和 都是长度为2的序列模式 是一个长度为3的候选产生46 个候选找出长度为3的序列模式再次扫描数据库, 收集(shuj)候选的支持度计数46个候选中有19个满足支持度计数11共五十四页GSP 挖掘(wju)过程 第1次扫描: 8 候选. 6 个长度为1 的序列模式第2次扫描: 51 候选. 19 个长度为2 的序列模式. 10 候选不在 DB第3次扫描: 46 个候选. 19 长度为3的序列模式. 20 个候选不在DB

8、第4次扫描: 8 个候选. 6 个长度为4的序列模式. 第5次扫描: 1 个候选. 1 长度为5 的序列模式候选不满足 支持度阈值候选不在DB中5040302010SequenceSeq. IDmin_sup =2 12共五十四页GSP 算法(sun f)取形如 的模式作为长度为1的候选(hu xun)扫描数据库1次, 找出 F1, 长度为1的序列模式的集合令 k=1; while Fk is not empty do由Fk形成Ck+1, 长度为(k+1) 的候选的集合;如果 Ck+1 非空, 扫描一次数据库, 找出 Fk+1, 长度为(k+1) 序列模式的集合令 k=k+1;13共五十四页G

9、SP的瓶颈(pn jn)可能产生(chnshng)的候选的集合可能很大1,000 长度为1的频繁序列可以产生 长度为2的候选!挖掘中多次扫描数据库实际挑战: 挖掘长序列模式指数个数短候选一个长度为100的序列模式 需要 1030 个候选序列!14共五十四页The SPADE AlgorithmSPADE (Sequential PAttern Discovery using Equivalent Class) developed by Zaki 2001垂直数据格式的序列模式挖掘方法序列数据库转化为垂直数据格式Item: 序列模式挖掘： 模式一次增长(zngzhng)一个项基于Apriori性

10、质，连接两个k-1子序列为k序列候选连接时必须保证涉及事件的时间序15共五十四页The SPADE Algorithm16共五十四页PrefixSpan: 前缀投影的序列(xli)模式增长PrefixSpan：不需要产生候选的方法基于投影(tuyng)，但仅基于前缀的投影(tuyng): 较少的投影, 并且序列收缩较快基本思想先找出频繁项，然后产生投影数据库的集合每个投影数据库关联一个频繁项每个(投影)数据单独(以递归方式)挖掘。算法构造前缀模式，与后缀模式相联得到频繁模式，从而避免产生候选17共五十四页前缀和后缀(huzhu) (投影), , 和 是序列 的前缀(qinzhu)给定序列 前缀

11、后缀 (基于前缀的投影)18共五十四页通过前缀投影挖掘序列(xli)模式步骤 1: 找出长度为1的序列(xli)模式, , , , , 步骤 2: 划分搜索空间. 序列模式的完全集可以划分成6个子集合 :具有前缀 的模式;具有前缀 的模式;具有前缀 的模式SID序列1020304019共五十四页找出具有(jyu)前缀 的序列模式只需要考虑关于 的投影-投影数据库 : , , , 找出所有长度为2的序列模式. 含有前缀 : , , , , , 进一步划分成6个子集合(jh)具有前缀 ;具有前缀 SID序列1020304020共五十四页PrefixSpan的完全性SID序列10203040SDB，

12、最小支持(zhch)度2长度(chngd)为1的序列模式, , , , , -投影数据库-投影数据库的1频繁项是a:2,b:4,_b:2, c:4,d:2, f:2.长度为2的序列模式, , , , 具有前缀 具有前缀 -proj. db-proj. db具有前缀 -projected database具有前缀 具有前缀 , , 21共五十四页PrefixSpan的有效性不需要(xyo)产生候选序列投影数据库不断收缩PrefixSpan的主要开销: 构造投影数据库可以用两级( bi-level) 投影改进22共五十四页通过(tnggu)伪投影加速PrefixSpan的主要开销: 投影序列(xl

13、i)的后缀经常 在递归投影数据库中重复地出现当 (投影) 数据库不能放在内存时, 使用指针形成投影指向序列后缀的偏移s=s|: ( , 2)s|: ( , 4)23共五十四页伪投影(tuyng) vs. 物理投影伪投影避免物理地拷贝后缀当数据库可以放在内存时, 运行时间和空间是有效的然而, 当数据库不能放在内存时, 它不太有效基于磁盘(c pn)的随即访问开销很大建议的方法:集成物理投影和伪投影当数据集可以放在内存时, 切换成伪投影24共五十四页伪投影(tuyng)的影响25共五十四页PrefixSpan的优化技术(jsh)PrefixSpan的优化技术单级 vs.两级投影具有3路检验的两级投

14、影可以压缩投影数据库的数量和大小物理投影 vs. 伪投影 当投影数据库可以放在内存时, 伪投影可能降低投影的效果并发投影 vs. 划分投影划分投影可以避免磁盘空间爆炸通过两级投影扩展基于(jy)长度为2的序列模式划分搜索空间只形成投影数据库, 并在两级投影数据库上进行递归挖掘26共五十四页两级投影（S矩阵(j zhn)）加速扫描数据库两次，构建s-矩阵所有长度为2的序列模式(msh)都在 S-矩阵中发现(逐个检查)27共五十四页使用(shyng)S-矩阵逐对检查SID序列10203040SDB长度(chngd)为1的序列模式:4, :4, :4, :3, :3, :3a2b(4, 2, 2)1

15、c(4, 2, 1)(3, 3, 2)3d(2, 1, 1)(2, 2, 0)(1, 3, 0)0e(1, 2, 1)(1, 2, 0)(1, 2, 0)(1, 1, 0)0f(2, 1, 1)(2, 2, 0)(1, 2, 1)(1, 1, 1)(2, 0, 1)1abcdefS-矩阵 出现2次 出现4次 出现2次 出现1次所有长度为2的序列模式 都在 S-矩阵中发现28共五十四页挖掘(wju) -投影数据库SID序列10203040SDBa2b(4, 2, 2)1c(4, 2, 1)(3, 3, 2)3d(2, 1, 1)(2, 2, 0)(1, 3, 0)0e(1, 2, 1)(1, 2

16、, 0)(1, 2, 0)(1, 1, 0)0f(2, 1, 1)(2, 2, 0)(1, 2, 1)(1, 1, 1)(2, 0, 1)1abcdefS-矩阵(j zhn)-投影数据库局部长度为1的序列模式:, , a0c(1, 0, 1)1(_c)(, 2, )(, 1, )ac(_c)S-矩阵不希望形成 (_ac), 因此不必对它计数.导致模式 长度为1的序列模式:4, :4, :4, :3, :3, :329共五十四页三路 Apriori 检查(jinch)a2b(4, 2, 2)1c(4, 2, 1)(3, 3, 2)3d(2, 1, 1)(2, 2, 0)(1, 3, 0)0e(1

17、, 2, 1)(1, 2, 0)(1, 2, 0)(1, 1, 0)0f(2, 1, 1)(2, 2, 0)(1, 2, 1)(1, 1, 1)(2, 0, 1)1abcdeF 不可能是模式(msh)!(因为:1小于2)从 -投影数据库排除 d使用 Apriori 启发式方法在投影数据库中剪去项类Apriori算法的优点30共五十四页两级投影(tuyng)的好处每次可以(ky)发现更多的模式较少的投影在上例中, 有 53 个模式.53 个逐级投影22 个两级投影31共五十四页PrefixSpan 比 GSP 和 FreeSpan快32共五十四页PrefixSpan的进一步演变(ynbin)闭的

18、和最大的序列模式仅找出最有意义的 (最大的) 序列模式基于约束(yush)的序列模式增长增加用户指定的约束由序列模式到结构化的模式除序列模式外, 在XML文档中挖掘结构化的模式33共五十四页闭的和最大的序列(xli)模式闭的序列模式 是频繁序列 s , 不存在s的 真超集, 与s具有相同的支持(zhch)读计数最大序列模式 是序列模式 p 使得 p的任何真超模式都不是频繁的闭的序列模式的优点, , min_sup = 1 有2100 序列模式, 但只有 2 是闭的最大序列模式有类似的优点34共五十四页挖掘(wju)闭的和最大的序列模式的方法PrefixSpan 或 FreeSpan 可以看作投

19、影引导的深度优先搜索 为挖掘 最大序列模式, 不包含比已经发现的序列模式更多东西的任何序列模式将从投影数据库中删除, , min_sup = 1 如果我们(w men)已经发现一个最大序列模式 , 不在任何投影数据库做投影类似的思想可以用于闭的序列模式35共五十四页由序列(xli)模式到结构化的模式集合(jh), 序列, 树和其它结构事务数据库: 项的集合 i1, i2, , im, 序列数据库: 集合的序列:, 序列的集合: , , , 树的集合 (每个元素是一棵树): t1, t2, , tn方法: 挖掘 XML 文档中结构化的模式36共五十四页DNA 分析(fnx)和生物医学数据挖掘相似

20、性搜索和 DNA 序列比较比较每个类频繁出现的模式 (例如(lr), 疾病和健康)识别在各种疾病中起作用的基因模式关联分析: 识别同时出现的基因序列大部分疾病不是由单个基因引发的, 而是由一起起作用的基因组引发的关联分析可以帮助确定多半可能同时出现在目标样本中的基因类型路径分析: 将基因与疾病的不同发展阶段相联系不同的基因可能在疾病的不同阶段是活跃的针对不同阶段, 分别开发治疗药物可视化工具和遗传数据分析37共五十四页流数据挖掘流数据频繁模式挖掘简介流数据频繁模式挖掘算法概念 一系列连续且有序的点组成的序列 x1, xi, , xn,称为(chn wi)数据流；按照固定的次序，这些点只能被读取

21、一次或者几次特点大数据量，甚至无限频繁的变化和快速的响应线性扫描算法，查询次数有限random access is expensive38共五十四页DBMS 与 DSMS持久的关系One-time queries随机的访问(fngwn)“无限”的磁盘空间当前状态有效相对较低的更新率很少“实时服务”假定数据精确无误访问策略由查询处理器在数据库设计时确定瞬间的流 连续的查询(chxn)序列化的访问有限的主存数据的到达顺序是关键数据传输率未知实时响应过时/模糊的数据变化的数据及数据量39共五十四页Scratch Space(Main memory and/or Disk)User/Applicati

22、onContinuous QueryStream QueryProcessorResultsMultiple streamsDSMS40共五十四页DSMSScratch StoreDSMSInput streamsRegisterQueryStreamedResultStoredResultArchiveStoredRelations41共五十四页目前(mqin)的DSMS项目STREAM (Stanford): A general-purpose DSMSCougar (Cornell): sensorsAurora (Brown/MIT): sensor monitoring, dataf

23、lowHancock (AT&T): telecom streamsNiagara (OGI/Wisconsin): Internet XML databasesOpenCQ (Georgia Tech): triggers, incr. view maintenanceTapestry (Xerox): pub/sub content-based filteringTelegraph (Berkeley): adaptive engine for sensorsTradebot (): stock tickers & streamsTribeca (Bellcore): network mo

24、nitoringStreaminer (UIUC): new project for stream data mining42共五十四页应用领域新的应用领域 以连续的、有序的“流”的形式输入数据网络监听和流量控制(Network monitoring and traffic engineering)电话通信(Telecom call records)网络安全 (Network security )金融领域(Financial Application)工业生产(Manufacturing Processes)网页(wn y)日志与点击流(Web logs and clickstreams)43共

25、五十四页应用(yngyng)实例网络安全 数据包流，用户的会话信息查询: URL 过滤，异常监测，网络攻击和病毒来源金融领域(ln y)交易数据流， 股票行情， 消息反馈查询: 套汇可能性分析，模式44共五十四页现有的研究(ynji)方向流数据建模(Stream data model)STanford stREam datA Manager (STREAM)Data Stream Management System (DSMS)流检索(jin su)/查询建模(Stream query model)Continuous QueriesSliding windows流数据挖掘(Stream data mining)Clustering & summarization (Guha, Motwani et al.)Correlation of data streams (Gehrke et al.)Classification of stream data (Domingos et al.)45共五十四页流数据