馮培坤,劉 杰,伍衛(wèi)國(guó),柴玉香,張祥俊
(1.西安交通大學(xué) 軟件學(xué)院,陜西 西安 710000;2.上海超級(jí)計(jì)算中心,上海 201203;3.西安交通大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安 710000)
隨著互聯(lián)網(wǎng)的蓬勃發(fā)展,硬件成本不斷降低,網(wǎng)絡(luò)帶寬得到了大幅提升,在進(jìn)入Web2.0時(shí)代后,Web站點(diǎn)日志增長(zhǎng),同時(shí)也伴隨著大量的用戶日志訪問(wèn)數(shù)據(jù)。站點(diǎn)流量是網(wǎng)絡(luò)維護(hù)的重要指標(biāo),反映著站點(diǎn)運(yùn)行的狀態(tài),對(duì)于站點(diǎn)流量進(jìn)行建模和預(yù)測(cè)成為了近幾年的研究熱點(diǎn)。
隨著站點(diǎn)業(yè)務(wù)量的增加和用戶的不斷積累,網(wǎng)站的網(wǎng)絡(luò)流量呈現(xiàn)出復(fù)雜多變的特點(diǎn),對(duì)站點(diǎn)的流量進(jìn)行有效的統(tǒng)計(jì)和預(yù)測(cè),能很好地優(yōu)化站點(diǎn)的運(yùn)營(yíng)和網(wǎng)絡(luò)管理。用戶訪問(wèn)站點(diǎn)的方式都是基于時(shí)間序列進(jìn)行的,根據(jù)用戶的每一個(gè)訪問(wèn),服務(wù)器端都會(huì)記錄用戶的訪問(wèn)數(shù)據(jù),其中包含有本次請(qǐng)求的流量大小,根據(jù)這些流量值來(lái)建立對(duì)應(yīng)的時(shí)間序列的流量預(yù)測(cè)模型?;跁r(shí)間序列的網(wǎng)絡(luò)流量預(yù)測(cè)方法有很多,主要有回歸預(yù)測(cè)模型、卡爾曼濾波模型、神經(jīng)網(wǎng)絡(luò)模型和支持向量機(jī)模型等[1]。
回歸預(yù)測(cè)模型是一種常見(jiàn)的預(yù)測(cè)性建模技術(shù),它研究的是因變量(目標(biāo))和自變量(預(yù)測(cè)器)之間的關(guān)系[2]。卡爾曼濾波預(yù)測(cè)模型是一種利用線性系統(tǒng)狀態(tài)方程,通過(guò)系統(tǒng)輸入輸出觀測(cè)數(shù)據(jù),對(duì)系統(tǒng)狀態(tài)進(jìn)行最優(yōu)估計(jì)的算法[3]。神經(jīng)網(wǎng)絡(luò)是具有自組織、自適應(yīng)和自學(xué)能力的非線性動(dòng)力學(xué)習(xí)系統(tǒng)[4-5]。基于支持向量機(jī)的模型預(yù)測(cè)是監(jiān)督學(xué)習(xí)中的常見(jiàn)算法,經(jīng)過(guò)長(zhǎng)時(shí)間的發(fā)展,在預(yù)測(cè)方面引入核函數(shù),在有限的樣本信息中,往往能得到比較好的預(yù)測(cè)效果。下面對(duì)涉及到的兩種預(yù)測(cè)模型進(jìn)行簡(jiǎn)要介紹。
卡爾曼濾波算法利用多次觀察和估計(jì)值來(lái)達(dá)到目的,整個(gè)算法是遞歸進(jìn)行的,需要多次重復(fù)調(diào)整??柭鼮V波器用于估計(jì)離散時(shí)間過(guò)程的狀態(tài)變量,記為X(t),該算法可用線性隨機(jī)微分方程(linear stochastic difference equation)來(lái)描述:
X(t)=AX(t-1)+BU(t)+W(t)
(1)
Z(t)=HX(t)+V(t)
(2)
其中,X(t)是t時(shí)刻的系統(tǒng)狀態(tài),U(t)是t時(shí)刻對(duì)系統(tǒng)的控制量,A和B是系統(tǒng)參數(shù),Z(t) 是t時(shí)刻的測(cè)量值,H是測(cè)量系統(tǒng)的參數(shù),W(t)和V(t)分別表示過(guò)程和測(cè)量的噪聲,被假設(shè)成高斯白噪聲(white Gaussian noise),其協(xié)方差分別是Q和R。
卡爾曼濾波算法的具體過(guò)程如下所示:
(1)計(jì)算上一狀態(tài)預(yù)測(cè)的結(jié)果X(t|t-1)。利用系統(tǒng)現(xiàn)有的狀態(tài)來(lái)預(yù)測(cè)現(xiàn)在時(shí)刻狀態(tài),得到預(yù)測(cè)值:
X(t|t-1)=AX(t-1|t-1)+BU(t)
(3)
其中,X(t-1|t-1)是上一狀態(tài)最優(yōu)結(jié)果,U(t)為現(xiàn)在狀態(tài)控制量,如果沒(méi)有控制量即為零。
(2)計(jì)算X(t|t-1)對(duì)應(yīng)的協(xié)方差P(t|t-1)。系統(tǒng)結(jié)果已經(jīng)更新,更新X(t|t-1)時(shí)刻的協(xié)方差,用P表示:
P(t|t-1)=AP(t-1|t-1)A`+Q
(4)
其中,P(t-1|t-1)是X(t-1|t-1)對(duì)應(yīng)的協(xié)方差,A'表示A的轉(zhuǎn)置矩陣,Q是系統(tǒng)過(guò)程的協(xié)方差。
(3)計(jì)算現(xiàn)在t時(shí)刻的最優(yōu)化估算值X(t|t)。目前為止有了對(duì)系統(tǒng)的預(yù)測(cè)值X(t|t-1),然后再收集現(xiàn)在狀態(tài)的測(cè)量值,結(jié)合預(yù)測(cè)值和測(cè)量值,根據(jù)公式計(jì)算可以得到現(xiàn)在t時(shí)刻的最優(yōu)估算值:
X(t|t)=X(t|t-1)+Kg(t)(Z(t)-
HX(t|t-1))
(5)
(4)其中Kg為卡爾曼增益(Kalman gain),其計(jì)算公式如下:
Kg(t)=P(t|t-1)H`/[HP(t|t-1)H+R]
(6)
(5)更新t狀態(tài)下X(t|t)的協(xié)方差。到現(xiàn)在為止,得到了t狀態(tài)下最優(yōu)的估算值X(t|t)。但是為了讓卡爾曼濾波器不斷運(yùn)行下去直到系統(tǒng)過(guò)程結(jié)束,還要更新t狀態(tài)下X(t|t)的協(xié)方差,也就是對(duì)應(yīng)式(4)中t-1時(shí)刻的協(xié)方差:
P(t|t)=[ (I-Kg(t))H]P(t|t-1)
(7)
支持向量機(jī),其基本模型定義為特征空間上的間隔最大的線性分類器,即支持向量機(jī)的學(xué)習(xí)策略便是間隔最大化,最終可轉(zhuǎn)化為一個(gè)凸二次規(guī)劃問(wèn)題的求解,在遇到線性不可分時(shí),通常是把樣例映射到高維空間中,引入核函數(shù)來(lái)代替非線性函數(shù)的內(nèi)積運(yùn)算,從而在維數(shù)可能為無(wú)窮大的線性空間中構(gòu)造出最優(yōu)分類超平面,并得到分離器的決策函數(shù)[6-7]。在預(yù)測(cè)領(lǐng)域,SVM的重視程度越來(lái)越高,例如:銷售量預(yù)測(cè)、金融股票預(yù)測(cè)、電力負(fù)荷預(yù)測(cè),網(wǎng)站業(yè)務(wù)量預(yù)測(cè)等[8]。
假定訓(xùn)練數(shù)據(jù)(x1,y1),…,(xn,yn),x∈Rn,y∈{+1,-1}(x1)可以被一個(gè)超平面g(x)=wx+b分開(kāi),存在一個(gè)最優(yōu)超平面可以使數(shù)據(jù)分開(kāi)并且離超平面最近的向量與超平面之間的距離是最大的,在線性可分時(shí),SVM采用以下函數(shù):
f(x)=sgn(wx+b)
(8)
超平面的參數(shù)不唯一,參數(shù)對(duì)分類結(jié)果無(wú)影響,故將決策函數(shù)值歸一化為1,即:
yi(wxi+b)≥1,i=1,2,…,n;yi=-1,1
(9)
(10)
為了便于求解,將上述問(wèn)題轉(zhuǎn)化為:
(11)
即現(xiàn)在變成線性約束的二次規(guī)劃問(wèn)題,對(duì)上述的式子進(jìn)行最優(yōu)化求解,采用拉格朗日方法,構(gòu)造拉格朗日函數(shù):
(12)
其中,αi≥0為拉格朗日乘子,分別對(duì)w和b求偏微并令它們等于0,可得對(duì)偶問(wèn)題:
(13)
針對(duì)上式的對(duì)偶問(wèn)題進(jìn)行求解,得到w*和b*:
其判別函數(shù)為f(x),帶入w*和b*,就可得最終的判別函數(shù)表達(dá)式:
(14)
對(duì)于線性不可分的情況,需要將原始的特征空間映射到高維空間,即x→φ(x),需要引入核函數(shù)K(xi,xj)=φ(xi)Tφ(xj)帶入到式(14),則針對(duì)線性不可分的情況,最終的判別函數(shù)是:
(15)
從低維到高維所選擇的核函數(shù)很多,根據(jù)Mercer定理,只需要關(guān)注K(xi,yi),而不用在意φ(xi)。
SVM預(yù)測(cè)模型主要有3個(gè)參數(shù):徑向基核函數(shù)參數(shù)σ、懲罰參數(shù)C、不敏感損失參數(shù)ε[9]。
K折交叉驗(yàn)證常常用來(lái)選擇SVM合適的參數(shù),將原始數(shù)據(jù)分成K組(一般是均分),將每個(gè)子集數(shù)據(jù)分別做一次驗(yàn)證集,其余的K-1組子集數(shù)據(jù)作為訓(xùn)練集,這樣會(huì)得到K個(gè)模型,用這K個(gè)模型最終的驗(yàn)證集的分類準(zhǔn)確率的平均數(shù)作為此K-CV下分類器的性能指標(biāo),K-CV可以有效地避免過(guò)學(xué)習(xí)以及欠學(xué)習(xí)狀態(tài)的發(fā)生,最后得到的結(jié)果也比較具有說(shuō)服性。
基于時(shí)間序列,根據(jù)歷史日志數(shù)據(jù)信息,使用并聯(lián)組合模型,結(jié)合SVM和卡爾曼濾波算法來(lái)實(shí)現(xiàn)流量預(yù)測(cè)。以下對(duì)預(yù)測(cè)模型設(shè)計(jì)與實(shí)現(xiàn)以及結(jié)果分析進(jìn)行詳細(xì)介紹。
SVM在時(shí)間序列預(yù)測(cè)中具有很好的效果,是優(yōu)秀的監(jiān)督學(xué)習(xí)算法,與此同時(shí),卡爾曼濾波算法簡(jiǎn)單,可以快速迭代出下一個(gè)預(yù)測(cè)狀態(tài)值[10]??紤]工業(yè)社區(qū)日志流量的特點(diǎn)和預(yù)測(cè)需求等因素,文中在站點(diǎn)網(wǎng)絡(luò)流量預(yù)測(cè)模塊中,采用卡爾曼濾波算法和SVM預(yù)測(cè)算法構(gòu)建并聯(lián)組合預(yù)測(cè)模型,為網(wǎng)站的流量預(yù)測(cè)提供可靠的參考數(shù)據(jù)。
文中使用RBF函數(shù)作為SVM的核函數(shù),因?yàn)镽BF函數(shù)可以將樣本非線性規(guī)劃到更高維的空間中,且核函數(shù)的參數(shù)較少,模型簡(jiǎn)單,限制條件少,更易于預(yù)測(cè)模型的實(shí)現(xiàn)。根據(jù)第2節(jié)的理論技術(shù)介紹,使用K折交叉驗(yàn)證,得到SVM最優(yōu)參數(shù)組合:σ=1,C=10,ε=0.2。
文中的流量預(yù)測(cè)是將日志訪問(wèn)時(shí)間作為時(shí)間序列{X(t),t=1,2,…,n},預(yù)測(cè)模型描述為:
X(t)=φ[X(t-1),X(t-2),…,X(t-p)]
(16)
其中,φ為非線性函數(shù),p為嵌入維數(shù)。表示用t時(shí)刻的前p個(gè)值來(lái)預(yù)測(cè)第t個(gè)值。在此處時(shí)間間隔的設(shè)置不宜太小,太小對(duì)于流量預(yù)測(cè)意義不大,嵌入維度也不應(yīng)過(guò)小或者過(guò)大,要考慮實(shí)際情況設(shè)置,權(quán)衡預(yù)測(cè)的精度和計(jì)算量[11]。
對(duì)于預(yù)測(cè)的精度,采用絕對(duì)誤差(AE)、相對(duì)誤差(RE)和平均誤差率(MAPE)預(yù)測(cè)指標(biāo)[12]來(lái)衡量,表1為預(yù)測(cè)的評(píng)價(jià)指標(biāo)公式。
表1 預(yù)測(cè)評(píng)價(jià)指標(biāo)
采用組合算法對(duì)網(wǎng)絡(luò)流量進(jìn)行預(yù)測(cè),彌補(bǔ)傳統(tǒng)時(shí)間序列模型單一預(yù)測(cè)[12]的不足。預(yù)測(cè)模型的組合方式有多種,根據(jù)實(shí)際情況,文中采用并聯(lián)組合模型,使用卡爾曼濾波算法和SVM算法來(lái)實(shí)現(xiàn)組合預(yù)測(cè)。
并聯(lián)組合預(yù)測(cè)是利用兩種不同的模型對(duì)時(shí)間序列進(jìn)行預(yù)測(cè),得到時(shí)間序列[13]的基本特征,對(duì)各個(gè)模型分別賦予合適的權(quán)重值,進(jìn)行組合預(yù)測(cè)[14]。設(shè)計(jì)的并聯(lián)組合模型基本步驟如下:
(1)設(shè)原始時(shí)間序列為{xt,t=1,2,…,n},其中n為預(yù)測(cè)樣本個(gè)數(shù),第i種預(yù)測(cè)方法在第t時(shí)刻的預(yù)測(cè)值記為xit,對(duì)應(yīng)方法的預(yù)測(cè)絕對(duì)誤差記為eit=|xt-xit|,其中i=1,2,x1t和x2t分別表示卡爾曼預(yù)測(cè)值和SVM預(yù)測(cè)值,t為時(shí)間間隔,取值為1~n。
(2)令w1和w2分別為預(yù)測(cè)模型的加權(quán)系數(shù)[15],且w1+w2=1,則在t時(shí)間的組合預(yù)測(cè)值為:
(17)
其中,x1t為卡爾曼預(yù)測(cè)值,x2t為SVM預(yù)測(cè)值,f(x)分別對(duì)應(yīng)第2節(jié)中介紹的預(yù)測(cè)模型。
minSe
s.tw1+w2=1,wi≥0,i=1,2
(18)
上式為一個(gè)二次凸優(yōu)化問(wèn)題[16],即對(duì)偶問(wèn)題,可使用拉格朗日函數(shù)來(lái)將其轉(zhuǎn)化為線性規(guī)劃問(wèn)題,從而確定出非負(fù)組合模型最優(yōu)的權(quán)重系數(shù)。
基于并聯(lián)組合預(yù)測(cè)模型的基本思想,按照上面的步驟,首先根據(jù)日志數(shù)據(jù)中的流量序列來(lái)建立預(yù)測(cè)模型,日志數(shù)據(jù)分訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)[17],使用訓(xùn)練數(shù)據(jù)輸入到卡爾曼和SVM預(yù)測(cè)模型中得到預(yù)測(cè)的站點(diǎn)網(wǎng)絡(luò)流量值,分別計(jì)算得到絕對(duì)誤差,針對(duì)上述步驟3進(jìn)行最優(yōu)化求解確定組合權(quán)值,使用測(cè)試數(shù)據(jù)來(lái)檢驗(yàn)?zāi)P皖A(yù)測(cè)的精度。確定了組合模型系數(shù)后,在第3節(jié)日志數(shù)據(jù)分析模塊的站點(diǎn)網(wǎng)絡(luò)流量預(yù)測(cè)中,基于時(shí)間序列[18],設(shè)計(jì)策略模式來(lái)進(jìn)行流量預(yù)測(cè)。
實(shí)驗(yàn)使用的數(shù)據(jù)來(lái)自于上海超級(jí)計(jì)算中心的工業(yè)社區(qū)用戶訪問(wèn)數(shù)據(jù),當(dāng)用戶訪問(wèn)工業(yè)社區(qū)站點(diǎn)時(shí),服務(wù)器端將記錄用戶的訪問(wèn)信息,其中包含本次請(qǐng)求的流量值。實(shí)驗(yàn)選取其中一部分的訪問(wèn)數(shù)據(jù),進(jìn)行數(shù)據(jù)清洗和數(shù)據(jù)統(tǒng)計(jì)分析,提取基于時(shí)間序列的站點(diǎn)流量數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)和測(cè)試數(shù)據(jù)。實(shí)驗(yàn)構(gòu)建Spark streaming流式處理集群來(lái)進(jìn)行日志數(shù)據(jù)的清洗和統(tǒng)計(jì)分析[19],然后進(jìn)行并聯(lián)組合預(yù)測(cè)模型的建立和實(shí)驗(yàn)。
實(shí)驗(yàn)環(huán)境:搭建數(shù)據(jù)預(yù)處理平臺(tái)的Hadoop和Spark集群均使用Cloudera提供的cdh5.7.0版本,使用Zookeeper來(lái)進(jìn)行協(xié)調(diào)服務(wù),提供分布式的可靠協(xié)議,構(gòu)建Hadoop分布式文件系統(tǒng),采用Spark on Yarn進(jìn)行部署,進(jìn)行資源的統(tǒng)一管理。測(cè)試環(huán)境的操作系統(tǒng)是Windows 10,CPU是Interl(R) Core(TM)i5-7400 CPU @ 3.00 GHz,機(jī)器內(nèi)核為4核,固態(tài)硬盤為128 GB,內(nèi)存大小為8 G。
圖1是本次實(shí)驗(yàn)的日志數(shù)據(jù)處理平臺(tái)架構(gòu),對(duì)日志數(shù)據(jù)源進(jìn)行ETL[20],在數(shù)據(jù)處理平臺(tái)完成原始日志到結(jié)構(gòu)化日志的轉(zhuǎn)化,實(shí)現(xiàn)數(shù)據(jù)清洗和數(shù)據(jù)分析,然后在此基礎(chǔ)上使用流量預(yù)測(cè)模型實(shí)現(xiàn)流量預(yù)測(cè)。
圖1 日志數(shù)據(jù)處理平臺(tái)架構(gòu)
本實(shí)驗(yàn)首先構(gòu)建站點(diǎn)日志數(shù)據(jù)處理平臺(tái),獲取工業(yè)社區(qū)的日志數(shù)據(jù),在處理平臺(tái)進(jìn)行數(shù)據(jù)清洗,整理統(tǒng)計(jì)出基于時(shí)間序列的流量數(shù)據(jù),然后基于歷史流量數(shù)據(jù),分別根據(jù)卡爾曼濾波算法和支持向量機(jī)來(lái)計(jì)算出預(yù)測(cè)值,對(duì)比實(shí)際流量值計(jì)算權(quán)值,構(gòu)建并聯(lián)組合模型來(lái)實(shí)現(xiàn)更為準(zhǔn)確的預(yù)測(cè)[21]。
首先構(gòu)建站點(diǎn)的日志數(shù)據(jù)處理平臺(tái),搭建分布式集群Hadoop作為底層數(shù)據(jù)存儲(chǔ),部署Spark on Yarn來(lái)實(shí)現(xiàn)數(shù)據(jù)的實(shí)時(shí)數(shù)據(jù)處理,對(duì)重復(fù)的日志數(shù)據(jù)和非必要的日志數(shù)據(jù)進(jìn)行剔除[22],對(duì)空缺的數(shù)值進(jìn)行補(bǔ)全,將原始的日志數(shù)據(jù)轉(zhuǎn)化為結(jié)構(gòu)化的日志數(shù)據(jù),在此基礎(chǔ)上,統(tǒng)計(jì)日志數(shù)據(jù)的時(shí)間和流量字段[23],整理后存儲(chǔ)HBase數(shù)據(jù)庫(kù)中,為下一步提供實(shí)驗(yàn)數(shù)據(jù)。
依據(jù)3.2節(jié)中的并聯(lián)組合模型的思路,讀取流量數(shù)據(jù),分別計(jì)算得到卡爾曼濾波和SVM的預(yù)測(cè)值,對(duì)比實(shí)際流量值得到絕對(duì)誤差,建立預(yù)測(cè)模型,帶入具體的數(shù)值,通過(guò)解決式(18)的二次凸優(yōu)化的問(wèn)題,依次得到多個(gè)最優(yōu)權(quán)值,然后求均值得到最優(yōu)的權(quán)重比例系數(shù)。
圖2 并聯(lián)組合預(yù)測(cè)流量結(jié)構(gòu)
通過(guò)對(duì)一段時(shí)間的工業(yè)社區(qū)日志數(shù)據(jù)進(jìn)行數(shù)據(jù)分析和統(tǒng)計(jì),統(tǒng)計(jì)出一部分的日志流量值做流量預(yù)測(cè)模型分析測(cè)試數(shù)據(jù)。在基于3.1和3.2的介紹上,文中采用的是并聯(lián)組合預(yù)測(cè)方法,通過(guò)解決式(18)中的二次凸規(guī)劃問(wèn)題,得到卡爾曼和SVM預(yù)測(cè)模型的權(quán)值為:w1=0.35,w2=0.65。
將w1和w2的值代入卡爾曼和SVM預(yù)測(cè)模型(式(16))中,可得流量預(yù)測(cè)結(jié)果,選取2018年4月份的日志流量進(jìn)行預(yù)測(cè)對(duì)比,根據(jù)實(shí)際值和預(yù)測(cè)值進(jìn)行對(duì)比,然后分別得到圖3~圖5的預(yù)測(cè)折線圖。預(yù)測(cè)模型誤差對(duì)比如表2所示。
表2 預(yù)測(cè)模型誤差對(duì)比
圖3 卡爾曼預(yù)測(cè)
圖4 SVM預(yù)測(cè)
圖5 并聯(lián)組合預(yù)測(cè)模型流量預(yù)測(cè)折線
從圖3~圖5可以看出,其組合預(yù)測(cè)模型的平均誤差率更小,折線擬合效果也更合理,組合預(yù)測(cè)模型與實(shí)際流量值的誤差更小,說(shuō)明組合模型對(duì)于流量預(yù)測(cè)也是可靠有效的。實(shí)驗(yàn)表明在預(yù)測(cè)步長(zhǎng)上,隨著步長(zhǎng)的增加平均誤差率也不斷增大,相比較長(zhǎng)期的來(lái)說(shuō),短期的誤差積累更明顯,步長(zhǎng)越大對(duì)于預(yù)測(cè)越?jīng)]有實(shí)際意義。
使用站點(diǎn)的用戶訪問(wèn)日志數(shù)據(jù),通過(guò)數(shù)據(jù)清洗和數(shù)據(jù)分析處理[24],利用其中的流量值來(lái)構(gòu)建并聯(lián)組合預(yù)測(cè)模型以實(shí)現(xiàn)站點(diǎn)的流量預(yù)測(cè)。使用分布式技術(shù),集合Hadoop和Spark來(lái)實(shí)現(xiàn)日志數(shù)據(jù)的實(shí)時(shí)處理,保證歷史流量值能及時(shí)結(jié)構(gòu)化存儲(chǔ),然后基于歷史流量數(shù)據(jù)來(lái)建立并聯(lián)組合預(yù)測(cè)模型,分別使用卡爾曼濾波算法和支持向量機(jī)進(jìn)行最優(yōu)化找到合適的權(quán)值,然后基于實(shí)時(shí)的流量處理數(shù)據(jù)進(jìn)行實(shí)時(shí)預(yù)測(cè)。
下一步將集成新的預(yù)測(cè)算法,實(shí)現(xiàn)細(xì)粒度[25]的站點(diǎn)流量預(yù)測(cè),并考慮站點(diǎn)的環(huán)境因素來(lái)進(jìn)一步提升預(yù)測(cè)方法的準(zhǔn)確性,提升該模型的精度。