基于EMD和粒子群優(yōu)化的LS－SVM的網(wǎng)絡(luò)流量預(yù)測(cè)

朱倩雨，覃錫忠，賈振紅，盛 磊，陳 麗

（1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊830046；2.中國(guó)移動(dòng)通信集團(tuán)新疆有限公司，新疆烏魯木齊830063）

0 引 言

伴隨著移動(dòng)互聯(lián)網(wǎng)、高清視頻、在線游戲、云應(yīng)用等業(yè)務(wù)的興起，網(wǎng)絡(luò)流量呈現(xiàn)爆炸式增長(zhǎng)，電信運(yùn)營(yíng)商雖然不斷地在提高網(wǎng)絡(luò)帶寬，卻依然感受到 “帶寬供不應(yīng)求”的壓力。對(duì)它的預(yù)測(cè)，為網(wǎng)絡(luò)的流量控制、帶寬分配、選路控制、故障管理等提供有效依據(jù)。這樣，在網(wǎng)絡(luò)過(guò)載發(fā)生之前，可以預(yù)先采取防范措施，來(lái)保證網(wǎng)絡(luò)的正常服務(wù)。

現(xiàn)有的網(wǎng)絡(luò)流量預(yù)測(cè)模型主要有時(shí)間序列模型、灰色模型、神經(jīng)網(wǎng)絡(luò)模型和支持向量機(jī)模型等，但這些模型在預(yù)測(cè)性能上都存在各自的缺陷，ARMA和ARIMA模型適應(yīng)于線性預(yù)測(cè)，算法簡(jiǎn)單，易于實(shí)現(xiàn)，但預(yù)測(cè)精度不高[1]?；疑Ｐ途哂兴铇颖旧?，建模簡(jiǎn)單的特點(diǎn)，但對(duì)波動(dòng)較大的數(shù)據(jù)預(yù)測(cè)精度低[2]。神經(jīng)網(wǎng)絡(luò)模型基于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則，適應(yīng)于非線性預(yù)測(cè)，但要求的訓(xùn)練樣本多，存在局部最小、泛化能力弱等缺點(diǎn)，易造成預(yù)測(cè)精度不高[3]。基于網(wǎng)絡(luò)流量數(shù)據(jù)的長(zhǎng)相關(guān)、自相似、周期性、突發(fā)性和多尺度等特點(diǎn)，單一的預(yù)測(cè)模型已遠(yuǎn)遠(yuǎn)不能準(zhǔn)確地刻畫(huà)復(fù)雜性較高的流量變化的規(guī)律。

因此，許多專(zhuān)家學(xué)者充分利用各種單一預(yù)測(cè)模型的優(yōu)點(diǎn)，對(duì)組合預(yù)測(cè)模型進(jìn)行了探索和研究。大量實(shí)踐研究結(jié)果表明，組合預(yù)測(cè)模型對(duì)復(fù)雜的流量特性的描述更加準(zhǔn)確和全面，可以有效提高網(wǎng)絡(luò)流量預(yù)測(cè)精度。而對(duì)于組合預(yù)測(cè)模型的研究大都建立在小波變換[4，5]的基礎(chǔ)上，但在基于小波變換的預(yù)測(cè)中，存在確定分解層數(shù)以及小波基難以選擇的問(wèn)題[6]。EMD（經(jīng)驗(yàn)?zāi)Ｊ椒纸猓┦且环N新的信號(hào)處理方法，它能夠吸取小波變換的多尺度分析能力的優(yōu)勢(shì)，從信號(hào)本身的尺度特征出發(fā)對(duì)信號(hào)進(jìn)行分解，具有自適應(yīng)性[7]，屬于自適應(yīng)小波分解。SVM（支持向量機(jī)）基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化理論提出，具有結(jié)構(gòu)簡(jiǎn)單、學(xué)習(xí)速度快、全局最優(yōu)、泛化能力強(qiáng)的優(yōu)點(diǎn)，能較好地解決數(shù)據(jù)的小樣本、非線性、高維數(shù)等問(wèn)題，預(yù)測(cè)能力較強(qiáng)[8]。優(yōu)化的SVM泛化能力增強(qiáng)，更適合做長(zhǎng)期預(yù)測(cè)[9]。根據(jù)網(wǎng)絡(luò)流量序列的特點(diǎn)，結(jié)合EMD和SVM兩種方法的不同功能，本文提出了基于EMD和粒子群優(yōu)化的LS－SVM （最小二乘支持向量機(jī)）相結(jié)合的方法，對(duì)網(wǎng)絡(luò)流量進(jìn)行預(yù)測(cè)。對(duì)實(shí)際的網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，證明了模型的有效性和可行性。

1 EMD和粒子群優(yōu)化的LS－SVM的基本原理

1.1 EMD的基本原理

EMD算法消除以時(shí)間尺度為特征的自相似性，降低數(shù)據(jù)的復(fù)雜性，從而實(shí)現(xiàn)將非線性、非平穩(wěn)數(shù)據(jù)的處理問(wèn)題向線性、平穩(wěn)的處理問(wèn)題的轉(zhuǎn)化，將原始信號(hào)分解為若干互不相關(guān)的本征模函數(shù) （IMF），它們都具有原信號(hào)不同的局部特征信息，而且滿(mǎn)足以下兩個(gè)條件:① 函數(shù)在整個(gè)時(shí)間范圍內(nèi)，局部極值點(diǎn)數(shù)目和過(guò)零點(diǎn)數(shù)目必須相等或最多相差一個(gè)；②在任意時(shí)刻點(diǎn)，局部最大值的包絡(luò) （上包絡(luò)線）和局部最小值的包絡(luò) （下包絡(luò)線）平均必須為零[10]。

設(shè)任一信號(hào)為h（t），采用三次樣條插值函數(shù)先對(duì)此信號(hào)的所有極大值擬合成上包絡(luò)線，再對(duì)所有極小值擬合成下包絡(luò)線[11]，記兩條包絡(luò)線的均值為m（t），則可設(shè)一個(gè)新的信號(hào)為

當(dāng)g（t）滿(mǎn)足上述兩個(gè)條件時(shí)，那么g（t）即為第一個(gè)IMF分量c1。設(shè)r（t）為信號(hào)余項(xiàng)，則

將r（t）視為新的原始信號(hào)，重復(fù) （1）操作，可以依次得到第二個(gè)IMF分量c2，第三個(gè)IMF分量c3，…，第m個(gè)IMF分量cm，其中m∈N，是本征模函數(shù)的個(gè)數(shù)。此時(shí)最終的信號(hào)余項(xiàng)r（t）滿(mǎn)足只有一個(gè)極值點(diǎn)或者單調(diào)函數(shù)的條件。于是信號(hào)可以表達(dá)為

1.2 最小二乘支持向量回歸機(jī)的原理

LS－SVM是利用二次損失函數(shù)，通過(guò)非線性映射φ（·），將低維非線性空間的數(shù)據(jù)轉(zhuǎn)化為高維線性空間的數(shù)據(jù)，從而實(shí)現(xiàn)最小二乘支持向量機(jī)的回歸問(wèn)題。其原理如下[12]:

設(shè)n組用 于 訓(xùn) 練 的樣本數(shù) 據(jù) （xi，yi），i∈ （1，2，…，n），xi∈Rn是樣本輸入，yi∈R是樣本輸出，則其最優(yōu)逼近回歸函數(shù)可估計(jì)為

若滿(mǎn)足結(jié)構(gòu)風(fēng)險(xiǎn)最小化的條件

則求解目標(biāo)方程可轉(zhuǎn)化為

其中Υ為懲罰系數(shù)，w∈R為權(quán)向量，b為偏置，ei（i＝0，1，2，…，N）為誤差。

由以上式子可把目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為拉格朗日函數(shù)

其中αi為拉格朗日乘子。

定義核函數(shù)為K（xi，xj）＝φ（xi）Tφ（xj），滿(mǎn)足Mercer對(duì)稱(chēng)函數(shù)條件。核函數(shù)有多種形式，本文選用徑向基函數(shù) （RBF），其中σ是核函數(shù)寬度。于是可得非線性預(yù)測(cè)回歸模型

由于核函數(shù)和懲罰參數(shù)影響LS－SVM的預(yù)測(cè)精度，粒子群優(yōu)化算法具有強(qiáng)大的全局搜索能力，實(shí)現(xiàn)起來(lái)較簡(jiǎn)單，故采用粒子群優(yōu)化[13]算法來(lái)優(yōu)化LS－SVM的參數(shù)，以獲得較優(yōu)的LS－SVM預(yù)測(cè)模型。

2 基于EMD和粒子群優(yōu)化的LS－SVM預(yù)測(cè)模型

經(jīng)驗(yàn)?zāi)Ｊ椒纸?（EMD）可以將非平穩(wěn)的流量序列按其本身的尺度特征自適應(yīng)地分解為若干不同尺度的平穩(wěn)的IMF（固有模態(tài)）分量。根據(jù)各個(gè)IMF的特點(diǎn)，選擇合適的LS－SVM模型對(duì)分解后的分量進(jìn)行預(yù)測(cè)，最后通過(guò)SVM合成原始流量。模型的預(yù)測(cè)流程圖如圖1所示。

圖1 EMD和粒子群優(yōu)化的LS－SVM預(yù)測(cè)模型

其預(yù)測(cè)步驟為:

（1）EMD分解將流量序列進(jìn)行EMD分解得到n個(gè)本征模函數(shù)和1個(gè)剩余分量。

（2）數(shù)據(jù)的處理由于流量數(shù)據(jù)的變化范圍比較大，為了提高預(yù)測(cè)的精度，對(duì)分解后的數(shù)據(jù)進(jìn)行歸一化處理。

（3）LS－SVM模型的確定與訓(xùn)練對(duì)EMD分解后的各個(gè)IMF分量分別建立LS－SVM預(yù)測(cè)模型，模型的參數(shù)由粒子群優(yōu)化算法得到。此模型采用多輸入單輸出[13]的預(yù)測(cè)方法，構(gòu)造時(shí)間序列輸入輸出向量矩陣從而建立訓(xùn)練樣本。訓(xùn)練樣本結(jié)構(gòu)如表1，其中x（i），x（i＋1），x（i＋2），x（k＋i－1）作為輸入向量，x（k＋i）作為輸出向量。k為輸入向量的嵌入維數(shù)。

（4）LS－SVM模型的預(yù)測(cè)通過(guò)對(duì)每個(gè)分量訓(xùn)練可以確定粒子群優(yōu)化LS－SVM[14]中的最優(yōu)參數(shù)，從而建立預(yù)測(cè)模型，對(duì)測(cè)試集部分進(jìn)行預(yù)測(cè)。

（5）流量的合成 由于分解后的每個(gè)IMF分量對(duì)最后的預(yù)測(cè)結(jié)果的貢獻(xiàn)率不同，簡(jiǎn)單的線性相加將會(huì)影響模型最后的預(yù)測(cè)精度，故使用SVM來(lái)實(shí)現(xiàn)最優(yōu)加權(quán)組合預(yù)測(cè)。先對(duì)每個(gè)預(yù)測(cè)值進(jìn)行反歸一化處理，再通過(guò)SVM對(duì)各個(gè)預(yù)測(cè)值組合得到最終的預(yù)測(cè)結(jié)果。

表1 構(gòu)造時(shí)間序列輸入輸出向量矩陣

3 仿真實(shí)驗(yàn)

實(shí)驗(yàn)的數(shù)據(jù)來(lái)源于某電信公司CMNET網(wǎng)絡(luò)的流量數(shù)據(jù)，采集了從2012年1月1號(hào)到1月25號(hào)共25天，每天每小時(shí)網(wǎng)絡(luò)的訪問(wèn)量，得到600個(gè)數(shù)據(jù)。采用前400個(gè)數(shù)據(jù)作為訓(xùn)練樣本，用于進(jìn)行參數(shù)的估計(jì)及模型的確定，后200個(gè)數(shù)據(jù)作為測(cè)試樣本，作為檢測(cè)預(yù)測(cè)值和真實(shí)值差別的依據(jù)。取輸入向量的嵌入維數(shù)為3，LS－SVM模型的參數(shù)由粒子群優(yōu)化算法得到。本文采用均方誤差 （mean squared error，MSE）作為評(píng)價(jià)預(yù)測(cè)結(jié)果的標(biāo)準(zhǔn)。圖2為原始網(wǎng)絡(luò)流量的數(shù)據(jù)。

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

圖3 為各個(gè)IMF分量真實(shí)值與預(yù)測(cè)值的差異。

圖3 各個(gè)IMF分量及其預(yù)測(cè)值

從圖3中可以看到，第一個(gè)分量IMF的預(yù)測(cè)效果不太理想，但是隨著IMF頻率的降低，預(yù)測(cè)精度逐漸提高。這種變化趨勢(shì)可以從MSE誤差上反映出來(lái)，見(jiàn)表2.

表2 各IMF分量預(yù)測(cè)的最小均方誤差 （MSE）（%）

另一方面，也可由圖3看出，預(yù)測(cè)誤差較大的序列，較之誤差較小的序列其幅值較小，所以當(dāng)將各IMF預(yù)測(cè)序列合成后，大誤差序列對(duì)預(yù)測(cè)結(jié)果影響不大，合成之后預(yù)測(cè)精度較高。將各個(gè)IMF預(yù)測(cè)序列用SVM合成，得到原始序列的預(yù)測(cè)曲線如圖4所示。

圖4 真實(shí)數(shù)據(jù)及其組合后的預(yù)測(cè)數(shù)據(jù)

為驗(yàn)證文中所提出模型的有效性和可行性，特采用單獨(dú)的粒子群優(yōu)化的LS－SVM和小波與粒子群優(yōu)化的LSSVM模型作為對(duì)比模型，其預(yù)測(cè)曲線如圖5所示。

圖5 對(duì)比模型的預(yù)測(cè)曲線

從圖5可以看出，采用EMD和PSO優(yōu)化的LS－SVM組合模型后曲線的擬合程度優(yōu)于其他兩個(gè)模型，預(yù)測(cè)精度較高。這是因?yàn)樵挤瞧椒€(wěn)的流量數(shù)據(jù)經(jīng)過(guò)EMD自適應(yīng)分解之后變成平穩(wěn)的單一分量，并且這些分量具有一定的規(guī)律，跟原始的非線性、非平穩(wěn)序列相比更易于預(yù)測(cè)。其預(yù)測(cè)誤差比較見(jiàn)表3。

表3 各個(gè)模型預(yù)測(cè)的最小均方誤差 （MSE）對(duì)比 （%）

4 結(jié)束語(yǔ)

根據(jù)網(wǎng)絡(luò)流量時(shí)間序列所具有的特性，首先用EMD對(duì)信號(hào)做了平穩(wěn)化處理。將具有復(fù)雜特性的原始流量分解為具有一定規(guī)律，相對(duì)比較單一，更加易于預(yù)測(cè)的時(shí)間序列。其次用粒子群優(yōu)化的LS－SVM對(duì)各分量進(jìn)行預(yù)測(cè)，最后通過(guò)SVM組合得到原始序列的預(yù)測(cè)結(jié)果。本文以真實(shí)的網(wǎng)絡(luò)流量數(shù)據(jù)對(duì)算法進(jìn)行了仿真實(shí)驗(yàn)，結(jié)果表明，該算法模型對(duì)網(wǎng)絡(luò)流量的預(yù)測(cè)具有一定的優(yōu)勢(shì)，預(yù)測(cè)精度有明顯提高，但在時(shí)間復(fù)雜度上有所欠缺，下一步的主要研究工作將在此方面展開(kāi)。

[1]JIANG Ming，WU Chunming，HU Damin.Research on the comparison of time series models for network traffic prediction[J].Acta Electronica Sinica，2009，37 （11）:2353－2359 （in Chinese）.[姜明，吳春明，胡大民.網(wǎng)絡(luò)流量預(yù)測(cè)中的時(shí)間序列模 型 比 較 研 究[J]. 電 子 學(xué) 報(bào)，2009，37 （11）:2353－2359.]

[2]MA Hualin，LI Cuifeng，ZHANG Liyan.Network traffic prediction based on grey model and adaptive filter[J].Computer Engineering，2009，35 （1）:155－157 （in Chinese）.[馬華林，李翠鳳，張立燕.基于灰色模型和自適應(yīng)過(guò)濾的網(wǎng)絡(luò)流量預(yù)測(cè)[J].計(jì)算機(jī)工程，2009，35 （1）:155－157.]

[3]Junsong W，Jiukun W，Maohu Z，et al.Prediction of internet traffic based on Elaman neural network[C]／／Guilin:Chinese Control and Deeision Conference，2009:1248－1252.

[4]WEI Yongtao，WANG Jinkuan，WANG Cuirong，et al.Network traffic prediction algorithm based on wavelet transform and combinational models[J].Journal of Northeastern University（Natural Science），2011，32 （10）:1382－1885 （in Chinese）.[魏永濤，汪晉寬，王翠榮，等.基于小波變換與組合模型的網(wǎng)絡(luò)流量預(yù)測(cè)算法[J].東北大學(xué)學(xué)報(bào) （自然科學(xué)版），2011，32（10）:1382－1885.]

[5]GONG Linming，ZHANG Zhenguo.Combination prediction model to network traffic based on grey－wavelet[J].Computer Engineering and Design，2010，31 （8）:1660－1662 （in Chinese）.[鞏林明，張振國(guó).基于灰色小波的網(wǎng)絡(luò)流量組合預(yù)測(cè)模型[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010，31 （8）:1660－1662.]

[6]CHEN Xiantian，LIU Jingxian. Network traffic prediction based on wavelet transformation and FARIIMA[J].Journal of Communications，2011，32 （4）:153－158 （in Chinese）.[陳曉天，劉靜嫻.改進(jìn)的基于小波變換和FARIMA模型的網(wǎng)絡(luò)流量預(yù)測(cè)算法[J].通信學(xué)報(bào)，2011，32 （4）:153－158.]

[7]WANG Jundong，QI Weigui.Prediction of river water turbidity based on EMD－SVM[J].Acta Electronica Sinica，2009，37（10）:2129－2133 （in Chinese）.[王軍棟，齊維貴.基于EMDSVM的江水濁度預(yù)測(cè)方法研究[J].電子學(xué)報(bào)，2009，37（10）:2129－2133.]

[8]HUANG Chenglung，WANG Chiehjen.A GA－based feature selection and parameters optimization for support vector machines[J].Expert Systems with Application，2006，31 （2）:231－240.

[9]ZHOU Xiaolei，WANG Wanliang，CHEN Weijie.Network traffic prediction model based on wavelet transform and optimized support vector machine[J].Applications and Software of Computers，2011，28 （2）:34－37 （in Chinese）.[周曉蕾，王萬(wàn)良，陳偉杰.基于小波變換和優(yōu)化的SVM的網(wǎng)絡(luò)流量預(yù)測(cè)模型[J].計(jì)算機(jī)應(yīng)用與軟件，2011，28 （2）:34－37.]

[10]Zhang X，Lai k K，Wang S Y.A new approach for crude oil price analysis based on empirical mode decomposition[J].Energy Economics，2008，30 （3）:905－918.

[11]Balocchi R，Menicucci D，Varanini M.Empirical mode decomposition to approach the problem of detecting sources from a reduced number of mixtures[C]／／Proceeding of the 25th Annual International Conference of the IEEE EMBS，2006.

[12]WU Haishan，CHANG Xiaoling.Power load forecasting with least squares support vector machines and chaos theory[C]／／Proc of Intelligent Control and Automation，2006:4369－4373.

[13]WU Lianghai.Prediction of petroleum demand based on SVM optimized by PSO[J].Computer Simulation，2010，27 （4）:291－295（in Chinese）.[吳良海.基于粒子群優(yōu)化支持向量機(jī)的石油需求預(yù)測(cè)[J].計(jì)算機(jī)仿真，2010，27 （4）:291－295.]

[14]LIU Yuan，WANG Peng.Combining wavelet transform and Bayesian least squares support Vector machines to predict network traffic[J].Application Research of Computers，2009，26 （6）:2229－2231 （in Chinese）.[劉淵，王鵬.融合小波變換與貝葉斯LS－SVM的網(wǎng)絡(luò)流量預(yù)測(cè)[J].計(jì)算機(jī)應(yīng)用研究，2009，26 （6）:2229－2231.]