融合小波變換與貝葉斯ＬＳ－ＳＶＭ的網(wǎng)絡(luò)流量預(yù)測

摘 要：為了提高網(wǎng)絡(luò)流量預(yù)測的精度，研究了一種融合小波變換與貝葉斯LS-SVM的網(wǎng)絡(luò)流量預(yù)測方法。首先將原始流量數(shù)據(jù)時間序列進(jìn)行小波分解，并將分解得到的近似部分和各細(xì)節(jié)部分分別單支重構(gòu)到原級別上;對各個重構(gòu)后的序列分別用最小二乘支持向量機(jī)進(jìn)行預(yù)測，將貝葉斯證據(jù)框架應(yīng)用于最小二乘支持向量機(jī)模型參數(shù)的選擇；將各個預(yù)測結(jié)果重構(gòu)后得到對原始序列的預(yù)測結(jié)果。對比實驗表明，該模型不僅具有較快的運行速度，而且具有較高的預(yù)測精度。

關(guān)鍵詞：網(wǎng)絡(luò)流量預(yù)測；小波變換；支持向量機(jī)；最小二乘支持向量機(jī)；貝葉斯框架

中圖分類號：TP393.01文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2009)06-2229-03

doi:10.3969/j.issn.1001-3695.2009.06.069

Combining wavelet transform and Bayesian least squares supportvector machines to predict network traffic

LIU Yuana，b，WANG Penga

(a.School of Information Engineering，b.Digital Media Research Center， Jiangnan University， Wuxi Jiangsu 214122， China)

Abstract:In order to improve the precision of the network traffic prediction，this paper proposed a new method of network traffic prediction combining wavelet transform and least squares support vector machines (LS-SVM).The original network traffic time series was decomposed into approximate series and several detail series. The result of single branch reconstruction of each decomposed series was more unitary than the original series in frequency， and it could be built traffic model with LS-SVM.The Bayesian evidence framework was applied to LS-SVM in order to determine the regularization parameters and kernel parameters effectively. The prediction of the original series could be obtained by the synthesis of each reconstructed series’ prediction result. The simulation results indicate the high accuracy and speed of this method.

Key words:network traffic prediction;wavelet transform;support vector machines;least squares support vector machines;Bayesian framework

網(wǎng)絡(luò)流量預(yù)測對于實現(xiàn)數(shù)據(jù)可靠傳輸、合理分配網(wǎng)絡(luò)資源具有重要的指導(dǎo)意義。當(dāng)前，已被證明網(wǎng)絡(luò)流量最為重要的統(tǒng)計特征是尺度和多尺度行為特性，如長相關(guān)性、自相似性以及多重分形性，這種特性同時存在于無線網(wǎng)絡(luò)、Ad hoc網(wǎng)絡(luò)以及衛(wèi)星網(wǎng)絡(luò)中。小波變換具有多分辨率，即多尺度的特點，可以由粗到精地逐步觀察信號。小波變換是處理非平穩(wěn)時間序列的有效方法之一^[1]，并且已有學(xué)者將其應(yīng)用于網(wǎng)絡(luò)流量預(yù)測^[2，3]。網(wǎng)絡(luò)流量序列數(shù)據(jù)同樣具有噪聲、不穩(wěn)定、非線性等特點；而神經(jīng)網(wǎng)絡(luò)在非線性建模中具有優(yōu)勢，它不必建立復(fù)雜的數(shù)學(xué)模型即可完成預(yù)測。目前已經(jīng)有許多工作者將神經(jīng)網(wǎng)絡(luò)用于流量預(yù)測^[4，5]，但由于神經(jīng)網(wǎng)絡(luò)算法采用的是經(jīng)驗風(fēng)險最小化原則，具有容易陷入局部極小點、過度學(xué)習(xí)、收斂速度慢等缺陷，這些不足極大地限制了它在實際問題中的應(yīng)用。Suykens等人^[6]提出最小二乘支持向量機(jī)方法（least squares support vector machines，LS-SVM）。這種方法采用最小二乘線性系統(tǒng)作為損失函數(shù)，求解過程變成了解一組等式方程，求解速度相對加快，具有較好的泛化能力，不存在局部極小點和維數(shù)災(zāi)難等問題，目前已有學(xué)者將其用于時間序列預(yù)測^[7，8]。然而，無論是SVM還是LS-SVM，都對核函數(shù)參數(shù)、正規(guī)化參數(shù)比較敏感。近年來，由于貝葉斯方法具備的邏輯一致性以及簡單靈活的特點，已經(jīng)被應(yīng)用于SVM和LS-SVM的參數(shù)優(yōu)化^[9，10]。本文在現(xiàn)有網(wǎng)絡(luò)流量預(yù)測研究以及對LS-SVM的研究基礎(chǔ)上，提出一種新的網(wǎng)絡(luò)流量預(yù)測模型，即融合小波變換與貝葉斯LS-SVM的網(wǎng)絡(luò)流量預(yù)測模型。

1 小波分解與其單支重構(gòu)

1987年，Mallat等人提出多分辨分析的概念和基于多尺度分析的小波基構(gòu)造方法，將小波正交基的構(gòu)造納入統(tǒng)一的框架之中，提出了離散信號按小波變換分解和重構(gòu)的快速小波算法。Mallat算法的分解、重構(gòu)公式如下：

aj+1，k=2p∈Zp-2kaj，p

dj+1，k=2p∈Zp-2kaj，p(1)

aj，k=2p∈Zhk-2paj+1，p+2p∈Zgk-2pdj+1，p(2)

其中:H={hj}j∈Z是低通濾波器；G={gj}j∈Z是高通濾波器；Aj={aj，1，aj，2，…，aj，k}稱為第j層的近似部分；Dj={dj，1，dj，2，…，dj，k}稱為第j層的細(xì)節(jié)部分。每次分解將序列分為近似部分和細(xì)節(jié)部分，近似部分反映了序列的大致趨勢，而細(xì)節(jié)部分反映的是序列在細(xì)節(jié)上的差異。對近似部分可以進(jìn)一步實施分解，從而得到新的近似部分和細(xì)節(jié)部分。

Mallat算法分解過程也可以形象地表示成圖1所示。設(shè)分解層數(shù)為j，則原始序列經(jīng)過算法分解成D1，D2，…，Dj和Aj。Aj和Dj分別為在分辨率2j下的近似部分和細(xì)節(jié)部分。容易看出，每進(jìn)行一層分解，序列的長度縮為分解前的1/2。分解層數(shù)越高，得到的序列長度越短。

單支重構(gòu)是指不對近似部分和細(xì)節(jié)部分同時進(jìn)行重構(gòu)，而是對它們分別進(jìn)行重構(gòu)，即在對某一部分進(jìn)行重構(gòu)時將其他部分置零。對近似部分Aj單支重構(gòu)過程如圖2 所示，各細(xì)節(jié)部分單支重構(gòu)的方法與之類似。

2 最小二乘支持向量機(jī)

訓(xùn)練數(shù)據(jù)的樣本可以表示為(X1，Y1)，(X2，Y2)，…，(Xl，Yl)。其中:Yi是目標(biāo)值；Xi是輸入向量。與經(jīng)典SVM不同，LS-SVM利用SRM準(zhǔn)則構(gòu)造如下最小目標(biāo)函數(shù)及其約束條件：

minω，b，e J(w，e)=wTw/2+γ/2li=1e2i(3)

s.t. yi=(xi)×w+b+ζi；i=1，…，l(4)

其中:(#8226;)：Rn→Rnh是核空間映射函數(shù)；權(quán)矢量w∈Rnh，誤差變量ζi∈R；b是偏差量；γ是可調(diào)參數(shù)。將求解式（6）的優(yōu)化問題轉(zhuǎn)換為求解如下線性方程組

01Tv1vΩ+1/γIbα=0y(5)

其中:x=[x1，…，xl]；y=[y1，…，yl]；α=[α1，…，αl]；核函數(shù)K[xk，xl]=(xk)T(xl)是滿足Mercer條件的對稱函數(shù)。

最小二乘支持向量機(jī)回歸估計為

y(x)=li=1αiK(x，xi)+b(6)

其中：α、b由式(5)求解出，核函數(shù)K（x，xi）為滿足Mercer條件的任意對稱函數(shù)。本文采用的核函數(shù)為高斯核函數(shù):

K(x，xi)=exp(-‖x-xi‖2/(2σ2))(7)

3 貝葉斯框架下的LS-SVM參數(shù)優(yōu)化

傳統(tǒng)LS-SVM參數(shù)(γ，σ)的確定一般采用交叉驗證方式，即對每一對(γ，σ)，將樣本分為訓(xùn)練驗證集和測試集。將訓(xùn)練驗證集均分為幾份，每次選取一份不同的數(shù)據(jù)作為驗證集，其他的作為訓(xùn)練集，用訓(xùn)練集訓(xùn)練LS-SVM后，對驗證集進(jìn)行預(yù)測。在每對(γ，σ)預(yù)測不同驗證集后，選取預(yù)測誤差均方差的平均值最小的(γ，σ)作為LS-SVM的模型參數(shù)。通過交叉驗證的步驟可知，利用這種辦法來確定較優(yōu)的(γ，σ)需要花費大量時間，尤其是對于大樣本規(guī)模。為此，本文采用文獻(xiàn)[9]中的方法，將樣本分為訓(xùn)練集和驗證集，通過對訓(xùn)練集進(jìn)行貝葉斯推斷來確定較優(yōu)的(γ，σ)，提高運行速率。

貝葉斯證據(jù)框架是通過最大化參數(shù)分布的后驗來得到最佳參數(shù)值或最佳模型的。貝葉斯推斷可分為三個層次：a）選擇模型的參數(shù)；b)選擇模型超參數(shù)；c)選擇模型的核參數(shù)，并選擇相關(guān)輸入變量。 

第一層推斷（w和b的推斷）。假設(shè)D為訓(xùn)練集，H為模型，由貝葉斯準(zhǔn)則可得

P（w，b|D，ln μ，ln ζ，H）=P（D|w，b，ln μ，ln ζ，H）×P(w，b|ln μ，ln ζ，H)/P（D|ln μ，ln ζ，H）(8)

其中:P（D|ln μ，ln ζ，H）為標(biāo)準(zhǔn)化常數(shù)。通過最小化式（8）的負(fù)對數(shù)可以獲得最大后驗估計wmp和bmp。

第二層推斷（μ和ζ的推斷）。假設(shè)P(ln μ，ln ζ|H)=P(ln ζ|H)P(ln μ|H)，利用貝葉斯法可以由訓(xùn)練集D推斷μ和ζ，即

P(ln μ，ln ζ|D，H)=P(D|lnμ，ln ζ，H)P(ln μ，ln ζ|H)/P(D|H)=P(D|lnμ，ln ζ，H)P(ln ζ|H)P(ln ζ|H)/P(D|H)(9)

從而求得超參數(shù)γ=ζ/μ。

第三層推斷（核函數(shù)參數(shù)的推斷）。將貝葉斯法則應(yīng)用于模型Hj的推斷，可得

P(Hj|D)

P(D|Hj)P(Hj)(10)

假設(shè)P(Hj)的概率為均勻分布，則可以得到

P(Hj|D)P(D|Hj)(11)

由式（9）可得

P(D|Hj)P(D|ln μmp，ln ζmp，Hj)×σln μ|D σln ζ|D/（σln μσln ζ）

其中：σln μ、σln ζ分別是第二層推斷中l(wèi)n μ、ln ζ高斯分布對應(yīng)的標(biāo)準(zhǔn)方差；P(D|ln μmp，ln ζmp，Hj)則為數(shù)據(jù)的擬合程度。詳細(xì)的數(shù)學(xué)推導(dǎo)過程請參見文獻(xiàn)[9，10]。

4 網(wǎng)絡(luò)流量預(yù)測模型

融合小波變換與貝葉斯最小二乘支持向量機(jī)的網(wǎng)絡(luò)流量預(yù)測步驟如下：

a)將采集到的原始網(wǎng)絡(luò)流量數(shù)據(jù)序列進(jìn)行歸一化處理，歸一化公式如下：

x(t)=[x(t)-min(x)]/[max(x)-min(x)](12)

b)將歸一化的流量數(shù)據(jù)進(jìn)行小波分解，并將分解得到的近似部分和各細(xì)節(jié)部分分別單支重構(gòu)到原級別上；

c)確定輸入節(jié)點數(shù)，分別對每個頻率通道的子序列采用滾動預(yù)測方式，進(jìn)行步驟d)~h)的操作；

d)初始化正規(guī)化參數(shù)γ和核參數(shù)σ2，對最小二乘支持向量機(jī)進(jìn)行訓(xùn)練，通過貝葉斯第一層推斷獲取模型參數(shù)w和b；

e）迭代推斷超參數(shù)γ；

f)迭代推斷核參數(shù)σ2；

g)返回d），用所求得的參數(shù)重新訓(xùn)練支持向量機(jī)，選出最優(yōu)模型及輸入；

h)用建好的模型進(jìn)行預(yù)測該頻率通道的子序列；

i)重構(gòu)各個預(yù)測的子序列得到最后的預(yù)測結(jié)果。

網(wǎng)絡(luò)流量預(yù)測模型結(jié)構(gòu)如圖3所示。

5 實驗與結(jié)果分析

5.1 仿真實驗

本文數(shù)據(jù)源于流量文庫：http://newsfeed.ntcu.net/~news/2006， 收集了自2006年12月7日～21日共15天，每天每小時網(wǎng)絡(luò)的訪問流量，得到15×24＝360個數(shù)據(jù)。首先將原始數(shù)據(jù)進(jìn)行歸一化處理，然后將歸一化后的流量數(shù)據(jù)進(jìn)行小波分解，經(jīng)實驗比較發(fā)現(xiàn)采用db2小波進(jìn)行三層分解時得到的預(yù)測效果最好。將分解得到的近似部分和各細(xì)節(jié)部分分別單支重構(gòu)到原級別上；分別對各個頻率通道的子序列采用滾動預(yù)測方式，確定輸入節(jié)點數(shù)為5。這樣將每個子序列劃分240個訓(xùn)練樣本，前216個樣本作為學(xué)習(xí)和訓(xùn)練樣本，后24個樣本作為預(yù)測檢驗樣本，分別預(yù)測出2006年12月21日的網(wǎng)絡(luò)流量在各個頻率通道的子序列，最后重構(gòu)預(yù)測的各個子序列得到預(yù)測的2006年12月21日全天24小時的網(wǎng)絡(luò)流量數(shù)據(jù)。

為了檢驗融合小波變換與貝葉斯框架下LS-SVM模型在網(wǎng)絡(luò)流量預(yù)測中的有效性，本文另外做了兩個實驗，直接將歸一化的原始流量數(shù)據(jù)作為輸入樣本。實驗二：基于BP網(wǎng)絡(luò)的網(wǎng)絡(luò)流量預(yù)測， BP網(wǎng)絡(luò)采用5-9-1的結(jié)構(gòu)，即網(wǎng)絡(luò)的輸入節(jié)點數(shù)為5，隱層神經(jīng)元為9個，輸出節(jié)點數(shù)為1；實驗三：基于經(jīng)典LS-SVM的網(wǎng)絡(luò)流量預(yù)測，輸入節(jié)點數(shù)同樣為5，輸出節(jié)點數(shù)為1。采用均方誤差作為評價預(yù)測水平的標(biāo)準(zhǔn)。

MSE=1/Kki=1(xi-i)2(13)

5.2 結(jié)果分析

圖4為基于小波變換與貝葉斯框架下LS-SVM模型對各個頻率通道子序列的預(yù)測結(jié)果；圖5~7分別為三種模型對流量數(shù)據(jù)的預(yù)測結(jié)果圖。表1為三種模型預(yù)測的MSE誤差與CPU時間比較。

從圖4可見，利用小波變換將流量數(shù)據(jù)一層一層分解到不同的頻率通道上，分解后的時間序列在頻率成分上比原始信號單一，并且小波分解對時間序列進(jìn)行了平滑。觀察實驗結(jié)果發(fā)現(xiàn)，對每個子序列進(jìn)行預(yù)測的效果都很好，尤其是對近似部分和第三層的細(xì)節(jié)部分的預(yù)測。從而將各個子序列的預(yù)測結(jié)果重構(gòu)后可得到預(yù)測精度較高的最終流量預(yù)測序列，并且預(yù)測序列能夠體現(xiàn)原始流量序列的突發(fā)性。未經(jīng)小波變換而直接對歸一化后的原始流量數(shù)據(jù)進(jìn)行預(yù)測的另外兩個實驗中，從實驗結(jié)果可明顯看出，預(yù)測精度較差，而且只能反映原始流量數(shù)據(jù)的均值，并不能反映流量數(shù)據(jù)的特性?；诮?jīng)典LS-SVM的實驗要比基于BP網(wǎng)絡(luò)的預(yù)測精度高，主要原因在于神經(jīng)網(wǎng)絡(luò)訓(xùn)練易陷入局部最優(yōu)，并且基于經(jīng)驗風(fēng)險最小化的訓(xùn)練容易產(chǎn)生訓(xùn)練誤差變小，預(yù)測誤差變大的過學(xué)習(xí)問題。LS-SVM采用結(jié)構(gòu)風(fēng)險最小化原則，折中考慮經(jīng)驗風(fēng)險和置信區(qū)間，使實際風(fēng)險最小。從表1可見，基于BP網(wǎng)絡(luò)的預(yù)測模型預(yù)測精度較低，基于經(jīng)典LS-SVM的預(yù)測精度稍高。融合小波變換與貝葉斯LS-SVM的預(yù)測模型不僅預(yù)測精度很高，而且預(yù)測速度最快。需要說明的是，三個實驗均在配置為CPU Celeron(R) 2.47 GHz，1 GB DDR內(nèi)存的計算機(jī)上運行的。

6 結(jié)束語

根據(jù)網(wǎng)絡(luò)流量數(shù)據(jù)時間序列所具有的多重分形性，首先將原始數(shù)據(jù)進(jìn)行小波變換預(yù)處理，將原始流量數(shù)據(jù)時間序列進(jìn)行小波分解，并將分解得到的近似部分和各細(xì)節(jié)部分分別單支重構(gòu)到原級別上；針對傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)預(yù)測模型隱層節(jié)點數(shù)難確定且容易過學(xué)習(xí)等問題，將最小二乘支持向量機(jī)運用于流量預(yù)測；鑒于傳統(tǒng)最小二乘支持向量機(jī)利用交叉驗證算法進(jìn)行參數(shù)選擇需耗費大量時間，采用貝葉斯證據(jù)框架進(jìn)行參數(shù)的選擇以提高運行速度。綜上提出一種新的網(wǎng)絡(luò)流量預(yù)測模型，即融合小波變換與貝葉斯LS-SVM的網(wǎng)絡(luò)流量預(yù)測模型。對比實驗表明，該模型不僅能夠取得較高的預(yù)測精度，還能夠反映原始流量數(shù)據(jù)的突變性，且預(yù)測速度較快。

參考文獻(xiàn)：

［1］YU I，KIM C.A novel short-term load forecasting technique using wavelet transform analysis[J].Electric Machines and Power Systems，2000，28（1）:537-549.

[2]白翔宇，葉新銘，蔣海.基于小波變換與自回歸模型的網(wǎng)絡(luò)流量預(yù)測[J].計算機(jī)科學(xué)，2007，34(7):47-49.

[3]洪飛，吳志美.基于小波的多尺度網(wǎng)絡(luò)流量預(yù)測模型[J].計算機(jī)學(xué)報，2006，29(1):166-170.

[4]ALARCON-AQUINO V，BARRIA J A.Multiresolution FIR neural-network-based learning algorithm applied to network traffic prediction[J].IEEE Trans on Systems，Man，and Cybernetics，Part C:Applications and Reviews，2006，36(2):208-220.

[5]CORTEZ P，RIO M，ROCHA M，et al.Internet traffic forecasting using neural networks[C]//Proc of International Joint Conference on Neural Networks.2006:2635-2642.

[6]SUYKENS J A K，VANDEWALLE J.Least squares support vector machine classifiers[J].Neural Processing Letters，1999，9(3):293-300.

[7]WANG Xiao-dong，ZHANG Hao-ran，ZHANG Chang-jiang，et al.Prediction of chaotic time series using LS-SVM with automatic parameter selection[C]//Proc of the 6th International Conference on Parallel and Distributed Computing，Applications and Technologies.Washington DC:IEEE Computer Society ，2005：962-965.

[8]WU Hai-shan，CHANG Xiao-ling.Power load forecasting with least squares support vector machines and chaos theory[C]//Proc of Intelligent Control and Automation.2006:4369-4373.

[9]SUYKENS J，GESTEL T V，BRABANTER J D，et al.Financial time series prediction using least squares support vector machines within the evidence framework[J].IEEE Trans on Neural Network，2001，12(4):809-821.

[10]陳磊，張土喬.基于貝葉斯最小二乘支持向量機(jī)的時用水量預(yù)測模型[J].天津大學(xué)學(xué)報，2006，39(9):1037-1042.