基于復(fù)雜網(wǎng)絡(luò)的時(shí)間序列轉(zhuǎn)換算法*

何茂雨，周 銀，周靜曦，沈 黎

(湖南農(nóng)業(yè)大學(xué)信息與智能科學(xué)技術(shù)學(xué)院，湖南 長(zhǎng)沙 410128)

復(fù)雜網(wǎng)絡(luò)是具有自組織、自相似、吸引子、小世界、無(wú)標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)[1].現(xiàn)實(shí)生活中，大量真實(shí)的系統(tǒng)如互聯(lián)網(wǎng)和電網(wǎng)等，都可以抽象成復(fù)雜網(wǎng)絡(luò)，所以復(fù)雜網(wǎng)絡(luò)已經(jīng)成為學(xué)術(shù)界熱門的研究領(lǐng)域.時(shí)間序列是指，將同一統(tǒng)計(jì)指標(biāo)的數(shù)值按其發(fā)生的時(shí)間先后順序排列而成的數(shù)列.時(shí)間序列存在于生產(chǎn)、生活的方方面面，如某地區(qū)的降雨量、某股票的交易情況、某物品的銷售數(shù)量等.時(shí)間序列分析就是發(fā)現(xiàn)時(shí)間序列的變化規(guī)律并用于預(yù)測(cè)的統(tǒng)計(jì)技術(shù)，常見的時(shí)間序列分析法有頻域分析、時(shí)域分析、模型分析和回歸分析等.近年出現(xiàn)很多將時(shí)間序列轉(zhuǎn)換成復(fù)雜網(wǎng)絡(luò)后，利用復(fù)雜網(wǎng)絡(luò)的特性間接分析時(shí)間序列特征的方法.例如，Lucas等[2]提出的可視圖算法，田甜等[3]提出的基于頻域復(fù)雜網(wǎng)絡(luò)分解的局部特征提取建網(wǎng)方法，李姝等[4]提出的基于隨機(jī)圖的復(fù)雜網(wǎng)絡(luò)建網(wǎng)方法.在經(jīng)典可視圖算法中，需要處理每個(gè)時(shí)間點(diǎn)對(duì)的可視情況，但是在實(shí)際情況中，絕大多數(shù)的點(diǎn)對(duì)都是互相不可視的，所以經(jīng)典算法中存在大量無(wú)意義的計(jì)算，有必要對(duì)其進(jìn)行改進(jìn).筆者擬引入最大值分裂算法和凸包發(fā)現(xiàn)算法來(lái)提升經(jīng)典可視圖算法的運(yùn)行效率.

1 經(jīng)典可視圖算法

在眾多時(shí)間序列映射成復(fù)雜網(wǎng)絡(luò)的算法中，可視圖算法是較新穎的一種.在離散的時(shí)間序列中，每個(gè)數(shù)據(jù)點(diǎn)被看作是網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)，數(shù)據(jù)點(diǎn)之間若滿足“相互可視”，則網(wǎng)絡(luò)中對(duì)應(yīng)的節(jié)點(diǎn)之間連線.對(duì)于任意2個(gè)數(shù)據(jù)點(diǎn)(ta,ya)和(tb,yb)(假定ta

經(jīng)典可視圖算法描述如下：

(ⅰ)初始化網(wǎng)絡(luò)，將時(shí)間序列中的所有數(shù)據(jù)點(diǎn)添加到網(wǎng)絡(luò)中；

(ⅱ)從時(shí)間序列第1個(gè)數(shù)據(jù)點(diǎn)i開始，定義每個(gè)數(shù)據(jù)點(diǎn)的初始斜率sl為無(wú)窮?。?/p>

(ⅲ)對(duì)于數(shù)據(jù)點(diǎn)i之后的每個(gè)數(shù)據(jù)點(diǎn)j，計(jì)算線段ij的斜率是否大于sl；

(ⅳ)若大于，則在網(wǎng)絡(luò)中添加(i，j)連邊，并將sl的值變?yōu)榫€段ij的值；

(ⅴ)重復(fù)步驟(ⅱ)～(ⅳ)，直到整個(gè)時(shí)間序列的點(diǎn)遍歷完成.

從算法中可以看出，該算法的時(shí)間復(fù)雜度為O(n2).這就意味著，時(shí)間序列的數(shù)據(jù)點(diǎn)個(gè)數(shù)較多的情況下，生成復(fù)雜網(wǎng)絡(luò)的代價(jià)是十分巨大的，因此有必要對(duì)經(jīng)典可視圖算法進(jìn)行改進(jìn)以提高效率.長(zhǎng)度為10的時(shí)間序列的轉(zhuǎn)換結(jié)果如圖1所示.

圖1 長(zhǎng)度為10的時(shí)間序列的轉(zhuǎn)換結(jié)果

2 經(jīng)典可視圖算法的改進(jìn)

2.1 最大值分裂算法

通過觀察發(fā)現(xiàn)，在時(shí)間序列中，最大值時(shí)間點(diǎn)的左邊的任意點(diǎn)都看不到其右邊的任意點(diǎn)，因此最大值的時(shí)間點(diǎn)就將時(shí)間序列恰好分裂為相互不可視的2個(gè)部分.若先求出時(shí)間序列的最大值，則其左右兩邊就是2個(gè)完全獨(dú)立的時(shí)間序列，之后再分別對(duì)這2個(gè)部分求最大值，于是時(shí)間序列被分成獨(dú)立的4個(gè)部分.這樣繼續(xù)分裂下去，直到每個(gè)小的時(shí)間序列長(zhǎng)度為1才停止分裂.具體算法描述如下：

(ⅰ)初始化網(wǎng)絡(luò)，將時(shí)間序列中的所有數(shù)據(jù)點(diǎn)添加到網(wǎng)絡(luò)中；

(ⅱ)遍歷時(shí)間序列，找到最大值，將序列分裂為2個(gè)部分；

(ⅲ)分別在2個(gè)分序列中找到最大值，將序列繼續(xù)分裂；

(ⅳ)重復(fù)上述操作，直至分裂后的序列長(zhǎng)度為1，算法終止.

圖2為最大值分裂算法的一個(gè)簡(jiǎn)單示例.

圖2 最大值分裂算法示例

在長(zhǎng)度為7的時(shí)間序列中，t4為該時(shí)間序列的最大值，那么t4左邊的時(shí)間點(diǎn)看不見右邊的時(shí)間點(diǎn)，于是序列被分裂為2個(gè)部分.接下來(lái)分析t4左邊的情況，t2為最大值，t1和t3互不可見.因分裂后的序列只有1個(gè)時(shí)間點(diǎn)，故分裂終止.然后分析t4右邊的序列，t5為最大值，因t5左邊沒有時(shí)間點(diǎn)，而右邊有2個(gè)時(shí)間點(diǎn)，繼續(xù)分析t6和t7的情況.t7為最大值，因t7左邊只有1個(gè)時(shí)間點(diǎn)，故算法終止.

2.2 凸包發(fā)現(xiàn)算法

點(diǎn)集的凸包是計(jì)算機(jī)圖形學(xué)中的術(shù)語(yǔ).在一個(gè)實(shí)數(shù)向量空間中，對(duì)于給定集合X，所有包含X的凸集的交集被稱為X的凸包.即凸包是一個(gè)最小凸多邊形，滿足點(diǎn)集中的所有點(diǎn)或者在多邊形邊上，或者在其內(nèi)部.

觀察時(shí)間序列(圖3(a))可注意到，時(shí)間序列上的分割點(diǎn)正好將其分成不可視的幾個(gè)部分.事實(shí)上，如果連接所有的分割點(diǎn)，就正好形成了時(shí)間序列頂點(diǎn)的上凸包(圖3(b)).

圖3 長(zhǎng)度為7的時(shí)間序列的分割點(diǎn)組成凸包的示例

對(duì)于求解二維坐標(biāo)下的凸包，其算法主要有窮舉法、分治法、Jarvis步進(jìn)法和Graham掃描法等，但是這些算法的時(shí)間復(fù)雜度都較大.因此，引入凸包發(fā)現(xiàn)算法[5]，該算法適用于不自交的簡(jiǎn)單多線段，是使用雙端隊(duì)列存儲(chǔ)凸包結(jié)果.

凸包發(fā)現(xiàn)算法的偽代碼如下：

輸入：n個(gè)頂點(diǎn)的簡(jiǎn)單多線段P[i]，這里為時(shí)間序列的頂點(diǎn).

空的雙端隊(duì)列D[]，隊(duì)列的首尾標(biāo)簽為b，t.

算法流程如下：

(ⅰ)將初始3個(gè)點(diǎn)P[0]，P[1]和P[2]加入隊(duì)列D[]，滿足隊(duì)列的首尾都為P[2]，并使得P[0]，P[1]和P[2]為一個(gè)逆時(shí)針的三角形.

(ⅱ)依次處理i=2以后的每一個(gè)點(diǎn)，檢查P[i]是否在D內(nèi)部：

If P[i]在D[b]D[b+1]和D[t-1]D[t]的左側(cè)，則跳過P[i]，處理下一個(gè)點(diǎn)

While P[i]在D[b]D[b+1]的右側(cè)，則從D[]中刪除D[b]

在D[]的首部插入P[i]

While P[i]在D[t-1]D[t]的右側(cè)，則從D[]中刪除D[t]

在D[]的尾部插入P[i]

輸出：雙端隊(duì)列D[]就是最后的結(jié)果.

在時(shí)間序列轉(zhuǎn)換為復(fù)雜網(wǎng)絡(luò)的過程中，首先利用凸包發(fā)現(xiàn)算法計(jì)算時(shí)間序列的凸包，其點(diǎn)集就是時(shí)間序列的分割點(diǎn)，然后分別判斷分割點(diǎn)與各個(gè)相鄰區(qū)域的可視情況，從而得到相應(yīng)的復(fù)雜網(wǎng)絡(luò).

3 實(shí)驗(yàn)部分

為了比較經(jīng)典可視圖算法(算法1)、經(jīng)最大值分裂算法改進(jìn)的可視圖算法(算法2)和經(jīng)凸包發(fā)現(xiàn)算法改進(jìn)的可視圖算法(算法3)的性能，將3個(gè)算法應(yīng)用于經(jīng)典的分形布朗運(yùn)動(dòng)時(shí)間序列中進(jìn)行觀察.分形布朗運(yùn)動(dòng)是布朗運(yùn)動(dòng)的拓展，是不規(guī)則擴(kuò)散和分形隨機(jī)行走的基礎(chǔ)，其時(shí)間序列可以利用MATLAB中的內(nèi)置函數(shù)wfbm(H，L)直接獲得，其中H為Hurst指數(shù)，L為時(shí)間序列的長(zhǎng)度.將3個(gè)算法應(yīng)用于H=0.2，0.5，0.8,L=106的分形布朗運(yùn)動(dòng)時(shí)間序列中，進(jìn)行20次實(shí)驗(yàn)后取平均結(jié)果，結(jié)果如圖4所示.

圖4 不同時(shí)間序列上3種算法的性能比較

從圖4可以看出，相對(duì)于算法1，算法2和算法3都能夠較好地縮短運(yùn)行時(shí)間，提升效率；且隨著Hurst指數(shù)的增加，算法3的優(yōu)勢(shì)更加明顯.這主要是因?yàn)?，算?是線性時(shí)間算法，其時(shí)間復(fù)雜度為O(n)，故在時(shí)間性能上表現(xiàn)更突出.

4 結(jié)語(yǔ)

時(shí)間序列轉(zhuǎn)換成復(fù)雜網(wǎng)絡(luò)是當(dāng)前復(fù)雜網(wǎng)絡(luò)研究的熱點(diǎn)問題.筆者分別引入最大值分裂算法和凸包發(fā)現(xiàn)算法對(duì)經(jīng)典可視圖算法進(jìn)行改進(jìn)，獲得了較好的實(shí)驗(yàn)結(jié)果.不足的是，仍然存在時(shí)間復(fù)雜度較高的問題，找到可以大幅降低時(shí)間復(fù)雜度的轉(zhuǎn)換算法是今后的研究方向.