基于改進的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.