基于改進(jìn)R/S估計(jì)算法的網(wǎng)絡(luò)流量長相關(guān)性分析

榮紅佳，盛虎，閆秋婷

(大連交通大學(xué) 電氣信息工程學(xué)院，遼寧 大連 116028)*

水文專家H.E.Hurst經(jīng)過長期研究發(fā)現(xiàn)水文數(shù)據(jù)存在長相關(guān)性(長記憶性)，即某一階段河流流量的數(shù)據(jù)變化將對以后很長時(shí)間的流量數(shù)據(jù)產(chǎn)生影響.而在此之前的水文數(shù)據(jù)研究都忽略了水文數(shù)據(jù)長相關(guān)性的存在，從而導(dǎo)致數(shù)據(jù)模型和流量預(yù)測數(shù)據(jù)不準(zhǔn)確[1-2].為了紀(jì)念Hurst的發(fā)現(xiàn)，使用Hurst指數(shù)來描述一個(gè)時(shí)間序列的長相關(guān)性.H.E.Hurst 1951年提出傳統(tǒng)R/S估計(jì)算法對Hurst指數(shù)進(jìn)行估計(jì)，為隨機(jī)信號的長相關(guān)特性分析奠定了基礎(chǔ).Hurst指數(shù)估計(jì)在股票趨勢分析、網(wǎng)絡(luò)流量預(yù)警、交通調(diào)度、反恐戰(zhàn)備等領(lǐng)域中起著至關(guān)重要的作用.而如今大數(shù)據(jù)時(shí)代的來臨，帶來了海量的數(shù)據(jù)資源，更是為Hurst指數(shù)的研究帶來重大的支持.

Hurst指數(shù)計(jì)算的準(zhǔn)確度直接影響著系統(tǒng)模型和預(yù)測的準(zhǔn)確度，為了提升R/S估計(jì)算法的準(zhǔn)確性，學(xué)者們提出了不同類型的R/S改進(jìn)算法，對算法性能進(jìn)行了評價(jià).Mandelbrot B.B.和 Wallis J.R.給出重標(biāo)極差R/S估計(jì)算法魯棒性分析[3]；Lo,Andrew W給出一種改進(jìn)型R/S估計(jì)算法，將長相關(guān)分析推廣到非高斯信號分析[4]；Giraitis L和Kokoszka P等人于2003年給出一種基于V/S統(tǒng)計(jì)量的重標(biāo)度方差估計(jì)算法，并分析了算法的可靠性[5].

本文針在對比分析以上研究成果的基礎(chǔ)上，對傳統(tǒng)R/S估計(jì)算法中的重新標(biāo)度方法進(jìn)行改進(jìn)和優(yōu)化，給出一種基于序列長度公約數(shù)的改進(jìn)R/S估計(jì)算法，一定程度上提升了算法準(zhǔn)確度和計(jì)算速度.此外，將算法應(yīng)用于真實(shí)的網(wǎng)絡(luò)流量數(shù)據(jù)長相關(guān)特性分析，得到了較好的分析結(jié)果.

1 Hurst指數(shù)和傳統(tǒng)估計(jì)算法及相關(guān)對比估計(jì)算法介紹

Hurst指數(shù)用于測量隨機(jī)序列的長相關(guān)或長記憶特性，當(dāng)H=0.5時(shí)，時(shí)間序列就是標(biāo)準(zhǔn)的隨機(jī)游走，可以認(rèn)為現(xiàn)在時(shí)刻對未來不會(huì)產(chǎn)生影響，時(shí)間序列是沒有記憶性的[6].當(dāng)0.5

傳統(tǒng)R/S估計(jì)算法提供了一個(gè)標(biāo)準(zhǔn)化的時(shí)間序列統(tǒng)計(jì)方法，用于揭示隨機(jī)過程中的長期相關(guān)性.傳統(tǒng)R/S估計(jì)算法是目前為止最常用的Hurst指數(shù)估計(jì)方法之一，基本思路是研究不同時(shí)間尺度條件下時(shí)間序列的變化，分為不相關(guān)的時(shí)間序列和相關(guān)的時(shí)間序列，研究整體與局部之間自相似性客觀存在的統(tǒng)計(jì)特性.傳統(tǒng)R/S估計(jì)算法首先將數(shù)據(jù)分成長度相等且互不重疊的子序列并計(jì)算子序列的均值和離差[8-10]，進(jìn)一步計(jì)算極差和標(biāo)準(zhǔn)差得到RS值的標(biāo)準(zhǔn)差，估計(jì)得到Hurst指數(shù).

具體的，針對長度為n的時(shí)間序列x1,x2,…,xn，傳統(tǒng)R/S估計(jì)算法的基本步驟如下：首先對序列進(jìn)行重新標(biāo)度，重新標(biāo)度的參考值集合dn={1,2,…,n}，即將序列按照集合d中的取值分為n組子序列，每個(gè)子序列的長度滿足：

(1)

然后再對以上每個(gè)子序列進(jìn)行特定的運(yùn)算，最后得出Hurst指數(shù)的值.從式1中可知，傳統(tǒng)的重新標(biāo)度方法中參考值的合集取到了從1～n的所有值，或者間隔某一定數(shù)量進(jìn)行取值，兩種方法都未對信息進(jìn)行刻意篩選，前者導(dǎo)致計(jì)算量過大，從而計(jì)算效率低，后者幾乎必然會(huì)導(dǎo)致信息的丟失，從而導(dǎo)致計(jì)算出現(xiàn)偏差.

殘差方差估計(jì)算法針對長度為n的時(shí)間序列x1,x2,…,xn，將序列分成大小為m的子塊，其中每個(gè)子塊的部分和為Y(t)，最小均方線為a+bt，然后計(jì)算其余數(shù)的樣本方差：

(2)

該方差正比于m2H，利用log-log圖進(jìn)行最小二乘擬合，得到擬合直線的斜率為2H，進(jìn)而可以得到Hurst指數(shù)的估計(jì)值H.

Higuchi估計(jì)算法對長度為n的時(shí)間序列x1,x2,…,xn，重新構(gòu)造成一組新的數(shù)據(jù)：

(3)

式中,m，k為整數(shù)，分別為初始時(shí)間和間隔時(shí)間.設(shè)定時(shí)間間隔為k，則可以構(gòu)造出k組新的序列.Higuchi法的計(jì)算公式如下：

(4)

如果給定的序列具有長相關(guān)性，那么滿足E(Lm(k))∝CmH-2.利用log-log圖進(jìn)行最小二乘擬合，得到擬合直線的斜率為H-2，由此可以得到Hurst指數(shù)的估計(jì)值H.

所以，傳統(tǒng)R/S估計(jì)算法中重新標(biāo)度過程對計(jì)算量和準(zhǔn)確度影響極大.本文就傳統(tǒng)R/S估計(jì)算法中重新標(biāo)度過程提出改進(jìn)，在提升計(jì)算效率和準(zhǔn)確度方面具有實(shí)際的意義.

2 基于序列長度公約數(shù)的改進(jìn)R/S估計(jì)算法

對傳統(tǒng)R/S估計(jì)算法進(jìn)行改進(jìn)，首先對時(shí)間序列進(jìn)行重新標(biāo)度，重新標(biāo)度的合理性直接影響其計(jì)算自相似序列Hurst指數(shù)的準(zhǔn)確度，算法在重新標(biāo)度的過程中，第一要考慮信息的完整性，當(dāng)序列的長度與份數(shù)不能整除時(shí)，會(huì)有一部分信息丟失，從而造成計(jì)算出現(xiàn)偏差；第二要考慮計(jì)算的效率，例如將序列完全離散化或者直接使用整個(gè)序列進(jìn)行計(jì)算，導(dǎo)致包含的信息量過大而沒有計(jì)算意義.

考慮到以上兩點(diǎn)，本文給出了一種基于序列長度公約數(shù)的重新標(biāo)度方法，在1～n的分組策略中，利用公約數(shù)可以被整除的特性，挑選出了基于序列長度公約數(shù)的集合，既保證了計(jì)算時(shí)不會(huì)出現(xiàn)信息丟失，保證了估算的準(zhǔn)確度，由于避免了一些沒有意義的計(jì)算，也一定程度上提高了計(jì)算的效率，節(jié)省了計(jì)算的時(shí)間.針對長度為n的時(shí)間序列x1,x2,…,xn，算法的基本步驟如下：

(1)找到一個(gè)略小于序列長度的參考值n′，其滿足n′=μn，μ為一個(gè)非常接近1的數(shù)，例如μ=0.99，這樣可以保證在重新標(biāo)度時(shí)，不會(huì)取到整個(gè)序列.

(2)找到參考值n′公約數(shù)的集合d={d1,d2,…,dk}，

(5)

其中，i為整數(shù)，由于d為公約數(shù)的集合.同時(shí)d1,d2,…，dk大小依次遞增，即公約數(shù)從小到大進(jìn)行排列，為了保證序列在重新標(biāo)度時(shí)，每個(gè)子序列的長度不至于太小，所以d1大于dmin，dmin是一個(gè)大小合適的數(shù)，例如取dmin=50.

(3)對序列進(jìn)行重新標(biāo)度，將序列分為k組子序列，其每個(gè)子序列的長度滿足

(6)

其中，dk取自序列長度公約數(shù)的集合.得到子序列

(7)

(4)計(jì)算子序列的均值:

j=1,2,…,Ni

(8)

(5)計(jì)算子序列的離差:

j=1,2,…,Ni

(9)

(6)計(jì)算累積離差:

i=1,2,…,k，j=1,2,…,Ni

(10)

(7)計(jì)算極差:

Ri=max(zij)-min(zij),

i=1,2,…,k，j=1,2,…,Ni

(11)

(8)計(jì)算標(biāo)準(zhǔn)差:

i=1,2,…,k，j=1,2,…,Ni

(12)

(9)計(jì)算RS值:

(13)

(10)將計(jì)算出的各子序列的RS值求平均:

(14)

并計(jì)算其標(biāo)準(zhǔn)差:

(15)

3 基于序列長度公約數(shù)的改進(jìn)R/S估計(jì)算法仿真分析

為了分析基于序列長度公約數(shù)的改進(jìn)R/S估計(jì)算法的準(zhǔn)確性和計(jì)算速度，首先采用功率譜快速傅里葉變換方法合成分?jǐn)?shù)階高斯噪聲(FGN：Fractional Gaussian Noise).該合成方法的原理是利用譜合成法構(gòu)造一定參數(shù)的分?jǐn)?shù)階布朗運(yùn)動(dòng)的功率譜密度函數(shù)，對功率譜密度函數(shù)進(jìn)行傅里葉逆變換得到分?jǐn)?shù)階布朗運(yùn)動(dòng)隨機(jī)序列，經(jīng)過一階差分便可得到FGN隨機(jī)序列[11-12].再設(shè)定合適的H參數(shù)就可以進(jìn)行FGN的仿真過程.仿真合成Hurst指數(shù)分別為0.85、0.8和0.75的長度為30 000的FGN序列，圖1給出了H=0.75的FGN序列.

圖1 H=0.75的FGN序列

使用改進(jìn)后的R/S估計(jì)算法，對相應(yīng)H值的FGN序列擬合后的結(jié)果如圖2所示.其中，星形折線為應(yīng)用改進(jìn)后R/S估計(jì)算法計(jì)算的Hurst值，實(shí)線為傳統(tǒng)R/S估計(jì)算法擬合值，三角折線為Hurst指數(shù)為0.75的真實(shí)值，點(diǎn)劃線為多項(xiàng)式擬合后的Hurst指數(shù)估計(jì)值，代表了Hurst指數(shù)的趨勢.

圖2給出了改進(jìn)R/S估計(jì)算法和傳統(tǒng)R/S估計(jì)算法計(jì)算H=0.75的FGN序列的對比圖，圖3將圖2中局部區(qū)域進(jìn)行放大，并對直線斜率值進(jìn)行了標(biāo)注，對比上圖中直線的斜率，可以看出點(diǎn)劃線代表的改進(jìn)R/S估計(jì)算法的斜率值更接近三角折線代表的真實(shí)值斜率，計(jì)算誤差也較傳統(tǒng)R/S估計(jì)算法小，當(dāng)計(jì)算H=0.8和0.85時(shí)的FGN序列也可以得出同樣的結(jié)論.

圖2 改進(jìn)R/S估計(jì)算法對H=0.75FGN序列的擬合

圖3 改進(jìn)R/S估計(jì)算法對H=0.75FGN序列的擬合局部放大圖

表1 本文方法傳統(tǒng)Hurst估計(jì)算法準(zhǔn)確度和計(jì)算速度對比

針對長度為30000Hurst指數(shù)分別為0.75、0.8和0.85的FGN序列，采用傳統(tǒng)R/S估計(jì)算法、改進(jìn)R/S估計(jì)算法、殘差方差估計(jì)算法、Higuchi估計(jì)算法進(jìn)行估計(jì)并記錄估計(jì)值和計(jì)算速度.表1給出了四種算法在Intel(R) Core(TM) i5-8250處理器，8G內(nèi)存，MATLAB2016b版本計(jì)算機(jī)運(yùn)行得到的估計(jì)值和計(jì)算耗時(shí)數(shù)據(jù)，對比數(shù)據(jù)可以看出在準(zhǔn)確度方面： 改進(jìn)R/S估計(jì)算法計(jì)相比其余三種估計(jì)算法的準(zhǔn)確度更高；在計(jì)算耗時(shí)方面：四種方法耗時(shí)從小到大分別為：Higuchi估計(jì)算法、殘差方差估計(jì)算法、改進(jìn)R/S估計(jì)算法、傳統(tǒng)R/S估計(jì)算法，改進(jìn)R/S估計(jì)算法雖然速度并不是最快，但是相比傳統(tǒng)R/S估計(jì)算法計(jì)算速度提升較大.

4 改進(jìn)R/S估計(jì)算法在網(wǎng)絡(luò)流量數(shù)據(jù)分析中的應(yīng)用

Hurst指數(shù)作為自相似性網(wǎng)絡(luò)流量的重要指標(biāo)，對網(wǎng)絡(luò)流量數(shù)據(jù)長相關(guān)特性的定量研究已成為網(wǎng)絡(luò)流量特性研究的重點(diǎn)內(nèi)容，如何快速、有效地估計(jì)Hurst指數(shù)對于網(wǎng)絡(luò)流量相關(guān)業(yè)務(wù)的應(yīng)用具有重要的意義[13-15].為了驗(yàn)證前面所介紹的基于序列長度公約數(shù)分段的改進(jìn)R/S估計(jì)算法的有效性，本文采用美國貝爾實(shí)驗(yàn)室名為BC-Oct89Ext.TL的網(wǎng)絡(luò)流量數(shù)據(jù)結(jié)合改進(jìn)R/S估計(jì)算法對自相似性網(wǎng)絡(luò)流量進(jìn)行分析和研究.從實(shí)際網(wǎng)絡(luò)流量分別獲取五段長度為30000的數(shù)據(jù)，得到五份原始樣本數(shù)據(jù)并展示其中一份數(shù)據(jù)樣本如圖4所示.

圖4 網(wǎng)絡(luò)流量樣本數(shù)據(jù)

利用改進(jìn)R/S估計(jì)算法計(jì)算五段網(wǎng)絡(luò)流量樣本數(shù)據(jù)的Hurst指數(shù)，得到的結(jié)果如表2所示.

表2 網(wǎng)絡(luò)流量樣本數(shù)據(jù)Hurst值

從表2可知，應(yīng)用改進(jìn)R/S估計(jì)算法計(jì)算的Hurst指數(shù)值介于0.5～1之間，說明網(wǎng)絡(luò)流量數(shù)據(jù)具有長期相關(guān)性，即該序列具有正的持續(xù)性，而且H值雖然在0.5～1之間但更偏向1，H值越大，說明這種正持續(xù)性越強(qiáng).并且隨著H值的增大，網(wǎng)絡(luò)流量數(shù)據(jù)具有的長相關(guān)性變強(qiáng).應(yīng)用傳統(tǒng)R/S估計(jì)算法在計(jì)算數(shù)據(jù)Ⅲ和Ⅴ的Hurst指數(shù)值時(shí)；應(yīng)用殘差方差估計(jì)算法在計(jì)算數(shù)據(jù)Ⅴ的Hurst指數(shù)值時(shí)；應(yīng)用傳統(tǒng)R/S估計(jì)算法在計(jì)算數(shù)據(jù)Ⅲ和Ⅴ的Hurst指數(shù)值時(shí)；應(yīng)用Higuchi估計(jì)算法在計(jì)算數(shù)據(jù)Ⅱ的Hurst指數(shù)值時(shí)出現(xiàn)了大于1的情況，無法刻畫網(wǎng)絡(luò)流量數(shù)據(jù)的長相關(guān)特性，計(jì)算結(jié)果沒有意義，因此就準(zhǔn)確性和有效性來說，改進(jìn)R/S估計(jì)算法計(jì)算結(jié)果更精準(zhǔn)，因此采用改進(jìn)R/S估計(jì)算法計(jì)算得出的Hurst指數(shù)值在刻畫網(wǎng)絡(luò)流量數(shù)據(jù)長相關(guān)特性方面顯得尤為重要.

5 結(jié)果分析

本文在計(jì)算準(zhǔn)確度以及計(jì)算速度方面將改進(jìn)R/S估計(jì)算法和傳統(tǒng)R/S估計(jì)算法、殘差方差估計(jì)算法、Higuchi估計(jì)算法進(jìn)行對比，從表1中可以看出，改進(jìn)R/S估計(jì)算法對H值不同的FGN序列估計(jì)結(jié)果相比傳統(tǒng)R/S估計(jì)算法的計(jì)算結(jié)果更加準(zhǔn)確，計(jì)算耗時(shí)更少，同時(shí)改進(jìn)R/S估計(jì)算法相比殘差方差估計(jì)算法、Higuchi估計(jì)算法，其計(jì)算結(jié)果也更加準(zhǔn)確.對傳統(tǒng)R/S估計(jì)算法進(jìn)行重新標(biāo)度是計(jì)算自相似序列Hurst指數(shù)的一個(gè)有力工具，消除了傳統(tǒng)R/S估計(jì)法中存在的短期依賴性，擴(kuò)大了長相關(guān)序列適用范圍.此外，通過對比H值分別為0.75、0.8、0.85時(shí)，傳統(tǒng)R/S估計(jì)算法和改進(jìn)R/S估計(jì)算法計(jì)算自相似序列Hurst指數(shù)的計(jì)算速度分別提升了9.76倍、10.25倍、10.48倍，極大的提升了計(jì)算效率.由此可見，利用公約數(shù)分段法對比傳統(tǒng)R/S估計(jì)算法中隨機(jī)分段法，由于省去了算法內(nèi)部一些無意義的計(jì)算，所以在計(jì)算速度上要上升一個(gè)檔次，在有限的時(shí)間內(nèi)運(yùn)用改進(jìn)R/S估計(jì)算法計(jì)算自相似序列的Hurst指數(shù)極大的縮短了運(yùn)算時(shí)間，提高了后續(xù)的計(jì)算效率.

表2給出了五段網(wǎng)絡(luò)流量樣本數(shù)據(jù)經(jīng)過改進(jìn)R/S估計(jì)算法和傳統(tǒng)R/S估計(jì)算法計(jì)算得出的Hurst指數(shù)值，對比了兩種方法，發(fā)現(xiàn)無論在準(zhǔn)確性還是有效性方面，改進(jìn)R/S估計(jì)算法都優(yōu)于傳統(tǒng)R/S估計(jì)算法.

6 結(jié)論

傳統(tǒng)的R/S估計(jì)算法在重新標(biāo)度方法上存在欠缺，當(dāng)序列的長度與分段數(shù)不能整除時(shí)，會(huì)有一部分信息丟失，從而造成計(jì)算出現(xiàn)偏差，而且傳統(tǒng)R/S估計(jì)算法在計(jì)算長相關(guān)序列Hurst指數(shù)時(shí)效率偏低，無法體現(xiàn)與其他方法在計(jì)算序列H值的優(yōu)勢所在.采用公約數(shù)分段法對傳統(tǒng)R/S估計(jì)算法進(jìn)行重新標(biāo)度，可以在準(zhǔn)確度和效率方面帶來明顯提升.改進(jìn)R/S估計(jì)算法在網(wǎng)絡(luò)流量數(shù)據(jù)分析結(jié)果驗(yàn)證了算法的有效性，對網(wǎng)絡(luò)流量數(shù)據(jù)長相關(guān)性分析提供了一種有效方法.