基于改进的HHT的网络流量预测算法

安计勇，范玉红，王 寅

（1.中国矿业大学 计算机科学与技术学院，江苏 徐州221116；2.中国矿业大学 图文信息中心，江苏 徐州221116）

0 引 言

Hilbert－Huang变换 （HHT）由两阶段组成，第一阶段叫做经验模式分解 （EMD），它把原来相对繁杂的非平稳多分量序列分解成几组单分量的本征模态函数 （IMF）；第二阶段叫做希尔伯特谱分析 （HAS），它对每个IMF 做Hilbert变换，得到有意义的瞬时频率，然后计算得到信号的Hilbert谱、三维时频谱以及Hilbert边际谱，并作后续分析。HHT 发展至今仅十几年的时间，针对HHT 中呈现的不足，也有很多的研究人员不断地对其进行研究并改进，同时HHT 也在很多不同的领域中用来分析。其中，第一阶段中，算法利用三次样条插值法 （cubic spline interpolation，CSI）来分别连接所有的极大值点和极小值点，得到序列的上下包络线，然而，三次样条插值法在插值过程中会导致过冲的问题；另外，由于序列的两端端点不一定就是极值点，因此，容易产生端点效应［1］，为了能够更准确地覆盖所有的数据点，需要在数据的两端延伸极值点，而且每端都需要在原始数据的基础上至少延伸两个极值。

1 HHT分析及改进

1.1 过冲问题

在EMD 算法过程［2］中，如果均值曲线计算不准确，那么对信号进行EMD 分解得到的结果也就不准确，这样再针对得到的不准确的各个IMF分量对信号进行分析，最终将得到的是错误的结果。由上文可知，利用三次样条插值法连接得到的上下包络曲线容易出现过冲现象，如图1 （a），包络线在A、B、C三处均产生过冲现象，使得到的均值曲线产生偏差，为此，本文利用三次Hermite插值拟合法［3］（cubic Hermite interpolation，CHI）连接包络线获取均值曲线的方法。

图1 三次样条插值与三次Hermite插值连接包络结果

图1 （b）是对80到100单位时间间隔的流量数据分别利用CSI和CHI连接得到的上下包络线结果，由图中可以发现，利用CHI连接得到的包络线虽然光滑度没有CSI高，但是能够保证在每一小段的曲线拟合光滑连续，且相对CSI来说，CHI得到的曲线比较平坦，更贴近原始信号，精确度更高。

1.2 端点飞翼

由图1 （c）和 （d）可以看出，不管是利用CSI还是CHI，在边界处都出现或多或少的端点飞翼。由EMD 算法过程我们知道EMD 是经过反复筛选的，一旦前面的IMF存在误差，那么后面的IMF 的误差就会越来越大，由一开始只是端点附近的包络失真逐渐向内传播，最终得到的误差就很大甚至得到错误的结果，这样对于数据的分解也就失去了原有的意义。

为了解决这种端点飞翼问题，需要对端点进行延拓处理，本文提出一种改进的HHT 方法 （improved HHT，IHHT），利用SVR 对原始数据进行端点预测延拓处理，并引入窗函数控制延拓误差，同时结合柔性更好的三次Hermite插值拟合法来拟合获得均值曲线。

假设离散信号

其中，n为序列个数，Δt是信号采集的单位时间间隔，假设x（t）存在M 个极大值跟N 个极小值，第i个极大值和极小值分别为tmax（i）和tmin（i），对应的函数值为xmax（i）和xmin（i）。

以右延拓为例，对数据进行右延拓算法如下：

（1）构造SVR 模型。已知预先设置好训练样本步长L，然后将原始数据序列根据所设置的样本步长分割成 （n－L＋1）组训练样本。利用SVR 对样本进行训练，将最终得到的训练数据集合利用SVR 回归构造回归模型，并根据该模型预测获得第一个预测值x（tn＋1）。

（2）对于预测得到的数据进行极值判断，若延拓的时候出现tmin（n＋1）＜n或tmax（n＋1）＜n的情况，那么需要继续对数据进行预测延拓得到x（tn＋2），即将x（t）＝ ［x（t1），x（t2），…，x（tn），x（tn＋1）］作为新的原始数据，继续运用同样的方法进行预测获得第二个预测值x（tn＋2），并进行极值判断。

利用SVR延拓得到tmax（n＋1）、tmax（n＋2）、tmax（n＋3）或tmin（n＋1）、tmin（n＋2）、tmin（n＋3），同时利用CHI对延拓后的数据序列进行连接得到上下包络线。同理，可以对数据进行左延拓。

图2为采用SVR 对序列左右两端进行预测延拓得到的结果，其中两端部分为延拓的部分。图中能够发现经过SVR预测延伸后的曲线相对接近于真实曲线，不过始终存在误差，特别在远离端点处，预测是依据就近的几个端点进行，因此越远偏差就越大，为此，引入窗函数进行偏差控制，从而控制误差范围，为获得更为准确的IMF提供保障。

对余弦窗函数的定义

图2 SVR 端点延拓

其中，L 为数据序列延拓后的长度；S 是信号延拓的长度。

图3是将序列x（t）利用窗函数控制端点误差的结果，与图2相比，能够发现延伸的时间点值慢慢减小直至变成零，这样就让延伸部分的误差得到了控制。

IHHT 先对序列进行延拓处理，再通过窗函数控制延拓误差，既控制了预测延拓造成的误差，也保证了序列本身的正确性，是一种有效的处理HHT 中存在的端点效应的方法。图4是利用改进方法得到的上下包络线，对比图4和图1可以看出，图1 （c）中下包络线幅值在－0.2左右，然而图4 （a）中下包络线幅值大概在0.5左右，这说明新方法能有效抑制端点飞翼，同时也可以发现，新方法基本消除了过冲的影响。

图3 余弦窗控制结果

图4 新方法得到的上下包络线

利用Hilbert谱我们能够对序列的频率分布一目了然，同时通过分析信号的边际谱，我们就可以得到信号的能量分布。图5 （a）、（b）、（c）分别是信号x（t）在没有利用任何处理方法处理的情况下和通过新方法处理得到的Hilbert谱、边际谱和三维时频图。由图5 （a）可以看出，没有经过任何处理的Hilbert谱在信号两端存在相对大的失真，这是由于此前的EMD 过程中存在的端点飞翼没有得到控制导致的，而通过本文方法处理后的Hilbert谱效果有明显改善。观察图5 （b）中的左图的边际谱，发现存在不少的毛刺，而利用IHHT 处理所得结果如图5 （b）中的右图，发现效果得到明显改善；而从图5 （c）也能清楚地看到，没有经过处理的信号存在比较多离散的能量，而处理后的信号两端能量相对而言就集中得多。此外，图6 （b）是利用新方法得到的EMD 分解结果，可以看出，分解趋势项与原始信号趋势相符。

图6 （c）把端点看成是极值点，虽然这样得到的EMD分解看似不存在端点飞翼现象，但是，由于端点处不一定是极值点，因此，得到的EMD 分解是不准确的；图6 （d）是利用镜像延拓法得到的结果，它是通过图形对称的方法进行极值延伸，图6 （f）是利用周期延拓法得到的结果，它是将临近两个极值点直接平移作为延拓点的值，这两种方法对于绝对周期性曲线效果比较好，对于流量数据则适用性不强；图6 （e）是利用均值延拓法得到的结果，由于它是利用邻近3个极值点的均值作为延拓点的值，得到的曲线不是对实际序列的估计。以上几种方法，从分解结果上分析，我们可以看出，他们对于端点内部附近的包络拟合结果都达到一定的改善效果，但是由于他们没有正确地估计端点值，对后面的IMF 分解影响会越来越大，以致最终得到的结果偏离实际结果越来越远。

利用IHHT 算法处理最终得到10个IMF 分量，如图6（b）所示；虽然图6 （d）显示的镜像延拓法最终也是得到10个IMF，但是对比分析图6 （b）和6 （d）中的分解项，发现利用改进后的HHT 算法得到的分解项相比镜像延拓法得到的分解项各项结果更均匀，得到的结果更有利于后续分析。

IHHT 算法通过利用SVR 估计序列两端端点外的数据，实现序列的端点延拓，并通过引入窗函数，减小延拓的误差，这种方法有效发挥了预测信息的作用，得到的包络线相比其它的方法来说更贴近实际，对于拟合中存在的端点飞翼问题有明显的改善。

图5 处理前与处理后的谱分析

图6 不同方法的分解结果

2 IHHT在网络流量特性方面的应用

2.1 实验数据

将Bellcore 实验室的BC 数据中的LAN 数据BCpOct89作为实验数据，该流量数据在1989 年10 月5 日11：00开始采集，时间跨度1759.62s，分为两列存储，第一列是跟踪的时间，精度达到10微秒，第二列是采集到的以字节为单位的数据，所有数据字节的大小范围是 ［64，1518］，一共捕获1 000 000条数据，数据量较大。由于原始数据的时间分辨率很高，针对原始数据进行分析根本无从下手，为此，在实际研究中，实验数据以0.3s作为单位时间尺度将原有BC－pOct89通过把单位尺度内的所有数据累加作为新的单位时间点上的一条数据，这样，原来有一百万的数据经过处理后数据的总量就只有5866 条。用X（n），n＝1，2，3，…，5866来表示处理之后的时间序列。累加序列计算方法如下所示

图7 BC－pOct89（1）流量数据

2.2 相关性验证

在实际研究过程中，本文通过hurst指数和各个固有模态函数分量的自相关函数下降到零的所花的时间长短来验证利用IHHT 方法分解处理完得到的每个固有模态函数的相关性。

分别通过绝对矩法 （absolute moment method）、平滑方差法 （aggregate variance method）和R/S分析估计法，这3种方法估计X（n）的hurst指数值。如图8 （a）为绝对矩法，得到hurst＿absval＝0.5922；图8 （b）为平滑方差法，得到hurst＿aggvar＝0.6282；图8 （c）为R/S法，得到hurst＿R/S＝0.7571。虽然用各种方法得到的hurst值存在一定的差别，但是都在 （0.5，1）范围内，因此，X（n）是自相似序列。

将处理后的序列X（n）用IHHT 方法进行分解处理，结合MATLAB进行编程仿真实验，最终获取到9 个固有模态函数以及1个趋势函数。IHHT 剖解处理的结果如图9所示，这里根据处理时获取到的各个IMF 的时间先后，将它们依次定义为IMF1、IMF2、IMF3、IMF4、IMF5、IMF6、IMF7、IMF8、IMF9，剩余趋势量命名为R10。

图8 各类hurst拟合法结果

图9 IHHT 分解结果

由图9 （a）～ （k）可以发现，随着IHHT 分解量的增加，后一个IMF的曲线弧度相比前一个来说慢慢变得相对舒缓，曲线的幅度值相比也慢慢地下降，经过分解后函数的曲线跳跃性有了很大改善，而且分解后每一个分量的曲线形状也慢慢地向正弦函数趋近，这对于我们后续的流量分析和预测提供了很大的帮助。因为，如果函数曲线的跳跃性比较大，那么所求得的相应函数方差也就比较大，一旦方差达到无限大，就说明该曲线各个时间点上的数据之间存在长程相关的特性，所以，一旦方差变小，就说明该曲线各个时间点上的具有长程相关性的数据正在蜕变为短时相关数据。

分别将10个IMF 函数通过绝对矩法、平滑方差分析法、R/S分析估计法3种方法计算hurst指数，计算的结果见表1。观察表1能够看出，不管选取哪一种计算方式，得到的IMF1～IMF6的hurst指数都小于0.5，根据前面的分析知道IMF1～IMF6 具有短相关性；但是从IMF7 开始，hurst指数突然增大到0.8以上，尤其是IMF9分量，利用3种方法计算得到的hurst 指数都快达到1 了。而分析IMF7、IMF8、IMF9和R10这4个函数的走势形状可以看到，这4个函数的走势跟正弦曲线很相像，但是由长程相关性的定义可以知道，正弦曲线不存在长程依赖性，那这又是为什么呢？有学者研究发现时间序列中周期的存在对hurst的估计有影响，周期越长，估计误差越大，而且会错误地检测到序列中存在长程依赖性。而观察这几个函数曲线我们可以发现其呈现出一定的周期性，这就解释了上述不合理的情况。不过，这并不影响我们后续的预测，相反，正因为IMF7、IMF8、IMF9和R10的曲线形状跟正弦波很相近，反而为我们的预测提供了便利。

表1 hurst参数估计结果

由于短相关序列相比具有长程依赖的序列来说方差趋于零的进度要慢得多，因此，在这里再对分解得到的10个固有模态函数和原始流量数据X（n）的自协方差趋于零的进度进行对比，由于数据级差别较大，这里为了方便对比，对它们进行归一化处理。

从图10 （a）可以发现，初始曲线X（n）的归一化自协方差函数趋于零的进度相当慢，在单位尺度长度达到100的时候还是没有下降到零点，曲线基本上就是在0.05附近上下抖动弯曲前行，可见，原始流量信号X（n）数据之间存在长程依赖性；利用IHHT 进行分解得到的前3个分量的归一化自协方差函数都在单位尺度间隔5之内发生了等于零的情况，而在到达零点后下降速度很快，并都在低于0点的某个点附近上下抖动弯曲前行，可见，这3个IMF 分量与原始流量信号X（n）相比呈现出的是短相关的特性。观察图10 （b）和图10 （c）可以看出，随着EMD 分解级数的递进，每个固有模态函数的归一化自协方差函数趋于零的进度按照IHHT 方法分解得到的固有模态函数先后顺序慢慢变得舒缓，第一零点的发生时间点随着级数的增加也慢慢地变远，同时可以看到方差曲线的幅度随着级数的增加也慢慢地变大，特别是IMF9 和R10 这两个分量。

经过以上的归一化自协方差函数分析，如图10 （a）、（b）、（c），可以发现所得到结论和前面利用绝对矩法、平滑方差分析法、R/S分析估计法3种方法计算得到hurst分析结论不谋而合，前3个IMF分量的归一化自协方差函数趋于零的进度非常快，相应的hurst指数值都比0.2要小，呈现出的短相关性非常显要；而IMF4～IMF6这3个分量的归一化自协方差函数趋于零的进度虽然比前3个IMF要慢，但它们的hurst指数值均小于0.5，也具有短相关性，只不过相比前面3 个IMF 来说没有那么地显要；IMF7～R10这4个分量的归一化自协方差函数趋于零的进度相比前面几个IMF 来说慢得多，而且它们的hurst 指数大于0.8，不过这还不足以验证IMF7、IMF8、IMF9 和R10 之间存在长程依赖性，由前面的分析，我们已经知道曲线的周期性会影响hurst值的正确估算，通过观察IMF7～R10的曲线形状，我们可以发现他们呈现出一定的周期性，不符合长相关性的定义，因此不具有长程依赖性，不过，它们的周期性反而为我们的进行后续流量预测提供了便利。

图10 各个IMFs和X（n）的归一化自协方差对比

3 IHHT在网络流量预测方面的应用

通过前一节的验证说明，可以得出一个结论，就是具有长程依赖性的网络流量数据在通过IHHT 方法分解处理后，得到的每个固有模态函数都存在短相关性，这样我们就可以利用这一特性进行后续研究。本文将新算法命名为IHHT－SVR，算法思想是：首先将原始流量信号利用IHHT 方法进行分解，得到一批具有短相关的IMF，然后分别对每个IMF利用本文算法进行预测，而后对每个短相关的IMF进行分析，剔除干扰部分，最后将所得的IMF的预计结果进行叠加重构，得到的结果即为总体预测结果。

3.1 仿真实验

3.1.1 实验准备

为了对预测结果进行评判，同时由于每一个IMF 分量的幅度是不一样了，为了保证结果对比的公平性，本文利用归一化的MAE、MAPE、MSE 和MAPE 这4 个误差指标来对预测方法的性能进行分析评价，它们的值越小，说明算法的预测准确度越高。

具体如下：

（1）Mean Absolute Error（平均绝对误差）

（2）Mean Absolute Percent Error（平均相对误差）

（3）Mean Square Error（均方误差）

（4）Mean Square Percent Error（相对均方误差）

3.1.2 实验及结果分析

把前350个数据作为训练样本，后150 个数据作为预测样本，所得到的结果如图11 所示。观察图11 （a）～（j）能够看出，随着EMD 的分解级数的增加，预测曲线跟实际曲线的重叠程度越来越高，由IMF2直至R10，预测曲线和实际曲线从视觉上看差不多是达到完全吻合的地步，应该说预测结果还是比较理想的，不过也可以发现IMF1的预测曲线跟实际曲线存在的偏差相比还是比较大的，从图11 （a）中，能够清晰地看到，相比实际曲线来说，预测曲线的整体基本上是偏低了，只有在比较少的单位时间达到了还算可以的预测效果，所以说IMF1 的预测误差相比其它EMD 分量来说相当大。

表2是将EMD 分解得到的10个IMF的预测结果利用本小节前面所给出的几个指标评价的结果，从表中我们能够看出利用4种指标得到的结果基本上是一致的，从MAE结果分析，IMF1 的MAE 达到0.3693，而其它分量除了IMF2 和IMF3 在0.01 左右，其它的都小于0.01；从MAPE方面分析，IMF1的MAPE 高达0.9776，而其它分量除了IMF2和IMF3接近0.1，其余分量的MAPE均小于0.05；从MSE上看，IMF1分量达到0.0339，而其它分量都小于0.003，尤其是IMF4～R10这几个分量，结果几近于零；从MSPE 分析，IMF1 达到0.0859，而其它分量都在0.025之下。由以上分析我们可以看出IMF1的预测误差相比于其它EMD 分解结果来说明显要高得多。

图11 IMFs及其预测结果

考虑到IMF1是属于高频部分，多由于网络的突发性引起，突发成分较大，高频的震荡致使预测的误差增大，进而导致最终的预测精度下降。表2中IMF2～R10一栏是将IMF2～R10这9个分量进行重构作为最终预测结果，并利用MAE、MAPE、MSE、MSPE 这4 个指标计算的结果；IMF1～R10一栏是将IMF1～R10这10个分量进行重构作为最终预测结果，并利用 MAE、MAPE、MSE、MSPE这4个指标计算的结果，分析结果可知，IMF1的预测结果对于我们最终的预测结果的影响不大，因此，本文考虑直接剔除IMF1 分量，而不将其纳入我们的预测考虑范围。图11 （k）是把IMF2～R10这9个IMF分量的预测结果进行重构的结果，并把它们作为IHHT－SVR 模型的预测结果，直观上分析，预测曲线与实际曲线还是比较接近的，应该说在绝大部分单位时间点上的幅度和整体趋势的吻合度都达到了相对理想的效果，预测精度还算比较高，所以，在预测过程中我们完全可以将IMF1 视为干扰项直接剔除，而只针对剩余的IMF分量进行预测分析。

3.1.3 不同预测方法的误差比较

为了说明本文改进算法IHHT－SVR 的优越性，这里分别利用BP神经网络、支持向量机、小波神经网络3种模型对同一组样本数据进行预测，表3给出不同模型预测结果的归一化误差结果对比。

表2 各IMF分量及重构结果归一化误差

表3 不同模型预测结果的归一化误差

观察表3能够发现，本文算法IHHT－SVR 预测结果的MAE、MAPE、MSE和MSPE相比较于其它3个模型的预测结果都比较低，而且IHHT－SVR 的MAE 和MSE 基本上是SVR 的1/2，可见样本数据经过IHHT 处理后的确提升了预测精度，所以说IHHT－SVR 是一种有效的预测方法。

4 结束语

本文在研究HHT 过冲问题和端点效应问题的基础上，对HHT 进行改进。先利用SVR 方法对原始信号两端进行端点预测延拓处理，并引入窗函数对信号加以处理，把延拓误差控制在两边，同时结合三次Hermite插值拟合法的良好柔性来拟合包络线，以获得均值曲线，最后在EMD 分解后去掉两边延拓部分，可以得到更准确的IMF。仿真实验结果表明，新方法基本消除了过冲问题，并对Hilbert－Huang变换中的端点效应有明显的改善。同时将IHHT 应用于网络流量的特性分析及网络流量预测之中，通过对真实网络历史业务流量数据进行分析，验证了该方法能从非线性流量信号中得到真实有用的信息，并对未来流量趋势进行了有效预测，在网络流量分析中有一定的应用价值。

［1］Bai L，Liu J Z，Xu A M，et al.Boundary extension technique for HHT based on response surface method ［J］.Applied Mechanics and Materials，2013，256：2854－2862.

［2］Wei Huang，Huiyan Peng.HHT algorithm in decomposition of high－frequency period jitter ［C］//The 2nd IEEE International Conference on Information Management and Engineering，2010：226－230.

［3］Zhu Weifang，Zhao Heming，Chen Xiaoping.Improving empirical mode decomposition with an optimized piecewise cubic Hermite interpolation method ［C］//International Conference on Systems and Informatics，2012：1698－1701.

［4］Gao Bo，Zhang Qinyu.One method from LRD to SRD ［C］//5th International Conference on Wireless Communications，Networking and Mobile Computing，2009：1－4.

［5］Gao Bo，Zhang Qinyu.Predicting self－similar networking traffic based on EMD and ARMA ［J］.Journal on Communications，2011，32 （4）：47－56.

［6］GAO Bo，Zhang Qinyu.LRD network traffic predicting based on SRD model ［C］//International Conference on Wireless Communications ＆Signal Processing，2012：1－6.

［7］Feng Huali，Liu Yuan.Network traffic prediction based on wavelet packet denoising and Elman neural network ［J］.Microcomputer Information，2010，30：116－118.

［8］Feng Huali，Liu Yuan，Chen Dong.Network traffic prediction based on BPNN optimized by QPSO algorithm ［J］.Computer Engineering and Applications，2012，48 （3）：102－104.

［9］Yang Juqiong，Ting Chu－Ho，Zhang Xudong.Network traffic prediction using the combination of chaos theory and simple－MKL ［J］.Journal of Networks，2013，8 （8）：1750－1756.

［10］Lin Xiang，Ge Xiaohu，Liu Chuang，et al.A new hybrid network traffic prediction method ［C］//Proceedings IEEE Global Communications Conference，2010：1－5.