时间序列和序列模式挖掘-Read课件

第六章时间序列和序列模式挖掘信息与计算科学系2009年4月概述时间序列：将某一指标在不同时间上的不同数值，按照时间的先后顺序排列而成的数列时间序列挖掘通过研究信息的时间特性，深入洞悉事务进化的机制，成为获得知识的有效途径序列挖掘挖掘从序列数据库中发现相对时间或其它顺序所出现的高频率子序列6.1时间序列及其应用时间序列挖掘就是从大量的时间序列数据中提取人民事先不知道的、但又是潜在有用的与时间属性相关的信息和知识，并用于短期、中期或长期预测，指导人们的社会、经济、军事和生活等行为时间序列的研究必须依据合适的理论和技术进行，相应的建模方法也不同：一元时间序列：可以通过单变量随机过程的观察获得规律性信息；多元时间序列：通过多变量描述变化规律离散型时间序列：序列中的每一个序列值所对应的时间参数为间断点连续型时间序列：序列中的每个序列值所对应的时间参数为连续函数序列的分布规律：序列的统计特征可表现平稳或有规律震荡，从而为序列分析提供理论根据6.2时间序列预测的常用方法确定性时间序列预测方法对于平稳变化特征的时间序列，其未来行为与现在的行为有关，利用属性现在的值预测将来的值是可行的一种更科学的评价方法：将数据的变动看成是长期趋势、季节变动和随机型变动共同作用的结果长期变动：岁时间变化的、按照某种规则稳步增长、下降或保持在某一水平上的规律；季节变动：在一定时间内的周期性变化规律随机型变动：不可控的偶然因素等时间序列分析就是设法消除随机型波动、分解季节性变化、拟合确定型趋势确定性时间序列预测技术可以控制时间序列变动的基本样式6.3基于ARMA模型的序列匹配方法基本概念ARMA模型对于平稳、正态、零均值的时序X={xt|t=0,1,…,n-1}，若X在t时刻的取值不仅与其前n步的各个值xt-1,xt-2,…,xt-n有关，且还与前m步的各个干扰at-1,at-2,…,at-m有关，则按多元线性回归的思想，得到最一般的ARMA(n,m)模型：6.3基于ARMA模型的序列匹配方法(cont.)AR模型(自回归模型)MA模型(m阶滑动平均模型)利用基本概念建立模型对于AR模型，有可用以下线性方程组表示：或写为参数矩阵可用最小二乘法计算6.6序列挖掘基本概念定义6-3一个序列是项集的有序表，记为a=a1a2…an,其中每个ai是一个项集。一个序列的长度是它所包含的项集。具有k长度的序列称为k-序列定义6-4设序列a=a1a2…an,序列β=β1β2…βn。若存在整数i1<i2<…<in,使得

,j=1,…,n，则称序列a是序列β的子序列。在一组序列中，若某序列a不包含在其他任何序列中，则称a是该组中最长序列例：<(3)(4,5)(8)>是<(7)(3,8)(9)(4,5,6)(8)>的子序列，但<(3)(5)>不是<(3,5)>的子序列，同样，<(3,5)>也不是<(3)(5)>的子序列定义6-5给定序列S，序列数据库DT，序列S的支持度是指S在DT中相对于整个数据库元组而言所包含S的元组出现的百分比。支持度大于最小支持度的k-序列，称为DT上的频繁k-序列数据源的形式1、带交易时间的交易数据库交易记录包含客户号、交易时间及交易中购买的项客户号交易时间物品1June25’99301June30’99902June10’9910,202June15’99302June20’9940,60,703June25’9930,50,704June25’99304June30’9940,704July25’99905June12’9990数据源的形式(cont.)数据源进行形式化整理,将一个顾客的交易按交易时间排序成项目集客户号物品1<(30)>2<(10,20)(30)(40,60,70>3<(30,50,70)>4<(30)(40,70)(90)>5<(90)>数据源的形式(cont.)2、系统调用日志操作系统及其系统进程调用时评价系统安全性的一个重要方面。通过对正常调用序列的学习，可预测随后发生的系统调用序列，发现异常的调用进程号调用时间调用号74404:01:10:302374404:01:10:3214106904:01:10:354904:01:10:3624106904:01:10:37574404:01:10:3881106904:01:10:3962904:01:10:4016-1数据源的形式(cont.)3、Web日志Web服务器中的日志文件记录了用户访问信息，包括IP地址、访问时间、URL以及访问方式等。考察用户的调用顺序并从中发现规律，可为改善站点设计和提高系统安全性提供重要依据IP地址URL调用序列192.168.120.10<(a)(b,c)(d)>192.168.120.20<(b)(c)(d,e)>192.168.120.30<(a,b)(d)>序列挖掘的一般步骤一般步骤包括：排序阶段将原始的数据库经排序后转换成序列数据库大项集阶段找出所有频繁的项集组成的集合转换阶段在寻找序列模式的过程中，不断地检测一个给定的大序列集合是否包含于一个客户序列中序列阶段利用转换后的数据库寻找频繁的序列，即大序列选最大阶段在大序列集中找出最长序列6.7AprioriAll算法算法思想：将Apriori扩展到序列挖掘中，在每一遍扫描中都利用前以便的大序列来产生候选序列，然后再完成对这个数据库的遍历后测试它们的支持度6.7AprioriAll算法(Cont.)算法描述：输入：大项集阶段转换后的序列数据库D输出：所有最长序列处理：L1={large1-sequence};For(k=2;Lk-1≠Φ;k++)BEGINCk=AprioriAll-generate(Lk-1);foreachcustomer-sequencecinDDOsumthecountofallcandidatesinCkwhichcontainedinc;

Lk=candidatesinCkwithminimumsupport;ENDAnswer=MaximalSequenceinUkLk;AprioriALL-generate输入：所有的大(k-1)序列的集合Lk-1输出：候选Ck处理(1)链接运算，得到CkSelectp.itemset1,p.itemset2,…,p.itemsetk-1,q.itemsetk-1FromLk-1p,Lk-1qWherep≠qandp.itemset1=q.itemset1,…p.itemsetk-2=q.itemsetk-2(2)删除Ck的那些(k-1)序列不在Lk-1中的元素For所有c∈Ck的序列DOFOR所有的c的(k-1)序列sDOIF(s不属于Lk-1)THENDelete来自于Ck的c；例：给出一个源数据库如下表所示，对其进行序列挖掘。设最小支持度为40%。客户号交易时间物品1June25’99301June30’99902June10’9910,202June15’99302June20’9940,60,703June25’9930,50,704June25’99304June30’9940,704July25’99905June12’9990数据源进行形式化整理与转换客户号原始顾客序列物品AfterMapping1<(30)><90><{(30)}{(90)}><{1}{5}>2<(10,20)(30)(40,60,70><{(30)}{(40),(70),(40,70)}><{1}{2,3,4}>3<(30,50,70)><{(30,70)}><{1,3}>4<(30)(40,70)(90)><{(30)}{(40),(70),(40,70)}{(90)}><{1}{2,3,4}{5}>5<(90)><{(90)}><{5}>例：原序列数据库：<(1,5)(2)(3)(4)><(1)(3)(4)(3,5)><(1)(2)(3)(4)><(1)(3)(5)><(4)(5)>1-sequencessupporseqsupport2-seqsupport1,222,421,343,431,433,521,5324,522,32<1,2><2,1><3,1><4,1><5,1><1,3><2,3><3,2><4,2><5,2><1,4><2,4><3,4><4,3><5,3><1,5><2,5><3,5><4,5><5,4><1,2,3><1,3,2><1,4,2><1,5,2><2,3,4><2,4,3><3,4,5><3,5,4><1,2,4><1,3,4><1,4,3><1,5,3><1,2,5><1,3,5><1,4,5><1,5,4>1-sequencessupport1,2,321,2,421,3,431,3,522,3,42<1,2,3><1,3,4><1,4,5><2,3,4><3,4,5><1,2,4><1,3,5><1,2,3,4><1,2,4,3><1,3,4,5><1,3,5,4><1,2,3,4>1-sequencessupport1,2,3,42最大序列为：<1,2,3,4><1,3,5><4,5>算法性能缺陷：缺少时间限制用户可能需要指定序列模式的相邻元素之间的时间间隔；事务的定义过于严格一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内的所有购买行为均作为一个事务缺少分类层次只能在项目的原始级别上进行挖掘6.8AprioriSome算法AprioriSome算法分为两个阶段：前推阶段：用于找出指定长度的所有大序列回溯阶段：用于查找其他长度的所有大序列AprioriSome算法描述输入：大项集阶段转换后的序列数据库D；输出：所有最长序列处理：前推阶段：L1={large1-sequences};C1=L1;Last=1;For(k=2;Ck-1≠ΦandLlast

≠Φ;k++)DOBEGINIf(Lk-1know)THENCk=NewcandidatesfromLk-1;ELSECk=NewcandidatesfromCk-1; If(k=next(last)THENBEGINFOReachcinDDO计算Ck各项的支持度;

Lk=Ck中满足最小支持度的候选项

last=k; ENDEND回溯阶段：For(k--;k>=1;k--;)if(Lknotfoundin前推阶段)then begindeleteallsequencesinCkcontainedinSomeLi,i>k; foreachcinDDOCk中包含在c中的所有候选者计数

Lk=满足最小支持度的Ck项

endelsedeleteallsequencesinLkcontainedinsomeLi,i>k;Answer=∪Lk算法next(k:integer)If(hitk<0.666)THENreturnk+1;Elseif(hitk<0.75)THENreturnk+2;Elseif(hitk<0.8)THENreturnk+3;Elseif(hitk<0.85)THENreturnk+4;Elsereturnk+5;Hitk=|Lk|/|Ck|确定对哪些序列进行计数，在对非最大序列计数时间的浪费和扩展小候选序列之间做出权衡算法示例：使用下表中的数据库信息，对于next(k)=2k,利用AprioriSome算法进行大序列求解原序列数据库：<(1,5)(2)(3)(4)><(1)(3)(4)(3,5)><(1)(2)(3)(4)><(1)(3)(5)><(4)(5)>AprioriAllVsAprioriSomeAprioriSome会产生比较多的候选AprioriSome跳跃式计算，可能在回溯阶段前就占满内存；对于较低的支持度，有较长的大序列，因此有较多的非最大序列，在一定条件下，AprioriSome会比较好6.9GSP算法算法描述：1、扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集；2、根据长度为i的种子集Li通过连接操作和剪切操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个序列模式的支持数，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集；3、重复第2步，直到没有新的序列模式或新的候选序列模式产生为止6.9GSP算法(cont.)连接阶段：如果去掉序列模式S1的第一个项目与去掉序列模式S2的最后一个项目所得到的序列相同，则可以将S1与S2进行连接，即将S2的最后一个项目添加到S1中剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从