（计算机应用技术专业论文）onlinehht方法在时间序列数据流预测中的应用研究.pdf

大连理工大学硕士学位论文 摘要 近年来，在传感器网络、系统性能保持等应用领域中产生的数据量越来越大，每天 以数以百万计甚至没有上限的速度增长，这样的数据流中蕴含大量信息，可以用来作为 智能决策的依据，如何从这些连续不断的非平稳的数据流中挖掘有用的信息，正变成我 们需要面对的新考验，这是传统的数据挖掘方法无法解决的问题。 本文重点对时间序列数据流预测方法进行了研究。结合流数据挖掘领域中的滑动窗 口技术和分析非线性、非平稳数据的蹦t 方法给出了一种时间序列数据流预测的新方 法o n h n e 卸盯，并提出了运用此方法进行预测的通用模型，此模型适合所有应用领域 的时间序列数据流预测。时间序列数据流的连续性、数据量大以及数据一次处理等固有 的特点是预测方法处理的一个难题。针对数据流的连续性，本文采用滑动窗口技术对原 始数据流建模，使得应用只关注最近一段时间内数据的变化，滑动窗口技术在本文用f 0 r 循环实现；针对某个时间点对应的滑动窗口中的数据，采用删t 方法进行分析，从而 进行预测；本文对已有唧方法采用了并行处理的思想，当滑动窗口中的数据量多时， 先将数据分段，对每段分别采用删t 方法进行e m d 分解，加快了算法处理的速度。 o i d 址肌t 方法解决了已有方法如小波分解等无法进行在线自适应预测以及分解的准 确性问题。 最后，本文用o m 硫h h t 方法对贵州电网提供的电力负荷时间序列数据流进行分 析，通过仿真实验表明，该方法能够有效地对时间序列数据流进行趋势预测。 关键词：数据流；时间序列；o n l i n e h h t ；滑动窗口 o m i 玎e _ 蹦t 方法在时间序列数据流预测中的应用研究 a p p l i c a t i o n r e s e a r c hf o rp r e d i c t i o no ft i m es e r i e sd a t as t r e 锄sb2 l s e do n 0 n l i n e h h tm e t h o d a b s t r a c t 1 1 1r e c e n ty e a r s ，t h e 锄o u l l to fd a ：t ap r o d u c e di i ls e n s o rn 咖r k s ，s y s t e mp e r f b m l a n c e a p p l i c a t i o nf i e l di n c r e a s e sc o n t i i m o u s l y ，研也m es p e e do f i i l i l l i o n sad a y ，a n de v e nn o th a sa c e i l i i 毽r a t e ，m e s ed a t as t r e a n l sc o 岫al a r g en 啪b e ro fi l l f o m a t i o n 、 ，! i l i c hc o u l db eu s e da s 也eb a s i sf o ri 疵l l i g e n td e c i s i o n 蚰a k i i l g ，h o wt 0m i n el l s e 彻i 廊n 1 1 a t i o n 胁mm e s e n o n s t a t i o n a r yc o n t i n u o u sd a l as t r e 锄si sb e c o m i i l gn e wc h a l l e n g e sw en e e dt 0f 砬e ，1 i s p r o b l e mc a i l tb es o l v e db y 仃a d i t i o n a ld a t am i i l i n gm e t h o d s t k sp a p e rf o c u s e do nm er e s e a r c hf o rt i i n es e r i e s 胁s t r e 锄s ng a v eai l e wt i m es e r i e s d a ：t as 臼e 锄p r e d i c t i o nm e 也o db a s e do ns l i d i n gw i d o wt e c q u ei ns t r e 锄纰m i i l i n gf i e l d a n dh h tm e 吐1 0 dw m c hi su s e df o ra n 2 l l y z 组gn o n i k 虬n o n - 蚴i o i l a r yd a a n dp r o p o s e da c o m m o np r e d i c t i o nm o d l l l ew h j c hi sf i tf o rt i m es e r i e sd a t as t r e 嬲l sp r e d i c t i o ni na l l 印p l i c a t i o nf i e l d t h ec o n t i i l u “y ，l a r g e 锄o u n to fd a ：a i l do i l l yo n c ep r o c e s s i n gf o ro n e d a t a 6 h a r a c ：t e r sa r ed i f ! f i c u l tp r o b l e m sf o rp r e d i c t i o n f o rt h ec o n 血u i t ) ，o fd a ：t ag 锄，t b j sp a p e r a d o p t e ds l i d i n gw i i l d o wt e c l l i l i q u et 0m o d e lo n 廿1 eo r i g i n a 】d a t 如m a d ea p p l i c a t i o r l so n l y c o n c 锄w i mt l l ed a ：t ac l l a i l g e si ns l i d i n gw m d o wi i lar e c e n tt i m e ，s l i d 洒gw i d o ww r a sr e a l i z e d b yf o rl o o pi 1 1 廿l i sp a p e r ；f o rm ed a t a 洫s l i d i n g 、) i ，i n d o wo f 趿) 7 缸ep o i n t ，u s e d i tm e t h o d t oa 1 1 a l y z ef o rp r e d i c t i o n ；1 1 1t h i sp 印h h tm e t l l o dh a db e e na d d e dm ei d e ao fp a r a j l e l p r o c e s s i i l g ，w h e l l 证1 e 锄o u n to f 纰i i ls l i m i 坞、析1 1 d o ww 弱t o om u c k f i r s td i v i d e dn l ed a 协 i i l t o 辩v e r a ls a m el e n g t hd a t as e c t i o n s ，也e nm a d ee m d d e c o m p o s i t i o ni n d 印e i l d e n t l y ， e n k l l l c e d 伽ep r o c e s s i n gs p e e do ft 1 1 i sa l g o d 皿o i l l i n e h h tm e m o ds o l v e dt l l ep r o b l e m so f b e i n gu 1 1 a b l et 0d o0 n l i n ea d a 砸v ep r e d i c t i o n 锄dd e c o m p o s i n ga c c u r a t e l yo fe x i s t e d m e t l l o d ( s u c ha u sw a v e l e td e c o i l l p o s i t i o n ) f i l l a l l y ，0 1 1 l i n e h h tm e t l l o dw a su s e dt oa n a l y z eg 试z l l o up o 、e r 嘶dt i m es 耐e sd a _ t a s t f e 锄，s 协m l a t i o ne x p e r i m e ms h o w e d 也a t 也i sm e t l l o dc o l l l de 丘b c t i v e l yd o 仃e n dp r e d i c t i o no n t i m es e 矗e s s 臼e 乏旺n k e yw o r d s ：d a t as t r e a m ；t i m es e r j e s ；o n “n e h h t ；s l i d i n gw n d o w i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：纽垃地z 堑魄呦乞兰：f 邋j 至剑土兰壁堕 作者签名：里查萎日期：珥年竺月j 互日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 日期：4 年垒月卫日 日期：丑必! 兰月j 垒日 大连理工大学硕士学位论文 1 绪论 1 1 研究背景 数据挖掘作为从海量信息中发现隐藏规律的技术引起了人们的极大兴趣，其主要原 因是：人们迫切需要把长期积累下来的海量数据转换为能利用的信息和知识。作为一种 新的数据应用模型，数据流的出现，从本质上对数据库技术和数据挖掘技术提出了新的 挑战。 近年来，数据流处理逐渐成为研究领域和许多应用领域的研究热点。数据流是一个 以一定速度连续到达的数据项序列x l ，x i ，x n ，这个数据项序列只能按下 标i 的递增顺序读取一次i l j 。目前数据流挖掘技术主要应用于传感器网络、网络监控、 事务日志分析和股票分析等领域，这些数据流产生的数据量在多个应用领域中快速增 长，小型无线传感设备的广泛使用将进一步使数据流体积的增长速度提高几个数量级。 而且，产生数据流的应用通常要求在线实时处理。 这种新的应用类型数量正在快速增长，它们要求在快速和大量的数据流上进行高 效、准确的分析和数据挖掘，以获取其中的趋势、模式和异常等。这种应用的特性产生 了一些新的研究问题，它们是传统的数据库技术和数据挖掘技术无法解决的，因为数据 流是以成倍的、快速的、连续的、随时间变化、和无限的方式到达的数据。对数据流进 行挖掘的算法必须满足数据流的如下一些特点：单次线性扫描，即算法只能按数据的流 入顺序依次读取数据一次；低的时间复杂度，因为流算法是在线算法，为了跟上数据流 的流速，算法处理每个数据项的时间不能太长；低的空间复杂度，因为流算法是主存算 法，其可用的空间是有限的；能在理论上保证计算结果具有好的近似度动态；能适应动 态变化的数据和流速；能有效处理噪音与空值；能作0 nd e m a 玎d 的挖掘；能作a i l v t i i n e 的回答；概要数据结构要有通用性，不仅要满足当前目标计算，也要能满足其它计算。 为适应这些新的应用需求，数据流挖掘技术变诞生了。流数据挖掘，是对流数据进行查 询和遍历，找出历史数据之间的潜在联系，从而促进信息的传递，发现隐含在其中的、 人们事先不知道的、但又是潜在有用的信息和知识，为管理者提供决策支持和服务。这 些特点促使人们去寻找处理数据流的高效方法。 目前数据流挖掘技术在工业控制领域也涉及到很多实时的数据流，如电力系统负荷 分析与电能质量扰动在线识别领域，并且这些领域的数据流是时间序列数据流，需要对 大量时间序列数据流进行实时、在线挖掘分析，研究数据流挖掘技术在工业控制领域的 应用具有重要的实际意义。本文研究的就是电力负荷时间序列数据流的分析预测，电力 o n l i n e 椰方法在时间序列数据流预测中的应用研究 负荷时间序列数据流具有非线性、非平稳特点，因此对这样的数据流进行分析从而进行 预测的算法应该能处理非线性、非平稳的特点。小波分解是目前这个领域比较有效的分 析两i 测方法，它能将某些非平稳时间序列分解成多层近似意义上的平稳时间序列，然后 采用自回归模型对分解后的时间序列进行预测，然而没有人提出怎样将小波分解的方法 普遍应用于非平稳时间序列的预测。因为需要对数据流进行在线自适应分析从而进行预 测，并且最好能提供一种通用的预测模型，结合删t 方法在处理非线性、非平稳数据 上的优越性、以及数据流中滑动窗口技术对数据流在线实时处理的优越性，本文提出 o r l l m 删t 方法对电力负荷时间序列数据流进行分析预测。 1 2 国内外研究现状 在数据流挖掘方面，国外研究的比较早，取得的科研成果较多、研究的进展比较快， 相应的思想和方法也比较成熟。 1 9 9 8 年，h e n z i n g e r 等人在“c o m p u t i l l go nd a t as 仃e 锄中首次将数据流作为一种 数据处理模型提出来【l 】，从2 0 0 0 年开始，数据流作为一个研究热点出现在数据挖掘与数 据库领域的几大顶级会议中，如v l d b ，s i g m o d 、s i g 】_ ( d d 、i c d e 、i c d m 等会议每年 都有多篇有关数据流处理的文章。目前，数据流研究大致可分为两个方面：数据流管理 系统( d a 土as 仃e a mm a n a g e m e n ts y 妣m s ，d s m s ) 和数据流挖掘f 2 1 。其中，建立数据流管 理系统方面的研究主要集中在数据流查询。已有多个研究机构进行了d s m s 的研究，并 构建出一些系统，如s t i 也a m 【3 】，t e l e g r a p h c q 【4 】，a u r o 一5 】等。d s m s 系统是基于关系 模型提出的，其研究内容涵盖了数据流查询处理的各个方面，如内存管理、近似查询、 数据流查询语言的定义等等。后者的研究侧重在数据流分析方面，对于数据流的在线分 析，从聚类、分类、频繁项集挖掘以及可视化等角度做了大量研究工作，提出了倾斜时 间窗口( t i l t e d t i m e 讹d o w ) 策略，采用不同时间粒度保存数据流的信息，他们的研究 得到了美国军方和国家自然科学基金的资助 6 】。数据流挖掘方面的研究已提出了大量数 据流挖掘算法，并开发出数据流挖掘系统。如u c 的m 触d s ( m i n i n g 砧a 锄i n gi n c i d e n t s 舶md a t as 地锄s ) 就是一个集查询、聚类、分类、频繁项挖掘，以及处理结果可视化 五大功能为一体的数据流挖掘系纠7 1 。 关于数据流的研究，国内开展的比较晚，还处于起步阶段，研究理论、算法和技术 不多也不够成熟，应用也处于试探阶段，有些学校和研究所正在对数据流进行研究。复 旦大学集中在流数据管理和挖掘的研究，中科院计算机技术研究所试图构建一个面向网 络信息安全的数据流计算模型，重点研究的一些问题有网络数据流的获取、网络数据流 大连理工大学硕士学位论文 建模、数据流查询模型、数据流计算算法等，他们的目标是在这个模型的基础上开发出 具体的有显示度的宏观网络监控应用系统。 近年来，有很多科研机构对此进行了研究：( 1 ) 有别于传统的存储型数据静态查 询，构造了一种对网络数据流进行连续查询的模型；( 2 ) 研究数据流中的近似查询处 理问题，提出了一系列如窗口查询、直方图、随机采样、小波等近似查询技术瞵j ；( 3 ) 通过分析基于实化聚集视图的查询重写方法，将相关的查询计算理论与数据流的查询相 结合，给出了一种具有广泛应用前景的基于数据流的近似查询计算方案嗍。 1 3 主要研究工作及章节安排 本文主要研究了时间序列数据流分析预测算法，考虑到时间序列数据流存在非线性 非平稳的特征，提出一种基于滑动窗口的数据流预测方法0 1 1 l i r l e h h t 对时间序列数据 流进行在线自适应预测。主要工作包括以下几个方面： ( 1 ) 研究了传统的非线性、非平稳数据集处理方法。如傅立叶变换只能处理线性非 平稳的信号；小波变换虽在理论上能处理非线性非平稳信号，但在实际算法实现中却只 能处理线性非平稳信号：h h t 则不同于这些传统方法，它彻底摆脱了线性和平稳性束 缚，非常适用于分析非线性非平稳信号。唧t 是完全自适应性的，姗t 能够自适应产 生“基 ，即由“筛选产生的m 卵，这点不同于傅立叶变换和小波变换。傅立叶变换 的基是三角函数，小波变换的基是满足“可容性条件的小波基，小波基是预先选定的。 在实际工程中，如何选择小波基也不是一件容易的事，选择不同的小波基可能产生很不 二样的处理结果，我们也没有理由认为所选的小波基能反映被分析数据或信号的特性。 ( 2 ) 研究了数据流的几种模型，分别是快照模型、界标模型和滑动窗口模型【lo j 。快 照模型将处理数据的范围限制在两个预定义的时间戳之间；界标模型处理数据的范围从 某一个已知的初始时间点到当前时间点为止；滑动窗口模型处理数据的范围由某个固定 大小的滑动窗口确定，此滑动窗口的终点永远为当前时刻。其中，滑动窗口的大小可以 由一个时间区间定义，也可以由窗口所包含的数据项数目定义，在这3 种模型中，界标 模型和滑动窗口模型是采用得比较多的模型。界标模型通常将数据流中的起始点作为数 据处理的初始时间点，此时，算法对数据流中所有数据进行处理，数据流中只存在插入 操作。在滑动窗口模型中，窗口随着数据的流入向前滑动，窗口中存在数据的插入和删 除，滑动窗口模型非常适用于只要求对最近一段时间内的数据集进行处理的应用，本文 采用的就是滑动窗口模型对电力负荷时间序列数据流进行建模。 ( 3 ) 采用滑动窗口技术，将处理非线性、非平稳数据的删t 方法用在处理非线性、 非平稳的时间序列数据流上( 即o i l l i n e h h t 方法) ，本文将肌t 方法用在了分析电力 o n l i n e 肼t 方法在时间序列数据流预测中的应用研究 负荷时间序列数据流上，用f o r 循环来实现滑动窗口技术，通过h h t 方法的谱分析可以 判断由e m d 方法分解出来的几个m f 中哪个i m f 可以代表电力负荷数据流的趋势，从 而对次日的电力负荷数据流趋势进行预测。 ( 4 ) 考虑到数据流的在线处理要求，要求算法具有低的时间复杂度，针对当前时间 点对应的滑动窗口中的数据量多的情况下，本文提出对滑动窗口中的数据集进行分段处 理的思想，将原始数据集分成等长的段，段的长度根据具体应用而定，然后对每段数据 分别采用e 方法进行分解，至于各小段数据集的e m d 分解什么时候结束，以及如 何组合各小段数据集分解后的结果，将在第四章给予详细描述，分段处理可以加快算法 的处理速度。 章节安排如下： 第一章为绪论部分。主要介绍课题研究背景，国内外研究现状和论文的主要工作及 本文章节安排。 第二章为时间序列数据流分析涉及到的数据挖掘技术介绍，重点介绍了流数据挖掘 技术。 第三章为0 i m i i l e 删t 时间序列数据流预测方法的提出，通过分析已有方法存在的 缺陷以及分析m 订方法的优势，引进了该方法。 第四章为o r l l k 圈 t 时间序列数据流预测方法的实现，包括模型提出、算法设计 和实验证明。 一4 一 大连理工大学硕士学位论文 2 数据流挖掘综述 2 1 时间序列分析理论简介 由于本文重点对时间序列数据流进行了研究，所以有必要对时间序列分析的理论进 行介绍。时间序列分析是一种重要的现代统计分析方法，广泛应用于自然领域、社会领 域、科学研究和人类思维。不论是自然现象，还是社会经济现象，都是一个有规律的辩 证发展过程【l 。任何运动都有一定的惯性，这种惯性就表现为系统的动态性，即记忆性。 时间序列是系统历史行为的客观记录，它包含了系统动态特征的全部信息。这些信息， 具体地表现为时间序列中观察值之间的统计相关性。因而，人们可以通过研究时间序列 中数值上的统计相关关系，来揭示相应系统的动态结构特征及其发展变化规律。基于上 述观点，时间序列分析就是用历史的观点，通过量的手段来研究现象的动态结构和动态 规律。这不仅是可能的，而且也是合理的、科学的。 2 1 1 随机过程与时间序列 所谓随机过程，是指现象的变化没有确定形式，没有必然的变化规律。用数学的语 言来讲，就是事物变化过程不能用一个( 或几个) 时间t 的确定函数来描述。也就是说， 如果对事物变化的全过程进行观测得到的结果是一个时间t 的函数；但是对同一事物的 变化过程独立的重复进行多次观测所得到的结果是不相同的】。 从时间变化的角度来考察的话，若对于每一个特定的t t ( t 是一个无穷集合，称 为参数集) ，x ( t ) 是一个随机变量，则称这一族无穷多个随机变量 x ( t ) ，t t ) 是一个 随机过程。可见，随机过程x ( t ) 是一族随机变量。定义如下：当t = 0 ，1 ，2 ，) 时，即 时刻t 只取整数时，随机过程 z ， t t ) 可写成 z ，t = 0 ，1 ，2 ，) ，此类随机过程称 为随机序列，也称时间序列。由此可见： ( 1 ) 时间序列是随机过程的一种，是将连续时间的随机过程等间隔采样后得到的序 列；换句话说，时间序列是指以时间顺序形态出现的一连串观测值集合f 1 2 1 。 ( 2 ) 时间序列也是随机变量的集合，只是与这些随机变量联系的时间不是连续的， 而是离散的。从统计意义上讲，时间序列就是将某一指标在不同时间上的不同数值，按 照时间的先后顺序排列而成的数列。这种数列由于受到各种偶然因素的影响，往往表现 出某种随机性，彼此之间存在统计上的依赖关系【l 刁。 时间序列分析是一种根据动态数据揭示系统动态结构和规律的统计方法。其基本思 想是：根据系统的有限长度的运行记录( 观察数据) ，建立能够比较精确地反映序列中 所包含的动态依存关系的数学模型，并借以对系统的未来进行预报的方法。 o n l i n e t 方法在时间序列数据流预测中的应用研究 对于时间序列 x 。，t t ) ，人去t ，s t ，定义序列 x 。) 的自协方差函数为： ，( f ，s ) = e ( z ，一p ，) ( x ，一。) ( 2 1 ) 其中，“= 倒，自协方差函数y ( t ，s ) 表示了时间序列 x 。) 在不同时刻t 和s 时的统计关系。 定义时间序列 x 。) 的自相关函数( a c f ) 为： 眺s ) ：下丝竺) _ ( 2 2 ) 一 qd x t d xs 其中，毯= 研置一麟r 】2 ，自相关函数刻画了时间序列 x 。) 在不同时刻t 和s 时 的线性相关程度。 2 1 2 非线性时间序列分析 随着混沌现象的发现，人们认识到在确定性系统内部也存在随机性，但这种复杂系 统的本质特征往往不是随机因素而是非线性动力系统中的混沌因素造成的，对从这样的 系统获取的时间序列，用随机过程方法分析显然是不合适的，而应当用基于混沌理论的 非线性时间序列分析方法进行研究【1 3 】。非线性时间序列分析就是研究如何通过复杂系统 的观测或实验获得的时间序列来辨识和重构原复杂系统，分析原复杂系统的性质，刻画 原复杂系统的特征，并对原复杂系统进行预测和控制。因此，研究非线性时间序列分析 的方法对解决实际问题中复杂系统的相关问题具有重要的意义。 非线性时间序列分析方法的研究对象是未知数学模型或无法建立解析数学模型的 复杂系统，研究过程中具有的信息是复杂系统中通过观测或实验手段获得的单变量或多 变量时间序列，研究目标就是寻求反映复杂系统本质特征的不变量，分析复杂系统的特 征、内在变化规律及内部关系，最终解释、指导甚至控制实际问题中具体的复杂系统。 非线性时间序列分析可以看作如图2 1 所示的输入输出过程，输入的是没有任何背景知 识的通过观测或实验手段获得的实际复杂系统的时间序列，输出是所研究系统的某些特 征。 图2 1 非线性时间序列的框架模型 f i g 2 1f 倒m e w o r km o d e l0 fn o n l i n e a rt i m es e r i e s 彻a l y s i s 一6 一 大连理工大学硕士学位论文 如果一个时间序列是由一个确定性系统通过观测或实验手段获得的，要考虑的是以 下反问题：如何由时间序列来恢复并刻画原复杂系统研究这个问题的基础是相空间重 构。一般的时间序列主要是在时间域或变换域中进行研究，而在非线性时间序列分析中， 无论是混沌特征不变量的计算、噪声处理还是预测都是在相空间中进行，因此可以说相 空间重构是非线性时间序列分析中非常重要也是极为关键的一步，下面介绍一下相空间 重构的基本思想和发展过程。 ( 1 ) 基本思想 相空间重构的基本思想是：由于混沌系统产生的轨迹经过一定时间的变化后，会最终 做一种有规律的运动，产生一种规则的，有形的轨迹( 混沌吸引子) ，而系统中任一分 量的演化都是由与之相互作用的其他分量所决定的，因此这些相关分量的信息就隐含在 任一分量的演化过程中，这样就可以从某一分量的时间序列中提取和恢复出动力系统原 来的规律。为了重构一个等价的状态空间，只需考察其中某一个分量，并将它在某些固 定时间延迟点上的观测量作为新维处理，即延迟值被看作是新的坐标，它们确定了某个 多维状态空间中的一点，重复这一过程并测量相对于不同时间的各延迟量，就可以产生 出许多这样的点。已经证明它可以将吸引子的许多性质保存下来，即用系统的一个观测 量就可以重构出原动力系统的模型，并可以初步确定该系统真实相空间的维数。由此可 见，相空间重构就是从时间序列出发创建一个多维状态空间，它保持了原系统的许多几 何特征量不变。 ( 2 ) 发展过程 为了从时间序列中提取更多有用信息，1 9 8 0 年p a c k a r d 等人i l4 】提出了用时间序列重 构相空间的两种方法：导数重构法和坐标延迟重构法。从原理上讲，导数重构和坐标延 迟重构都可以用来进行相空间重构，但就实际应用而言，由于通常不知道时间序列的任 何先验信息，而且从数值计算的角度看，数值微分是一个对误差很敏感的计算问题，因 此对时间序列的相空间重构普遍采用坐标延迟的方法。坐标延迟法的本质是通过一维时 间序列 x ( n ) ) 的不同时间延迟来构造m 维相空间矢量： 以= ，- f ，毛一( 肘1 ) f ) ( 2 1 ) 1 9 8 1 年t a l ( e 1 1 s 提出嵌入定理【1 4 】：对于无限长、无噪声的d 维吸引子的标量时间序 列 x ( n ) ，总可以在拓扑不变的意义上找到一个m 维的嵌入相空间，只要维数m - 2 d + 1 。 t a k e n s 定理保证了可以从维时间序列中重构出一个与原动力系统在拓扑意义下等价 的相空间，时间序列的判定、分析与预测都是在这个重构的相空间中进行的，因此相空 间重构是混沌时间序列研究的关键。这意味着原未知数学模型的动力系统中的任何微分 或拓扑不变量可以在重构的状态空间中计算，并且可以通过在重构的m 维状态空间中建 o n i j n e 眦t 方法在时间序列数据流预测中的应用研究 立数学模型对原未知数学模型的动力系统进行预测，进一步解释、分析、指导原未知数 学模型的动力系统，这一过程可以用图2 2 表示。 r 、厂、1 寻找特征置。建秒数 未知数学模型昀混沌 一皿厶正能已 4 嗡坩刑擀叠芊| 矗她挫 动力系缓 一 研什、，v l 、n 了 - ；，j r _ ，k 一 预测等 7k 观溅蜜验h ：心 。l 厂、 过 r、 适当选取m 和t ，形 甜弼序列 搬j 或m 雏状i 鲑空嘲 l 厂 拥宰露蕾鞠 一l 利黧雕堂嬲 图2 2 相空间嵌入 f i g 2 2p h a s e s p a c e 锄b e d d i n g 1 9 8 3 年 勰s b e r g e r 和p r o c a c c i a 基于坐标延迟法，提出了关联积分的概念和计算公 式，该方法适合从实际时间序列来计算混沌吸引子的维数，被称作g p 算法。g p 算法 是非线性时间序列分析研究中的一个重要突破，从此对非线性时间序列的研究不仅再局 限于已知的混沌系统，而且也扩展到实测非线性时间序列中，从而为非线性时间序列分 析研究进入实际应用开辟了一条道路。 坐标延迟相空间重构技术有两个关键参数：即嵌入维m 和时间延迟t 的确定。在 t a k e n s 定理中，对于理想的无限长和无噪声的一维时间序列，潜入维m 只须大于2 d + l 即可，雨时间延迟：可以取任意值：但实际应用中得到的时间序列都是含有噪声的有限长 时间序列，嵌入维数和时间延迟就不能再任意取值，否则会严重影响重构相空间的效果。 一个好的重构相空间是使重构后的吸引子和系统真正的吸引子尽可能做到拓扑等 价。有关时间延迟与嵌入维的选取方法，目前主要有两种观点。一种观点认为两者是互 大连理工大学硕士学位论文 不相关的，先求出时间延迟后再来选择合适的嵌入维。求时间延迟：比较常用的方法有 自相关法、平均位移法、复自相关法和互信息法等，选取的目的是使原时间序列经过时 间延迟后可以作为独立坐标使用。目前寻找最小嵌入维的方法主要有几何不变量法、虚 假最近邻点法和它的改进形式c a o 方法等。另一种观点认为时间延迟间隔和嵌入维数是 相关的，1 9 9 6 年k l l g n l m t z i s 提出的时间窗长度是综合考虑两者的重要参数。1 9 9 9 年， 磁m 等人基于嵌入窗法的思想提出了c c 方法，该方法使用关联积分同时估计出时延与 嵌入窗。c c 方法也是实际时间序列中比较常用的方法，针对该方法的缺陷，国内学者 作了相应的改进。 以上讨论的是常用的相空间重构方法，重构的目标是使重构吸引子和真正吸引子的 近似程度达到全局最优。但由于无法得到非线性时间序列关于相空间重构的先验知识， 因此上面提到的方法都具有一定的主观性。目前并没有一种适合各种非线性时间序列的 通用相空间重构方法，需要结合具体情况进行分析，以选择出适合具体情况的重构方法。 此外，各种新的重构方法也不断地被提出。 2 。2 数据流挖掘介绍 2 2 1 数据流模型 数据流是大量的、快速的、按时间顺序连续到达的数据形式。对数据流的研究可追 溯到1 9 5 0 年m u l 妁和p a t t e r s 0 n 所作的工作，1 9 9 8 年，h e n z h 毽e r 等人首次对数据流模 型进行了定义，其中还包括了对多路访问的描述，自1 9 9 6 年，舢o n 等人证明了单路访 问算法计算数据流统计摘要所需内存大小的上限和下限，数据流模型引起广泛的兴趣。 目前，在数据流研究领域中存在多种数据流模型。不同的数据流模型具有不同的适 用范围，需要设计不同的处理算法。设数据流中的数据项，x 。，x 2 ，x n 。， 依次按下标顺序到达，它们描述了一个信号a 。按照x i 描述信号a 的方式，流数据模 型可分为i l 副： ( 1 ) 时序模型：a i 】= x i 。此时，数据流中的每个数据项都代表一个独立的信号。 ( 2 ) 现金登记模型：令x i _ 0 ，i i ) ，且i i = o ，则a i d = a i 1 d + i i 。此时，数据流中的 多个数据项增量式地表达一个a 啪。 ( 3 ) 十字转门模型：令x i = ( j ，u i ) ，则a i d 】a i 1 d 】+ u j 。其中u i 可为正数，也可为负 数。此时，数据流中的多个数据项表达一个a d 】。a d 】随着数据的流入，可能会增加， 也可能会减小。 在这3 种模型中，十字转门模型是最具一般性的数据流模型，其适用范围最广，也 o n l i n e - 矾t 方法在时间序列数据流预测中的应用研究 最难处理。流数据分类与聚类通常使用的是时序模型，它们将数据流中的每个数据项看 作一个独立的对象。若将a j 】一记为信号j 出现的次数，则流数据频繁模式挖掘通常使 用的是现金登记模型，只允许数据的插入。也有算法研究了同时存在数据插入和删除时 的流数据频繁模式挖掘问题。此时，算法应用的是数据流的十字转门模型。 2 2 2 数据流模型与传统数据模型的区别 我们知道传统数据库技术的一个共同点是：数据存储在介质中，可以多次利用；用 户提交数据操纵语言( d a ：t am a 啷u l a t i o nl a i l g u a g e ，简称d m l ) 来获取查询结果。在传 统的数据库管理系统中数据存储是有限的、具有一定稳定性的数据集合，系统可以很好 地解决它的传输、计算、存储( t c s ) 等问题，但是，当数据规模很大时，数据如果以 磁盘或者磁带为介质，执行查询操作需要大量的i o 交换，导致效率低下。t ，c ，s 的 解释如下： t ：传输，将全部数据信息传输到程序当中。 c ：计算，在大块的输入数据上以当前的速率进行复杂函数的计算。 s ：存储，对数据进行临时存储或者将全部数据进行长期存档。 数据流的出现对t c s 需求提出了两个独特的挑战： ( 1 ) 自动数据采集设备等先进的数据采集设备能够自动地提供高细节的数据，并且 这种数据供给包含了持续的数据更新能力。 如互联网这种通用网络系统，它分布在大量的数据源和成百万的用户间。它提升了 事务处理速率并且能够产生了多个流：浏览点击、用户查询、p 通讯日志、e i i l a i l 地址和 通讯日志、w e b 服务和点对点下载等等。 ( 2 ) 需要在近似实时的方式下在变化的流上进行复杂的分析。 在传统的数据形式中，对基础数据的修改会影响到更新，而其上进行的实时查询一 般是简单的。更复杂的分析如趋势分析、预测等是典型的离线操作。这些在线和离线操 作的一个真实例子就是银行的信用卡交易及信息分析。然而，由于应用监控器产生了自 动的流数据入，这种流入产生了流数据形式。这些监控器可能是天文、大气、网络、金 融、或者相关的传感器，检测孤立点，需要近似实时精确地和流数据更新保持步调一致 并且反映数据快速的变化趋势，或者从数据中快速地分析出结果以快速地响应需求。 区别于传统应用模型，流数据模型具有以下4 点共性：( i ) 数据实时到达； ( 2 ) 数据到达次序独立，不受应用系统所控制；( 3 ) 数据规模宏大且不能预知其最大值； ( 4 ) 数据一经处理，除非特意保存，否则不能被再次取出处理，或者再次提取数据 代价昂贵。 大连理工大学硕士学位论文 利用传统技术处理这种模型，必须将数据全部存储到介质中，然后通过提交d m l 语句访问存储介质来获取查询结果。但是，由于数据规模宏大且到达速度很快，传统技 术难以满足实时要求。 2 2 3 数据流挖掘框架 数据流挖掘 1 61 7 】是数据流管理技术的一个重要研究方向。数据流挖掘就是在流式数 据上发现提取隐含在其中的、人们事先不知道的、但是又潜在有用的信息和知识的过程。 由于数据流本身的特点，许多传统的数据挖掘技术不适合于数据流挖掘因为数据是以流 动方式出现，并不像传统的数据是静态存储在磁盘中，许多数据如果没有被保存将无法 重新访问，所以，要求数据流挖掘技术不能多次重复扫描数据只能对数据进行一次或几 次扫描就完成挖掘。而且，数据流中的数据规模宏大，内存无法存储全部数据，也使得 数据挖掘技术只能利用有限的内存提取数据流的概要特征信息作为挖掘算法输入数据， 所以挖掘的结果通常是近似的。由于数据不断被更新，挖掘的结果也随时间不断变化， 因此，数据流挖掘技术应当支持增量计算，并不断将挖掘结果返回给用户。基于数据流 的快速流入和数据流中的数据量极大的特点，要求算法的事件复杂度必须较低，必须能 够在内存中实现，不能进行内外存数据交换，因为内外存数据交换会浪费大量的时间。 内存资源的有限性也要求算法占用的内存不能太大。 图2 3 数据流挖掘框架 f i g 2 3d a t as 缸e 锄m i l l i n gf 托i i n e 根据数据流的独特性，开辟一条新的思路，提出基于概要数据结构的数据流挖掘技 术，以满足在线、实时挖掘数据流的需求。图2 3 所示为数据流挖掘框架。在这个架构 中，数据流算法需要在内存中维护一个概要数据结构，当新“元组到来时，更新概要 数据结构，当需要查询挖掘算法处理结果时，也同样要从概要数据结构中获取信息。 o i l l i n e - m 盯方法在时间序列数据流预测中的应用研究 2 2 4 数据流挖掘算法 目前，流数据挖掘算法的研究主要集中在频繁模式挖掘、聚类、分类、时间序列和 孤立点挖掘等方面。 ( 1 ) 频繁模式挖掘【1 8 】 频繁模式挖掘无论是在理论还是应用方面均得到了广泛的研究并取得了非常多的 成果，出现了许多经典算法，如a p r i 耐、f p g r o w c l l 、c l o s e t 、c h a i 己m 算法，但这些 算法难以实现增量式更新，不适合流数据挖掘。因为频繁模式挖掘是一系列连接操作的 集合，在看到所有过去和将来的数据之前，任何项集的计算不可能完整地完成，使得在 数据流环境中挖掘和更新频率模式变得困难。与对静态数据集的挖掘相比，流数据有更 多信息要追踪和更复杂的处理，频繁项集会随时间而变化，非频繁项在后来可能成为频 繁项而不容忽视，存储结构需要动态调整以反映频繁项集随时间进化的情况。针对流数 据的频繁模式挖掘，专家学者也陆续提出许多相关算法，其中，f p 妣锄和f p d s 算 法是两个典型的频繁模式挖掘算法。c g i 锄e l l a 和j ia _ w e ih 趾等提出了f p s 仃e 锄【1 9 】数 据结构，用于解决流数据频繁项集的挖掘，采用倾斜时间窗口技术来维护频繁模式以解 决时间敏感问题。f p d s 算法【2 0 】提出了一种f p d s 树数据结构来存储潜在的频繁项集， 每个数据分段只存储了潜在频繁闭合项集，不需要独立存储项集的各个子集，极大地减 少了项集的存储量，而且，项集按全局1 项集的支持数降序排列，使得出现频率越高的 项目越靠近树根，这样的压缩树有更高的压缩率。 ( 2 ) 分类分析 流数据分类是流数据挖掘的重要组成部分，目前己有许多相关的算法。v f d t 和 c ? d t 是两种很典型的流数据分类方法。p d o m i n g o s 和g h u l t e n 提出了一种改进的 h o e 妇f d i n g 决策树分类算法v f d t e 巧f a s td e c i s i o nt r e e ) 2 ，算法使用恒定的内存大小 和时间处理每个样本，有效解决了时间、内存和样本对数据挖掘，特别是高速流数据上 的数据挖掘的限制。p d o m i i l g o s 和g h l l l t e n 引入了滑动窗口技术，对v f d t 算法进行 改进，提出了c v f d t 算法【2 2 】，除了保留v f d t 算法在速度和精度方面的优点外，增 加了对数据产生过程中变化趋势的检测和响应，得算法更好地适应对高速时变流数据的 分类。 ( 3 ) 聚类分析 ， 流数据的出现对传统的聚类算法提出了前所未有的挑战。由于无法完整地存储历史 数据，只能根据新数据来追踪聚类变化，这就要求算法必须是增量式的，对聚类表示要 简洁，对新数据的处理要快速，对噪音和异常数据要稳健。又由于流数据可看成是随时 大连理工大学硕士学位论文 间不断变化的无限过程，其隐含的聚类可能随时间动态地变化而导致聚类质量降低，这 又要求聚类结果能够不断调整，算法要有很好的可扩展性。目前关于流数据聚类的研究 大致可分为两类：在传统聚类方法的基础上探讨增量式的聚类方法，通过不断的增量学 习来保证聚类质量，它们可以应用于某些流数据问题；针对流数据的聚类算法，典型的有 s 仃e 锄算法、c l u s t r e 锄算法和s d s 吮锄算法。 s g u l l a 等人提出的s 臼锄算法幽j 采用分级聚类的方法，使用质心和权值( 类中数据 个数) 表示聚类。c l u s 仃e 锄算法【2 4 】把流数据看成一个随时间变化的过程，而不是一个整 体进行聚类分析，该算法有很好的可扩展性，可产生高质量的聚类结果，尤其是在流数 据随时间变化较大时比其它算法产生更高质量的聚类。s d g 吮a n l 【2 5 】算法是一种基于密度 的流数据聚类算法，该算法引入了滑动窗口技术，采取了动态剪枝策略，不仅能发现任 意形状任意数目的聚类，而且能处理噪声，减少内存开销，并能对流数据历史信息进行 查询分析，是一种高效的聚类算法。该算法实用性、有效性和可扩展性好，适合处理和 分析大规模的进化数据流。 ( 4 ) 时间序列分析 在实时时间序列模式的分析中，需要在线时间序列分割算法，以便及时发现和预测 时态模式。从时间序列数据抽取模式的一般方法是，先将原始时间序列进行分割，将所 得到的子序列转换为某种高级的数据表示，如符号序列或某个特征空间中的点，然后在 此符号序列或特征空间中进行分类，生成模式或模式集合。进行时间序列分割的方法有 许多，包括基于分段回归分析技术的时间序列分割算法、人工神经网络模型的分割时间 序列算法、在线分割时间序列算法以及分段直线表示分割时间序列算法口l r