基于seasonal-trend-loess方法的符號(hào)化時(shí)間序列網(wǎng)絡(luò)*

汪麗娜 成媛媛 臧臣瑞

1) (內(nèi)蒙古工業(yè)大學(xué)理學(xué)院,呼和浩特 010051)

2) (內(nèi)蒙古自治區(qū)生命數(shù)據(jù)統(tǒng)計(jì)分析理論與神經(jīng)網(wǎng)絡(luò)建模重點(diǎn)實(shí)驗(yàn)室,呼和浩特 010051)

3) (中國(guó)聯(lián)合網(wǎng)絡(luò)通信有限公司內(nèi)蒙古分公司,呼和浩特 010050)

為了有效控制海量數(shù)據(jù)時(shí)間序列網(wǎng)絡(luò)的規(guī)模并使得網(wǎng)絡(luò)更貼近實(shí)際,符號(hào)化時(shí)間序列網(wǎng)絡(luò)成為研究熱點(diǎn).結(jié)合周期性時(shí)間序列的seasonal-trend-loess方法和符號(hào)化轉(zhuǎn)化方法,本文提出一種新的符號(hào)化時(shí)間序列建網(wǎng)方法.該方法考慮了單個(gè)數(shù)據(jù)值的狀態(tài)又結(jié)合了序列的長(zhǎng)遠(yuǎn)變化趨勢(shì).以符號(hào)模式為節(jié)點(diǎn)；依時(shí)間順序推移,以節(jié)點(diǎn)間的鄰接轉(zhuǎn)換關(guān)系定義連邊；根據(jù)轉(zhuǎn)換方向和轉(zhuǎn)換頻次確定連邊的方向和權(quán)重,建立有向加權(quán)網(wǎng)絡(luò).分別以航空旅客吞吐量時(shí)間序列和因特網(wǎng)流量時(shí)間序列為實(shí)驗(yàn)數(shù)據(jù)構(gòu)建的兩個(gè)時(shí)間序列網(wǎng)絡(luò),有明顯差異的拓?fù)涮卣?；進(jìn)一步對(duì)移動(dòng)通信語(yǔ)音時(shí)間序列做了實(shí)證分析,挖掘時(shí)間序列數(shù)據(jù)的本質(zhì)規(guī)律.

1 引 言

將時(shí)間序列通過(guò)某種對(duì)應(yīng)關(guān)系映射為復(fù)雜網(wǎng)絡(luò)的思想最早由Zhang和Small提出,這一創(chuàng)造性的想法為時(shí)間序列的分析方法提供了新的研究方向和視角.2006年,Zhang和Small[1]首次由偽周期時(shí)間序列構(gòu)建了復(fù)雜網(wǎng)絡(luò).之后,時(shí)間序列網(wǎng)絡(luò)方法成為熱門的研究方向之一并被應(yīng)用到許多領(lǐng)域,如：醫(yī)學(xué)[2]、金融學(xué)[3]、交通運(yùn)輸[4,5].目前,普遍應(yīng)用的時(shí)間序列建網(wǎng)方法有：基于相空間重構(gòu)法建網(wǎng)[6,7]、基于可視圖方法建網(wǎng)[8,9]、基于遞歸法建網(wǎng)[10]和基于符號(hào)模式建網(wǎng)[11-13].

基于相空間重構(gòu)法建網(wǎng)是經(jīng)典的時(shí)間序列建網(wǎng)方法之一.Yue和Yang[6]提出基于相空間建網(wǎng)方法分析時(shí)間序列.將時(shí)間序列劃分、重構(gòu),轉(zhuǎn)化為一系列長(zhǎng)度一定的向量；然后以向量為節(jié)點(diǎn),根據(jù)向量間的Pearson相關(guān)系數(shù)確定連邊,構(gòu)建出一個(gè)無(wú)向無(wú)權(quán)網(wǎng)絡(luò).應(yīng)用該方法分析時(shí)間序列時(shí),確定向量的滯后期以及確定相關(guān)系數(shù)的閾值比較復(fù)雜.為此,一些科學(xué)家對(duì)相空間重構(gòu)建網(wǎng)方法進(jìn)行了改進(jìn).其中,Gao和Jin[7]引入偽最近鄰方法[14]估計(jì)嵌入維數(shù)和延遲時(shí)間,使得由時(shí)間序列重構(gòu)相空間變得更加精確,從而可以根據(jù)復(fù)雜網(wǎng)絡(luò)的拓?fù)涮卣鞯贸鲎罴训南嚓P(guān)系數(shù)閾值.但是,由于該方法在確定閾值時(shí)存在不確定性,導(dǎo)致建立的網(wǎng)絡(luò)的魯棒性較差.

可視圖建網(wǎng)方法[8,9]是另外一種經(jīng)典建網(wǎng)方法.該方法將時(shí)間序列柱狀圖中的每個(gè)時(shí)間序列值視為一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn),如果柱狀圖中的兩個(gè)柱體可以無(wú)障礙可視,則柱體對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn)之間連邊,從而構(gòu)建出一個(gè)無(wú)向無(wú)權(quán)網(wǎng)絡(luò).網(wǎng)絡(luò)的總節(jié)點(diǎn)數(shù)等于時(shí)間序列數(shù)據(jù)值的總個(gè)數(shù).由于可視圖建網(wǎng)方法的生成過(guò)程簡(jiǎn)便、網(wǎng)絡(luò)魯棒性較好,使得該法應(yīng)用于醫(yī)學(xué)[15]、地質(zhì)學(xué)[16]、經(jīng)濟(jì)學(xué)[17]、天文學(xué)[18]等眾多領(lǐng)域.根據(jù)類似的原理,Luque等[19]于2009年提出水平可視時(shí)間序列建網(wǎng)方法.周婷婷等[20]提出有限穿越水平可視圖時(shí)間序列建網(wǎng)方法,高忠科等[21]運(yùn)用有限穿越水平可視圖方法分析了兩相流的形成動(dòng)力學(xué).傳統(tǒng)的可視圖方法是有限穿越水平可視圖方法在可視距為1時(shí)的特殊情況.此外,高忠科等[22]還提出了多尺度有限穿越水平可視圖時(shí)間序列建網(wǎng)方法,它是水平可視圖和有限穿越水平可視圖的進(jìn)一步拓展.

遞歸網(wǎng)絡(luò)建網(wǎng)方法由Marwan等[10]提出.Subramaniyam和Hyttinen[23]應(yīng)用遞歸網(wǎng)絡(luò)建網(wǎng)方法分析了腦電圖時(shí)間序列,研究癲癇病患者的行為動(dòng)力學(xué).近幾年,基于符號(hào)模式建網(wǎng)方法成為新的研究熱點(diǎn).符號(hào)化時(shí)間序列建網(wǎng)方法考慮了節(jié)點(diǎn)之間的方向和權(quán)重,構(gòu)建的加權(quán)有向網(wǎng)絡(luò)更加貼近實(shí)際.Karimi和Darooneh[11]對(duì)平穩(wěn)時(shí)間序列做符號(hào)化轉(zhuǎn)化,將時(shí)間序列映射為網(wǎng)絡(luò),發(fā)現(xiàn)網(wǎng)絡(luò)度的組合參數(shù)對(duì)不同流型之間的過(guò)渡非常敏感,可以用來(lái)區(qū)分不同的流型.之后,曾明等[12]提出符號(hào)化模式表征建網(wǎng)方法,將原始時(shí)間序列標(biāo)準(zhǔn)化、符號(hào)化處理后,映射為一個(gè)有向加權(quán)網(wǎng)絡(luò)并分析了網(wǎng)絡(luò)的拓?fù)湫再|(zhì).符號(hào)化模式表征建網(wǎng)方法可以區(qū)分周期時(shí)間序列和混沌時(shí)間序列.此外,Zhang和Na[13]應(yīng)用符號(hào)化模式表征的建網(wǎng)方法研究了空氣質(zhì)量指數(shù)等問(wèn)題.

針對(duì)一類周期性時(shí)間序列,本文提出一種基于STL (seasonal and trend decomposition using loess,STL)方法的符號(hào)化有向加權(quán)網(wǎng)絡(luò)建網(wǎng)方法.與其他的符號(hào)化建網(wǎng)方法相比,本文提出的基于STL方法的時(shí)間序列建網(wǎng)方法以數(shù)據(jù)點(diǎn)為基元構(gòu)建網(wǎng)絡(luò),既考慮了單個(gè)數(shù)據(jù)的狀態(tài)又融合了時(shí)間序列的長(zhǎng)遠(yuǎn)變化趨勢(shì).首先,依據(jù)STL方法將時(shí)間序列轉(zhuǎn)化為三個(gè)狀態(tài)項(xiàng)：季節(jié)項(xiàng)、趨勢(shì)項(xiàng)和隨機(jī)項(xiàng)；然后,使用符號(hào)化方法對(duì)狀態(tài)值做區(qū)間劃分和符號(hào)轉(zhuǎn)化,使得每個(gè)數(shù)據(jù)值表示為由狀態(tài)符號(hào)構(gòu)成的符號(hào)模式；接著,以符號(hào)模式為節(jié)點(diǎn),依時(shí)間順序推移,把數(shù)據(jù)間的鄰接轉(zhuǎn)換關(guān)系定義為節(jié)點(diǎn)間的連邊；最后以轉(zhuǎn)換方向和轉(zhuǎn)換頻次作為連邊的方向和權(quán)重,建立有向加權(quán)網(wǎng)絡(luò).

2 基本概念

2.1 STL方法

STL方法是一種基于局部加權(quán)回歸的時(shí)間序列分析方法[24].運(yùn)用局部多項(xiàng)式回歸擬合方法,STL方法將時(shí)間序列表示為趨勢(shì)、季節(jié)和余項(xiàng)三部分.即時(shí)間序列Yn= {yi,i = 1,2,…,n }通過(guò)STL可以轉(zhuǎn)化為趨勢(shì)Tn= {ti,i = 1,2,…,n },季節(jié)Sn= {si,i = 1,2,…,n }和余項(xiàng)Rn= {ri,i =1,2,…,n }；其中n 表示時(shí)間序列長(zhǎng)度.STL方法由內(nèi)循環(huán)和外循環(huán)組成；內(nèi)循環(huán)包含去趨勢(shì)、周期序列平滑等六步；外循環(huán)的主要作用是引入穩(wěn)健性權(quán)重項(xiàng),以控制數(shù)據(jù)中異常值產(chǎn)生的影響.STL方法具有快速的計(jì)算速度和分析含缺失值時(shí)間序列的能力.此外,STL方法對(duì)具有趨勢(shì)和季節(jié)性成分的數(shù)據(jù)形成可靠估計(jì),使得這些數(shù)據(jù)不會(huì)被異常行為所扭曲.

2.2 度與度分布

網(wǎng)絡(luò)中,節(jié)點(diǎn)的度k 定義為直接與節(jié)點(diǎn)相連的連邊的數(shù)目.對(duì)于一個(gè)給定的有向加權(quán)網(wǎng)絡(luò)G,假設(shè)網(wǎng)絡(luò)的權(quán)值鄰接矩陣為W= (wij),則節(jié)點(diǎn)i 的加權(quán)出度和加權(quán)入度分別為

則節(jié)點(diǎn)i 的加權(quán)度為

網(wǎng)絡(luò)的加權(quán)出度分布p (s—)定義為加權(quán)出度為s—的節(jié)點(diǎn)被隨機(jī)選中的概率.類似地,網(wǎng)絡(luò)的加權(quán)入度分布p (s+)定義為加權(quán)入度為s+的節(jié)點(diǎn)被隨機(jī)選中的概率.實(shí)際應(yīng)用中,為了降低分布的尾部噪音,常常采用累積分布分析網(wǎng)絡(luò)的拓?fù)涮卣?累積分布描述了序列中頻數(shù)不小于某個(gè)特定值的概率.本文分析了時(shí)間序列網(wǎng)絡(luò)的累積加權(quán)入度分布,累積加權(quán)出度分布和累積加權(quán)度分布.

在基于STL方法的符號(hào)化有向加權(quán)網(wǎng)絡(luò)中,節(jié)點(diǎn)的加權(quán)出度越大表示節(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)值在時(shí)間序列中出現(xiàn)的頻率越高,這表明該節(jié)點(diǎn)向其他節(jié)點(diǎn)轉(zhuǎn)化的次數(shù)越多.如果節(jié)點(diǎn)的加權(quán)度值很小,則說(shuō)明該狀態(tài)在時(shí)間序列中出現(xiàn)的頻次很少,可能是一些突發(fā)情況導(dǎo)致的時(shí)間序列值突然增大或減小.

2.3 聚類系數(shù)與路徑長(zhǎng)度

網(wǎng)絡(luò)中,節(jié)點(diǎn)的聚集程度可以用節(jié)點(diǎn)的聚類系數(shù)來(lái)描述.節(jié)點(diǎn)i 的聚類系數(shù)定義為

其中,ki為節(jié)點(diǎn)i 的度,aij是鄰接矩陣A= (aij)的元素.當(dāng)且僅當(dāng)節(jié)點(diǎn)i ,j ,k 構(gòu)成一個(gè)三角形時(shí),aijajkaki= 1,否則aijajkaki= 0.網(wǎng)絡(luò)中所有節(jié)點(diǎn)的聚類系數(shù)的平均值定義為網(wǎng)絡(luò)的聚類系數(shù).社會(huì)網(wǎng)絡(luò)中,節(jié)點(diǎn)的聚類系數(shù)可以表示“朋友的朋友也是朋友”的傾向性大小.在基于STL方法的符號(hào)化有向加權(quán)網(wǎng)絡(luò)中,節(jié)點(diǎn)i 的聚類系數(shù)越大,表明符號(hào)模式i 的相鄰符號(hào)模式之間轉(zhuǎn)換越頻繁.

節(jié)點(diǎn)i 和節(jié)點(diǎn)j 之間的最短路徑長(zhǎng)度lij定義為從節(jié)點(diǎn)i 到節(jié)點(diǎn)j 的最短路徑上連邊的數(shù)量.網(wǎng)絡(luò)的平均路徑長(zhǎng)度L定義為任意兩個(gè)節(jié)點(diǎn)的最短路徑長(zhǎng)度的平均值,即

2.4 介 數(shù)

以經(jīng)過(guò)某個(gè)節(jié)點(diǎn)的最短路徑的數(shù)目刻畫(huà)節(jié)點(diǎn)重要性的指標(biāo)被稱為介數(shù)中心性,簡(jiǎn)稱介數(shù).網(wǎng)絡(luò)中,節(jié)點(diǎn)i 的介數(shù)用bi表示,定義為

其中,nst是從節(jié)點(diǎn)s 到節(jié)點(diǎn)t 的最短路徑的數(shù)目,nist為從節(jié)點(diǎn)s 到節(jié)點(diǎn)t 的nst條最短路徑中經(jīng)過(guò)節(jié)點(diǎn)i 的最短路徑的數(shù)目.從信息傳輸?shù)慕嵌瓤?網(wǎng)絡(luò)中介數(shù)越高的節(jié)點(diǎn)重要性越大,對(duì)網(wǎng)絡(luò)的信息傳輸影響越大.

3 基于STL方法的時(shí)間序列網(wǎng)絡(luò)

針對(duì)一類具有周期性特征的時(shí)間序列數(shù)據(jù),本文提出基于STL方法的符號(hào)化有向加權(quán)網(wǎng)絡(luò)建網(wǎng)方法.原始時(shí)間序列數(shù)據(jù)經(jīng)過(guò)STL分析以及符號(hào)化處理之后,不僅保持了數(shù)據(jù)的信息量,而且可以在短期細(xì)節(jié)和長(zhǎng)期趨勢(shì)兩方面體現(xiàn)時(shí)間序列數(shù)據(jù)的特點(diǎn).具體的時(shí)間序列網(wǎng)絡(luò)建立過(guò)程如下.

a) STL分析.依據(jù)STL方法,將時(shí)間序列轉(zhuǎn)化為季節(jié)項(xiàng)、趨勢(shì)項(xiàng)和余項(xiàng)之和,即Yn= Sn+ Tn+Rn.其中n 是時(shí)間序列的長(zhǎng)度,Sn= {si,i = 1,2,…,n }是季節(jié)項(xiàng),Tn= {ti,i = 1,2,…,n }是趨勢(shì)項(xiàng),Rn= {ri,i = 1,2,…,n }是余項(xiàng).

b)符號(hào)化.根據(jù)三個(gè)狀態(tài)項(xiàng)對(duì)原時(shí)間序列的影響程度,選用不同權(quán)重的符號(hào)化階數(shù)對(duì)狀態(tài)變量序列做層次劃分.得到三組符號(hào)化時(shí)間序列：

其中g(shù) (si),g (ti),g (ri)表示符號(hào).此時(shí),每個(gè)時(shí)間序列值表示為符號(hào)模式

c)構(gòu)建網(wǎng)絡(luò).以互不相同的符號(hào)模式為節(jié)點(diǎn),以兩個(gè)不同符號(hào)模式的相鄰關(guān)系作為連邊,以兩個(gè)互異符號(hào)模式相鄰的次數(shù)和符號(hào)模式的先后順序作為連邊的權(quán)重和方向,建立一個(gè)有向加權(quán)網(wǎng)絡(luò).

為了實(shí)現(xiàn)對(duì)真實(shí)時(shí)間序列數(shù)據(jù)的比較分析,在執(zhí)行STL分析與符號(hào)化之前,對(duì)原始時(shí)間序列數(shù)據(jù){xi,i = 1,2,…,n }進(jìn)行歸一化處理.采用歸一化方法：yi= (xi—xmin)/(xmax—xmin).歸一化之后的時(shí)間序列{yi,i = 1,2,…,n }保持了原時(shí)間序列的周期性特征和變化趨勢(shì)等特點(diǎn),并且取值范圍在[0,1].

在執(zhí)行數(shù)據(jù)符號(hào)化時(shí),如果符號(hào)化階數(shù)太小,會(huì)導(dǎo)致時(shí)間序列信息的流失；如果符號(hào)化階數(shù)太大,會(huì)使得符號(hào)模式過(guò)多,不能體現(xiàn)符號(hào)化的優(yōu)勢(shì).因此,考慮到準(zhǔn)確體現(xiàn)時(shí)間序列特點(diǎn)和構(gòu)建網(wǎng)絡(luò)的規(guī)模需要適度,經(jīng)過(guò)多次試驗(yàn)才確定了最優(yōu)的符號(hào)化階數(shù).季節(jié)項(xiàng)的符號(hào)化階數(shù)為m1= 8,趨勢(shì)項(xiàng)的符號(hào)化階數(shù)為m2= 18,隨機(jī)項(xiàng)的符號(hào)化階數(shù)為m3= 4.

4 兩種時(shí)間序列網(wǎng)絡(luò)測(cè)試

為了驗(yàn)證所提出的基于STL方法的時(shí)間序列網(wǎng)絡(luò)建模方法的有效性和實(shí)用性,分別以具有非平穩(wěn)特征的航空旅客吞吐量時(shí)間序列和具有平穩(wěn)特征的因特網(wǎng)流量時(shí)間序列為例,使用新方法建立有向加權(quán)網(wǎng)絡(luò).分析網(wǎng)絡(luò)的度分布、聚類系數(shù)、平均路徑長(zhǎng)度等拓?fù)湫再|(zhì),從網(wǎng)絡(luò)拓?fù)涮卣鞯慕嵌葘?duì)這兩個(gè)實(shí)際時(shí)間序列做比較分析.

4.1 航空旅客吞吐量時(shí)間序列網(wǎng)絡(luò)

航空旅客吞吐量數(shù)據(jù)取自澳門國(guó)際機(jī)場(chǎng)專營(yíng)股份有限公司(Macau International Airport Co.Ltd.)的官方網(wǎng)站.時(shí)間序列跨度從1996年1月到2017年12月.每月記錄一次吞吐量數(shù)據(jù),表示該月內(nèi)航空旅客的人數(shù),共有264條記錄.時(shí)間序列整體呈現(xiàn)上升趨勢(shì),其周期為12.此外,ADF檢測(cè)結(jié)果顯示,該時(shí)間序列數(shù)據(jù)為非平穩(wěn)性時(shí)間序列.

航空旅客吞吐量時(shí)間序列的STL分析如圖1(a)—(d)所示.季節(jié)項(xiàng)時(shí)間序列以周期規(guī)律呈現(xiàn),每個(gè)周期有12個(gè)值,反映這個(gè)周期內(nèi)數(shù)據(jù)波動(dòng)的細(xì)微變化.趨勢(shì)項(xiàng)時(shí)間序列體現(xiàn)了原時(shí)間序列的變化趨勢(shì).整體而言,數(shù)據(jù)呈上升狀態(tài)；但是,其中有兩個(gè)時(shí)間段下降明顯.隨機(jī)項(xiàng)時(shí)間序列為季節(jié)項(xiàng)和趨勢(shì)項(xiàng)的殘差值,呈現(xiàn)不規(guī)則變化.

圖1(e)是航空旅客吞吐量時(shí)間序列網(wǎng)絡(luò).該網(wǎng)絡(luò)有107個(gè)節(jié)點(diǎn),178條有向邊.節(jié)點(diǎn)的面積大小與節(jié)點(diǎn)的加權(quán)度有關(guān),加權(quán)度越大,節(jié)點(diǎn)的面積越大；連邊的寬度反映了連邊的權(quán)重,邊權(quán)越大,連邊的寬度越寬.網(wǎng)絡(luò)中加權(quán)度最大的節(jié)點(diǎn)是V42和V43,它們的加權(quán)度都是20；網(wǎng)絡(luò)中加權(quán)度最小的節(jié)點(diǎn)比較多,加權(quán)度值為1.網(wǎng)絡(luò)中邊權(quán)的最大值為7,即圖中連接V42和V43的邊；網(wǎng)絡(luò)中邊權(quán)的最小值為1.航空旅客吞吐量時(shí)間序列網(wǎng)絡(luò)的平均加權(quán)度為4.430,聚類系數(shù)為0.169,平均路徑長(zhǎng)度為13.355.

航空旅客吞吐量時(shí)間序列網(wǎng)絡(luò)具有指數(shù)加權(quán)度分布.s+表示節(jié)點(diǎn)的加權(quán)入度,s-表示節(jié)點(diǎn)的加權(quán)出度,s 表示節(jié)點(diǎn)的加權(quán)度.單對(duì)數(shù)坐標(biāo)系下,航空旅客吞吐量時(shí)間序列網(wǎng)絡(luò)的累積加權(quán)度分布近似呈直線型,擬合優(yōu)度檢驗(yàn)顯示三個(gè)度分布均服從指數(shù)分布.其中,網(wǎng)絡(luò)的累積加權(quán)入度分布服從指數(shù)為0.3990的指數(shù)分布(可決系數(shù)R2= 0.9280),如圖2(a)所示；網(wǎng)絡(luò)的累積加權(quán)出度分布服從指數(shù)為0.6151的指數(shù)分布(R2= 0.9960),如圖2(b)所示；網(wǎng)絡(luò)的累積加權(quán)度分布服從指數(shù)為0.2555的指數(shù)分布(R2= 0.9670),如圖2(c)所示.

圖1 (a)-(d)航空旅客吞吐量時(shí)間序列的STL分析 (a)原始時(shí)間序列；(b)季節(jié)項(xiàng)時(shí)間序列；(c) 趨勢(shì)項(xiàng)時(shí)間序列；(d) 隨機(jī)項(xiàng)時(shí)間序列；(e)航空旅客吞吐量時(shí)間序列網(wǎng)絡(luò)Fig.1.(a)-(d) The STL analyzing for the air passengers throughput time series：(a) Original time series；(b) seasonal time series；(c) trend time series；(d) remainder time series；(e) the time series network of the air passengers throughput data.

圖2 航空旅客吞吐量時(shí)間序列網(wǎng)絡(luò)度分布 (a)累積加權(quán)入度分布；(b)累積加權(quán)出度分布；(c)累積加權(quán)度分布Fig.2.The degree distribution of the time series network for air passengers throughput data：(a) The cumulative weighted in-degree distribution；(b) the cumulative weighted out-degree distribution；(c) the cumulative weighted degree distribution.

4.2 因特網(wǎng)流量時(shí)間序列網(wǎng)絡(luò)

因特網(wǎng)流量數(shù)據(jù)[25]表示英國(guó)學(xué)術(shù)網(wǎng)絡(luò)主干網(wǎng)的聚合流量.數(shù)據(jù)時(shí)間截取于2005年1月16日至2005年1月26日.每5 min記錄一次流量數(shù)據(jù),1天有288條記錄,11天共產(chǎn)生3168條記錄.該時(shí)間序列是周期為288的周期性時(shí)間序列.ADF檢測(cè)顯示,因特網(wǎng)流量時(shí)間序列為平穩(wěn)時(shí)間序列.

圖3(a)—(d)是因特網(wǎng)流量時(shí)間序列的STL分析圖.2005年1月16日、22日和23日分別為星期日、星期六和星期日,這三天產(chǎn)生的因特網(wǎng)流量偏小.星期一至星期五的流量時(shí)間序列整體趨勢(shì)一致且較為穩(wěn)定.季節(jié)項(xiàng)時(shí)間序列以周期規(guī)律呈現(xiàn),包含11個(gè)周期,每個(gè)周期有288個(gè)數(shù)據(jù),反映這個(gè)周期內(nèi)數(shù)據(jù)波動(dòng)的細(xì)微變化.趨勢(shì)項(xiàng)時(shí)間序列從星期一至星期五,數(shù)據(jù)伏動(dòng)較小,呈現(xiàn)平穩(wěn)狀態(tài)；在星期六、星期日,數(shù)據(jù)伏動(dòng)有明顯的下降.隨機(jī)項(xiàng)時(shí)間序列呈現(xiàn)不規(guī)則變化.

根據(jù)本文第3節(jié)提出的方法,將因特網(wǎng)流量時(shí)間序列映射為一個(gè)有向加權(quán)網(wǎng)絡(luò)(圖3(e)).該網(wǎng)絡(luò)有160個(gè)節(jié)點(diǎn),244條有向邊.節(jié)點(diǎn)V79和V80的加權(quán)度值最大,為54；網(wǎng)絡(luò)中存在大量加權(quán)度值較小的節(jié)點(diǎn).連邊權(quán)重的最大值為22,如圖3(e)所示,恰好是連接節(jié)點(diǎn)V79和節(jié)點(diǎn)V80的連邊的權(quán)重.因特網(wǎng)流量時(shí)間序網(wǎng)絡(luò)的平均加權(quán)度為5.538,聚類系數(shù)為0.249,平均路徑長(zhǎng)度為25.61.

因特網(wǎng)流量時(shí)間序列網(wǎng)絡(luò)的度分布服從冪律分布.如圖4所示,在雙對(duì)數(shù)坐標(biāo)下,累積加權(quán)度分布近似呈直線型,擬合優(yōu)度檢驗(yàn)顯示三個(gè)累積加權(quán)度分布均服從冪律分布.其中,網(wǎng)絡(luò)的累積加權(quán)入度分布服從冪指數(shù)為1.202的冪律分布(可決系數(shù)R2= 0.9960),如圖4(a)所示；網(wǎng)絡(luò)的累積加權(quán)出度分布服從冪指數(shù)為1.202的冪律分布(R2=0.9957),如圖4(b)所示；網(wǎng)絡(luò)的累積加權(quán)度分布服從冪指數(shù)為1.223的冪律分布(R2= 0.9940),如圖4(c)所示.綜上,三個(gè)累積度分布均服從冪指數(shù)小于2的冪律分布.因特網(wǎng)流量時(shí)間序列網(wǎng)絡(luò)是一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò).

圖3 (a)-(d)因特網(wǎng)流量時(shí)間序列的STL分析 (a)原始時(shí)間序列；(b)季節(jié)項(xiàng)時(shí)間序列；(c) 趨勢(shì)項(xiàng)時(shí)間序列；(d) 隨機(jī)項(xiàng)時(shí)間序列；(e)因特網(wǎng)流量時(shí)間序列網(wǎng)絡(luò)Fig.3.(a)-(d) The STL decomposition results of the Internet traffic time series：(a) Original time series；(b) seasonal time series；(c) trend time series；(d) remainder time series；(e) the time series network of the Internet traffic data.

圖4 因特網(wǎng)流量時(shí)間序列網(wǎng)絡(luò)的度分布 (a)累積加權(quán)入度分布；(b)累積加權(quán)出度分布；(c)累積加權(quán)度分布Fig.4.The degree distribution of the time series network for the Internet traffic data：(a) The cumulative weighted in-degree distribution；(b) the cumulative weighted out-degree distribution；(c) the cumulative weighted degree distribution.

4.3 分析與比較

航空旅客吞吐量時(shí)間序列是非平穩(wěn)時(shí)間序列,因特網(wǎng)流量時(shí)間序列是平穩(wěn)時(shí)間序列.采用所提出的STL分析符號(hào)化時(shí)間序列網(wǎng)絡(luò)建模方法,得到網(wǎng)絡(luò)的拓?fù)涮卣骺偨Y(jié)如表1所示.航空旅客吞吐量時(shí)間序列的數(shù)據(jù)長(zhǎng)度是102數(shù)量級(jí),構(gòu)建的加權(quán)有向時(shí)間序列網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)為102數(shù)量級(jí)；因特網(wǎng)流量時(shí)間序列的數(shù)據(jù)長(zhǎng)度是103數(shù)量級(jí),構(gòu)建的加權(quán)有向時(shí)間序列網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)為102數(shù)量級(jí).航空旅客吞吐量時(shí)間序列具有非平穩(wěn)性.隨著時(shí)間的推移,符號(hào)模式很大程度上不重復(fù),使得符號(hào)化時(shí)間序列的符號(hào)模式種類較多,從而航空旅客吞吐量時(shí)間序列網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)亦較多.因特網(wǎng)流量時(shí)間序列的趨勢(shì)項(xiàng)整體呈平穩(wěn)狀態(tài),對(duì)應(yīng)的符號(hào)化序列不規(guī)則重復(fù).在轉(zhuǎn)換成符號(hào)模式的過(guò)程中,符號(hào)模式的重復(fù)率較高,轉(zhuǎn)換頻率較大,從而種類較少,連邊的權(quán)重較大.所以,因特網(wǎng)流量時(shí)間序列網(wǎng)絡(luò)具有較少的節(jié)點(diǎn)數(shù)和較大的平均加權(quán)度.

表1 兩類時(shí)間序列網(wǎng)絡(luò)拓?fù)涮卣鞯谋容^Table 1.The comparison for topological characteristics of two kinds time series networks.

5 基于STL方法的時(shí)間序列網(wǎng)絡(luò)

5.1 時(shí)間序列數(shù)據(jù)

依據(jù)所提出的基于STL方法的時(shí)間序列建網(wǎng)方法,將移動(dòng)通信語(yǔ)音業(yè)務(wù)時(shí)間序列映射為一個(gè)有向加權(quán)網(wǎng)絡(luò).刪除數(shù)據(jù)記錄不完整的周期,并對(duì)初始數(shù)據(jù)進(jìn)行歸一化處理,得到一個(gè)數(shù)值范圍在[0,1]的長(zhǎng)度為52032的時(shí)間序列,如圖5(a)所示,為前10個(gè)周期的語(yǔ)音時(shí)間序列數(shù)據(jù).通過(guò)STL分析,季節(jié)項(xiàng)由長(zhǎng)度為24的單周期季節(jié)趨勢(shì)循環(huán)推移生成；趨勢(shì)項(xiàng)呈現(xiàn)不規(guī)則起伏變化.

5.2 時(shí)間序列網(wǎng)絡(luò)

由語(yǔ)音時(shí)間序列數(shù)據(jù)建立的有向加權(quán)網(wǎng)絡(luò)如圖5(e)所示.該網(wǎng)絡(luò)有230個(gè)節(jié)點(diǎn),1275條邊.網(wǎng)絡(luò)中,節(jié)點(diǎn)加權(quán)度的最大值為7740,連邊權(quán)重的最大值為2555.網(wǎng)絡(luò)的平均加權(quán)度為260.626,聚類系數(shù)為0.298,平均路徑長(zhǎng)度為5.142.

圖5 (a)-(d)語(yǔ)音時(shí)間序列數(shù)據(jù)的STL分析 (a)原始時(shí)間序列；(b)季節(jié)項(xiàng)時(shí)間序列；(c) 趨勢(shì)項(xiàng)時(shí)間序列；(d) 隨機(jī)項(xiàng)時(shí)間序列；(e)基于STL方法的語(yǔ)音時(shí)間序列網(wǎng)絡(luò)Fig.5.(a)-(d) The STL analyzing for the mobile traffic data：(a) Original time series；(b) seasonal time series；(c) trend time series；(d) remainder time series；(e) based on the STL decomposition,the time series network of the mobile traffic data.

圖6 語(yǔ)音時(shí)間序列網(wǎng)絡(luò)的度分布 (a)累積加權(quán)入度分布；(b)累積加權(quán)出度分布；(c)累積加權(quán)度分布Fig.6.The degree distribution of the time series network for the mobile traffic data：(a) The cumulative weighted in-degree distribution；(b) the cumulative weighted out-degree distribution；(c) the cumulative weighted degree distribution.

語(yǔ)音時(shí)間序列網(wǎng)絡(luò)的累積加權(quán)度分布服從冪律分布,度分布如圖6所示.累積加權(quán)度在雙對(duì)數(shù)坐標(biāo)下呈近似線性關(guān)系.網(wǎng)絡(luò)的累積加權(quán)入度分布(圖6(a))、累積加權(quán)出度分布(圖6(b))和累積加權(quán)度分布(圖6(c))均服從冪律分布.語(yǔ)音時(shí)間序列網(wǎng)絡(luò)是一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò).

5.3 局部特征分析

通過(guò)網(wǎng)絡(luò)的一些局部拓?fù)涮卣?分析了語(yǔ)音時(shí)間序列數(shù)據(jù)值的特點(diǎn).移動(dòng)通信語(yǔ)音時(shí)間序列網(wǎng)絡(luò)依局部拓?fù)涮卣鲄?shù)由大到小排序如表2所示.依節(jié)點(diǎn)的聚類系數(shù)由大到小排序,節(jié)點(diǎn)的符號(hào)模式如第一列所示；依節(jié)點(diǎn)的加權(quán)出度由大到小排序,節(jié)點(diǎn)的符號(hào)模式如第三列所示；依節(jié)點(diǎn)的介數(shù)中心性由大到小排序,節(jié)點(diǎn)的符號(hào)模式如第五列所示.

節(jié)點(diǎn)的聚類系數(shù)為1表示該模式的任意兩個(gè)鄰居模式之間都存在連邊,即該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)之間彼此相連,如圖5(e)中的節(jié)點(diǎn)dcb的聚類系數(shù)為1,說(shuō)明節(jié)點(diǎn)dcb的鄰居節(jié)點(diǎn)之間也是相鄰關(guān)系.在時(shí)間序列中,符號(hào)dcb對(duì)應(yīng)于0點(diǎn)或1點(diǎn).這個(gè)時(shí)間位于趨勢(shì)項(xiàng)時(shí)間序列的局部極大值處.類似地,其他聚類系數(shù)為1的節(jié)點(diǎn)對(duì)應(yīng)于語(yǔ)音時(shí)間序列數(shù)據(jù)時(shí),均由趨勢(shì)項(xiàng)的局部極大值或局部極小值映射而來(lái).這代表了一天的語(yǔ)音量高峰期或低谷期.

表2 網(wǎng)絡(luò)節(jié)點(diǎn)模式特征表Table 2.The table for characteristics of node patterns.

加權(quán)出度較大的節(jié)點(diǎn)對(duì)應(yīng)于時(shí)間序列上局部極大值和局部極小值之間的時(shí)刻.例如,圖5(e)中節(jié)點(diǎn)faa對(duì)應(yīng)于語(yǔ)音時(shí)間序列上的12點(diǎn)、15點(diǎn)和19點(diǎn)等數(shù)據(jù).結(jié)合實(shí)際情況,可知加權(quán)出度大的節(jié)點(diǎn)對(duì)應(yīng)于時(shí)間序列上的上班時(shí)間與休息時(shí)間的過(guò)渡時(shí)刻.對(duì)于周期性時(shí)間序列而言,這樣的數(shù)據(jù)較多,使得對(duì)應(yīng)的節(jié)點(diǎn)的加權(quán)度較大.語(yǔ)音時(shí)間序列網(wǎng)絡(luò)中,一些節(jié)點(diǎn)的介數(shù)中心性很大,這些符號(hào)模式對(duì)網(wǎng)絡(luò)上信息的流動(dòng)有較大的影響力.節(jié)點(diǎn)eoa的介數(shù)中心性為9810.72,該符號(hào)模式對(duì)應(yīng)于時(shí)間序列中每天的14點(diǎn)和20點(diǎn).

6 結(jié) 論

采用復(fù)雜網(wǎng)絡(luò)的量化統(tǒng)計(jì)量挖掘時(shí)間序列的內(nèi)在信息為時(shí)間序列分析方法提供了一個(gè)全新的視角.其中,時(shí)間序列網(wǎng)絡(luò)建模是最重要的方法之一.經(jīng)典方法構(gòu)建出無(wú)向無(wú)權(quán)網(wǎng)絡(luò),主要有相空間重構(gòu)法和可視圖方法以及他們的拓展模型.這些方法實(shí)施簡(jiǎn)便,但是,卻忽略了時(shí)間的單向性和基元之間的關(guān)聯(lián)程度的差異.針對(duì)上述問(wèn)題,科學(xué)家們提出了符號(hào)化時(shí)間序列建網(wǎng)方法,基于該類方法構(gòu)建的加權(quán)有向網(wǎng)絡(luò)更加貼近實(shí)際.已有的符號(hào)化時(shí)間序列建網(wǎng)方法以時(shí)間序列相鄰數(shù)據(jù)的變化趨勢(shì)的符號(hào)組為基元,考慮了數(shù)據(jù)的變化過(guò)程,卻忽略了數(shù)據(jù)值本身的特征.本文提出的基于STL方法的時(shí)間序列網(wǎng)絡(luò)方法,既考慮了單個(gè)數(shù)據(jù)值的狀態(tài),又考慮了時(shí)間序列的長(zhǎng)遠(yuǎn)變化趨勢(shì).以時(shí)間序列上的數(shù)據(jù)點(diǎn)為基元構(gòu)建網(wǎng)絡(luò),可以通過(guò)網(wǎng)絡(luò)的局部拓?fù)涮卣黧w現(xiàn)時(shí)間序列單個(gè)數(shù)據(jù)值的信息.

本文提出的基于STL方法的時(shí)間序列建網(wǎng)方法,結(jié)合周期性時(shí)間序列的STL分析和符號(hào)轉(zhuǎn)化方法構(gòu)建出一個(gè)有向加權(quán)網(wǎng)絡(luò).首先,依據(jù)STL方法將時(shí)間序列的每個(gè)數(shù)據(jù)值表示為三個(gè)狀態(tài)值.其次,通過(guò)對(duì)狀態(tài)值做區(qū)間劃分和符號(hào)化轉(zhuǎn)化,將每個(gè)數(shù)據(jù)值表示為狀態(tài)符號(hào).最后,依時(shí)間順序推移,以節(jié)點(diǎn)間的鄰接轉(zhuǎn)換關(guān)系定義連邊；根據(jù)轉(zhuǎn)換方向和轉(zhuǎn)換頻次確定連邊的方向和權(quán)重,建立有向加權(quán)網(wǎng)絡(luò).有向加權(quán)網(wǎng)絡(luò)的拓?fù)涮卣骺梢苑从硶r(shí)間序列的特點(diǎn)：1)周期時(shí)間序列經(jīng)STL分析之后,趨勢(shì)項(xiàng)可以展示時(shí)間序列的長(zhǎng)期變化特點(diǎn)；2)對(duì)于平穩(wěn)性周期時(shí)間序列,其周期項(xiàng)的規(guī)則性和趨勢(shì)項(xiàng)的平穩(wěn)性,使得在轉(zhuǎn)換成符號(hào)模式時(shí),符號(hào)模式的重復(fù)率較高,轉(zhuǎn)換頻率較大,所以生成網(wǎng)絡(luò)的連邊的權(quán)重較大；3)在有向加權(quán)網(wǎng)絡(luò)中,聚類系數(shù)較大的節(jié)點(diǎn)對(duì)應(yīng)著時(shí)間序列的高峰期或低谷期；而加權(quán)出度較大的節(jié)點(diǎn)對(duì)應(yīng)著時(shí)間序列上的局部極大值和局部極小值之間的過(guò)渡時(shí)刻.

在構(gòu)建網(wǎng)絡(luò)時(shí),使用了航空旅客吞吐量時(shí)間序列、因特網(wǎng)流量時(shí)間序列和移動(dòng)通信語(yǔ)音業(yè)務(wù)量時(shí)間序列.它們的共性是均為周期性時(shí)間序列,差異性表現(xiàn)在平穩(wěn)性上.本文研究重點(diǎn)是基于時(shí)間序列構(gòu)建新的建網(wǎng)方法,適用于具有周期性的時(shí)間序列.時(shí)間序列表示為周期態(tài)、趨勢(shì)態(tài)和隨機(jī)態(tài)的符號(hào)形式,這些時(shí)刻符號(hào)不僅體現(xiàn)時(shí)間序列值的細(xì)節(jié)變化,而且反映時(shí)間序列的長(zhǎng)期發(fā)展趨勢(shì).在確定符號(hào)化階數(shù)時(shí),需要通過(guò)實(shí)驗(yàn)驗(yàn)證,尚缺乏普適性的規(guī)則.未來(lái)將繼續(xù)完善方法并探索它們?cè)趧?dòng)態(tài)建模[26,27]等領(lǐng)域的應(yīng)用.