一種基于并聯(lián)組合模型預測站點流量的策略

馮培坤，劉 杰，伍衛(wèi)國，柴玉香，張祥俊

(1.西安交通大學 軟件學院，陜西 西安 710000;2.上海超級計算中心，上海 201203;3.西安交通大學 計算機學院，陜西 西安 710000)

0 引 言

隨著互聯(lián)網(wǎng)的蓬勃發(fā)展，硬件成本不斷降低，網(wǎng)絡帶寬得到了大幅提升，在進入Web2.0時代后，Web站點日志增長，同時也伴隨著大量的用戶日志訪問數(shù)據(jù)。站點流量是網(wǎng)絡維護的重要指標，反映著站點運行的狀態(tài)，對于站點流量進行建模和預測成為了近幾年的研究熱點。

隨著站點業(yè)務量的增加和用戶的不斷積累，網(wǎng)站的網(wǎng)絡流量呈現(xiàn)出復雜多變的特點，對站點的流量進行有效的統(tǒng)計和預測，能很好地優(yōu)化站點的運營和網(wǎng)絡管理。用戶訪問站點的方式都是基于時間序列進行的，根據(jù)用戶的每一個訪問，服務器端都會記錄用戶的訪問數(shù)據(jù)，其中包含有本次請求的流量大小，根據(jù)這些流量值來建立對應的時間序列的流量預測模型?；跁r間序列的網(wǎng)絡流量預測方法有很多，主要有回歸預測模型、卡爾曼濾波模型、神經(jīng)網(wǎng)絡模型和支持向量機模型等[1]。

回歸預測模型是一種常見的預測性建模技術，它研究的是因變量(目標)和自變量(預測器)之間的關系[2]?？柭鼮V波預測模型是一種利用線性系統(tǒng)狀態(tài)方程，通過系統(tǒng)輸入輸出觀測數(shù)據(jù)，對系統(tǒng)狀態(tài)進行最優(yōu)估計的算法[3]。神經(jīng)網(wǎng)絡是具有自組織、自適應和自學能力的非線性動力學習系統(tǒng)[4-5]?；谥С窒蛄繖C的模型預測是監(jiān)督學習中的常見算法，經(jīng)過長時間的發(fā)展，在預測方面引入核函數(shù)，在有限的樣本信息中，往往能得到比較好的預測效果。下面對涉及到的兩種預測模型進行簡要介紹。

1 卡爾曼濾波

卡爾曼濾波算法利用多次觀察和估計值來達到目的，整個算法是遞歸進行的，需要多次重復調整?？柭鼮V波器用于估計離散時間過程的狀態(tài)變量，記為X(t)，該算法可用線性隨機微分方程(linear stochastic difference equation)來描述：

X(t)=AX(t-1)+BU(t)+W(t)

(1)

Z(t)=HX(t)+V(t)

(2)

其中，X(t)是t時刻的系統(tǒng)狀態(tài)，U(t)是t時刻對系統(tǒng)的控制量，A和B是系統(tǒng)參數(shù)，Z(t) 是t時刻的測量值，H是測量系統(tǒng)的參數(shù)，W(t)和V(t)分別表示過程和測量的噪聲，被假設成高斯白噪聲(white Gaussian noise)，其協(xié)方差分別是Q和R。

卡爾曼濾波算法的具體過程如下所示：

(1)計算上一狀態(tài)預測的結果X(t|t-1)。利用系統(tǒng)現(xiàn)有的狀態(tài)來預測現(xiàn)在時刻狀態(tài)，得到預測值：

X(t|t-1)=AX(t-1|t-1)+BU(t)

(3)

其中，X(t-1|t-1)是上一狀態(tài)最優(yōu)結果，U(t)為現(xiàn)在狀態(tài)控制量，如果沒有控制量即為零。

(2)計算X(t|t-1)對應的協(xié)方差P(t|t-1)。系統(tǒng)結果已經(jīng)更新，更新X(t|t-1)時刻的協(xié)方差，用P表示：

P(t|t-1)=AP(t-1|t-1)A`+Q

(4)

其中，P(t-1|t-1)是X(t-1|t-1)對應的協(xié)方差，A'表示A的轉置矩陣，Q是系統(tǒng)過程的協(xié)方差。

(3)計算現(xiàn)在t時刻的最優(yōu)化估算值X(t|t)。目前為止有了對系統(tǒng)的預測值X(t|t-1)，然后再收集現(xiàn)在狀態(tài)的測量值，結合預測值和測量值，根據(jù)公式計算可以得到現(xiàn)在t時刻的最優(yōu)估算值：

X(t|t)=X(t|t-1)+Kg(t)(Z(t)-

HX(t|t-1))

(5)

(4)其中Kg為卡爾曼增益(Kalman gain)，其計算公式如下：

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)。但是為了讓卡爾曼濾波器不斷運行下去直到系統(tǒng)過程結束，還要更新t狀態(tài)下X(t|t)的協(xié)方差，也就是對應式(4)中t-1時刻的協(xié)方差：

P(t|t)=[ (I-Kg(t))H]P(t|t-1)

(7)

2 支持向量機(SVM)

支持向量機，其基本模型定義為特征空間上的間隔最大的線性分類器，即支持向量機的學習策略便是間隔最大化，最終可轉化為一個凸二次規(guī)劃問題的求解，在遇到線性不可分時，通常是把樣例映射到高維空間中，引入核函數(shù)來代替非線性函數(shù)的內積運算，從而在維數(shù)可能為無窮大的線性空間中構造出最優(yōu)分類超平面，并得到分離器的決策函數(shù)[6-7]。在預測領域，SVM的重視程度越來越高，例如：銷售量預測、金融股票預測、電力負荷預測，網(wǎng)站業(yè)務量預測等[8]。

假定訓練數(shù)據(jù)(x1,y1),…,(xn,yn),x∈Rn,y∈{+1,-1}(x1)可以被一個超平面g(x)=wx+b分開，存在一個最優(yōu)超平面可以使數(shù)據(jù)分開并且離超平面最近的向量與超平面之間的距離是最大的，在線性可分時，SVM采用以下函數(shù)：

f(x)=sgn(wx+b)

(8)

超平面的參數(shù)不唯一，參數(shù)對分類結果無影響，故將決策函數(shù)值歸一化為1，即：

yi(wxi+b)≥1,i=1,2,…,n;yi=-1,1

(9)

(10)

為了便于求解，將上述問題轉化為：

(11)

即現(xiàn)在變成線性約束的二次規(guī)劃問題，對上述的式子進行最優(yōu)化求解，采用拉格朗日方法，構造拉格朗日函數(shù)：

(12)

其中，αi≥0為拉格朗日乘子，分別對w和b求偏微并令它們等于0，可得對偶問題：

(13)

針對上式的對偶問題進行求解，得到w*和b*:

其判別函數(shù)為f(x)，帶入w*和b*，就可得最終的判別函數(shù)表達式：

(14)

對于線性不可分的情況，需要將原始的特征空間映射到高維空間，即x→φ(x)，需要引入核函數(shù)K(xi,xj)=φ(xi)Tφ(xj)帶入到式(14)，則針對線性不可分的情況，最終的判別函數(shù)是：

(15)

從低維到高維所選擇的核函數(shù)很多，根據(jù)Mercer定理，只需要關注K(xi,yi)，而不用在意φ(xi)。

SVM預測模型主要有3個參數(shù)：徑向基核函數(shù)參數(shù)σ、懲罰參數(shù)C、不敏感損失參數(shù)ε[9]。

K折交叉驗證常常用來選擇SVM合適的參數(shù)，將原始數(shù)據(jù)分成K組(一般是均分)，將每個子集數(shù)據(jù)分別做一次驗證集，其余的K-1組子集數(shù)據(jù)作為訓練集，這樣會得到K個模型，用這K個模型最終的驗證集的分類準確率的平均數(shù)作為此K-CV下分類器的性能指標，K-CV可以有效地避免過學習以及欠學習狀態(tài)的發(fā)生，最后得到的結果也比較具有說服性。

3 并聯(lián)組合模型

基于時間序列，根據(jù)歷史日志數(shù)據(jù)信息，使用并聯(lián)組合模型，結合SVM和卡爾曼濾波算法來實現(xiàn)流量預測。以下對預測模型設計與實現(xiàn)以及結果分析進行詳細介紹。

3.1 流量預測模型

SVM在時間序列預測中具有很好的效果，是優(yōu)秀的監(jiān)督學習算法，與此同時，卡爾曼濾波算法簡單，可以快速迭代出下一個預測狀態(tài)值[10]?？紤]工業(yè)社區(qū)日志流量的特點和預測需求等因素，文中在站點網(wǎng)絡流量預測模塊中，采用卡爾曼濾波算法和SVM預測算法構建并聯(lián)組合預測模型，為網(wǎng)站的流量預測提供可靠的參考數(shù)據(jù)。

文中使用RBF函數(shù)作為SVM的核函數(shù)，因為RBF函數(shù)可以將樣本非線性規(guī)劃到更高維的空間中，且核函數(shù)的參數(shù)較少，模型簡單，限制條件少，更易于預測模型的實現(xiàn)。根據(jù)第2節(jié)的理論技術介紹，使用K折交叉驗證，得到SVM最優(yōu)參數(shù)組合：σ=1，C=10，ε=0.2。

文中的流量預測是將日志訪問時間作為時間序列{X(t),t=1,2,…,n}，預測模型描述為：

X(t)=φ[X(t-1),X(t-2),…,X(t-p)]

(16)

其中，φ為非線性函數(shù)，p為嵌入維數(shù)。表示用t時刻的前p個值來預測第t個值。在此處時間間隔的設置不宜太小，太小對于流量預測意義不大，嵌入維度也不應過小或者過大，要考慮實際情況設置，權衡預測的精度和計算量[11]。

對于預測的精度，采用絕對誤差(AE)、相對誤差(RE)和平均誤差率(MAPE)預測指標[12]來衡量，表1為預測的評價指標公式。

表1 預測評價指標

3.2 并聯(lián)組合模型設計

采用組合算法對網(wǎng)絡流量進行預測，彌補傳統(tǒng)時間序列模型單一預測[12]的不足。預測模型的組合方式有多種，根據(jù)實際情況，文中采用并聯(lián)組合模型，使用卡爾曼濾波算法和SVM算法來實現(xiàn)組合預測。

并聯(lián)組合預測是利用兩種不同的模型對時間序列進行預測，得到時間序列[13]的基本特征，對各個模型分別賦予合適的權重值，進行組合預測[14]。設計的并聯(lián)組合模型基本步驟如下：

(1)設原始時間序列為{xt,t=1,2,…,n}，其中n為預測樣本個數(shù)，第i種預測方法在第t時刻的預測值記為xit，對應方法的預測絕對誤差記為eit=|xt-xit|，其中i=1,2，x1t和x2t分別表示卡爾曼預測值和SVM預測值，t為時間間隔，取值為1～n。

(2)令w1和w2分別為預測模型的加權系數(shù)[15]，且w1+w2=1，則在t時間的組合預測值為：

(17)

其中，x1t為卡爾曼預測值，x2t為SVM預測值，f(x)分別對應第2節(jié)中介紹的預測模型。

minSe

s.tw1+w2=1,wi≥0,i=1,2

(18)

上式為一個二次凸優(yōu)化問題[16]，即對偶問題，可使用拉格朗日函數(shù)來將其轉化為線性規(guī)劃問題，從而確定出非負組合模型最優(yōu)的權重系數(shù)。

基于并聯(lián)組合預測模型的基本思想，按照上面的步驟，首先根據(jù)日志數(shù)據(jù)中的流量序列來建立預測模型，日志數(shù)據(jù)分訓練數(shù)據(jù)和測試數(shù)據(jù)[17]，使用訓練數(shù)據(jù)輸入到卡爾曼和SVM預測模型中得到預測的站點網(wǎng)絡流量值，分別計算得到絕對誤差，針對上述步驟3進行最優(yōu)化求解確定組合權值，使用測試數(shù)據(jù)來檢驗模型預測的精度。確定了組合模型系數(shù)后，在第3節(jié)日志數(shù)據(jù)分析模塊的站點網(wǎng)絡流量預測中，基于時間序列[18]，設計策略模式來進行流量預測。

4 實驗及結果分析

實驗使用的數(shù)據(jù)來自于上海超級計算中心的工業(yè)社區(qū)用戶訪問數(shù)據(jù)，當用戶訪問工業(yè)社區(qū)站點時，服務器端將記錄用戶的訪問信息，其中包含本次請求的流量值。實驗選取其中一部分的訪問數(shù)據(jù)，進行數(shù)據(jù)清洗和數(shù)據(jù)統(tǒng)計分析，提取基于時間序列的站點流量數(shù)據(jù)作為實驗數(shù)據(jù)和測試數(shù)據(jù)。實驗構建Spark streaming流式處理集群來進行日志數(shù)據(jù)的清洗和統(tǒng)計分析[19]，然后進行并聯(lián)組合預測模型的建立和實驗。

4.1 實驗環(huán)境

實驗環(huán)境：搭建數(shù)據(jù)預處理平臺的Hadoop和Spark集群均使用Cloudera提供的cdh5.7.0版本，使用Zookeeper來進行協(xié)調服務，提供分布式的可靠協(xié)議，構建Hadoop分布式文件系統(tǒng)，采用Spark on Yarn進行部署，進行資源的統(tǒng)一管理。測試環(huán)境的操作系統(tǒng)是Windows 10，CPU是Interl(R) Core(TM)i5-7400 CPU @ 3.00 GHz，機器內核為4核，固態(tài)硬盤為128 GB，內存大小為8 G。

圖1是本次實驗的日志數(shù)據(jù)處理平臺架構，對日志數(shù)據(jù)源進行ETL[20]，在數(shù)據(jù)處理平臺完成原始日志到結構化日志的轉化，實現(xiàn)數(shù)據(jù)清洗和數(shù)據(jù)分析，然后在此基礎上使用流量預測模型實現(xiàn)流量預測。

圖1 日志數(shù)據(jù)處理平臺架構

4.2 實驗步驟

本實驗首先構建站點日志數(shù)據(jù)處理平臺，獲取工業(yè)社區(qū)的日志數(shù)據(jù)，在處理平臺進行數(shù)據(jù)清洗，整理統(tǒng)計出基于時間序列的流量數(shù)據(jù)，然后基于歷史流量數(shù)據(jù)，分別根據(jù)卡爾曼濾波算法和支持向量機來計算出預測值，對比實際流量值計算權值，構建并聯(lián)組合模型來實現(xiàn)更為準確的預測[21]。

首先構建站點的日志數(shù)據(jù)處理平臺，搭建分布式集群Hadoop作為底層數(shù)據(jù)存儲，部署Spark on Yarn來實現(xiàn)數(shù)據(jù)的實時數(shù)據(jù)處理，對重復的日志數(shù)據(jù)和非必要的日志數(shù)據(jù)進行剔除[22]，對空缺的數(shù)值進行補全，將原始的日志數(shù)據(jù)轉化為結構化的日志數(shù)據(jù)，在此基礎上，統(tǒng)計日志數(shù)據(jù)的時間和流量字段[23]，整理后存儲HBase數(shù)據(jù)庫中，為下一步提供實驗數(shù)據(jù)。

依據(jù)3.2節(jié)中的并聯(lián)組合模型的思路，讀取流量數(shù)據(jù)，分別計算得到卡爾曼濾波和SVM的預測值，對比實際流量值得到絕對誤差，建立預測模型，帶入具體的數(shù)值，通過解決式(18)的二次凸優(yōu)化的問題，依次得到多個最優(yōu)權值，然后求均值得到最優(yōu)的權重比例系數(shù)。

圖2 并聯(lián)組合預測流量結構

4.3 結果分析

通過對一段時間的工業(yè)社區(qū)日志數(shù)據(jù)進行數(shù)據(jù)分析和統(tǒng)計，統(tǒng)計出一部分的日志流量值做流量預測模型分析測試數(shù)據(jù)。在基于3.1和3.2的介紹上，文中采用的是并聯(lián)組合預測方法，通過解決式(18)中的二次凸規(guī)劃問題，得到卡爾曼和SVM預測模型的權值為：w1=0.35，w2=0.65。

將w1和w2的值代入卡爾曼和SVM預測模型(式(16))中，可得流量預測結果，選取2018年4月份的日志流量進行預測對比，根據(jù)實際值和預測值進行對比，然后分別得到圖3～圖5的預測折線圖。預測模型誤差對比如表2所示。

表2 預測模型誤差對比

圖3 卡爾曼預測

圖4 SVM預測

圖5 并聯(lián)組合預測模型流量預測折線

從圖3～圖5可以看出，其組合預測模型的平均誤差率更小，折線擬合效果也更合理，組合預測模型與實際流量值的誤差更小，說明組合模型對于流量預測也是可靠有效的。實驗表明在預測步長上，隨著步長的增加平均誤差率也不斷增大，相比較長期的來說，短期的誤差積累更明顯，步長越大對于預測越?jīng)]有實際意義。

5 結束語

使用站點的用戶訪問日志數(shù)據(jù)，通過數(shù)據(jù)清洗和數(shù)據(jù)分析處理[24]，利用其中的流量值來構建并聯(lián)組合預測模型以實現(xiàn)站點的流量預測。使用分布式技術，集合Hadoop和Spark來實現(xiàn)日志數(shù)據(jù)的實時處理，保證歷史流量值能及時結構化存儲，然后基于歷史流量數(shù)據(jù)來建立并聯(lián)組合預測模型，分別使用卡爾曼濾波算法和支持向量機進行最優(yōu)化找到合適的權值，然后基于實時的流量處理數(shù)據(jù)進行實時預測。

下一步將集成新的預測算法，實現(xiàn)細粒度[25]的站點流量預測，并考慮站點的環(huán)境因素來進一步提升預測方法的準確性，提升該模型的精度。