基于相空间重构和ESN的流量预测模型

基于相空间重构和ESN的流量预测模型 基于相空间重构和 ESN 的流量预测模型 薛凯，郭燕慧 (北京邮电大学信息安全中心，北京 100876) 5摘要:针对网络流量复杂的非线性和混沌性, 提出一种基于相空间重构和回声状态网络的流 量预测方法。首先通过相空间重构理论来确定最佳延迟时间和最小嵌入维数,重构网络流量 时间序列。然后根据重构后的时间序列特性匹配合适参数 ESN 模型进行训练及预测。通过 对实际网络流量的预测实验 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明, 该模型的流量预测精度可达到 90%以上,证明了该预测模 型在实际流量预测领域的有效性和实用性。 关键词:点对点;回声状态网络;相空间重构;流量预测 10 中图分类号:TP183 A network traffic prediction model based on chaotic time series and ESN Xue Kai, Guo Yanhui 15 (Information Security Center,Beijing University of Posts and Telecommunications, Beijing 100876) Abstract: For the network traffic are complex nonlinear and chaotic, a novel model based on phase space reconstruction theory (PSRT) and echo state network (ESN) is proposed. First, The optimal delay time and minimal embedding dimension are determined by PSRT, and then the 20 network traffic time series is reconstructed. Then the traffic is sent to a ESN model with suitable parameters which match it’s characteristics for prediction. Experimental results show that the prediction accuracy achieved by the proposed model is more than 90%, proved that this model is effective and practical in the field of the actual network traffic prediction. Keywords: P2P; ESN; phase space reconstruction; traffic prediction 25 0 引言 随着计算机网络规模的扩展和业务种类的急剧增长，互联网规模呈指数级增长，各种应 用对网络带宽的巨大消耗，甚至会引起网络拥塞，大大降低了网络性能，劣化网络服务质量， 因此网络流量预测对网络的管理和规划越来越重要和迫切。 30 以往的研究表明，网络流量时间序列是一个非线性、多时间尺度变换的动力系统，是一 类混沌时间序列[1],在各种因素相互作用下, 表现出极其复杂而难以精确预测的演化特征。具 有明显的自相似性[2,3]、突发性[4]、和周期性等特性。传统的时间序列预测模型(Markov 模型、 AR 模型、ARMA 模型等)只能处理平稳网络流量序列，难以刻画网络流量复杂的非线性关 系，在实际应用中受到很大限制。近些年来，许多新的模型不断被提出，如回归模型、神经 35 ，6] ，8] ，10] 、统计学习理论方法等。随着混沌学理 网络理论[5 、支持向量机理论[7 、小波理论[9 论的飞速发展，混沌理论也逐渐被用于 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 这种复杂网络流量的特性。为了利用网络流量的 混沌性实现高精度预测，本文提出一种结合相空间重构理论和回声状态网络(Echo State Network，简称 ESN)的网络流量预测模型，并通过对实际网络流量进行预测实验，证明了 该模型的有效性。 40 作者简介:薛凯，(1989-)，男，硕士，研究方向:信息安全。 通信联系人:郭燕慧，(1974-)，女，博士，副教授，研究方向:自然语言理解、智能信息处理。E-mail: yhguo@bupt.edu.cn -1- 1 ESN 的结构模型 ESN 是由 Jaeger 等人[11]提出的一种新型递归神经网络，近年来受到众多领域学者的广 泛关注。与很多神经网络类似，回声状态网络也由三大部分组成:输入层、输出层和隐层。 但隐层由大量随机生成的神经元且相互之间稀疏连接而成，构成一个巨大的动态储备池 45 (Dynamic Reservoir，简称 DR)，其网络结构如图 1 所示。 W in W back W out 图 1 ESN 结构示意图 Fig.1 ESN structure ESN 的状态更新方程和输出方程可以写为: 50 in back (1) x(k ， 1) , f (W u(k ， 1) ， Wx(k ) ， W y(k )) y(k ， 1) , f out (Wout (u(k ， 1), x(k ， 1))) (2) 其 中 , u(k ) , [u1 (k ), u2 (k ), , uK (k )]T 、 x(k ) , [ x1 (k ), x2 (k ), , xN (k )]T 、 y(k ) , [ y1(k ), y2 (k ), , y L (k )]T 分别为 k 时刻网络的输入向量、储备池的状态向量以及网 W in 为输入权值矩阵、 W 为储备池内部神经元的连接矩阵、 W back 是输出 络的输出向量。55 神经元与储备池的反馈矩阵， f (,) 是储备池神经元激活函数，一般为非线性函数如双曲正 out 切函数， f (,) 为输出激活函数，一般选取线性函数。 假设给定 M 组训练样本对为{u(i), y (i)}, i , 1, 2, M ，Wout 是唯一需要训练的权值矩 阵，训练过程如下: in back 均是随机产生，且产生后不再变 60 1) 首先初始化 ESN。各权值矩阵 W 、 W 、 W 化，状态向量 x(0) 由于开始没有任何状态故直接初始化为 0。 2) 更新 ESN 储备池状态向量。根据状态更新方程(1)依次对于给定的样本对 {u(i), y(i)} 更新储备池状态向量 x(k ) 。 3) 计算输出权值矩阵 Wout 。确定抛弃时间点 M0，舍弃之前的所有状态，取 65 , y(M )]T ，W out X , [x(M 0 ), x(M 0 ， 1), , x(M )]T 、Y , [y (M 0 ), y(M 0 ， 1), 的训练可用基本的线性回归算法求出: (W out )T , X 1Y (3) 2 基于相空间重构和 ESN 的网络流量预测模型 ESN 是一种极为适合混沌系统预测的新型模型，无论从网络结构或者是学习机理上， 都是以前的神经网络所没有具备过的，它良好的非线性逼近能力，使得其在非线性的预测中 70 -2- 取得良好的效果。与传统方法相比，其预测精度指标(归一化均方根误差)能提高若干个数 量级。但是 ESN 网络的参数选择对预测精度有很大的影响，为了选择合适的参数构建 ESN 网络，进一步提高预测性能，本文结合混沌理论，提出基于相空间重构和 ESN 的网络流量 预测模型。 [12]，令 y ， n， 表示 相空间重构是分析混沌时间序列的一种重要方法。依据 Takens 理论75 所研究的时间序列，可得到 m 维延迟向量:Y (n) , [ y(n), y(n , ), , y(n (m 1), )] ，即 相空间重构后的多维序列。通过选择合适的嵌入维数 m 和延迟时间, ，一维观测原序列的 动力学特性可被重构的多维空间向量所表达，故序列的相空间重构包含了原序列所有的特 性。相空间重构是分析混沌时间序列的第一步，选择适当的嵌入维数和延迟时间是相空间重 构的主要研究内容。 80 本文模型首先通过相空间重构理论来确定最佳延迟时间和最小嵌入维数,重构网络流量 时间序列，以此作为 ESN 的输入序列，然后根据重构后的时间序列特性匹配合适参数 ESN 模型进行训练及预测，具体过程如下: 计算延迟时间, 2.1 最佳时间延迟的意义在于让参加系统重构的相点尽可能的不相关。因为存在噪声干扰和 85 估计误差，若, 选择过小，时间序列的相空间轨迹会向同一方向挤压，信息不易显露，产生 冗余误差，而, 选择过大，会使得简单的几何对象表现得很复杂，动力系统信号失真，产生 不相关误差，重构的相空间不能描述原序列的动力学特性。 在计算, 的众多方法中，自相关函数法和互信息函数法应用最为广泛。本文采用互信息 90 函数法分析网络流量的最佳延迟时间。计算方法如下，x(i) 和 y(i) 为两组信号，给定 x(i) 的 一个测量值，预测 y(i) 的平均互信息量为互信息函数， I ( x, y) , H ( x) ， H ( y) H ( x, y) (4) (5) H ( x) , P [ x(i)]log{P [ x(i)]} x x i (6) H ( x, y) , Pxy[ x(i), y(i)]log{Pxy [ x(i), y(i)]} i 95 H ( x) 、H ( y) 为熵，H ( x, y) 为联合熵，Px [ x(i)]、Py [ y(i)] 表示信号在点 x(i) 和 y(i) 处的概率密度， Pxy [ x(i), y(i)] 表示同时测得 x(i) 和 y(i) 的概率。通过计算网络流量时间序 列的平均互信息函数，对应的第一极小值点确定为延迟时间, 。 计算嵌入维数 m 2.2 一般认为，如果重构相空间的维数足够大，就可以揭示出系统的运动规律，但是太大会 造成数据资源的浪费，且大幅增加了计算的复杂度;若选择过小，则又会丢失某些特性，重 100 构得到的多维空间不能涵盖原序列的特征。 计算嵌入维度的常用方法一般有以下几种:饱和关联维数(G-P)法[13]，伪最近领域法， 真实矢量场法和 Cao 氏法[14]。本文计算方法选取 Cao 氏法，定义下式: N m, 1 X i (m ， 1) X n (i,m ) (m ， 1) E (m , )(7) N m, X i (m) X n (i,m ) (m) i,1 为向量的范数， X i (m ， 1) 为第 i 个重构相空间向量，嵌入维度为 m+1; X n(i,m ) (m) 105 -3- 是离 X i (m ， 1) 最近的向量，为了 E (m) 检测的变化情况，令 E1(m) , E (m ， 1) E (m) (8) 如果序列是混沌时间序列，那么 E (m) 会随着 m 的增加而趋于饱和，当大于 m0 时趋于 饱和，则最小嵌入维度为 m0 ， 1。 构建流量预测模型并预测 110 2.3 在确定嵌入维数和延迟时间后，流量序列则可根据 Takens 理论相空间重构，用得到序 列 Y (n) , [ y(n), y(n , ), , y(n (m 1), )] ，作为 ESN 的输入序列，并针对其特性，选 择合适的参数构建 ESN 模型，ESN 的输入向量维度即是重构后序列的维数。储备池规模在 阈值内越大越能体现模型的动力学特性，更好的逼近训练序列，精度越高;但是，当超过阈 值后又会出现过拟合现象，导致预测时精度下降，故规模选择也要适中，其他参数一般为非 115 敏感参数，具体数值要参考重构后的序列特性做相应选择。 Y (n) 的一部分作为 ESN 网络构建好后就参照第一章中的训练过程，取相空间重构后的 训练输入样本序列，训练输出样本选取 y(n ， 1) ，将训练样本送入构建好的模型中训练 ESN 网络;最后用训练完成后的 ESN 网络对剩下的流量序列做预测即可。 3 实验与分析 120 实验数据及性能指标 3.1 本文实验数据为在某一路由器节点上每 5 秒为一个时间单元抓取的流量数据，选取 600 个流量数据做仿真预测。并与传统 ESN 模型的预测效果对比分析。为了描述模型的预测性 能，选取以下 2 个指标来衡量预测精度:归一化均方根误差(normalized root mean square error， 125 简称 NRMSE)、平均绝对百分比(mean absolute percentage error，简称 MAPE)。 S 1 ( yˆ(n) y(n))2 NRMSE , (9) D( y(n)) S n,1 1 S yˆ (n ) y(n) MAPE , ,100% (10) y(n) S n , 1 yˆ(n) 、 y(n) 为 n 时刻的预测值和实测值， D( y(n)) 表示 y(n) 的方差，S 为序列长度。 实验结果 3.2 利用互信息函数法、Cao 氏方法计算网络流量序列的相空间重构的参量，结果如图 2 所 130 示。其中，图 2(a)为延迟时间的计算结果，当延迟时间, , 2 时，互信息函数取得第一个极 小值，故由互信息法计算确定的延迟时间为 2。图(b)为嵌入维数的计算结果，当嵌入维数 m , 7 时，趋于饱和，故由 Cao 氏法计算确定的嵌入维数为 8。 -4- (a) 互信息法求时间延迟 (b) Cao 氏法求嵌入维数 135 (a) Time delay by mutual information method (b) Embedding dimension by Cao's method 图 2 网络流量的相空间重构参量的结果图 Fig.2 Phase space reconstruction parameters results of the network traffic 选取 ESN 的输入维数为 Cao 氏法求得的嵌入维度 8，经过实验发现储备池规模设为 200 140 时预测效果较好,储备池权值矩阵稀疏连接率取 5%。要使 ESN 具有回声效应，谱半径选取 需小于 1，取 0.7,储备池激活函数取非对称型 Sigmoid 函数，输出激活函数取恒等函数。 预测效果图如下图 3 所示，红线实线表示网络的真实流量，蓝色虚线表示该模型的预测 值。预测误差数据由计算可得 NRMSE = 0.81，MAPE = 9.59%，预测精度达到 90%以上。 145 图 3 网络流量预测效果图 Network traffic prediction result Fig.3 4 结论 本文针对网络流量时间序列的混沌特性，结合 ESN 在混沌系统中的良好预测效果，提 150 出一种基于相空间重构理论和 ESN 的网络流量预测模型，实际的网络流量预测实验表明， 该模型的预测效果好，平均绝对百分比误差(MAPE)低于 10%。同时，该模型也为其他类似 时间序列的预测提供了一种新方法。 -5- [参考文献] (References) [1] 陆锦军,王执铨.基于混沌特性的网络流量预测[J].南京航空航天大学学报,2006,38(2) :217-221. [2] G. Zhang, G. Xie, J. Yang, D. Zhang, D. Zhang. Self-similar characteristic of traffic in current metro area 155 network[J]. Proc. of 15th IEEE Workshop on Local and Metro Area Networks, 2007,1:176-181. [3] A Callado, C Kamienski, G Szabó, B Péter-Gerö, J Kelner, S Fernandes et al. A Survey on Internet Traffic Identification[J]. IEEE Communications Surveys and Tutorials, 2009,11(3):37-52. [4] Kun-Chan Lan, John, Heidemann. A measurement study of correlations of Internet Flow characteristics[J].The International Journal of Computer and Telecommunications Networking,2006,50(1):46-62. 160 [5] V. A, J. A B., Multiresolution FIR neural-network-based learning algorithm applied to network traffic prediction[J]. Systems, Man, and Cybernetics, IEEE Transactions on,2006,36(2):208-220. [6] Z.S. Yang, Y. Wang, Q. Guan. Short-term traffic flow prediction method based on SVM[J]. Journal of Jilin University,2006, 36(6):881-884. [7] Time-series prediction using a local linear wavelet neural network[J]. Neurocomputing, 2006,69(4-6):449-465. 165 [8] H.F. Feng. SVM-Based Models for Predicting WLAN Traffic[J]. IEEE International Conference on Communications,2006,2:597-602. [9] Wei Y, Wang J, Wang C, Network Traffic Prediction Based on Wavelet Transform and Season ARIMA Model[J]. Lecture Notes in Computer Science,2011,6677:152-159. [10] Y.C. Xie, Y.L. Zhang. A Wavelet Network Model for Short-Term Traffic Volume Forecasting[J]. Journal of 170 Intelligent Transportation Systems: Technology, Planning, and Operations,2006,10(3):141-150. [11] Jaeger H, Haas H. Harnessing non-linearity:Predicting chaotic systems and saving energy in wireless communication[J]. SCIENCE,2004,304(5667):78-80. [12] Takens F.Detecting Strange Attractors in Turbulence[J].Springer Lecture Notes in Mathematics.1981,898:366-381. 175 [13] GRASSBERGER P, PROCACCIA I. Measuring the Strangeness of Strange Attractors[J]. Physics D.1983,9: 189-208. [14] CAO L. Practical method for determining the minimum embedding dimension of a scalar time series [J] . Physica D: Nonlinear Phenomena.1997, 110(1-2): 43-50. 180 -6-