数据挖掘chapter序列数据挖掘.ppt

11Chapter 8. 序列数据挖掘2序列数据库和序列模式挖掘?事务数据库vs. 序列数据库?频繁模式vs. (频繁) 序列模式?序列模式挖掘的应用?顾客购物序列: ?在3个月内, 先买计算机, 然后买CD-ROM, 再后买数字照相机.?医疗处治, 自然灾害(例如, 地震), 科学和工程进度, 股票和市场等.?电话呼叫模式, Web日志点击流?DNA 序列和基因结构3什么是序列模式挖掘??给定一个序列的集合, 找出所有的频繁子序列?序列:事件的有序列表一个序列数据库一个序列: <(ef) (ab) (df) c b >,我们可以用字典序列出它们.<a(bc)dc> 是<<a(abc)(ac)d(cf)>的子序列给定支持度阈值min_sup =2, <(ab)c> 是一个序列模式<eg(af)cbc>40<(ef)(ab)(df)cb>30<(ad)c(bc)(ae)>20<a(abc)(ac)d(cf)>10sequenceSID4序列模式挖掘的挑战?大量的可能的序列模式隐藏在数据库中?挖掘算法应当?可能的话, 找出满足最小支持度阈值的模式的完全集?高度有效的, 可伸缩的, 仅涉及不多次数的数据库扫描?可以与各种用户指定的约束结合5序列模式挖掘研究?概念引进和最初的类Apriori算法?R. Agrawal & R. Srikant. “Mining sequential patterns,” ICDE’95?GSP—一种基于Apriori的, 有影响的算法(IBM Almaden开发)?R. Srikant & R. Agrawal. “Mining sequential patterns: Generalizations and performance improvements,” EDBT’96?由序列模式到episodes (类Apriori+ 约束)?H. Mannila, H. Toivonen & . Verkamo. “Discovery of frequent episodes in event sequences,” Data Mining and Knowledge Discovery, 1997?挖掘具有约束的序列模式?. Garofalakis, R. Rastogi, K. Shim: SPIRIT: Sequential Pattern Mining with Regular Expression Constraints. VLDB 19996序列模式的基本性质: Apriori?基本性质: Apriori (Agrawal & Sirkant’94) ?如果序列S 不是频繁的?则S 的任何超序列都不是频繁的?例, <hb> 是非频繁的?<hab> 和<(ah)b>也是非频繁的<a(bd)bcb(ade)>50<(be)(ce)d>40<(ah)(bf)abf>30<(bf)(ce)b(fg)>20<(bd)cb(ac)>10SequenceSeq. ID给定支持度阈值min_sup =2 7GSP—一种拓广的序列模式挖掘算法?GSP (Generalized Sequential Pattern) 挖掘算法?Agrawal和Srikant提出, EDBT’96?方法概述?初始, 数据库中的每个项都是长度为1的候选?for each level (即, 长度为k的序列) do?扫描数据库对每个候选序列收集支持度计数?使用Apriori , 由长度为k 的频繁序列产生长度为(k+1)的候选序列?repeat until 找不到频繁序列或候选?主要优点: 根据Apriori对后选剪枝8找长度为1的序列模式?使用一个例子考查GSP?初始候选: 所有单元素序列?<a>, <b>, <c>, <d>, <e>, <f>, <g>, <h>?扫描数据库一次, 对候选进行支持度计数<a(bd)bcb(ade)>50<(be)(ce)d>40<(ah)(bf)abf>30<(bf)(ce)b(fg)>20<(bd)cb(ac)>10SequenceSeq. IDmin_sup =2 1<h>1<g>2<f>3<e>3<d>4<c>5<b>3<a>SupCand9产生长度为2的候选<ff><fe><fd><fc><fb><fa><f><ef><ee><ed><ec><eb><ea><e><df><de><dd><dc><db><da><d><cf><ce><cd><cc><cb><ca><c><bf><be><bd><bc><bb><ba><b><af><ae><ad><ac><ab><aa><a><f><e><d><c><b><a><f><(