（计算机应用技术专业论文）基于混沌时间序列分析与支持向量机的网络流量预测.pdf

两华人学硕士学位论文 基于混沌理论与支持向量机的网络流量预测 计算机应用技术 研究生谢渺指导教师刘兴伟 现在，计算机网络已经成为人们最为重要的信息交互方式。随着网络的快 速发展，日益复杂化的应用需求使得网络管理工作越来越困难。同时，网络拥 塞、网络安全和网络故障等难题实际上也在阻碍着信息化社会的正常发展。怎 样提高网络资源利用效率，保障网络安全和及时调整、升级网络设备成为最近 的研究热点。 近年来，随着网络流量预测技术的发展，它逐渐成为解决上述难题的一项 关键技术。研究者已经提出基于网络流量预测技术在q o s ( q o s ，q u a l i t yo f s e r v i c e ) 机制中建立对不同业务的动态资源分配策略：此外，网络流量预测技 术在网络安全、网络规划方面也能发挥重要的作用，例如设计基于网络流量预 测的入侵检测系统、建立动态网络带宽分配策略等等。 通过广泛地学习和研究传统时间序列分析理论、混沌时间序列分析理论、 计算智能预测算法，本文对基于混沌理论和支持向量机的网络流量短期预测算 法进行了深入地研究，并提出了一种预测性能更佳、适应性更强的 l s v m d t w k 算法。本文的主要贡献在于：提出了一种针对小规模数据集情 形，基于混沌时间序列分析和支持向量机( s v m ，s u p p o r tv e c t o rm a c h i n e ) 的网络流量短期预测算法l s v m d t w k 。在之前提出的局域支持向量机 ( l s v m ，l o c a ls u p p o r tv e c t o rm a c h i n e ) 预测算法的基础上，通过分析其在 模型建立时的缺陷，提出用动态时间折叠( d t w ，d y n a m i ct i m ew r a p p i n g ) 算法代替欧氏距离算法度量向量之间的相似度，从而获得更为准确的预测模 型；进一步，提出“动态k 策略，使得预测模型中最临近相点的个数不再是 固定值，而是依据优化策略仅挑选最临近相点集中“合理的 相点用做预测， 使得算法适应性和预测准确度都得到提高。我们采用一段无线网络和一段有线 西华大学硕十学位论文 网络的i p 流量数据集分别进行了若干组实验，证实了提出的l s v m d t w k 算法不仅在预测准确度上更胜l s v m 算法筹，而且适应性也更强。 关键词：预测，网络流量，混沌理论，支持向量机 西华人学硕十学位论文 f o r e c a s t i n go fn e t w o r k s t r a f f i cb a s e d o nc h a o s t h e o r yw i t hs u p p o r t v e c t o rm a c h i n e c o m p u t e ra p p l i c a t i o nt e c h n o l o g y m a s t e rc a n d i d a t em i a ox i e s u p e r v i s o rx i n g w e il i u n o w a d a y sc o m p u t e rn e t w o r k sh a v e b e e nt h em o s ti m p o r t a n tw a yt h a t p e o p l ec o m m u n i c a t ei n f o r m a t i o n w i t h e a c h o t h e r a l o n gw i t h t h e r a p i d d e v e l o p m e n to fn e t w o r k ，i n c r e a s i n g l yc o m p l i c a t e dr e q u i r e m e n t si np r a c t i c e m a k en e t w o r km a n a g e m e n tm u c hm o r ed i f f i c u l t m e a n w h i l e ，c o n g e s t i o n ， s e c u r i t ya n dm a l f u n c t i o ni nn e t w o r k sa c t u a l l ya r eh a n d i c a p p i n gt h en o r m a l d e v e l o p i n go fi n f o r m a t i o nb a s e ds o c i e t y h o wt oe f f e c t i v e l yu t i l i z en e t w o r k s r e s o u r c e s ，p r o t e c tn e t w o r k s s e c u r i t y ，a d j u s ta n du p g r a d en e t w o r k s e q u i p m e n t s i nt i m ei sc u n e n t l yt h eh o t s p o ti nr e s e a r c h r e c e n t l y ，a sar e s u l to fl o n gp r o g r e s so fn e t w o r kt r a f f i cf o r e c a s t i n g ，i th a s b e e na t y p eo fk e yt e c h n o l o g y t oc o p ew i t hd i f f i c u l t i e sm e n t i o n e da b o v e r e s e a r c h e r si n t r o d u c e dt r a f f i cf o r e c a s t i n gb a s e ds t r a t e g yt od y n a m i c a l l ya l l o c a t e r e s o u r c ea c c o r d i n gt od i f f e r e n tt y p e so fo p e r a t i o ni nq o sm e c h a n i s m ；b e s i d e s ，i t a l s op l a y ss i g n i f i c a n tr o l ei no t h e ra s p e c t ss u c h 勰n e t w o r ks e c u r i t y ，n e t w o r k l a y o u te t c ，f o ri n s t a n c e ，t r a f f i cf o r e c a s t i n gb a s e di d s ( i n t r u s i o nd e t e c t i o n s y s t e m ) a n do p t i m i z i n gs c h e m eo fn e t w o r k sb a n d w i d t hw o u l db ei m p l e m e n t e d t h r o u g hw i d es t u d ya n dr e s e a r c hw i t h i nt r a d i t i o n a lt i m es e r i e sa n a l y s i s ， c h a o t i ct i m es e r i e sa n a l y s i s ，a n dc o m p u t a t i o n a li n t e l l i g e n c eb a s e df o r e c a s t i n g a l g o r i t h m s ，s h o r t t e r mf o r e c a s t i n ga l g o r i t h mo fn e t w o r k s t r a f f i cr e l y i n go n c h a o st h e o r ya n ds u p p o r tv e c t o rm a c h i n ei si n v e s t i g a t e di np r o f u n d i t y ，a n dt h e n an o v e ll s v m - d t w ka l g o r i t h mw i t hb e t t e rf o r e c a s t e dp r e c i s e n e s sa n ds t r o n g e r m 两华大学硕十学位论文 a d a p t a b i l i t y i sp r o p o s e d t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa r e p u t t i n g f o r w a r dac h a o t i ct i m es e r i e sa n a l y s i sa n ds u p p o r tv e c t o rm a c h i n eb a s e d s h o r t - t e r mn e t w o r k s t r a f f i cf o r e c a s t i n ga l g o r i t h mw h i c hi sa d e p ta ts c e n a r i o s t h a to n l ys m a l ls c a l ed a t a s e ti sa v a i l a b l e w i t ht h ep r e v i o u s l yp r o p o s e dl o c a l s u p p o r tv e c t o rm a c h i n ef o r e c a s t i n ga l g o r i t h m ，a f t e ra n a l y z i n ga n dc o n s i d e r i n g t h ev u l n e r a b i l i t i e si n m o d e l i n g , u s i n gd y n a m i ct i m ew r a p p i n gt or e p l a c e e u c l i d sd i s t a n c ei nm e a s u r i n gt h es i m i l a r i t yb e t w e e nap a i ro fv e c t o ri s i n t r o d u c e de v e n t u a l l y ；f u r t h e r m o r e t h e “d y n a m i ck ，s t r a t e g yi sd e s i g n e dt o d y n a m i c a l l yo r g a n i z et h o s er e a s o n a b l eo n e sf r o mn e a r e s tn e i g h b o r i n gp o i n t si n f o r e c a s t i n g , i n s t e a do fk e e p i n gt h en u m b e ro fn e a r e s tn e i g h b o r i n gp o i n t s i n v a r i a b l ea l la l o n g ，w h i c hb r i n g sa b o u tt h ep e r f o r m a n c es t r o n g e ri na d a p t a b i l i t y 弱w e l la si np r e c i s e n e s s as e to fe x p e r i m e n te m p l o y e dt w od a t a s e t sr e s p e c t i v e l y f r o mc a m p u sw i r e dn e t w o r k si pt r a f f i ca n dc a m p u sw i r e l e s sn e t w o r k si p t r a f f i cd e m o n s t r a t ep r o p o s e dl s v m d t w ka l g o r i t h mc e r t a i n l yc a np e r f o r m b e t t e rt h a nl o c a ls u p p o r tv e c t o rm a c h i n ea l g o r i t h mn o to n l yi nt h ef o r e c a s t e d p r e c i s e n e s s ，b u ti na d a p t a b i l i t ya sw e l l k e y w o r d s ：f o r e c a s t i n g ，n e t w o r kt r a f f i c ，c h a o st h e o r y ，s v m i v 西华大学硕士学位论文 9 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成 果归西华大学所有，特此声明。 作者签名： 导师签名： r 日 口 u 月 月l1 西华大学硕士学位论文 l o 授权书 西华大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，西华大学可以将本论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 印手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书； 2 、不保密彤适用本授权书。 ( 请在以上口内划) 学位论文作者签名：诵叻 指导教师签名 日期：叫川 日期：加7 西华大学硕士学位论文 1 绪论 1 1 研究背景及意义 近年来，随着计算机网络的快速发展，网络的o o s ( q u a l i t yo fs e r v i c e ) 也 受到了越来越多的关注。q o s 是指网络提供更高优先服务的一种能力，包括专 用带宽、抖动控制和延迟( 用于实时和交互式流量情形) 、丢包率的改进以及 不同w a n 、l a n 和m a n 技术下的指定网络流量等，同时确保为每种流量提 供的优先权不会阻碍其它流量的进程。o o s 是网络的一种安全机制，是用来解决 网络延迟和阻塞等问题的一种技术。在正常情况下，如果网络只用于特定的无 时间限制的应用系统，并不需要o o s 机制，比如w e b 应用，或e m a i l 等。但是 对关键应用和多媒体应用就十分必要。当网络过载或拥塞时，q o s 机制能确保 重要业务量不受延迟或丢弃，同时保证网络的高效运行。 然而，当前q o s 机制中对不同业务的资源分配仍主要采用静态方法。静态 资源分配算法具有如下明显缺陷： ( 1 ) 业务流量统计特征很难用模型精确描述； ( 2 ) 由于排队影响，业务流量的统计特征具有动态性； ( 3 ) 不同业务类型，流量往往具有不同的特征。由于上述原因，静态资源 分配算法既难以做到在网络拥塞时有效保证优先业务的服务质量，又难以在网 络较为空闲时提高网络的吞吐量。 基于静态资源分配所存在的问题，文献【l 】提出了基于测量的参数估计方法， 该方法在边界路由器中周期性地测量网络流量参数，并利用大数据量业务源复 用渐近分析理论估算o o s 指标，根据估算值动态调整网络资源分配参数；文献 【2 n 提出基于对各业务流量的测量，动态调整w f q 的权值来实现不同业务的 资源分配。网络流量表现出的突发性及复杂的强非线性，使网络流量参数的测 量具有较明显的滞后性，当前各业务流量的分配关系与流量特性，并不代表几 小时、几分钟或几秒钟后的流量分配特征，因此基于测量的动态资源分配方法 仍然具有较大的局限性。 预测技术的发展与成熟则使得建立一种基于流量精确预测的动态资源分配 7 西华大学硕士学位论文 方案成为可能1 3 1 。通过对网络流量特征的分析与建模，以比较高的准确度预测出 下一时刻流量的变化，根据预测结果建立动态资源分配方案将显著的提高q o s 性能。此外，网络流量预测技术在网络管理、网络拥塞控制和网络安全方面也 扮演着重要的角色，例如网络资源优化、基于流量预测的网络异常入侵检测系 统等【4 】- i 剐。因此，进一步研究准确度更高、适应性更强的网络流量预测算法是十 分有意义的。 1 2 国内外研究现状 预测实际上是时问序列分析( t s a ，t i m es e r i e sa n a l y s i s ) 这门学科的一个 分支。当前流行的预测技术大致可以分为以数理统计学为理论基础的传统方法 和最近兴起的基于计算智能的方法两种类型。其中，基于计算智能的方法是目 前的研究重点，并会在将来一段时问内仍是热点。 传统预测方法主要是以统计学为理论基础，其中最为广泛也最为成功地应用 到网络流量预测领域的是b o x - j e n k i n s 时间序列分析1 7 1 。a f t ，m a 和a r m a 模 型主要用于线性稳定过程建模；a r i m a ，a r f i m a 则主要解决线性不稳定过程 的建模问题。此外，m a r k o v 模型，门限自回归模型等也有相当广泛的应用。对 于传统预测方法，国内外的研究都已经非常成熟，但是随着计算机网络规模快 速地膨胀，其流量表现出的特征也日益复杂化。强非线性，突发性的存在使得 以统计学为理论基础的传统预测技术对于网络流量的建模和预测不再得心应 手。尽管在一些对预测精度要求不高的场合，例如只关注流量的总体长期变化 趋势，可以借助一些预处理手段如滤波、平滑、差分等，使得传统方法仍有用 武之地【8 】【1 0 l ，然而要想根本地改进预测性能，还需要借助更新的理论。 计算智能算法以人工神经网络( a n n ，a r t i f i c i a ln e u r a ln e t w o r k ) 1 1 1 j 、支持 向量机【1 2 l 、混沌理论( c h a o st h e o r y ) 1 1 3 l 为代表，在网络流量预测领域应用得 最为广泛，并且受到了越来越多的关注。基于计算智能的预测方法目前仍是国 内外研究的热点，而且已有很多成功的例子1 1 4 】- 1 1 8 l 。总得来说，采用计算智能算 法的缺陷在于模型建立比较困难，计算复杂度比较高，但是其良好的泛化能力、 适应性及可信赖的准确度仍然使其具有相当大的吸引力，尤其是在大规模数据 8 西华大学硕士学位论文 并且特征复杂的情形下，它们更能表现出卓越的性能。 同样是基于统计学习理论i l l j 的人工神经网络和支持向量机在网络流量预测 领域也有比较多成功应用，例如【1 9 】和【2 0 】。与支持向量机相比，人工神经网络 更容易陷入局部最优，解的稀疏性稍差一些。但是，要应用到预测，它们两者 真正地共同面临的问题的是：它们本身仅仅是一种解优化问题的算法，并没有 系统特征分析和模型建立的功能。因此，在使用这类算法的时候我们还需要额 外的理论来辅助建立模型，实际上在预测精确度要求比较高的场合，不能足够 准确地建立预测模型将对预测性能有很重大的影响。但是，即使是这样，在数 据特征比较复杂的情况下，也很容易利用支持向量机或者人工神经网络获得好 于传统预测方法的性能。 从上世纪9 0 年代起，三大非线性学科之一的混沌理论( 另外两门学科为分 形和孤子) 在时白j 序列分析领域的应用丌始受到关注l d j 。之后，基于混沌理论 发展起来的混沌时问序列分析( c t s a ，c h a o t i ct i m es e r i e sa n a l y s i s ) 带给了我 们一套解决预测问题的全新理论和工具。混沌理论从系统动力学角度出发，度 量确定性系统表现出来的内在随机性，从而使得混沌系统具有短期可预测性。 混沌时间序列分析不同于其它计算智能方法之处在于，支持向量机和人工神经 网络本质上仅仅是解决非线性优化问题的强大工具，而并不具备对于系统特征 分析及模型建立的功能；而混沌时间序列分析却从特征分析、模型建立到非线 性优化计算都提供了解决方案。然而，混沌时间序列分析中提出的若干种预测 算法在函数逼近( 回归) 计算中多采用传统的诸如最小二乘法之类的算法，通 常会对预测精度有一定影响，因此，结合混沌时间序列分析的强大的系统特征 分析与建模能力和支持向量机或人工神经网络的强大非线性计算能力，往往能 进一步改善预测的性制1 3 l 【2 1 】。因此，基于混沌时间序列分析与支持向量机或人 工神经网络结合的预测算法的研究引起了越来越多的关注。 1 3 主要内容 首先应该明确对于网络流量的定义。网络流量是指在一定时间内网络中的通 信总量，如果根据网络类型来分类，网络流量可以分为：有线网络i p 分组流量、 9 西华大学硕士学位论文 无线网络m 分组流量或a t m 信元流量等等；根据应用层服务类型不同也可分 为：h r r p 流量、f t p 流量、m m s r s t p 流量、v b r m p e g 流量等等。事实上， 同一时刻各种类型的网络流量大致是表现出类似统计特征的，因为同一时刻的 l p 流量即是各种网络服务流量的总和；或从应用层考虑，某一段时间内，使用 w e b 服务和f 1 曙服务的人数大致是稳定的，因此以任意种类型的流量作为对 象来研究的预测算法对于其它类型的流量同样是适用的。从数据处理的复杂度 考虑，在本文的实验部分，我们从个校园有线网络和另外一个校园无线网络 获取原始流量数据并预处理成实验用的i p 流量数据。 其次，网络流量预测根据应用场合不同，通常可分为长期预测和短期预测， 或者依据不同的时间颗粒度划分，例如：月、同、小时、分钟等。长期预测通 常是以比较大的颗粒度( 月、只) 的长时问段内的历史数据为参考来分析建模， 预测未来时刻流量变化，通常更注重趋势上的准确，而不是预测值的绝对准确。 短期预测则更要求实时性，一般是依据比较短期的颗粒度较小( 通常是几分钟 至几小时) 的历史数据，预测出未来短期内流量的变化，同时也要求更高的预 测准确度。相对于长期预测，短期预测更具有挑战性。另一方面，从预测模式 的角度出发，预测一般可分为单步预测和多步预测。单步预测是指一次仅预测 下一时刻的值，而多步预测则是一次预测出未来几个时刻的值。直接的多步预 测虽然也是可行的，但是其模型建立相对比较困难，预测准确度也不高，所以 我们通常采用单步迭代的方法来实现多步预测。不过由单步迭代实现的多步预 测的最大可预测长度( 预测误差在可容忍的范围之内的最长步数，可容忍的最 大误差视具体情况而定，可以是5 、1 0 等) 将取决于每次单步预测的误差累 积。 在本研究中，我们将重点放在小规模数据集情形下，针对网络流量的短期预 测算法的研究，目标是在保证单步预测准确度更佳的基础上，尽可能地延长算 法在多步预测模式下的生命期。根据1 2 节的综述，并且文献 2 2 】已经证明网络 流量确实表现出混沌特征，因此我们考虑采用基于混沌时问序列分析和支持向 量机结合的预测算法，试图在将其成功应用到网络流量短期预测的基础上，研 究出预测准确度更佳，适应性更强的预测算法。 在理论研究部分，首先对传统的基于统计学的预测方法进行一个大致了解， 通过学习、分析和对比之前的研究成果，发现传统方法应用在网络流量短期预 1 0 西华大学硕士学位论文 测上的不足。然后， 机结合的预测算法， 进一步，通过观察、 预测的性能；之后， 1 4 本文结构 针对目前已经提出的若干种混沌时间序列分析与支持向量 深入地学习混沌时间序列分析和支持向量机的理论基础。 对比、仿真等手段来评估将这些算法应用到网络流量短期 发现其缺陷，并针对其不足提出相应的改进算法。 全文共分为6 个章节，各章节组织安排如下： 第1 章绪论部分介绍了课题的研究背景和意义，着重对国内外网络流量预测 关键技术研究的现状进行综述，并罗列出论文的研究内容和组织结构安排。 第2 章节将介绍时间序列分析的基础理论，包括对传统时白j 序列分析和混沌 时间序列分析的介绍；参考已有的研究成果，总结这些理论在网络流量预测领 域的应用。 第3 章节将介绍支持向量机的理论基础。支持向量机理论经过十几年的发 展，其各种改进和变形非常丰富，本章节将会进一步讨论几种可用的支持向量 机算法之间的性能对比，最终确定一种适用于网络流量短期预测的支持向量机 算法。 第4 章节将详细介绍混沌时间序列分析结合支持向量机的预测算法；并且介 绍用于混沌参数估计的互信息量算法和c a o 氏法。 第5 章节中，首先将检验混沌时间序列分析结合支持向量机算法应用的网络 流量短期预测的性能，之后分析其缺陷。针对算法中暴露出来的不足，提出有 效的改进方案。最后将进行更为广泛的实验来验证改进算法的有效性，并给出 实验结论。 文章的最后，对全文的研究工作进行总结，并对未来还需要进行的工作进行 了展望。 西华大学硕士学位论文 2 时间序列分析理论基础 2 1 概述 所谓时间序列就是按时间次序排列的观测值集合。按照研究现象或问题的 不同，可以得到各种时间序列。例如经济学家观察某种物价指数波动，气象学 家研究某地降雨量，电气工程师研究电子接收机的内部噪声等都会观测到依某 种度量单位测量的一串数据，其自然顺序就是按出现的时间先后次序排列而得 到的时间序列。或也可表示为，对某一个或一组变量工( f ) 进行观察测量，将在 一系列时刻f ，f ：，f _ ( t 。 f ： 0 。 活1 卢1 应用a r m 籼l m a 模型的步骤为： ( 1 ) 根据时间序列的散点图、自相关函数和偏自相关函数图识别其平稳 性。 ( 2 ) 对非平稳的时间序列数据进行平稳化处理。直到处理后的自相关函 数和偏自相关函数的数值非显著非零。 ( 3 ) 根据所识别出来的特征建立相应的时间序列模型。平稳化处理后， 若偏自相关函数是截尾的，而自相关函数是拖尾的，则建立a r 模型：若偏自 相关函数是拖尾的，而自相关函数是截尾的，则建立m a 模型；若偏自相关 函数和自相关函数均是拖尾的，则序列适合a r m a 模型。 ( 4 ) 参数估计，检验是否具有统计意义。 ( 5 ) 假设检验，判断( 诊断) 残差序列是否为白噪声序列。 ( 6 ) 利用已通过检验的模型进行预测。 1 4 西华大学硕士学位论文 文献8 1 中，邹柏贤等提出一种结合a r m a ( 2 ，1 ) 模型和最小均方误差 预测算法的基于流量预测的网络管理系统，当预测值以一定概率超过事先设置 的阈值，系统则认为下一时刻网络将发生过载，并发出告警。h u a n g 和s h i h 也提出一种改进的基于a r m a 模型的方法应用到预测电力负载【引。根据累积 量和双谱原理，两个高斯性验证过程被整合进提出的改进方案之中，用于寻找 更为合适的模型。由于参数估计将直接决定a r m a 模型的性能，【9 1 也证实， 这种改进能显著提高参数估计的准确性。在【1 0 】中，研究者利用小波多分辨分 析( w m r ，w a v e l e tm u l t i r e s o l u t i o n ) 技术来平稳化原始流量数据，获得长期 总体变化趋势。之后，基于a r i m a 模型，f 1 0 】中提出的算法能保持大约1 0 上下的误差( 时间单位：周) 对i n t e r a c t 骨干网流量进行长期预测( 至少6 个 月) 。此外，金旗等通过分段平均、取自然对数、一次差分三个步骤的预处理， 把具有较强突发性、线性非平稳的网络流量变换为一个短时相关的平稳时间序 列并用a r i m a 模型获得了比较好的预测效果1 2 8 盯。 可以看出，参数估计准确与否是能否利用a r m a 系列模型获得良好性能 的关键，而参数估计的准确度又往往依赖于数据本身的特性，这意味着对于具 有强非线性和突发性的流量数据，对其进行平稳化预处理至关重要。然而，如 果可用于分析建模的时间序列比较短，势必将极大地增加平稳化的难度，从而 影响模型参数的估计：另一方面，对数据的平稳化处理后，实际已经破坏了数 据的原始特征，这时已经没有准确地获得下一时刻预测值的可能。而在本研究 课题中，我们希望是获得一种可用于流量短期准确预测的算法，并且为了使算 法具更广泛的适应性和应用场合，也要求不依赖于比较大规模的历史数据。因 此，a r m a 系列模型还不能完全满足需要，应该尝试从另外的角度出发寻求 解决方案。 2 3 混沌时间序列分析 2 3 1 引言 从时间序列研究混沌【1 3 1 ，开始于p a c k a r d ( 1 9 8 0 ) 等提出的重构相空间理 论。我们知道，对于决定系统长期演化的任一变量的时间演化，均包含了系统 1 5 西华大学硕士学位论文 所有变量长期演化的信息。因此，我们可以通过决定系统长期演化的任一单变 量的时间序列来研究系统的混沌行为。而吸引子的不变量一关联维( 系统复杂 度估计) 、k o l m o g o r o v 熵( 动力系统混沌水平) 、l y a p u n o v 指数( 系统特征 指数) 等在表征系统的混沌性质方面一直起着重要的作用。其中l y a p u n o v 指 数量化初始封闭轨道的指数发散和估计系统的混沌量，它从整体上反应了动力 系统的混沌量水平。 混沌时间序列分析的预测方法包括：全域法、局域法、加权零阶局域法、 加权一阶局域法、基于l y a p u n o v 指数的预测方法和基于人工神经网络的预测 方法等。但是，大体上这些方法可以划分为全域法和局域法两大类型。关于这 些方法本文后面章节会有更为详细的介绍。此外，由于支持向量机理论的发展 和成熟，也有研究者提出了基于支持向量机的混沌预测方、法1 2 1 j 。 2 3 2 混沌动力学与混沌特性 所谓一个系统，是指一些相互联系和相互作用的客体所组成的集合。这里 的客体可以指自然界中任意确定的事情，也可以是一个抽象的事物。系统的性 质或特征可以由一些所谓的状态变量来表征，若一个系统的历史和未来完全由 某一个指定时刻的状态所确定，则称之为确定性系统。动力系统就是研究一个 确定性系统状态变量随时间变化的规律。 一个系统是混沌的，归结起来有以下几点： ( 1 ) 混沌具有内在随机性。它是确定性系统内部随机性的反映，无须附 加任何随机因素，但系统仍会表现出类似随机的行为。 ( 2 ) 规律性。尽管混沌时间序列体现出随机性质，但它是确定性方程的 解，初始条件确定后，时间序列就已经确定，即其随机性是内在的，这就是混 沌运动的规律性。 ( 3 ) 混沌具有分维性。各种奇异吸引子都具有分形结构，由分数维来描 述其特征。 ( 4 ) 混沌现象具有对初始条件的敏感依赖性。只要初始条件稍有差别或 者小扰动，则会使系统最终状态出现巨大差异。 1 6 西华大学硕士学位论文 2 3 3 相空间重构 在时间序列的分析中，决定序列的可观测因素很多，而且相互作用的动力 学方程往往是非线性的，甚至是混沌的。同时，因测量精度的实际限制、计算 的复杂性、以及可能存在的本质上的非确定性因素等多方面的困难，严重制约 着人们对时阳j 序列内在机制的理解。2 0 世纪8 0 年代以来，由于t a k e n s 2 9 l 对 w h i t n e y 早期在拓扑学方面工作的发展，使得深入分析时间序列的背景和动力 学机制成为可能。在确定性的基础上，对序列动力学因素的分析，目前广泛采 用的是延迟坐标状态相空间重构法。一般来说，非线性系统相空间可能维数很 高，甚至无穷，但是在大多数情况下维数并不知道。在实际问题中，对于给定 的时间序列五，屯，i 。，- 1 ，我们通常是将其扩展到三维甚至更高的空间中 去，以便把时间序列中蕴藏的信息充分地显露出来，这就是延迟坐标状态相空 白j 重构法。 定义l 设( ，l p ) ，( n j ，n ) 是两个度量空间，如果存在映射妒：一l 满足： ( 1 ) 妒满射； ( 2 ) p ( x ，y ) = 一( 1 i 口o ) ，q ( y ) x v x ，y ) ，则称( ，p ) ，( ，n ) 是等距同构的。 定义2 如果( 川，n ) 与另一度量空间( 1 v 2 ，见) 的子空间( 0 ，以) 是等距同构的， 则称( l ，n ) 可嵌入( 2 ，办) 。 t a k e n s 定理m 是d 维流形，妒：m 一肘是一个光滑的微分同胚，y ：m r ， y 有二阶连续导数，( 仍y ) ：m - - - , r 材卅，其中烈妒，y ) = o ，o ) ，y ( 妒2 0 ) ) ，y 纠o ) ) ) ， 则咖( 妒，y ) 是m 到r 斛1 的一个嵌入。 t a k e n s 证明了可以找到适当的嵌入维数，在这个嵌入维数下，可以把有规 律的轨迹( 混沌吸引子) 恢复出来，从而为混沌时间序列的预测奠定了理论基 础。对于时间序列x “) ，石( f ：) ，工纯) ，厅是序列的长度，根据t a k e n s 提出的嵌入 定理，重构相空间为： 置i 五- z o ) ，工o + f ) 9 * 19 工o + 细一驴) ) ，i 一1 , 2 ，m 。其中置为 相空间的点，m 为嵌入维数，f 了为时间延迟，j l f 为重构相空间中相点的个数， mi l l 以一( 臃一1 弦。 嵌入维数m 和时间延迟f 的选取极为重要。最佳时间延迟的意义在于让参 加系统重构的相点尽可能的不相关，从而让嵌入空间中的样点所包含的关于原 吸引子的信息尽可能的大。目前，常用的最佳延迟时间的选取方法主要有自相 关函数法( a c ，a u t oc o r r e l a t i o n ) 、复自相关函数法( c a c ，c o m p l e xa u t o 1 7 西华大学硕士学位论文 c o r r e l a t i o n ) 、互信息量法( m u t u a li n f o r m a t i o n ) 和c c 法。常用的最佳嵌 入维数的选取方法有g p 算法、预测误差最小法、c a o 氏法【3 1 】等。 然而，无论采取何种方法都不能完全避免参数估计中的误差，考虑到它们 的性能和实现的复杂度，在我们的算法中，采取了互信息量算法来计算时间延 迟和c a o 氏法来计算最佳嵌入维。 2 3 4 时间序列预测 要利用混沌理论分析一个系统，首先应该保证这个系统具有混沌性，这可 以通过对混沌参数例如l y a p u n o v 指数度量来判断。通过对系统混沌性判别和 相空间重构两个步骤之后，实际上已经为系统建立起了模型，然而要进行预测， 我们还需要一套计算方法。 圃 f 乞1 l 竺一j f i g2 1p r o c e d u r eo fl o c a lf o r e c a s t i n gm e t h o df r o mc h a o t i ct i m es e r i e sa n a l y s i s 图2 1 混沌时间序列局域预测法过程 前面已经提到，混沌时间序列预测大致上分为全域预测法和局域预测法两 大类型。混沌时间序列的全域预测法就是用相空间中所有的相点来拟合重构函 1 8 西华大学硕士学位论文 数f ，而局域预测法则是用相空自】中某些相点来拟合重构函数f 。由于全域预 测中要用到空间中所有的相点，相点的个数相对较多，所以当重构函数，比较 复杂时，全域预测法的实现会相当困难。局域预测法只考虑了相空间中的某些 相点，所以局域预测法实现起来比全域预测法要容易得多。通常，局域预测法 是在所有的相点中选出与需要预测的状态点欧氏距离最近的k 个相点来拟合 重构函数f 。普遍选取距离参考状态点空间欧氏距离最近相点的原因是认为： 空间距离最近的相点其演化的特性也是相近的。然而在各种不同的应用场合或 对应不同特征的时间序列，欧氏距离不一定是最理想的度量“相似度”的工具， 对它的进一步考虑在之后的研究中会涉及到。 除了混沌时间序列分析中提出的零阶局域预测法、加权零阶局域预测法、 一阶局域预测法、加权一阶局域预测和l y a p u n o v 预测法，可用的拟合重构函 数，的算法还非常丰富，包括一元线性函数，或非线性的如多项式函数，人工 神经网络或者支持向量机等等。图2 1 所示为混沌时间序列局域预测法的过 程。 2 3 5 应用 陆锦军等人基于混沌时间序列重构相空间理论，根据最大l y a p u n o v 指数， 分别采用w o l f 原始算法和改进算法，对高速网络中自相似信源的速率进行了 预测，并给出了最大可预报时间i r 丌。在文献【1 8 】中，作者利用低通滤波技术预 处理原始数据后，用最大l y a p u n o v 指数法预测了长期的g s m 通信网络中的 流量，在未来6 个月流量的预测中，准确度大概可以维持在平均5 ，最大8 误差的水平。雷霆等提出了一种基于混沌时间序列分析的全新的网络流量加权 局域预测模型3 2 j 。该模型采用互信息量和主成分分析的方法来确定重构相空 间里面预测中心的临近相点，并且根据各临近相点与预测中心的互信息的大小 来定义它们在预测公式中的权值；其中实验部分也证明了相对于空间距离来确 定临近相点及其权值的传统局域模型，该模型有更好的预测效果。以颗粒度为 1 小时，每天2 4 个数据点，共计9 1 天的历史数据来建模，并预测未来1 天之 内2 4 个数据点，其中9 0 左右的预测点误差都小于1 0 。在文献f 3 3 1 中，作 者采用了混沌时间序列分析与支持向量机相结合的局域预测算法( 局域支持向 1 9 西华大学硕士学位论文 量机算法，l s v m ，l o c a ls v m ) ，在v b r m p e g 流量的短期预测应用中， 获得了比较好的性能。 通过对上述文献的分析，关于混沌时间序列分析应用到网络流量预测，我 们大致可以获得如下的结论： ( 1 ) 在拥有较长历史数据可供分析的情况下，用混沌时间序列分析进行 大颗粒度的长期预测比较容易获得良好性能； ( 2 ) 在拥有较长历史数据可供分析的情况下，用局域预测法通常性能好 于全域预测法，但是如何选取相似相点是关键； ( 3 ) 与传统的预测算法相比，混沌时间序列预测算法本身的复杂度更低， 需要估计的参数仅有2 种，另外算法整体契合度更高。 然而，考虑我们期望的应用场合： ( 1 ) 可用于分析的历史数据较少； ( 2 ) 小颗粒度，通常为几分钟到几十分钟； ( 3 ) 准确度较高的短期预测； ( 4 ) 生命期尽可能长的基于单步迭代的多步预测。 基于这样的要求，上述的算法似乎都不能直接应用。我们曾经针对这种应用场 合作过一些研究( 川。考虑到对预测准确度的要求和口流量的强非线性特征， 因此我们没有选用最大l y a p u n o v 指数预测法或其它近似线性的预测算法。另 外，虽然在这罩我们并没有太多的历史数据用于分析和参数估计，采用全域预 测法时白j 耗费也不会太大，但是考虑到局域预测法不仅在性能上优于全域法， 而且在很多场合其预测精度也略胜一筹，因此我们最终还是选择了基于混沌相 空间重构和支持向量机的局域预测算法。但是，在这种情况下，我们仍然面临 以下挑战： ( 1 ) 由于历史数据并不太充分，使得流量中存在的突发性对整个数据特 征及参数估计影响都比较大； ( 2 ) 预测性能对参数选择非常敏感： ( 3 ) 预测性能对局域法中k 值的选择非常敏感。 如果事先对数据进行平滑( 通过插值) 预处理，可以使得参数估计的准确度上 升，但这样做不仅破坏了原始系统特征，同时也使整个算法的复杂度显著上升， 与其这样做，不如直接采取b o x - j e n k i n s 模型。而事实上，我们发现，即使不 西华大学硕士学位论文 对原始数据进行预处理，只要k 值大小选取得当，我们总能选到足够多的能够 比较准确反映未来流量变化趋势的相点。但是，由于参数估计误差的存在，选 取的k 个相点中又存在完全不能反映未来变化的相点，我们称之为异常点，假 设我们能够依据某种策略剔除这些异常点，则利用剩下的相对准确的相点我们 同样能获得比较准确的预测结果。于是，我们提出了“k i c k - o n e 策略，即根 据空间距离最近原则选取k 个相点后，剔除掉其中一个最有可能为异常的点， 用剩下的k 一1 个相点预测；另一方面，即使是k 个相点中并不存在异常点，依 此策略剔除掉一个点后，对预测结果也并没太大影响。实验证实，在单步迭代 预测模式下，这种改进通常可以使我们获得3 步以上误差在5 上下的预测值， 这个结果至少可以保证不会比改进之前的性能差。但是，这种策略还是显得有 些粗糙，而且并没有从根本上解决问题，比如每次都剔除1 个点这个做法是否 合理，动态调整k 值会不会有效果，用其它策略来代替空间距离度量相似度是 否更加合理，这些问题都值得进一步的研究。因此，如果想要获得真正适应性 更强，性能更佳的算法，还需要从更多的方面进行考虑。 2 4 其它计算智能预测算法 2 4 1 灰色理论 灰色预测是对灰色系统所做的预测【3 5 1 。一般地说，社会系统、经济系统、 生态系统都是灰色系统。灰色系统理论认为对既含有己知信息又含有未知或非 确定信息的系统进行预测，就是对在一定方位内变化的、与时间有关的灰色过 程的预测。尽管过程中所显示的现象是随机的、杂乱无章的，但毕竟是有序的、 有界的，因此这一数据集合具备潜在的规律，灰色预测就是利用这种规律建立 灰色模型对灰色系统进行预测。通过少量的、不完全的信息，建立灰色微分预 测模型，对事物发展规律做出模糊性的