結合可視圖的多狀態交通流時間序列特性分析?

邢雪 于德新 田秀娟 王世廣

1)(吉林大學交通學院,長春 130022)

2)(吉林化工學院信息與控制工程學院,吉林 132022)

3)(吉林大學吉林省道路交通重點實驗室,長春 130022)

結合可視圖的多狀態交通流時間序列特性分析?

邢雪1)2)?于德新1)3)田秀娟1)王世廣1)

1)(吉林大學交通學院,長春 130022)

2)(吉林化工學院信息與控制工程學院,吉林 132022)

3)(吉林大學吉林省道路交通重點實驗室,長春 130022)

交通流時間序列,可視圖,復雜網絡,聚類分析

1 引 言

交通流運行狀態隨人、車、路和環境等多要素變化,交通流時間序列呈現非線性特征和隨機特性[1].對于交通流時間序列的分析主要采用隨機過程理論、數理統計學方法[2]和機器學習方法(如聚類法、支持向量機)等[3,4],結合交通理論[5]進行動態特征分析.近年來,復雜網絡理論在時間序列動態特征分析中的使用引起了極大關注[6?8],已經有相應的研究應用于不同領域的時間序列分析中[9].研究表明用復雜網絡分析動態系統是可行的,這為交通流序列提供了可視化分析的途徑[10].

由于交通狀態的不同會影響其時間序列的幅度變化范圍,為此首先建立交通流主要變量(交通流量、占有率和地點平均速度)之間的實際關聯關系,利用K-medoids方法進行交通流狀態分類,然后通過可視圖理論構建多狀態交通流時間序列復雜網絡,分析比較其對應網絡的特征,如度分布、聚類系數、網絡直徑、模塊化,比較不同交通流狀態下交通流時間序列的統計規律.

2 基于K-medoids方法的交通流狀態分類

為分析交通流時間序列的特征,研究實際數據發現交通狀態不同對交通流參量時間序列幅度變化有相應的影響.考慮到這種影響,首先利用聚類分析方法對交通流進行分類.選用K-medoids算法進行交通狀態的聚類分析.K-medoids算法具有算法簡單、收斂速度快及局部搜索能力強等優點,已應用于很多領域[11?13].

實驗數據源采用2015年1月24日廈門市某路段實時檢測的1440條交通數據(每條數據包括實時交通流量、占有率和地點平均速度),交通參量采集時間單位為1 min.根據宏觀基本圖理論,不同交通狀態下的交通流量、占有率和速度之間存在關聯.為了進一步探討不同交通流狀態下交通流時間序列的特征,根據《城市道路交通擁堵評價指標體系》中給出的道路擁堵等級將數據分為5級(擁堵程度分為非常暢通、暢通、輕度擁堵、中度擁堵和嚴重擁堵).采用K-medoids方法對輸入樣本進行分類,向量xi=(xi1,xi2,···,xij),i=1,2,3,其中j表示樣本數據的數量,x1j表示時間占有率,x2j表示路段交通流量,x3j表示區域平均速度.從數據集中選出平方差最小的k個聚類中心,并將數據集劃分為k個聚類(實驗中選取k=5).

交通流狀態的K-medoids方法分類主要流程如下:從1440個對象的數據集中隨機選擇k個樣本(k=5)作為初始中心點;將剩余的樣本指派給距其最近的中心點所代表的簇;計算平方差函數w(l),

式中p為類Lj中的樣本,oi為聚類中心,按照平方差函數值減小的方向,更新每個簇的中心點,重復執行直到聚類不再發生變化.

圖1 基于K-medoids方法的交通流狀態分類三維數散點圖Fig.1.Scatter plot of traffic state classi fication based on K-medoids.

圖3 三個交通參量在不同交通狀態下的提取圖 (a)時間占有率的時間序列曲線;(b)交通流量的時間序列曲線;(c)區域平均速度的時間序列曲線Fig.3.Extraction figures of three traffic parameters in different states:(a)Time series of time occupancy;(b)time series of traffic flow;(c)time series of speed.

實驗樣本數據點分類結果如圖1所示,圖中數據點以實時交通流量、占有率和地點平均速度為坐標確定樣本點位置,1—5級表示交通流的等級劃分,1級表示交通運行最暢通,5級表示交通運行最擁堵.為清晰表示不同交通流狀態下變量之間的關系,根據宏觀基本圖理論構建任意兩個交通流變量之間的關系模型,并進行數據擬合.圖2(a)所示為時間占有率與交通流量之間的相互關系及基于時間占有率增長的交通流量散點擬合曲線;圖2(b)為時間占有率與區域平均速度之間的相互關系及基于時間占有率增長的平均速度散點擬合曲線;圖2(c)為區域平均速度與交通流量之間的相互關系及基于區域平均速度增長的交通流量散點擬合曲線.在圖2(a)中,數據擬合線方程為Q=?0.0234T2+1.4979T+6.5924,其中T為時間占有率,Q為交通流量,三個估計參數的置信區間為[?0.02399,?0.02281],[1.46934,1.52045]和[6.22742,6.95738]. 在圖2(b)中,數據擬合線方程為V=?0.0334T+33.9681,其中V為區域平均速度,兩個估計參數的置信區間為[?0.03516,?0.03164]和[33.58776,34.34844]. 在圖2(c)中,數據擬合線方程為Q=?0.0281V2+1.5126V+1.2703,三個估計參數的置信區間 為[?0.03354,?0.02265],[1.11743,1.90776]和[0.46310,2.07749].上述估計均為95%置信度.

圖3為提取5個級別狀態劃分中三個交通變量的時間序列圖.在圖3中,I1,I2,I3,I4和I5表示從數據樣本向量中分別提取5個級別交通狀態下時間占有率的時間序列,II1,II2,II3,II4和II5表示從數據樣本向量中分別提取5個級別交通狀態下交通流量的時間序列,III1,III2,III3,III4和III5表示從數據樣本向量中分別提取5個級別交通狀態下區域平均速度的時間序列.I1,II1,III1均表示1級狀態下的交通非常暢通,從中可以發現交通流量與時間占有率變化較大,區域平均速度在5個級別狀態中波動最大,表明實際情況中車輛的數量不穩定且車輛行駛自由度較高.I2,II2,III2均表示2級狀態下的交通暢通,從中可以發現交通流量與時間占有率變化自由度同1級相比幅度有所減小,交通參量的數值明顯增大,區域平均速度保持平穩且數值較高,說明實際情況中車輛的數量增多且車輛行駛狀態趨于穩定.I3,II3,III3均表示3級狀態下的交通輕度擁堵,此狀態特點為持續時間長且所有變量的值相對穩定,交通流量與時間占有率持續保持在較高水平,區域平均速度長時間保持平穩,表明在實際情況中車輛的數量繼續增多且車輛行駛狀態保持穩定.I4,II4,III4均表示4級狀態下的交通中度擁堵,從中可以發現交通流量與時間占有率變化幅度與3級相似,區域平均速度明顯下降,表明實際情況中車輛行駛受阻且道路負荷呈現飽和態.I5,II5,III5均表示5級狀態下的交通嚴重擁堵,從中可以發現交通流量與時間占有率保持相反變化狀態,時間占有率明顯上升而交通流量降至較低水平,區域平均速度明顯下降,表明在實際情況中車輛行駛受阻嚴重且道路呈現過飽和態.

3 交通流時間序列的復雜網絡構建

時間序列的復雜網絡構建方法主要有可視圖法[14,15]、周期時間序列構建法[16,17]和相空間重建法[18].其中后兩種方法的機理是基于時間序列的相關系數,所以必須估計臨界閾值[19?21].實際獲取的交通流時間序列不滿足周期時間序列的分析要求,不適用周期時間序列構建法.而相空間重建法對于嵌入維度和時間窗參數的依賴性強.綜合考慮后利用可視圖法構建針對交通流時間序列的復雜網絡,利用復雜網絡的表象重新認識交通流時間序列,以復雜網絡的分析方法來分析交通流時間序列的規律.

可視圖法是一種將時間序列映射到網絡的快捷方法,算法主要借助構建復雜網絡來表征時間序列的網絡結構,對交通流(相關三個交通參量)構建復雜網絡的流程如圖4所示,其中若時間序列中的兩個任意數據值(ta,y(ta))和(tb,y(tb))之間的任何(ti,y(ti))(ta＜ti＜tb),使得成立,則這兩個數據值(ta,y(ta))和(tb,y(tb))所構成的圖節點間關聯是可見的.

圖4 交通流時間序列的復雜網絡構建流程Fig.4.Construction process of complex network of traffic flow time series.

通過每一類交通狀態中三個交通參量時間序列的柱狀圖,分析每一類交通狀態下交通參量對應網絡的鄰接矩陣.對每個交通狀態分類下三個交通參量時間序列的三個鄰接矩陣進行矩陣疊加,使得矩陣可以最大化反映交通流時間序列的關聯特征.由于每個矩陣都是布爾矩陣,所以每一類交通狀態對應網絡的鄰接矩陣為M=MQ∨MT∨MV,即以矩陣表示法得到相應構造的復雜網絡.

4 交通流時間序列網絡特征分析

4.1 交通流時間序列的復雜網絡結構

結合上述方法,構建了基于多種交通狀態的交通流時間序列網絡,相應每類交通狀態網絡的矩陣圖表示如圖5所示,形成的網絡結構如圖6所示.圖5(a)—圖5(e)分別為5個級別交通流狀態的交通流時間序列網絡矩陣圖,圖6(a)—圖6(e)分別為5個級別交通流狀態的交通流時間序列網絡使用Gephi軟件繪制的網絡結構圖.

圖5 不同交通狀態構建網絡的交通流時間序列矩陣圖 (a)1級;(b)2級;(c)3級;(d)4級;(e)5級Fig.5.Matrix of traffic time series for different traffic state networks:(a)Level 1;(b)level 2;(c)level 3;(d)level 4;(e)level 5.

圖6 (網刊彩色)基于不同交通狀態的交通流時間序列復雜網絡圖 (a)1級;(b)2級;(c)3級;(d)4級;(e)5級Fig.6.(color online)Complex network diagram of traffic time series based on different states:(a)Level 1;(b)level 2;(c)level 3;(d)level 4;(e)level 5.

利用可視圖方法構建的網絡鄰接矩陣有如下特征.在交通非常暢通的狀態下,交通流中各參量時間序列的變化均較大且車流自由度較大(如圖3中I1,II1和III1所示),反映在矩陣(即體現可見的邊)中著色點分布呈現分散狀,即沿著對角線方向重疊的大方形,如圖5(a)所示.同樣在可見圖中映射出的邊與節點分布較均勻,僅在個別節點處(對應時間序列的結束階段)顯現出可見邊密集的情況,如圖6(a)所示.這表明在交通非常暢通的狀態下,網絡呈現均勻分布狀態.在交通暢通的狀態下,交通流中各參量時間序列的變化幅度趨緩(如圖3中I2,II2和III2所示),反映在矩陣中著色點分布呈現沿對角線方向成型的小方形,如圖5(b)所示;同樣在可見圖中映射出的邊與節點分布中出現集聚的特征,即出現彼此緊密連接的節點,如圖6(b)所示,這表示對應的原時間序列中的數據點相關性較高,且其矩陣中對應方形越小網絡的集聚特征越明顯.在交通輕度擁堵的狀態下,交通流中各參量時間序列處于穩定狀態,在各個交通參量時間序列中均沒有明顯的波動點,且此狀態持續時間在整個采集時間中所占比例最大(如圖3中I3,II3和III3所示),對應圖5中最大的矩陣分布.由于矩陣較大,因而體現反映狀態的表象特征比例略小,但依然可判斷出著色點分布呈現成型的小方形且這些方形分布密集,如圖5(c)所示;同樣在可見圖中出現非常明顯的集聚特征,如圖6(c)所示,交通狀態從非常暢通到暢通,再從暢通到輕度擁堵的狀態變化過程中,網絡中的集聚群落數量逐漸增多,可視圖中集聚群落特征也呈現得更加明顯,由此網絡的集聚群落特征可充分映射與交通流時間序列的關聯特性.在交通中度擁堵狀態下,道路負荷呈現飽和狀態,交通流中各參量時間序列依舊保持平穩,未呈現大幅度波動,但區域平均速度明顯下降(如圖3中I4,II4和III4所示),時間序列的局部峰值被映射到周邊鄰近的點,在矩陣中呈現沿對角線方向成型的小方形且同比可見邊增多,如圖5(d)所示;同樣在可見圖中映射具有集聚特征的網絡結構,但由于網絡對應映射的時間序列點較少,可見圖中特征不顯著,如圖6(d)所示.在交通嚴重擁堵狀態下,交通參量中交通流量與時間占有率時間序列呈現反向變化趨勢,且呈現較大幅度的波動(如圖3中I5,II5和III5所示),因而在多個交通參量時間序列的復合矩陣中反映出相同的沿對角線方向形態明顯的方形,如圖5(e)所示;由于圖6(e)中網絡對應映射的時間序列點偏少,可見圖中特征不顯著.上述分析表明,交通狀態從非常暢通到中度擁堵的過程中,網絡群落數目迅速增長;交通狀態從中度擁堵到嚴重擁堵的過程中,網絡群落數目緩慢減少.

4.2 交通流時間序列的復雜網絡特征

通過統計網絡的度分布、聚類系數、網絡直徑、模塊化等描述和分析網絡特征,并進一步研究網絡的動力學特征.研究分析了實例中構造的不同交通狀態時間序列網絡的聚類系數、網絡直徑、模塊化、圖密度和平均路徑長度等統計特征,如表1所示.表中比較不同狀態交通流時間序列網絡的統計特征,表現為網絡直徑基本保持同一水平.網絡的聚類系數和模塊化應結合時間序列可視化特性分析,表現為交通狀態變化越趨近于中度擁堵,網絡結構模塊化越高.由于交通狀態的網絡時間序列點數目不同,當序列點數量變少時模塊化呈現不足,而將整體考慮為一個模塊,表現為體現整體關聯的聚類系數增大,同樣符合交通狀態越擁堵、網絡結構模塊化(在小網絡結構中表現為聚類系數)越高的特點.

構建的5個網絡的節點度分布散點及擬合曲線如圖7所示,其中度分布分別對應圖6(a)—圖6(e)的交通流時間序列網絡度分布.圖7中對應圖6(a)網絡的散點擬合符合冪律分布,數據擬合線方程為y1=9043d?12.143,其中y1表示相同節點度的個數,d1表示圖中節點度數,擬合估計參數的置信區間為[?638.9,18720],[?2.522,?1.764].圖7中對應圖6(b)—圖6(e)的散點擬合符合高斯分布,圖6(b)網絡數據擬合線方程為y2=17.29exp{?[(d2?18.89)/10.02]2},擬合估計參數的置信區間為[14.52,20.05],[17.5,20.27]和[7.851,12.18];圖6(c)網絡數據擬合線方程為y3=40.75exp{?[(d3?17.64)/8.262]2},擬合估計參數的置信區間為[36.95,44.56],[16.99,18.29]和[7.25,9.273];圖6(d)網絡數據擬合線方程為y4=8.183exp{?[(d4?18.31)/9.332]2},擬合估計參數的置信區間為[6.687,9.678],[16.87,19.75]和[7.01,11.65];圖6(e)網絡數據擬合線方程為y5=2.938exp{?[(d5?18.58)/12.72]2},擬合估計參數的置信區間為[2.075,3.801],[15,22.16]和[5.283,20.16].上述估計置信度均為95%.

表1 交通流時間序列的復雜網絡統計特征Table 1.Statistical characteristics of complex network with traffic time series.

圖7 網絡節點度分布圖Fig.7.Degree distribution of network.

5 結 論

在考慮現有實例數據對應交通狀態差異的基礎上,針對K-medoids方法進行交通狀態分類后的交通流時間序列,結合可視圖算法構建了交通流時間序列的復雜網絡.算法對實際路網的實時檢測交通數據進行處理,并分析了不同交通狀態下交通流時間序列網絡的統計特性.

與傳統的交通流序列研究方法不同,本研究使用復雜網絡作為工具,利用網絡分析統計特性的方式來分析交通流的屬性,即從可視化的網絡角度重新認識交通流:1)衡量交通流狀態需要多個參量,而可視圖法只能處理單變量時間序列,直接應用可視圖法不能體現交通流整體特征,所以采用矩陣疊加的方式構建多參量的交通流時間序列的網絡矩陣,為交通流時間序列映射到網絡提供了有效方式;2)傳統交通流理論通過宏觀基本圖分析交通流變量之間的相關性,進而對交通狀態進行劃分,而本研究構建的實例網絡發現網絡特性(如網絡結構的模塊化、聚類系數和度分布)在不同狀態下具有不同的模式,通過不同的屬性模式可以識別不同的交通狀態.現階段初步利用可視圖方法分析研究了交通流時間序列的屬性,之后將繼續探討其他構建時間序列網絡的方法并比較其優缺點,為分析交通流的運行態勢提供更多途徑.

[1]He Z C,Li Z T,Zhao J M 2010J.Sw.Jiaotong Univ.45 946(in Chinese)[何兆成,黎志濤,趙建明 2010西南交通大學學報45 946]

[2]Dou H L,Liu H D,Wu Z Z,Yang X G 2009J.Tongji Univ.(Natural Science Edition)37 486(in Chinese)[竇慧麗,劉好德,吳志周,楊曉光 2009同濟大學學報(自然科學版)37 486]

[3]Xing X,Yu D X,Tian X J,Cheng Z Y 2016J.Huazhong Univ.Sci.Technol.(Natural Science Edition)44 160808(in Chinese)[邢雪,于德新,田秀娟,程澤陽 2016華中科技大學學報(自然科學版)44 160808]

[4]Zhang Y M,Wu X J,Bai S L 2013Acta Phys.Sin.62 190509(in Chinese)[張玉梅,吳曉軍,白樹林2013物理學報62 190509]

[5]Treiber M,Kesting A,Helbing D 2010Transp.Res.B44 983

[6]Ling X,Hu M B,Jiang R,Wu Q S 2010Phys.Rev.E81 16113

[7]Gao Z K,Jin N D,Yang D,Zhai L S,Du M 2012Acta Phys.Sin.61 120510(in Chinese)[高忠科,金寧德,楊丹,翟路生,杜萌2012物理學報61 120510]

[8]Gao X Y,An H Z,Fang W 2012Acta Phys.Sin.61 098902(in Chinese)[高湘昀,安海忠,方偉2012物理學報61 098902]

[9]Gao Z,Jin N 2012Physica A391 3005

[10]Zhang J,Cao X B,Du W B,Cai K Q 2010Physica A389 3922

[11]Arora P,Deepali D,Varshney S 2016Proc.Comput.Sci.78 507

[12]Madhulatha T 2012Int.Organ.Sci.Res.J.Eng.2 719

[13]Mishra N,Motwani R 2004Mach.Learn.56 35

[14]Lucas L,Bartolo L,Fernando B,Jordi L,Juan C N 2008Proc.Natl.Acad.Sci.105 4972

[15]Lacasa L,Toral R 2010Phys.Rev.E82 36120

[16]Zhang J,Sun J F,Luo X D,Zhang K,Nakamura T,Small M 2008Physica D237 2856

[17]Zhang J,Small M 2006Phys.Rev.Lett.96 238701

[18]Xu X,Zhang J,Small M 2008Proc.Natl.Acad.Sci.105 19601

[19]Donner R V,Zou Y,Donges J F,Marwan N,Kurths J 2010Phys.Rev.E81 15101

[20]Yang Y,Yang H J 2008Physica A387 1381

[21]Tang J,Wang Y,Liu F 2013Physica A392 4192

Analysis of multi-state traffic flow time series properties using visibility graph?

Xing Xue1)2)?Yu De-Xin1)3)Tian Xiu-Juan1)Wang Shi-Guang1)

1)(College of Transportation,Jilin University,Changchun 130022,China)
2)(College of Information and Control Engineering,Jilin Institute of Chemical Technology,Jilin 132022,China)
3)(Jilin Provincial Key Laboratory of Road Traffic,Jilin University,Changchun 130022,China)

19 March 2017;revised manuscript

23 July 2017)

A traffic flow time series is a sequence of traffic detection parameters in chronological order.This differs from a general quantitative data sequence in that the time series includes a time attribute that contains not only the data with time characteristics,but also the distribution of the data itself.To date,studies of traffic time series have primarily adopted data mining methods consisting of data mining and machine learning methods—similar sequence search,dimension reduction,clustering,classification,pattern analysis,prediction,etc.In order to improve the visualization of traffic flow time series and feature analyses,a proposed method builds the association networks of traffic flow time series by using visibility graph theory.This approach differs from traditional traffic flow theory as it performs feature analysis of traffic flow time series from the perspective of complex networks,and then analyzes the relationship between the characteristics of the structure in the visual network and the state characteristics of the traffic flow.The proposed method also takes into account the different traffic flow time sequences that correspond to different traffic states.

In the network building process using the proposed method,the traffic flow is classified by correlating the traffic flow parameters to the structure of the complex time series networks under different traffic conditions through considering the changes in traffic flow characteristics under various traffic conditions.Next,statistical analyses of the signs and attributes of the networks(e.g.degree distribution,clustering coefficient,network diameter,and modularization)are conducted.The analysis results show that the proposed visibility graph method can provide an effective approach to mapping traffic flow time series to the network.Moreover,the modularity,clustering coefficient,and degree distribution of the traffic flow time series networks in different traffic states show specifically varying patterns,providing a way to visually analyze the trends in traffic flow operation.When the traffic condition is at level 1,the distribution of the scattered points of the network conforms to a power law distribution.When the traffic condition is at any other level,the distribution of the scattered points of the network is consistent with a Gaussian distribution.The modularity of the time series network also shows some statistical characteristics,that is,the number of modules grows rapidly when the traffic state switches from smooth to moderate congestion,but decreases slowly when the traffic state switches from moderate congestion to serious congestion.These characteristics can be used to distinguish different traffic states,providing more perspective to understand different traffic scenarios.In this work we preliminarily study the attributes of traffic time series based on the proposed visibility graph method.Future efforts will continue to compare various methods of time series network construction to determine the pros and cons of each method for further analysis.

traffic flow time series,visibility graph,complex network,cluster

PACS:05.45.Tp,45.70.Vn,89.75.FbDOI:10.7498/aps.66.230501

*Project supported by the National Natural Science Foundation of China(Grant No.51308248)and the National Key Technology Support Program of China(Grant No.2014BAG03B03).

?Corresponding author.E-mail:patricia_xx@126.com

(2017年3月19日收到;2017年7月23日收到修改稿)

交通流時間序列的研究主要采用數據挖掘和機器學習的方法,這些“黑箱”挖掘方法很難直觀反映序列特性.為增強交通流時間序列及其特征分析的可視化性,結合可視圖理論來構建交通流時間序列的關聯網絡,從復雜網絡角度實現交通流時間序列的特性分析.在網絡構建的過程中,考慮到不同交通狀態下交通流表征具有的差異性,首先利用交通流參量的相關性對交通流狀態進行分類,然后構建不同交通狀態下的時間序列復雜網絡,并對這些網絡的特征屬性給出統計分析,如度分布、聚類系數、網絡直徑、模塊化等.研究表明,可視圖法可為交通流時間序列映射到網絡提供有效途徑,并且不同狀態下交通流時間序列構建的復雜網絡的模塊化、聚類系數和度分布等統計特征呈現一定的變化規律,為交通流運行態勢的研究提供了可視化的分析角度.

10.7498/aps.66.230501?國家自然科學基金(批準號:51308248)和國家科技支撐計劃(批準號:2014BAG03B03)資助的課題.

?通信作者.E-mail:patricia_xx@126.com