王電鋼，黃 林，常 健，梅克進，牛新征

1) 國網(wǎng)四川省電力公司信息通信公司，四川成都 610015; 2)電子科技大學計算機科學與工程學院，四川成都 611731

隨著業(yè)務量的上升，服務器主機上的負載壓力不斷增大，而長時間處于高負載狀態(tài)不利于主機設備的穩(wěn)定運行，需要運維操作人員及時發(fā)現(xiàn)并釋放資源，這對運維工作帶來了困難．雖然現(xiàn)有的運維監(jiān)控系統(tǒng)中已有對CPU和內(nèi)存等的監(jiān)控功能，并可以通過設置告警閾值提醒運維人員，但這種事后處理的方式具有一定滯后性，存在問題處理不及時的風險．因此，對CPU和內(nèi)存等資源的歷史負載信息和波動模式進行分析挖掘，并預測未來一段時間的負載趨勢，對于智能化運維工作是極其重要的．負載的趨勢預測有助于提高運維工作的預見性，為運維人員制定解決方案提供一定的緩沖期，對于可能出現(xiàn)的問題防患于未然．

對于負載預測的研究，目前主流的方法是利用歷史數(shù)據(jù)建立線性預測模型．然而在實際工作中，主機負載受復雜的內(nèi)外部環(huán)境影響，如溫度、網(wǎng)絡、業(yè)務量和硬件狀況等．真實的主機負載信息并不嚴格滿足線性關系，存在一定的非線性部分，而現(xiàn)有的一些方法并未對非線性部分進行預測，預測效果較差．如李剛等[1-3]基于特定范圍內(nèi)的歷史數(shù)據(jù)，采用自回歸差分滑動平均(autoregressive integrated moving average，ARIMA)模型來預測未來特定范圍的值，可以較好地擬合線性部分，但并未考慮非線性部分，丟失了部分模型精度．此外，雖然部分研究提出不同的參數(shù)估計方法來提升模型精度．如單銳等[4-5]提出基于改進譜共軛梯度的ARIMA模型參數(shù)估計法，通過調(diào)整參數(shù)，使得算法滿足充分下降條件或者共軛條件，達到優(yōu)化的目的．張宗華等[6]提出了基于加權改進的AR模型的負載預測，他認為不同時間點對當前時間點的影響不同，離當前時間點距離越近，通常對預測造成更大的影響，應在不同的時間點上分配不同的權值，讓影響更大的點擁有更大的權值，減小偏遠點的影響，提升精度．上述方法盡管在不同層次上提升了模型對負載數(shù)據(jù)的預測效果，但是這種提升僅體現(xiàn)在對模型線性部分的預測，并未真正解決數(shù)據(jù)中非線性部分的預測問題．為此，本研究提出將負載數(shù)據(jù)分解為線性部分和非線性部分，并分別對兩部分進行訓練和預測，采用基于加權最小二乘參數(shù)估計方法[7]的線性模型ARIMA[8]預測負載數(shù)據(jù)的線性部分，采用基于Fayyad邊界判定[9]優(yōu)化方法的分類回歸樹[10-11](classification and regression tree，CART)模型擬合負載數(shù)據(jù)的非線性部分，最后將預測結果融合，提升預測精度．

1 負載預測模型

給定數(shù)據(jù)集D={x1,x2, …,xt}， 其中，xt表示以負載數(shù)據(jù)作為時間序列時t時刻的負載值，負載預測模型解決的是t時刻后續(xù)的多個數(shù)據(jù)值的預測問題．

1.1 ARIMA模型

ARIMA模型是一種基于時間序列的預測方法，它用某種數(shù)學模型將時間和預測對象組成的序列擬合起來．一旦模型確定后，就可以通過這個模型預測未來，被廣泛應用在實際中，如就業(yè)發(fā)展趨勢分析、機場客流量預測、疫情分析和負荷預測等．ARIMA模型滿足

(1)

(2)

當模型中心化后，可簡寫為

xt=φ1xt-1+…+φpxt-p+εt-

θ1εt-1-…-θqεt-q

(3)

ARIMA模型的建模步驟如下：

1)首先用ADF[12]單位根檢驗法判斷數(shù)據(jù)的平穩(wěn)性．當數(shù)據(jù)不平穩(wěn)時，對序列進行差分處理．差分階數(shù)的選取方法一般為將其從1逐漸增大，直至序列滿足ADF校驗．

ADF單位根檢驗法：

如果序列經(jīng)過d階差分后平穩(wěn)，不妨設

|λi<1|;i=1, 2, …,p

(4)

則

(5)

由式(5)可知，ARIMA模型共有p+d個根，其中，p個根在單位圓外，d個根在單位圓上．當d≠0時，ARIMA模型不平穩(wěn)．

2)根據(jù)樣本自相關函數(shù)ACF和偏自相關函數(shù)PACF的拖尾性和截尾性來確定p和q值．采用AIC[13]標準，選擇使AIC達到最小值的自回歸滑動平均模型(autoregressive moving average model，ARMA)進行擬合．AIC標準函數(shù)為

AIC=nlnL+2(p+q+1)

(6)

其中，L為似然函數(shù)．選擇最佳p、q值使得AIC達到最?。?/p>

3)估計線性預測模型中參數(shù)的值．常用的方法是最小二乘法．

在ARIMA中，記

(7)

θ1εt-1-…-θqεt-q

(8)

其中，φi為自回歸系數(shù)；θi為移動平滑系數(shù)；εi為零均值白噪聲序列. 則殘差項為

(9)

4)檢驗模型的顯著性．如果擬合模型未通過檢驗，則轉(zhuǎn)向步驟2)重新選擇模型再擬合，直到殘差序列為白噪聲為止．

5)利用擬合的模型，預測將來的走勢．

1.2 CART模型

CART是一種非線性的分類和回歸模型．它能很好地處理高維數(shù)據(jù)，并篩選出重要的變量，具有良好的可解釋性．在機器學習中，利用對象屬性和對象值之間的映射關系，可以將回歸樹作為預測模型．但當訓練集太大時，需要多次順序掃描數(shù)據(jù)集，因此傳統(tǒng)構造回歸樹的算法效率比較低．本研究對傳統(tǒng)CART算法的分裂策略進行了優(yōu)化．傳統(tǒng)CART回歸樹的訓練算法包括2個步驟．

1.2.1 CART的生成

CART的生成是決策樹的核心問題之一，決策樹的生長是反復分支的過程，當分支沒有意義，即分支后結果差異不再顯著下降，就不再分組．也就是說，分組的目的是為了使輸出變量更加接近．在CART中，為了使預測的效果更好，通常使GINI值更小．GINI值為

(10)

其中，pi為在樣本集中取到分類為Ci的子集的概率；l為子集數(shù)量．對于回歸樹來說，采用均方根誤差來確定分法，均方根誤差公式為

(11)

其中，xi為樣本值；μ為樣本均值；n為樣本數(shù)量．σ越小，表明預測效果越好．因此要選擇使回歸方差最小的屬性作為分裂方案．

1.2.2 剪枝

對決策樹的精簡，是另一個核心問題．回歸樹的剪枝是為了防止模型過擬合,CART使用CCP[14-15]算法進行剪枝，在訓練集上計算表面誤差增益率為

(12)

其中，R(t)為結點數(shù)t的錯誤代價，為

R(t)=r(t)p(t)

(13)

其中，r(t)為結點t的錯分樣本率；p(t)為所有樣本中落入結點t的樣本所占的比例；R(T)為子樹T的錯誤代價；N(T)為子樹中的結點數(shù)．CCP的剪枝策略為取出最小指標α對應的節(jié)點，將其剪掉，生成第1個子樹，重復這個過程，直到只剩下根節(jié)點時，將其作為最后一個子樹．然后利用驗證集去驗證所有子樹，取誤差最小的樹．

1.3 基于ARIMA和CART的負載預測模型

運用組合模型對負載序列進行預測，存在兩個關鍵點：

1)需要通過ARIMA模型較好的擬合序列中存在的線性因素，使序列的線性因素基本提取完全．因此，本研究在傳統(tǒng)ARIMA模型參數(shù)估計方法上做了優(yōu)化，采用加權最小二乘估計法來消除異方差性，使得參數(shù)估計更加準確，模型擬合更好．

2)當擬合完序列中存在的線性因素后，需要對殘差序列的非線性因素進行提取，本研究采用CART來擬合非線性因素，降低了訓練時間，并且分類更為簡單．

1.3.1 加權最小二乘的ARIMA參數(shù)估計

定義wi為滯后i階的數(shù)據(jù)的權重，我們認為，殘差更大的項占有的權值應該更低，這樣能使誤差更?。疄榱讼撎枎淼挠绊懀脷埐畹钠椒絹肀磉_，即

(14)

以此構建對角權重矩陣[16]

(15)

(16)

(17)

xi為時間序列；Y為預測時間t前真實值組成的(n-p)×1矩陣．

1.3.2 基于邊界判定的CART分裂策略

Fayyad邊界點判定與熵[17]有關，其熵越小，對屬性進行分類所需的平均信息量就越少．熵值為

(18)

其中，pi表示在樣本集中取到分類為Ci的子集的概率. 由于熵值和GINI系數(shù)的變化趨勢相同，因此，要找到最小GINI系數(shù)，只需要找到使平均類熵達到最小的值．由Fayyad邊界點判定原理可知，該值在排序后兩個相鄰異類樣本之間．本研究的CART分裂屬性為連續(xù)屬性，所以每次只需要找出一個將屬性取平均值后的分界點作為分割閾值，將樣本集分為兩邊，此時，閾值點即為該分界點．此方法并不需要計算每個分割點的GINI系數(shù)，大大提升了訓練效率．只有當出現(xiàn)屬性值達到最小這種不理想情況時，才會與原來的分類次數(shù)相同．

1.3.3 組合算法

通過改進的ARIMA模型得到預測數(shù)據(jù)和歷史數(shù)據(jù)的線性組合，即式(3)．由于εt參數(shù)的不可獲得性，所以xt的估計值為

(19)

(20)

由式(20)得到負載數(shù)據(jù)的非線性部分后，需要利用改進的CART回歸樹對滯后期從1到p階的歷史數(shù)據(jù)進行殘差擬合訓練，提取序列中的非線性關系，得到擬合更為準確的非線性關系，即

(21)

最終i時刻的觀測值可以表示為

(22)

具體算法為：

步驟1：數(shù)據(jù)預處理，并通過AIC標準確定最優(yōu)階數(shù)p、q；

步驟2：通過加權最小二乘參數(shù)估計法得到ARIMA的相應參數(shù)，得到線性預測模塊ARIMA的預測模型；

步驟3：將觀測值與預測模型的擬合值作差，得到殘差序列；

步驟4：通過步驟一中所定階數(shù)p， 用CART回歸樹將p個歷史數(shù)據(jù)與對應殘差進行訓練；

步驟5：結合ARIMA模型和CART模型的預測結果，得到最終結果．

2 實驗結果及分析

2.1 實驗數(shù)據(jù)集

本研究采用不同采樣頻率的CPU和內(nèi)存負載數(shù)據(jù)，采集自某企業(yè)真實的主機(表1)．算法采用Python實現(xiàn)，實驗環(huán)境為Windows8.1、Intel Core i7-4510CPU@2.60 GHz、4 Gbyte內(nèi)存．

表1 實驗數(shù)據(jù)集

2.2 實驗結果

本研究在采樣頻率為5、10和20 min的CPU負載上進行訓練，并預測未來的40個數(shù)據(jù)，與傳統(tǒng)ARIMA模型進行對比，實驗結果如圖1至圖3．

圖1 CPU_5負載預測結果對比Fig.1 (Color online) CPU_5 load prediction results comparison

圖2 CPU_10負載預測結果對比Fig.2 (Color online) CPU_10 load prediction results comparison

圖3 CPU_20負載預測結果對比Fig.3 (Color online) CPU_20 load prediction results comparison

從圖1至圖3可見，ARIMA+CART組合模型對偏遠點的預測均比ARIMA模型準確，整體的預測效果也要比ARIMA模型好．這是由于它預測了負載數(shù)據(jù)中的非線性部分，更接近實際數(shù)據(jù)分布．

進一步，以不同采樣間隔的內(nèi)存負載數(shù)據(jù)分別對ARIMA模型和ARIMA+CART組合模型進行訓練并預測，實驗結果如圖4至圖6．

圖4 內(nèi)存_5利用率預測結果對比Fig.4 (Color online) Memory_5 utilization rate prediction results comparison

圖 5 內(nèi)存_10利用率預測結果對比Fig.5 (Color online) Memory_10 utilization rate prediction results comparison

圖 6 內(nèi)存_20利用率預測結果對比Fig.6 (Color online) Memory_20 utilization rate prediction results comparison

從圖4至圖6可見，ARIMA+CART組合模型的預測均比ARIMA模型準確，這是由于組合模型擬合了殘差中含有的非線性因素，所以比ARIMA更貼近真實值，誤差更?。诓煌瑫r間間隔的內(nèi)存利用率數(shù)據(jù)中，組合模型同樣有更好的效果．

為了量化本研究算法的預測精度，我們采用平均絕對誤差和作為評價標準，即

(23)

通過分析實驗數(shù)據(jù)，得到ARIMA模型和ARIMA+CART組合模型的負載預測誤差，如表2．

表2 不同模型的負載預測誤差對比

從表2可見，ARIMA+CART模型相比ARIMA模型的預測誤差有明顯降低，預測精度比傳統(tǒng)ARIMA模型提高了15%以上，證明了本研究模型的預測精度更高．

結 語

本研究提出基于加權參數(shù)估計法的ARIMA和CART的組合負載預測模型，較單一線性模型而言，CART解決了負載數(shù)據(jù)中非線性部分的預測問題，模型預測精度得到明顯提升．實驗結果證明，本研究模型對一些波動較大的偏遠點預測要更優(yōu)于單一線性模型，這是由于CART對殘差的非線性部分的預測彌補了線性模型的缺陷，使得模型的最終預測值要比傳統(tǒng)模型更靠近真實值，整體的預測精度提高了15%以上．