基于ARIMA和CART的負(fù)載預(yù)測(cè)模型

王電鋼，黃 林，常 健，梅克進(jìn)，牛新征

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

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

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

1 負(fù)載預(yù)測(cè)模型

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

1.1 ARIMA模型

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

(1)

(2)

當(dāng)模型中心化后，可簡(jiǎn)寫為

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

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

(3)

ARIMA模型的建模步驟如下：

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

ADF單位根檢驗(yàn)法：

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

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

(4)

則

(5)

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

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

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

(6)

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

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

在ARIMA中，記

(7)

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

(8)

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

(9)

4)檢驗(yàn)?zāi)Ｐ偷娘@著性．如果擬合模型未通過檢驗(yàn)，則轉(zhuǎn)向步驟2)重新選擇模型再擬合，直到殘差序列為白噪聲為止．

5)利用擬合的模型，預(yù)測(cè)將來的走勢(shì)．

1.2 CART模型

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

1.2.1 CART的生成

CART的生成是決策樹的核心問題之一，決策樹的生長(zhǎng)是反復(fù)分支的過程，當(dāng)分支沒有意義，即分支后結(jié)果差異不再顯著下降，就不再分組．也就是說，分組的目的是為了使輸出變量更加接近．在CART中，為了使預(yù)測(cè)的效果更好，通常使GINI值更?。瓽INI值為

(10)

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

(11)

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

1.2.2 剪枝

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

(12)

其中，R(t)為結(jié)點(diǎn)數(shù)t的錯(cuò)誤代價(jià)，為

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

(13)

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

1.3 基于ARIMA和CART的負(fù)載預(yù)測(cè)模型

運(yùn)用組合模型對(duì)負(fù)載序列進(jìn)行預(yù)測(cè)，存在兩個(gè)關(guān)鍵點(diǎn)：

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

2)當(dāng)擬合完序列中存在的線性因素后，需要對(duì)殘差序列的非線性因素進(jìn)行提取，本研究采用CART來擬合非線性因素，降低了訓(xùn)練時(shí)間，并且分類更為簡(jiǎn)單．

1.3.1 加權(quán)最小二乘的ARIMA參數(shù)估計(jì)

定義wi為滯后i階的數(shù)據(jù)的權(quán)重，我們認(rèn)為，殘差更大的項(xiàng)占有的權(quán)值應(yīng)該更低，這樣能使誤差更?。疄榱讼?fù)號(hào)帶來的影響，用殘差的平方來表達(dá)，即

(14)

以此構(gòu)建對(duì)角權(quán)重矩陣[16]

(15)

(16)

(17)

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

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

Fayyad邊界點(diǎn)判定與熵[17]有關(guān)，其熵越小，對(duì)屬性進(jìn)行分類所需的平均信息量就越少．熵值為

(18)

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

1.3.3 組合算法

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

(19)

(20)

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

(21)

最終i時(shí)刻的觀測(cè)值可以表示為

(22)

具體算法為：

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

步驟2：通過加權(quán)最小二乘參數(shù)估計(jì)法得到ARIMA的相應(yīng)參數(shù)，得到線性預(yù)測(cè)模塊ARIMA的預(yù)測(cè)模型；

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

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

步驟5：結(jié)合ARIMA模型和CART模型的預(yù)測(cè)結(jié)果，得到最終結(jié)果．

2 實(shí)驗(yàn)結(jié)果及分析

2.1 實(shí)驗(yàn)數(shù)據(jù)集

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

表1 實(shí)驗(yàn)數(shù)據(jù)集

2.2 實(shí)驗(yàn)結(jié)果

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

圖1 CPU_5負(fù)載預(yù)測(cè)結(jié)果對(duì)比Fig.1 (Color online) CPU_5 load prediction results comparison

圖2 CPU_10負(fù)載預(yù)測(cè)結(jié)果對(duì)比Fig.2 (Color online) CPU_10 load prediction results comparison

圖3 CPU_20負(fù)載預(yù)測(cè)結(jié)果對(duì)比Fig.3 (Color online) CPU_20 load prediction results comparison

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

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

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

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

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

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

為了量化本研究算法的預(yù)測(cè)精度，我們采用平均絕對(duì)誤差和作為評(píng)價(jià)標(biāo)準(zhǔn)，即

(23)

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

表2 不同模型的負(fù)載預(yù)測(cè)誤差對(duì)比

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

結(jié) 語

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