混沌理論和LSSVM相結(jié)合的網(wǎng)絡流量預測

張文金，許愛軍

廣州鐵路職業(yè)技術學院 教育技術中心，廣州 510430

混沌理論和LSSVM相結(jié)合的網(wǎng)絡流量預測

張文金，許愛軍

廣州鐵路職業(yè)技術學院 教育技術中心，廣州 510430

網(wǎng)絡流量是衡量網(wǎng)絡運行負荷和狀態(tài)的重要參數(shù)，通過對網(wǎng)絡流量進行監(jiān)測，可以及時了解網(wǎng)絡系統(tǒng)運行狀況，因此網(wǎng)絡流量預測成為當前一個重要研究課題[1]。

目前網(wǎng)絡流量預測方法主要有兩類：一類是以時間序列法為代表的傳統(tǒng)預測方法[2]；另一類是以神經(jīng)網(wǎng)絡為代表的人工智能預測方法[3]。傳統(tǒng)時間序列模型只能處理短相關網(wǎng)絡流，然而隨著網(wǎng)絡測量技術的發(fā)展，網(wǎng)絡研究人員發(fā)現(xiàn)高速網(wǎng)絡的業(yè)務具有長相關性（相似性），這是傳統(tǒng)方法不能處理的，因此時間序列預測方法應用受限[4]。神經(jīng)網(wǎng)絡采用經(jīng)驗風險最小化準則，要求訓練樣本大，易產(chǎn)生過擬合（即泛化能力不強），導致預測精度下降，且神經(jīng)網(wǎng)絡的結(jié)構(gòu)復雜，隱含層節(jié)點數(shù)等難以恰當選擇，隨著輸入維數(shù)的增加，神經(jīng)元個數(shù)急劇增加往往導致“維數(shù)災”難題，這些都大大限制了神經(jīng)網(wǎng)絡應用[5]。支持向量機（Support Vector Machine，SVM）是一種基于結(jié)構(gòu)風險最小化原則的人工智能學習算法，較好地解決了小樣本、非線性、高維數(shù)和局部極小點等實際問題，廣泛應用于網(wǎng)絡流量的預測領域[6-7]。但SVM預測性能不僅與自身參數(shù)相關，還與網(wǎng)絡流量的訓練樣本相關，當前主要采用人為確定訓練樣本的輸入和輸出矩陣，采用均方根誤差對模型的逼近能力和預測效果進行評價，該方法的不足之處是訓練樣本選取缺乏理論指導，一旦選定就只能通過預測值與真實值之間的誤差來反復修正模型，直到模型達到滿意的預測精度，導致訓練時間長，容易產(chǎn)生過擬合現(xiàn)象[8]。大量的實驗證明，網(wǎng)絡流量存在非平穩(wěn)性、時變性、混沌性等特性，需要采用非線性混沌理論對網(wǎng)絡流量預測進行建模[9]。

在混沌理論的相空間重構(gòu)基礎上，本文將最小二乘支持向量機（Least Squares Support Vector Machine，LSSVM）作為預測模型擬合網(wǎng)絡流量相空間中相點的演化趨勢，建立一種基于混沌理論和LSSVM相結(jié)合的網(wǎng)絡流量預測模型。首先通過混沌理論的相空間重構(gòu)將一維的網(wǎng)絡流量時間序列轉(zhuǎn)化成矩陣形式，然后通過LSSVM對構(gòu)造時間序列進行訓練，從而避免了LSSVM在訓練過程的數(shù)據(jù)選取的盲目性，最后采用具體網(wǎng)絡流量數(shù)據(jù)進行仿真實驗，仿真結(jié)果表明該方法能明顯提高網(wǎng)絡流量的預測精度，獲得了滿意的預測效果。

1 相空間重構(gòu)和最小二乘支持向量機

1.1 基于混沌理論相空間重構(gòu)

相空間重構(gòu)（Phase Space Reconstruction，PSR）基本思想為：系統(tǒng)中任一分量的演化均由與之相互作用著的其他分量所決定，因此在進行相空間重構(gòu)時，只需考察一個分量，并將它在某些固定的時間延遲點上的測量作為新維處理，它們確定了某個多維狀態(tài)空間中的一點，不斷重復這一過程并測量相對于不同時間的各延遲量，就可以產(chǎn)生出許多這樣的點，將吸引子的許多性質(zhì)保存下來，就可以通過采用系統(tǒng)的一個分量重構(gòu)出原動力系統(tǒng)模型，初步確定系統(tǒng)的真實相空間的維數(shù)[9-10]。

假設觀測到的混沌時間序列為：{x(t)};t=1，2，…，n，其中n表示樣本個數(shù)，根據(jù)Τakens定理，通過選定合適的延遲時間（τ）和嵌入維（m）就可以將混沌時間序列時間重構(gòu)為：

從式（1）可知，相空間重構(gòu)結(jié)果的好壞由m和τ決定。實驗研究表明[11-12]，如果τ選取不適合，導致信息冗余或丟失，而m太小，不足以展示復雜行為的細致結(jié)構(gòu)；太大卻會使計算工作大大復雜化，所以τ與m的正確選取對混沌時間序列分析有著重要的意義。

當前，針對τ和m的選取有兩種思想，一種是兩者分開、獨立選擇，別一種應該聯(lián)合選擇。根據(jù)Τakens定理，對于無限長的、無噪聲的時間序列，τ可以任意選擇，即與m無關，但實際時間序列不可避免地帶有噪音且不能保證序列長度足夠，因此，現(xiàn)在多數(shù)研究者認為τ和m是相互關聯(lián)的，應該同時進行[11]。由于C-C方法在確定時間延遲過程中同時得到合適的嵌入維數(shù)，且該方法操作容易、計算量小、對小數(shù)據(jù)組可靠且具有較強的抗噪聲能力，因此本文采用C-C進行相空間重構(gòu)，具體計算過程見文獻[12]。

1.2 最小二乘支持向量機

Suykens等在標準支持向量機的基礎上提出了最小二乘支持向量機（LSSVM），其將標準支持向量機型中的損失函數(shù)設定成誤差平方和，把不等式約束改成等式約束，減少待定參數(shù)，又將求解二次規(guī)劃的問題轉(zhuǎn)化成線性KKΤ（Karush Kuhn Kucker）方程組的求解，降低了求解的復雜性[13-14]。

對于樣本集{(xi， }yi)，i=1，2，…，n，xi和yi分別表示樣本輸入和輸出，通過非線性映射函數(shù)φ(·)將樣本映射到高維特征空間，從而獲得最優(yōu)線性回歸函數(shù)：

式中，w為特征空間的權(quán)值向量，b為偏置量。

根據(jù)結(jié)構(gòu)風險最小化原則，式（2）問題求解的LSSVM回歸模型為：

式中，γ為懲罰參數(shù)，平衡訓練誤差和模型復雜度；ei為實際值與預測值間的誤差。

通過引入拉格朗日乘子將上述約束優(yōu)化問題轉(zhuǎn)變?yōu)闊o約束對偶空間優(yōu)化問題，即

式中，αi為拉格朗日乘子，γ表示核函數(shù)參數(shù)。

對于非線性預測問題，通過引入核函數(shù)進行求解，根據(jù)Mercer條件，核函數(shù)定義如下：

本文選擇徑向基核函數(shù)作為LSSVM核函數(shù)，徑向基核函數(shù)定義為：

最后LSSVM回歸模型為：

式中，σ表示徑向基核數(shù)寬度。

從上述LSSVM建模過程可知，基于徑向基核函數(shù)的LSSVM預測性能主要取決于γ和σ，當前參數(shù)選擇方法主要有梯度下降算法、網(wǎng)絡搜索算法、粒子群優(yōu)化算法和遺傳算法等，梯度下降算法對初始值敏感，網(wǎng)絡搜索算法，計算量大，搜索速度慢；遺傳算法和粒子群算法，極易陷入局部最優(yōu)，為此本文采用混沌粒子群算法對LSSVM的參數(shù)γ和σ進行優(yōu)化，具體優(yōu)化過程如圖1所示。

圖1 基于混沌粒子群的LSSVM參數(shù)優(yōu)化流程

2 混沌理論和LSSVM結(jié)合的網(wǎng)絡流量預測模型

2.1 訓練預測前的數(shù)據(jù)預處理

網(wǎng)絡流量受到多種因素影響，具有非線性和隨機性，數(shù)據(jù)之間相差比較大，LSSVM對0到1之間數(shù)據(jù)最為敏感，為此，將數(shù)據(jù)輸入到LSSVM進行訓練之前，對網(wǎng)絡流量數(shù)據(jù)進行歸一化處理，具體為：

最后對網(wǎng)絡流量預測結(jié)果進行反歸一化處理，恢復真實預測值。

式中，x表示網(wǎng)絡流量原始數(shù)據(jù)，xmax和xmin表示網(wǎng)絡流量最大值和最小值。

2.2 預測模型輸入輸出結(jié)構(gòu)

混沌相空間中任一相點xi演變到下一相點xi+1可以用函數(shù)關系表示為：

由于xi+1的前m-1個分量都是已知的歷史數(shù)據(jù)，為簡單起見只要構(gòu)造一個映射F作為預測器，使得︵=f(xi)即可。但是，由于F是吸引域內(nèi)的未知映射且系統(tǒng)具有強非線性，因此只能從觀測數(shù)據(jù)得到系統(tǒng)動力學行為，因此采用LSSVM擬合非線性映射函數(shù)F，其輸入節(jié)點的數(shù)目取相空間的飽和嵌入維數(shù)m，輸出節(jié)點為1個。

2.3 訓練樣本集構(gòu)成方法

為減少不相關相點對預測的不良影響，本文的訓練樣本集按預測相點的最近鄰點集原理生成，它能增強預測模型對系統(tǒng)混沌動力學的聯(lián)想和泛化推理能力[15]。實驗中使用預測中心點的k個近鄰作為樣本進行模型訓練，其中近鄰相點的求取按照歐氏距離標準，即

式中，Xr表示預測中心相點；Xri表示Xr的第i個近鄰相點。

“都過去了，不會計較你的。若找不到工作，回來跟我干，不會虧待你?！薄鞍游魇睕]有作聲，像見不得人似的，捂著臉跑了。

2.4 預測步驟

基于混沌理論和LSSVM相結(jié)合的網(wǎng)絡流量具體預測步驟如下：

（1）根據(jù)上述的方法對網(wǎng)絡流量原始數(shù)據(jù)進行預處理。

（2）相空間重構(gòu)。采用C-C方法選取最佳延遲時間和嵌入維數(shù)，繼而建立網(wǎng)絡流量時間序列的多維相空間。

（3）按照上述的方法構(gòu)造模型的輸入、輸出變量，并采用K近鄰算法選擇樣本，形成訓練樣本集。

（4）模型訓練。采用混沌粒子群算法對LSSVM模型參數(shù)進行優(yōu)化，在樣本數(shù)據(jù)集上進行訓練。

（5）預測。將預測中心點數(shù)據(jù)代入上一步訓練得到的模型中，即可獲得對未來網(wǎng)絡流量的預測值。

3 仿真實驗

3.1 數(shù)據(jù)來源

實驗數(shù)據(jù)來源于網(wǎng)絡流量文庫：http：//newsfeed.ntcu. net/～news/2011/，收集了主節(jié)點路由器Incoming articles從2011年8月1日到2012年2月20日的每小時網(wǎng)絡訪問流量，得到4 400個數(shù)據(jù)，這些數(shù)據(jù)組成了一個一維網(wǎng)絡流量時間序列{x(t)，t=1，2，…，4 400}，為了全面測試本文網(wǎng)絡流量預測模型的有效性，并對不同訓練樣本和測試樣本比較對模型預測性能的影響，將訓練樣本數(shù)∶測試樣本數(shù)=100∶1；50∶1；20∶1；10∶1；5∶1；2∶1，訓練樣本集通過相空間重構(gòu)和LSSVM建立網(wǎng)絡流量預測模型；測試樣本集對建立的網(wǎng)絡流量預測模型的泛化推廣能力進行預測檢驗，網(wǎng)絡流量時間序列數(shù)據(jù)如圖2所示。

圖2 網(wǎng)絡流量原始數(shù)據(jù)

在網(wǎng)絡流量的預測研究中，預測算法和樣本集選擇方法均影響預測精度，為檢驗本文提出的網(wǎng)絡流量預測方法的有效性，構(gòu)造了5個預測模型進行比較。

（1）模型1：采用加權(quán)一階局域法（Adding Weight One rank Local region method，AWOL）對網(wǎng)絡流量混沌時間序列進行預測。

（2）模型2：采用混沌理論與BP神經(jīng)網(wǎng)絡相結(jié)合的預測方法（PHR-BPNN），首先采用混沌理論的相空間重構(gòu)對網(wǎng)絡流量進行重構(gòu)，然后使用BP神經(jīng)網(wǎng)絡對相點演變規(guī)律進行建模，從而得到網(wǎng)絡流量預測結(jié)果，但該模型僅直接選擇預測中心點的前k個相點作為訓練樣本。

（3）模型3：采用LSSVM作為預測模型，其他與模型2相同。

（4）模型4：采用BP神經(jīng)網(wǎng)絡作為預測模型，但此時訓練樣本集由預測中心相點的k個最近鄰構(gòu)成，其他與模型2一致。

（5）模型5：與模型3一樣，也是采用LSSVM作為預測器，但樣本選擇與模型3不同，而是采取與模型4一樣的方法，各模型的預測方法及樣本選擇見表1。

表1 五種模型的預測方法和樣本選擇

表2 五種模型對不同訓練樣本數(shù)和測試樣本數(shù)的預測誤差結(jié)果比較

為了評價模型性能，采用均方誤差（Mean Squared Error，MSE）和平均相對百分比誤差（Mean Absolute Percent Error，MPAE）作為模型性能評價指標，它們定義如下：

式中，xt表示網(wǎng)絡流量實際觀測值，x?t表示預測值，n表示所預測的網(wǎng)絡流量樣本數(shù)。

3.3 模型的實現(xiàn)

首先對網(wǎng)絡流量歷史數(shù)據(jù)進行歸一化處理，然后采用C-C方法確定最優(yōu)延遲時間τ=1和嵌入維m=5，然后采用最近鄰法選擇訓練樣本集，最后采用LSSVM進行訓練建模，并采用粒子群算法優(yōu)化LSSVM的參數(shù)，最后對測試集進一步預測，得到的結(jié)果如表2所示。

3.4 結(jié)果分析

（1）從表2的對比結(jié)果可知，主要是因為加權(quán)一階局域法采用線性方法擬合混沌的網(wǎng)絡流量時間序列相點的演化規(guī)律，雖然計算簡單，運行速度快，但網(wǎng)絡流量時間序列本質(zhì)上是非線性、時變性的，其相空間發(fā)展規(guī)律不能只使用線性方法進行擬合，而其他模型采用的是非線性方法，符合相空間的本質(zhì)特征，因此預測效果更好，但是加權(quán)一階局域法的預測速度要快于其他非線性預測模型，時間復雜度最低。

（2）模型3比模型2，模型5比模型4的效果要好，主要是因為模型2和模型4使用BP神經(jīng)網(wǎng)絡進行建模，而BP神經(jīng)網(wǎng)絡是基于經(jīng)驗風險最小化原則的非線性學習算法，容易出現(xiàn)過擬合，降低了預測模型的泛化能力，因此預測精度較低，預測誤差比較大，預測性能較差，而模型3和模型5使用LSSVM進行建模，LSSVM采用結(jié)構(gòu)風險最小化原則，可以取得更好的推廣能力以提高預測精度。基于LSSVM的模型訓練速度要明顯慢于基于BP神經(jīng)網(wǎng)絡的速度，訓練時間和空間復雜度較高，然而模型一旦建立，預測速度和BP神經(jīng)網(wǎng)絡差不多，即預測時間和空間復雜度沒有什么大的區(qū)別。

（3）模型4比模型2，模型5比模型3的預測精度更高，主要是因為模型4和模型5采用最近鄰樣本訓練集，避免了不相關點的不良影響，因此取得了更好的預測效果，尤其是模型5預測性能最好，大幅提高了網(wǎng)絡流量的預測精度。對比結(jié)果表明，本文提出的混沌理論和最小二乘支持向量機結(jié)合的網(wǎng)絡流量預測模型是有效、可行的，為具有混沌特性的網(wǎng)絡流量時間序列預測問題提供了一種新的解決思路。

（4）從表2可知，當訓練樣本和測試樣本數(shù)不同時，其預測結(jié)果差異很大，當訓練樣本越大時，預測精度越高，預測誤差相對較小，說明訓練樣本數(shù)目越大，提供最優(yōu)K鄰點信息就越豐富，更加能夠準確描述網(wǎng)絡流量變化趨勢，預測結(jié)果更加可靠，泛化推廣能力越強。

4 結(jié)論

針對網(wǎng)絡流量非線性、混沌等特點，提出了基于混沌理論和LSSVM相結(jié)合的網(wǎng)絡流量預測方法，并采用實際網(wǎng)絡流量數(shù)據(jù)進行了仿真測試。測試結(jié)果研究表明：

（1）針對網(wǎng)絡流量非線性、非平穩(wěn)的特點，通過引入混沌理論，對網(wǎng)絡流量時間序列進行相空間重構(gòu)，將其整理為5維狀態(tài)空間向量序列，最大可能地提取和恢復網(wǎng)絡流量的演化信息。

（2）LSSVM采用結(jié)構(gòu)風險最小化原則，解決了在神經(jīng)網(wǎng)絡方法中易陷入局部最小值、精度與泛化不可調(diào)和的矛盾，可以減少過擬合風險，使用該方法進行預測比BP神經(jīng)網(wǎng)絡和加權(quán)一階局域法有更好的效果。

（3）采用預測相點的最近鄰點構(gòu)成模型訓練樣本集可以有效提高預測精度。

（4）基于混沌理論和LSSVM的網(wǎng)絡流量預測方法可以大幅提高網(wǎng)絡流量預測精度，具有廣泛應用前景。

[1]程光，龔儉.大規(guī)模網(wǎng)絡流量宏觀行為周期性分析研究[J].小型微型計算機系統(tǒng)，2003，24（6）：992-994.

[2]高波，張欽宇，梁永生.基于EMD及ARMA的自相似網(wǎng)絡流量預測[J].通信學報，2011（4）.

[3]曹建華，劉淵，戴悅.一種基于灰色神經(jīng)網(wǎng)絡的網(wǎng)絡流量預測模型[J].計算機工程與應用，2008，44（5）：155-157.

[4]Jin Yi，Zhou Gan.Τheoretical mean-variance relationship of IP network traffic based on ON/OFF model[J].Sci China Ser F-Inf Sci，2009，52（4）：645-655.

[5]饒云華，曹陽，楊艷.自相似網(wǎng)絡通信量的多尺度預測研究[J].計算機工程與應用，2005，41（28）：26-28.

[6]王俊松，高志偉.基于RBF神經(jīng)網(wǎng)絡的網(wǎng)絡流量建模及預測[J].計算機工程與應用，2008，44（13）：6-7.

[7]Chen Z，Delis A，Wei P.A pragmatic methodology for testing intrusion prevention systems[J].Computer Journal，2009，52：429-460.

[8]孫知信，張玉峰.基于多維支持向量機的P2P網(wǎng)絡流量識別模型[J].吉林大學學報：工學版，2010，40（5）：1298-1303.

[9]孫韓林，金躍輝，崔毅東，等.粗粒度網(wǎng)絡流量的灰色模型預測[J].北京郵電大學學報，2010，33（1）：7-11.

[10]謝高崗，閔應驊，張大方，等.一個基于實際測試的網(wǎng)絡流量模型[J].計算機工程與科學，2001，23（5）：51-54.

[11]Icol D M，Yan G.High-performance simulation of low-resolution network flows[J].Simulation，2006，82：21-42.

[12]Kim H S，Eykholt R，Salas J D.Nonlinear dynamics，delaytimes，and embedding windows[J].Physica D，1999，127：48-60.

[13]Zhong Weimin，Pi Daoying，Sun Youxian.Support vector machine based nonlinear model multi-step-ahead optimizing predictive control[J].Journal of Central South University of Τechnology，2005，12（5）：591-595.

[14]Pan Jinshui，Hong Meizhu，Zhou Qifeng，et al.Integrated application of uniform design and least-squares support vector machines to transfection optimization[J].BMC Biotechnology，2009，9（1）：52-57.

[15]孫雅明，張智晟.相空間重構(gòu)和混沌神經(jīng)網(wǎng)絡融合的短期負荷預測研究[J].中國電機工程學報，2004，24（1）：44-48.

ZHANG Wenjin,XU Aijun

Education Τechnology Center,Guangzhou Institute of Railway Τechnology,Guangzhou 510430,China

In order to improve the prediction accuracy of network traffic,this paper proposes a network traffic forecasting method based on chaotic theory and Least Squares Support Vector Machine.Phase space reconstruction is used to reconstruct the network traffic time series and restore the network flow evolution path,and then the network traffic time series are modeled and trained by Least Squares Support Vector Machines which has good nonlinear forecasting ability,and the parameters of Least Squares Support Vector Machine are optimized by chaotic particle swarm algorithm to obtain the optimal network traffic forecasting model.Τhe forecasting method is tested by the network traffic time series data.Τhe results show that the method can well depict the network flow change trend and improves the forecasting accuracy of network traffic whose forecasting performance is superior to the traditional forecasting method.

chaotic theory;Least Squares Support Vector Machine（LSSVM）;network traffic;forecasting model

為提高網(wǎng)絡流量的預測精度，提出一種基于混沌理論和最小二乘支持向量機相結(jié)合的網(wǎng)絡流量預測方法。采用相空間重構(gòu)對網(wǎng)絡流量時間序列進行重構(gòu)，恢復網(wǎng)絡流量的演化軌跡，采用非線性預測能力強的最小二乘支持向量機對網(wǎng)絡流量時間序列進行訓練建模，采用混沌粒子群算法對最小二乘支持向量機參數(shù)進行優(yōu)化，從而獲得最優(yōu)網(wǎng)絡流量預測模型。用實際網(wǎng)絡流量數(shù)據(jù)對該算法有效性進行驗證，結(jié)果表明該方法能夠很好刻畫網(wǎng)絡流量的變化趨勢，提高了網(wǎng)絡流量的預測精度，預測性能優(yōu)于傳統(tǒng)的預測方法。

混沌理論；最小二乘支持向量機；網(wǎng)絡流量；預測模型

A

ΤP181

10.3778/j.issn.1002-8331.1201-0014

ZHANG Wenjin,XU Aijun.Network traffic forecasting based on chaotic theory and Least Squares Support Vector Machine.Computer Engineering and Applications,2013,49（15）：101-104.

張文金（1972—），講師/工程師，研究方向：計算機網(wǎng)絡、智能計算；許愛軍（1978—），男，副教授，研究方向：計算機網(wǎng)絡應用、數(shù)據(jù)挖掘。E-mail：zhangwenjin_2009@126.com

2012-01-04

2012-03-13

1002-8331（2013）15-0101-04

CNKI出版日期：2012-06-18 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120618.1131.001.html