时间序列和序列模式挖掘-Read.PPT

第六章 时间序列和序列模式挖掘 信息与计算科学系 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=a1?a2?…?an,其中每个ai是一个项集。一个序列的长度是它所包含的项集。具有k长度的序列称为k-序列 定义6-4 设序列a=a1?a2?…?an,序列β=β1?β2?…?βn。若存在整数i1i2…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、带交易时间的交易数据库 交易记录包含客户号、交易时间及交易中购买的项 数据源的形式(cont.) 数据源进行形式化整理,将一个顾客的交易按交易时间排序成项目集 数据源的形式(cont.) 2、系统调用日志 操作系统及其系统进程调用时评价系统安全性的一个重要方面。通过对正常调用序列的学习，可预测随后发生的系统调用序列，发现异常的调用 数据源的形式(cont.) 3、Web日志 Web服务器中的日志文件记录了用户访问信息，包括IP地址、访问时间、URL以及访问方式等。考察用户的调用顺序并从中发现规律，可为改善站点设计和提高系统安全性提供重要依据 序列挖掘的一般步骤 一般步骤包括： 排序阶段 将原始的数据库经排序后转换成序列数据库 大项集阶段 找出所有频繁的项集组成的集合 转换阶段 在寻找序列模式的过程中，不断地检测一个给定的大序列集合是否包含于一个客户序列中 序列阶段 利用转换后的数据库寻找频繁的序列，即大序列 选最大阶段 在大序列集中找出最长序列 6.7 AprioriAll算法 算法思想： 将Apriori扩展到序列挖掘中，在每一遍扫描中都利用前以便的大序列来产生候选序列，然后再完成对这个数据库的遍历后测试它们的支持度 6.7 AprioriAll算法(Cont.) 算法描述： 输入：大项集阶段转换后的序列数据库D 输出：所有最长序列 处理： L1={large 1-sequence}; For (k=