王 彪,王克儉+，何振學(xué)，高萬豪，魏雪川

(1.河北農(nóng)業(yè)大學(xué) 信息科學(xué)與技術(shù)學(xué)院，河北 保定 071001；2.天津城建大學(xué) 控制與機(jī)械工程學(xué)院，天津 300384；3.國網(wǎng)河北省電力公司 石家莊供電公司，河北 石家莊 050052)

0 引 言

云計(jì)算平臺搭建在大規(guī)模服務(wù)器之上，通過系統(tǒng)中存儲的大量數(shù)據(jù)提取有價值的信息[1]。在對分布式文件系統(tǒng)的研究中，如何有效提高系統(tǒng)的可靠性和訪問效率成為當(dāng)今的研究熱點(diǎn)[2]。現(xiàn)有分布式文件系統(tǒng)副本管理機(jī)制分為靜態(tài)管理和動態(tài)管理[3]。靜態(tài)管理因副本數(shù)目固定，難以確保高熱度文件的訪問效率[4]。動態(tài)管理根據(jù)資源環(huán)境的動態(tài)變化動態(tài)調(diào)整副本的數(shù)目，可提升文件訪問效率和存儲空間利用率[5]。

文獻(xiàn)[6]針對靜態(tài)副本策略的缺點(diǎn)，提出基于灰色模型的預(yù)測模型，根據(jù)文件最近的訪問特征預(yù)測數(shù)據(jù)未來訪問熱度。文獻(xiàn)[7,8]依據(jù)時間局部性原理，最近訪問的文件短時間內(nèi)會被再次訪問。文獻(xiàn)[9,10]采用組合預(yù)測模型應(yīng)對單一預(yù)測模型的局限性。文獻(xiàn)[11]神經(jīng)網(wǎng)絡(luò)模型在建立過程中需要設(shè)置準(zhǔn)確的層次和大量的樣本空間進(jìn)行訓(xùn)練，文件熱度預(yù)測效率低。文獻(xiàn)[12]采用了灰色馬爾可夫模型，利用C均值聚類法分析儀器設(shè)備信號數(shù)據(jù)頻譜輪廓峰值幅值序列殘差狀態(tài)，對殘差預(yù)測值進(jìn)行修正，但效果不是很好。

綜上，目前已有的文件熱度預(yù)測方法都存在一些缺點(diǎn)，本文采用布谷鳥搜索(cuckoo search，CS)優(yōu)化的馬爾可夫模型修正無偏灰色預(yù)測文件熱度，消除灰色預(yù)測的固有偏差，提高預(yù)測精度。此方法首先采集文件歷史訪問熱度，通過優(yōu)化算法利用新陳代謝思想，對文件熱度序列進(jìn)行預(yù)測更新，利用最新的熱度數(shù)據(jù)對未來熱度進(jìn)行預(yù)測。

1 CS無偏灰色馬爾可夫模型理論

1.1 灰色預(yù)測模型

灰色模型主要用于具有不確定因素的灰色系統(tǒng)進(jìn)行預(yù)測。其優(yōu)點(diǎn)是可以利用少量不完整信息，通過建立數(shù)學(xué)模型并對數(shù)據(jù)未來的發(fā)展趨勢做出預(yù)測的一種模型?；疑A(yù)測模型定義請參見文獻(xiàn)[13]。本文采用灰色預(yù)測模型應(yīng)用于文件熱度預(yù)測，將文件歷史訪問熱度作為預(yù)測數(shù)據(jù)序列，通過對預(yù)測序列進(jìn)行簡單變換，從中尋找數(shù)據(jù)變動規(guī)律并對文件未來的熱度發(fā)展趨勢進(jìn)行預(yù)測。

1.2 馬爾可夫模型

馬爾可夫模型根據(jù)在不同狀態(tài)之間轉(zhuǎn)移的概率對未來的發(fā)展趨勢進(jìn)行預(yù)測。系統(tǒng)在狀態(tài)轉(zhuǎn)換過程中第n次轉(zhuǎn)換后的狀態(tài)決定于前一次(第n-1次)結(jié)果狀態(tài)。馬科夫模型定義請參見文獻(xiàn)[14]。本文關(guān)于文件熱度預(yù)測，因用戶訪問的隨機(jī)性和數(shù)據(jù)熱度變化的突發(fā)性是兩個不可避免的因素，導(dǎo)致灰色預(yù)測可能會產(chǎn)生較大的誤差，故采用馬爾可夫模型預(yù)測未來一段時間內(nèi)文件訪問量所在的狀態(tài)區(qū)間，對文件熱度預(yù)測偏差進(jìn)行修正，提升模型預(yù)測準(zhǔn)確性。

1.3 布谷鳥搜索算法

布谷鳥搜索(CS)算法最早由楊新社和S.戴布提出，是一種自然啟發(fā)式算法。具有收斂速度快、效率高、調(diào)節(jié)參數(shù)少等優(yōu)點(diǎn)[15,16]。該方法基于布谷鳥的寄生性育雛和Lévy飛行。

這個算法的靈感來自布谷鳥的寄生繁殖行為。在自然界中，布谷鳥在寄主鳥的巢中產(chǎn)卵，被識破后破壞或干脆放棄巢。為了降低蛋被破壞或遺棄的可能性，一些布谷鳥模仿寄主鳥蛋的顏色和圖案；一些布谷鳥選擇合適的時間孵化蛋，通常比寄主鳥早，拿走一些寄主鳥的蛋，以增加后代獲得更多食物的機(jī)會。尋巢過程可以看作Lévy飛行，一個Lévy飛行是一種隨機(jī)行走。

該算法的實(shí)現(xiàn)將所有的寄主巢看作是一代，每個巢穴都攜帶鳥蛋作為解決方案。目標(biāo)就是通過不斷地迭代尋找潛在的最優(yōu)解來取代現(xiàn)有的方案。本文用到的是對多目標(biāo)優(yōu)化的布谷鳥搜索算法?；谝韵?個準(zhǔn)則：

(1)每只布谷鳥一次產(chǎn)下k枚蛋(代表k個目標(biāo)的解決方案)，將它們放在隨機(jī)選擇的某個寄主巢穴中；

(2)每一代中有高質(zhì)量蛋(解決方案)的最佳巢穴被帶到下一代；

(3)可用的寄主巢數(shù)量是固定的，寄主發(fā)現(xiàn)布谷鳥放的蛋概率為pa∈(0,1)。 發(fā)現(xiàn)后，寄主可以消滅該蛋或放棄舊巢另建新巢。

本文運(yùn)用CS搜索算法對馬爾可夫狀態(tài)區(qū)間與實(shí)際值和預(yù)測值之間的關(guān)系進(jìn)行發(fā)掘，尋找該區(qū)間最合適的值對預(yù)測值進(jìn)行修正。

2 CS動態(tài)無偏灰色馬爾可夫模型建模

灰色馬爾可夫模型在針對小樣本和指數(shù)分布樣本數(shù)據(jù)預(yù)測方面應(yīng)用廣泛，但是該模型仍然存在不足。本章主要從灰色模型參數(shù)、馬爾可夫修正值計(jì)算、預(yù)測數(shù)據(jù)序列更新3個方面對該模型進(jìn)行優(yōu)化并對該模型進(jìn)行建模。

2.1 無偏灰色預(yù)測

本文利用無偏灰色預(yù)測模型對文件訪問量序列進(jìn)行處理并預(yù)測未來文件熱度。該模型通過對灰色發(fā)展系數(shù)a和灰作用量u的優(yōu)化，解決了灰色預(yù)測固有偏差，達(dá)到減小預(yù)測誤差的目的。借助灰色模型的灰色發(fā)展系數(shù)a和灰作用量u確定無偏灰色預(yù)測模型的原始數(shù)據(jù)序列擬合模型，對文件未來熱度進(jìn)行預(yù)測。

無偏灰色模型的原始數(shù)據(jù)序列為某文件在前m個相等時間段內(nèi)的文件訪問量。建模過程如下：

(2)對該文件歷史訪問量序列進(jìn)行累加處理：累加序列的首個數(shù)據(jù)直接獲取原始序列的第一個數(shù)據(jù)，從第二個數(shù)據(jù)開始將原始序列的第n個數(shù)據(jù)與第n+1個數(shù)據(jù)相加作為新序列的第n個數(shù)據(jù)。根據(jù)式(1)得到累加序列

(1)

(3)準(zhǔn)指數(shù)檢驗(yàn)與光滑性檢驗(yàn)

準(zhǔn)指數(shù)檢驗(yàn)，級比表示見式(2)

(2)

光滑性檢驗(yàn)，時間序列光滑比表示見式(3)

(3)

(4)累加序列的變化趨勢我們可以近似使用式(4)白化微分方程來描述

(4)

該微分方程中參數(shù)a和u為待識別常量，其中a稱為發(fā)展系數(shù)，u為灰作用量。

(5)模型求解：采用最小二乘法求待識別常量的估計(jì)值。

(5)

模型表示見式(6)

(6)

(6)求解白化微分方程，得到無偏灰色預(yù)測的離散時間響應(yīng)函數(shù)，見式(7)

(7)

(7)基于灰色模型中參數(shù)估計(jì)值a、u得到無偏灰色預(yù)測模型中的參數(shù)b、A，消除固有偏差，見式(8)

(8)

(8)無偏灰色預(yù)測模型的原始數(shù)據(jù)的擬合模型見式(9)

(9)

通過對灰色預(yù)測模型參數(shù)的更新，無偏灰色預(yù)測模型無需在進(jìn)行預(yù)測數(shù)據(jù)累減還原，簡化了建模步驟同時還提升了系統(tǒng)的運(yùn)算效率。

2.2 CS優(yōu)化的馬爾可夫?qū)︻A(yù)測值修正

在馬爾可夫模型中，選取灰色預(yù)測值所處狀態(tài)區(qū)間的中心值對其進(jìn)行誤差修正。但僅考慮狀態(tài)區(qū)間的中心值可能會忽略其它誤差分布信息的影響，狀態(tài)區(qū)間的中心值并不能適當(dāng)代表誤差狀態(tài)。因此，為馬爾可夫模型對灰色預(yù)測值進(jìn)行更加準(zhǔn)確地修正，本文借助布谷鳥搜索算法更深入地挖掘狀態(tài)區(qū)間信息，以識別更具代表性的修正值，而不是狀態(tài)區(qū)間的中心值。CS優(yōu)化馬爾可夫模型具體建模過程如下。

2.2.1 馬爾可夫模型

馬爾可夫模型見式(10)所示

X(m)=X(t)P(m-t),t=1,2,3,…,m-1

(10)

其中，狀態(tài)X(m)為初始狀態(tài)概率向量X(t)經(jīng)過(m-t)個時刻之后的狀態(tài)概率向量，向量P為一步狀態(tài)轉(zhuǎn)移概率矩陣。

2.2.2 狀態(tài)區(qū)間劃分

本文由相對精度來確定狀態(tài)區(qū)間的劃分，相對精度為實(shí)際值和預(yù)測值差值，即殘差。每個數(shù)據(jù)根據(jù)自己的相對精度區(qū)分所處狀態(tài)。為了適應(yīng)不同數(shù)據(jù)序列預(yù)測，首尾狀態(tài)的區(qū)間的邊界值選取相對精度的最值。狀態(tài)個數(shù)一般取3個～5個，將目標(biāo)區(qū)間等分。

2.2.3 狀態(tài)轉(zhuǎn)移概率矩陣構(gòu)造

這里采用頻率近似等于概率的思想，利用式(11)計(jì)算狀態(tài)轉(zhuǎn)移概率

(11)

假設(shè)劃分了n個狀態(tài)區(qū)間，nij(k) 表示熱度預(yù)測值所在狀態(tài)區(qū)間Ei經(jīng)k步轉(zhuǎn)移到狀態(tài)區(qū)間Ej的次數(shù)，ni為所在狀態(tài)區(qū)間Ei的數(shù)據(jù)個數(shù)。按照上述方法計(jì)算即可得到k步狀態(tài)轉(zhuǎn)移概率矩陣，如式(12)所示

(12)

2.2.4 CS優(yōu)化馬爾可夫修正值

假設(shè)狀態(tài)區(qū)間i為 [ai,bi]， 經(jīng)布谷鳥搜索算法優(yōu)化后的修正值計(jì)算見式(13)

vi=αiai+(1-αi)bi,i=1,2,…,n

(13)

本小節(jié)優(yōu)化的目標(biāo)就是對每個狀態(tài)區(qū)間尋找合適的馬爾可夫修正值，前提就是尋找到每個區(qū)間的參數(shù)α。當(dāng)α=0.5時，修正值就是狀態(tài)區(qū)間中心值。下文介紹布谷鳥搜索算法尋找狀態(tài)區(qū)間決策系數(shù)α=(α1,α2,…,αn)。

(1)布谷鳥搜索區(qū)間決策系數(shù)

CS搜索方式是基于Lévy飛行的直接搜索和基于宿主鳥在巢中發(fā)現(xiàn)外來蛋的概率的隨機(jī)搜索。

如下方法實(shí)現(xiàn)局部隨機(jī)搜索，計(jì)算方式見式(14)

(14)

本文借助Lévy飛行實(shí)現(xiàn)全局隨機(jī)搜索，由于方向的選擇是隨機(jī)的，各方向的概率都是一樣的，服從均勻分布。還要確定需要搜索范圍，Lévy分布要求大概率落在值比較小的地方，于是借助Mantegna算法可以近似滿足這樣的情況，具體建模過程見式(15)、式(16)、式(17)

(15)

(16)

(17)

(2)迭代過程中最優(yōu)方案判定

(18)

(3)修正值計(jì)算

由第一步搜索出的最優(yōu)決策區(qū)間系數(shù)α=(α1,α2,…,αn)， 計(jì)算每個狀態(tài)區(qū)間的修正值。根據(jù)式(13)，得到修正值v1,v2,…,vn

(19)

2.2.5 馬爾可夫?qū)︻A(yù)測值修正

通過k步狀態(tài)轉(zhuǎn)移概率矩陣和當(dāng)前數(shù)據(jù)所處狀態(tài)Ei及其初始向量X(0)， 可以對下一時刻預(yù)測值所處狀態(tài)進(jìn)行預(yù)測。假設(shè)max(Pij)=Pik， 則認(rèn)為下一時刻數(shù)據(jù)最有可能由狀態(tài)Ei轉(zhuǎn)向Ek。

本文根據(jù)相對精度劃分每個狀態(tài)區(qū)間，根據(jù)此相對精度來對無偏灰色預(yù)測對預(yù)測值進(jìn)行修正，減小誤差，增加預(yù)測的準(zhǔn)確度，如式(20)所示

(20)

2.3 數(shù)據(jù)更新

數(shù)據(jù)更新是對灰色預(yù)測模型的預(yù)測序列進(jìn)行優(yōu)化。本文采用的是基于灰色預(yù)測模型對文件熱度進(jìn)行預(yù)測，該模型特點(diǎn)就是針對小樣本對數(shù)據(jù)預(yù)測。數(shù)據(jù)訪問有時間局部性特征，當(dāng)前被頻繁訪問的文件在未來的一定段時間內(nèi)存在較高的概率會被再次訪問，因此較舊的數(shù)據(jù)不能很好地反映當(dāng)前的趨勢變化。

分布式系統(tǒng)中的文件每時每刻都在被訪問，隨時會產(chǎn)生最新的文件訪問量數(shù)據(jù)。為了能夠更加準(zhǔn)確地利用歷史熱度對未來的文件熱度進(jìn)行預(yù)測，根據(jù)文獻(xiàn)[8]新數(shù)據(jù)權(quán)重高的思想，采用新陳代謝思想對原始數(shù)據(jù)序列進(jìn)行等維處理。更新數(shù)據(jù)序列時，將最新的文件熱度加入原始序列中，剔除陳舊的熱度數(shù)據(jù)，如式(21)。根據(jù)文件統(tǒng)計(jì)周期循環(huán)以上操作，即可更新文件熱度預(yù)測序列。這樣能更好地反映文件最近熱度的變化趨勢，更準(zhǔn)確地預(yù)測文件未來熱度

(21)

3 實(shí)驗(yàn)與結(jié)果分析

3.1 原始數(shù)據(jù)及預(yù)處理

為達(dá)到真實(shí)模擬用戶對文件訪問量的變化，本文數(shù)據(jù)來源于某社交通訊軟件實(shí)時數(shù)據(jù)，如表1所示。表中數(shù)據(jù)是每隔10 min收集一次用戶對某文件的訪問量(文件熱度)，以此作為處理前的原始數(shù)據(jù)序列。以此數(shù)據(jù)序列來驗(yàn)證幾種預(yù)測模型的擬合效果，做出分析比對。

表1 某社交通訊平臺用戶對熱點(diǎn)新聞實(shí)時訪問量

首先對原數(shù)列進(jìn)行累加得到新的數(shù)列，對新數(shù)列進(jìn)行光滑和指數(shù)規(guī)律檢測。通過式(2)、式(3)以及檢驗(yàn)標(biāo)準(zhǔn)，驗(yàn)證該累加序列為光滑序列，并且具有指數(shù)規(guī)律，可以采用灰色模型對未來數(shù)據(jù)進(jìn)行預(yù)測。

3.2 實(shí)驗(yàn)設(shè)置及實(shí)驗(yàn)評價

3.2.1 實(shí)驗(yàn)參數(shù)設(shè)置

經(jīng)過多次實(shí)驗(yàn)對CS算法的參數(shù)進(jìn)行調(diào)整，最終確定綜合考慮算法效率和準(zhǔn)確度對參數(shù)進(jìn)行了設(shè)定。見表2。

表2 CS算法各項(xiàng)參數(shù)設(shè)置

3.2.2 實(shí)驗(yàn)相關(guān)評價

本文對預(yù)測模型的擬合程度評價指標(biāo)為相對誤差絕對值的平均值(MAPE)，如式(18)所示。根據(jù)MAPE既可以判定模型預(yù)測效果是否良好，又可以作為模型之間效果比較的參考。

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

3.3.1 狀態(tài)區(qū)間劃分

根據(jù)灰色模型和馬爾可夫模型基本原理，代碼實(shí)現(xiàn)相關(guān)功能，并對數(shù)據(jù)進(jìn)行了處理。實(shí)現(xiàn)了幾種模型依據(jù)原始數(shù)據(jù)序列對未來文件訪問量的預(yù)測。其中灰色預(yù)測模型發(fā)展系數(shù)a=0.0061，灰作用量u=385.1279。無偏灰色預(yù)測模型參數(shù)b=-0.0061，A=383.9498。根據(jù)各模型對原始數(shù)據(jù)序列的預(yù)測擬合結(jié)果，通過計(jì)算殘差我們?nèi)埐畹膬蓚€最值作為狀態(tài)區(qū)間的邊界，并將其等分為3個區(qū)間，對應(yīng)E1，E2，E3這3個狀態(tài)。此處的狀態(tài)個數(shù)與CS算法參數(shù)宿巢容量數(shù)值相同。如表3、表4分別給出了狀態(tài)區(qū)間的具體劃分和無偏灰色馬爾可夫模型的殘差。

表3 馬爾可夫修正狀態(tài)區(qū)間劃分

表4 無偏灰色模型預(yù)測值與實(shí)際值的殘差和具體狀態(tài)

根據(jù)表4數(shù)據(jù)顯示每個數(shù)據(jù)所處狀態(tài)，在這里給出一步狀態(tài)轉(zhuǎn)移概率矩陣。狀態(tài)轉(zhuǎn)移概率矩陣用于對未來訪問量的預(yù)測，以提前應(yīng)對文件訪問量突增，及時對文件副本進(jìn)行動態(tài)調(diào)整

3.3.2 馬爾可夫修正值

默認(rèn)的馬爾可夫修正值為區(qū)間中值，狀態(tài)區(qū)間的中心值并不能適當(dāng)代表誤差狀態(tài)。借助布谷鳥搜索算法更深入地挖掘狀態(tài)區(qū)間信息，以識別更具代表性的修正值。經(jīng)過布谷鳥算法優(yōu)化的修正值由式(19)計(jì)算。

通過CS算法迭代尋優(yōu)，當(dāng)?shù)螖?shù)為100次的時候已經(jīng)可以顯示出預(yù)期效果。綜合考慮實(shí)驗(yàn)準(zhǔn)確性和計(jì)算效率，本文將迭代200次，得到α=(α1,α2,α3)=(0.9883,0.4183,0.4889)， 得到優(yōu)化馬爾可夫修正值。v=(-84.81，-4.56,42.93)。 這里有一點(diǎn)需要注意的是得到的馬爾可夫修正值僅適合該預(yù)測序列的預(yù)測值殘差修正。當(dāng)預(yù)測序列經(jīng)過新陳代謝思想更新后，還需要再次預(yù)測α最優(yōu)解，才能達(dá)到優(yōu)化預(yù)測殘差的最優(yōu)效果。

3.3.3 CS優(yōu)化的無偏灰色預(yù)測模型分析

表5展示了本文預(yù)測修正模型與默認(rèn)情況下的擬合效果對比，以此評判該預(yù)測模型的優(yōu)化效果。殘差由實(shí)際值減去擬合值得到。相對殘差為殘差絕對值與實(shí)際值的比值，最后采用MAPE對3種模型擬合度進(jìn)行評測。

表5 3種灰色預(yù)測模型修正后擬合效果對比

如圖1所示，給出了灰色模型(grey model)、無偏灰色模型(unbiased grey model)、灰色馬爾可夫模型(grey Markov)、無偏灰色馬爾可夫模型(unbiased grey Markov)、CS無偏灰色馬爾可夫模型(CS unbiased grey Markov)與實(shí)際值之間的擬合效果。其中1個～8個周期是擬合值，第9個周期是預(yù)測值。

圖1 5種灰色模型擬合效果對比

實(shí)驗(yàn)結(jié)果表明，灰色馬爾可夫模型和無偏灰色馬爾可夫模型的MAPE都在4.4%左右，說明馬爾可夫修正模型對縮小灰色模型的誤差有很好的效果。而經(jīng)過CS算法優(yōu)化后的馬爾可夫模型對誤差的修正又有所提升，MAPE僅為3.08%。

為了進(jìn)一步說明CS無偏灰色馬爾可夫模型在小樣本預(yù)測情景下，能夠有效的對下一時刻數(shù)據(jù)進(jìn)行快速、準(zhǔn)確的實(shí)時預(yù)測。我們采用同一組的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，對未來的幾個時刻訪問量進(jìn)行預(yù)測，將其與BP神經(jīng)網(wǎng)絡(luò)和文獻(xiàn)[17]中灰色神經(jīng)網(wǎng)絡(luò)模型進(jìn)行對比，以MAPE作評價指標(biāo)。

實(shí)驗(yàn)將本文方法與幾種常見預(yù)測方法通過預(yù)測值的MAPE進(jìn)行比較，預(yù)測值擬合程度如表6所示。得出結(jié)論：灰色模型和無偏灰色模型在預(yù)測準(zhǔn)確性方面幾乎相同，但是無偏灰色預(yù)測模型預(yù)測結(jié)果就是預(yù)測值，無需進(jìn)行累減操作，計(jì)算效率會略高。CS無偏灰色馬爾可夫模型在小樣本的情景下，MAPE要小于其它模型，比其它幾種模型MAPE平均值降低了2.26%。對數(shù)據(jù)預(yù)測準(zhǔn)確度更高。說明該模型可以更好地利用少量數(shù)據(jù)預(yù)測短期內(nèi)未來時刻的數(shù)據(jù)變化，對提前應(yīng)對未來環(huán)境變化，采取相應(yīng)措施提供有力依據(jù)。

表6 幾種模型的預(yù)測結(jié)果擬合度匯總/%

4 結(jié)束語

本文采用CS優(yōu)化的馬爾可夫模型修正無偏灰色模型預(yù)測值，采用新陳代謝思想更新數(shù)據(jù)，使預(yù)測序列保持最新文件熱度值，對預(yù)測文件下一時刻熱度起到重要作用。馬爾可夫模型修正可以有效降低灰色預(yù)測模型因數(shù)據(jù)波動而產(chǎn)生的誤差，提高了預(yù)測數(shù)據(jù)的準(zhǔn)確度，經(jīng)過CS優(yōu)化的馬爾可夫模型可以更好縮小誤差值。通過與幾種預(yù)測模型對比，CS優(yōu)化的灰色馬爾可夫模型平均相對殘差最小，說明該模型在數(shù)據(jù)量少的情況下，能夠?qū)ξ募岫阮A(yù)測達(dá)到較好效果。接下來的研究會根據(jù)文件熱度進(jìn)行副本個數(shù)的調(diào)整，降低熱點(diǎn)文件訪問沖突和執(zhí)行時間，提升系統(tǒng)效率和資源利用率。