基于復雜網絡的交通序列數據特性

孟勃 孔祥科 李樹彬

摘要：為了進一步研究交通流特性，采用復雜網絡方法對交通序列數據進行分析。提出了箱型圖-聚類算法模型用于識別和填充初始數據中的缺失值和異常值；通過相空間重構方法將一維數據重構為網絡節點，選取連接閾值確定網絡節點的連接關系，將交通序列數據構建為復雜網絡，對復雜網絡的結構和定量指標進行分析。研究結果表明交通序列數據復雜網絡的結構一定程度上可以反映路段的交通流狀態。該結果有助于優化數據預處理方法，拓展復雜網絡在交通序列數據研究中的應用。

關鍵詞：復雜網絡；數據分析；網絡構建方法；相空間重構；聚類算法

中圖分類號：U491?? 文獻標志碼：A?? 文章編號：1002-4026（2024）01-0107-11

The characteristics of traffic sequence data based on complex network

Abstract∶To study the traffic flow characteristics， the traffic data is analyzed using a complex network method. A box plot-clustering algorithm model is proposed to identify and fill in missing values and outliers in the initial data. The one-dimensional data is reconstructed into network nodes using the phase space reconstruction method. Additionally， the connection threshold is selected to determine the connection relationship of network nodes to convert the traffic sequence data as a complex network and analyze the structure and quantitative indicators of the network. The result shows that the structure of the complex network of traffic data can reflect the traffic flow state of the road section to a certain extent. The research optimizes the data preprocessing method and extends the application of complex networks into traffic data research.

Key words∶complex networks; data analysis; network building methods; phase space reconstruction; clustering algorithm

近年來，隨著數據分析、人工智能的發展，通過交通序列數據研究復雜的交通系統逐漸成為研究熱點。交通序列數據是按照時間順序和固定的時間間隔采集的交通流參數數據，用于描述交通流隨時間的變化情況。目前，基于交通序列數據的研究主要集中在采用人工智能算法的交通流預測。武瓊[1]基于支持向量回歸模型預測交通流參數，并進行了動態預測系統開發。趙懷柏等[2]利用遺傳算法對BP（back propagation）反向傳播神經網絡神經網絡的參數進行優化，實驗證明了優化后模型在進行交通流預測時在預測精度和運算效率方面具有明顯提升。Ma等[3]構建了基于長短期神經網絡的交通流預測模型，對比驗證了該模型具有更好的預測精度。上述研究主要集中于交通序列數據的直接應用，研究重點集中在通過優化模型參數或構建組合模型來提高模型的預測精度，往往缺乏對交通序列數據的深入分析和挖掘。

復雜網絡理論作為一種表征系統內部各因素相互關系的通用工具，逐漸在各個研究領域得到更多應用。以交通領域為例，復雜網絡廣泛應用在城市道路網和城市公共交通網的研究中。對于城市道路網，Strano等[4]以原始圖法對比分析了歐洲10個城市的街道網絡的結構相似性和特性。葉彭姚[5]分析了中國城市道路網絡的特征，并驗證了網絡節點度服從冪分布。對于城市公交網絡，Lu等[6]驗證了公交網絡參數符合復雜網絡特征，并發現這些參數對公共交通的可達性、安全性有影響。許晴等[7]利用公交路線換乘關系模型研究了中國330個城市的公交復雜網絡結構特征。Yang等[8]構建了公交-地鐵復合網絡，通過級聯失效模型，研究極端天氣下公共交通網絡的魯棒性。

城市道路和公共交通均具備一定的網絡實體結構，如城市道路可以抽象為交叉口和路段組成的網絡結構，公共交通可以抽象為站點和線路組成的網絡結構，因此在構建復雜網絡時往往是對其物理結構的復現。然而，不同于上述網絡，數據不具備典型的網絡結構形式，在構建復雜網絡時需要進行節點的構造和連接關系的確定。Wang等[9]利用可見圖法構建GDP國內生產總值時序數據復雜網絡，并分析網絡特性。Gao等[10]驗證了以時間序列數據構建的網絡能夠保留數據的主要性質。Mao等[11]基于可見圖的預測方法將時間序列轉換成復雜網絡，預測節點間的相似度。

目前，通過復雜網絡對交通序列數據的研究還較少，在交通序列數據處理、網絡構建等方面還存在不足。因此，本文以交通序列數據為研究對象，主要研究交通序列數據的網絡化表示方法以及網絡結構、特性指標所表現出的交通流特征，探究二者之間的內在聯系。本文首先提出了箱型圖-聚類算法模型，用于處理數據中的缺失值和異常值；然后通過相空間重構和臨界閾值將交通序列數據構建為復雜網絡，最后進行網絡結構分析和網絡指標計算。

1 數據分析與預處理

1.1 交通序列數據

交通系統是一個多維、動態的復雜系統，系統內部各因素相互影響。交通流特性是交通流運行狀態的定性、定量表征，宏觀上用于描述交通流作為一個整體表現出來的特性，微觀上是指彼此相關的交通參與者的運行狀態。在不受橫向交叉影響的路段上，交通流呈連續流狀態；當受到橫向干擾時，如路口信號燈管制時，交通流呈現出斷續流狀態。

交通流隨著時間和空間的變化而變化，由于出行的規律性，交通流在一定周期內呈現出重復性，即具有周期性特征；同時，交通流受到車輛、行人和其他干擾因素的影響，又表現出強烈的隨機性和不確定性。交通流的特性可以通過交通序列數據進行表征和分析，本文主要以交通流的速度序列數據為研究對象。圖1繪制了廣州市兩條快速路不同時間周期的速度變化圖，數據來源于廣州市交通委員會公布的開源數據。由圖1可以看出路段速度變化在一周內具有明顯的周期波動性，每天的速度變化具有相似性，但并非完全相同，這表明了交通系統具有一定的隨機性。

交通序列數據是交通系統運行狀態的最直接反應，分析研究交通序列數據對于挖掘交通系統運行規律、緩解城市交通擁堵具有重要意義。目前，交通序列數據的采集方式主要有磁頻采集技術、波頻采集技術和視頻采集技術等方法，由于受到環境干擾、傳感器精度等因素的影響，交通序列數據的質量往往會受到缺失數據和噪聲數據的干擾，從而影響到基于數據的分析結果[12]。

1.2 改進數據預處理方法

數據預處理是進行數據分析的重要前提，缺失值的填充、異常值的替換是數據預處理的兩個關鍵。插值法和數理統計法是較為常見的數據預處理方法[13-14]。插值法主要依賴時間或空間相鄰數據進行填充，對于連續缺失的數據處理效果較差。數理統計法主要通過假設的數據分布估計填充值，相關參數的假設對于填充值的影響較大。為了提高數據預處理的效果，本文基于機器學習，改進傳統的數據預處理方法，提出了箱型圖-聚類算法的數據預處理模型。模型共分為如下關鍵步驟。

步驟一：通過箱型圖法識別數據集中的異常值。箱型圖法是一種較為客觀的判定異常值的有效方法[14]。如式（1）所示，f（x）為異常值的判定函數，當f（x）=1時，判定數據為異常值；反之，當f（x）=0時，判定數據為正常值。

其中，Q1為升序數列的25%位點；Q3為升序數列的75%位點；Δ=Q3－Q1。

步驟二：通過聚類算法對交通序列數據進行聚類分析。本文選用的聚類算法為層次聚類算法，該方法依據數據點的相似度，構建多層嵌套樹模型進行數據聚類，主要聚類流程為將采集的原始數據構建為初始數據簇，在初始數據簇的基礎上，每次選擇相似度最高的兩個數據簇合并為新的簇，依次迭代到目標分類數。

步驟三：根據步驟二的層次聚類結果對不同類別的交通狀態進行認定，計算相同交通狀態數據的平均值。

步驟四：確定缺失值或異常值所處的交通狀態，以相同狀態數據的平均值進行填充。層次聚類算法填充缺失值和異常值的主要流程如圖2所示。

2 復雜網絡的構建

2.1 網絡節點的確定

網絡是由節點和節點間的連接關系確定的，以城市軌道交通網絡為例，在構建復雜網絡時常以軌道站點作為節點，存在地鐵線路連接的站點之間則設置連邊。由于在數據中不存在典型的網絡節點，因此本文利用相空間重構方法，將一維數據構建為多維相空間，作為復雜網絡的節點。相空間重構存在兩個關鍵參數：延遲時間和嵌入維數。在Takens嵌入定理中，證明了延遲時間和嵌入維數理論上的存在性[15]。在實際數據應用中，需要根據數據的實際情況選取。

假設交通流時間序列為x=xii=1，2，…，n，其中n為時間序列長度。通過相空間重構將該分量重構矩陣X，如式（2）所示。

其中，τ表示延遲時間，即序列時間間隔；m表示嵌入維數，即重構后矩陣維度；N=n－（m－1）τ。

2.1.1 延遲時間選取

本文采用互信息熵法[16]計算相空間重構的延遲時間。假設存在序列A=a1，a2，…，an和序列B=b1，b2，…，bn，則二者的互信息熵δ（A，B）計算如式（3）。

其中，p（ai），p（bj）為樣本集合中ai和bj所占的比例，p（ai，bj）為ai和bj的聯合分布概率。

互信息熵表示在已知序列A的前提下，序列B的不確定性減小程度。兩個序列之間的互信息熵越小，說明序列間的相關程度越低。因此在相空間重構時，通過計算原始序列數據和延遲后的序列數據的互信息熵，并繪制互信息熵隨延遲時間的變化圖來確定最佳的延遲時間。

2.1.2 嵌入維數選取

Cao方法[17]是在偽臨近點法的基礎上改進而來，該方法相較于其他方法，所需數據量小，設定參數少且能夠有效識別數據的確定性和隨機性。Cao方法通過判定指標E1（m）的變化來選取嵌入維數。假設Xi（m）=（xi，xi+τ，…，xi+（m－1）τ）是重構后矩陣的第i個相點矢量，i=1，2，…，N， m表示重構矩陣的維數，其最鄰近點為XNNi（m），定義

其中，

E1（m）的計算公式如式（6）所示，當E1（m）從某個值m0不再改變時，則認為m0為最小嵌入維數。

在實際研究中，對于E1（m）是緩慢增長還是停止變化是難以判斷的，因此增加一個判斷指標E2（m），如式（7）～（8）。

對于隨機數列，數據之間不存在相關性，E2（m）的值會始終為1；對于確定性序列，數據點間的相關性取決于嵌入維數m的值，總存在一些E2（m）的值不等于1。因此在相空間重構時，通過E2（m）的值確定數據是否為確定性數據，通過E1（m）隨著嵌入維數的變化情況來確定最佳嵌入維數。

2.2 網絡邊的確定

對于相空間重構后的時間序列，以重構空間中的矢量點作為網絡節點v，節點間的連接由節點間的空間距離L和臨界閾值ε共同決定。假設矩陣W=（wvivj）為網絡鄰接矩陣，其連接規則由公式（9）所示。

式中，wvivj=1表示節點vi，vj連接；wvivj=0表示節點vi，vj之間斷開。

由式（9）可以看出，連接閾值對于網絡的構建具有重要意義。本文將網絡密度的變化率作為確定最佳連接閾值的指標。隨著連接閾值的增加，網絡中節點之間的連邊數增加，即網絡密度增加。當連接閾值接近網絡中所有簇的平均半徑時，邊增加將達到最大速率；繼續增加連接閾值將導致節點間的冗余連接，邊增加得趨于緩慢，網絡密度的增速放緩[18-19]。因此，本文通過繪制網絡密度變化率隨連接閾值的變化圖，選取網絡密度增加速率最大的點作為最佳閾值。

3 案例分析

本研究采用廣州市2條快速路的實測車速數據，時間窗為10 min，一周的數據總量為1 008條。通過箱型圖-聚類算法模型對原始數據進行預處理，然后將車速數據構建為復雜網絡，并通過復雜網絡的相關指標對網絡特性進行分析。

3.1 數據預處理

本節首先利用箱型圖-聚類算法模型對原始數據中的異常值和缺失值進行識別與填充。圖3繪制了箱型圖對車速數據中異常值的判定結果，由圖3可以看出，本文采用的快速路車速數據中的異常值主要分布在較小值。

本文采用的聚類算法為層次聚類算法，以原始數據中的每個值作為一個初始聚類簇，依次選擇距離最近的兩個簇合并為新的簇，直到迭代達到目標分類數。德國學者Kerner[20]在對大量交通流數據進行統計分析的基礎上，提出了三相交通流理論，即認為交通流存在自由流、同步流和寬運動堵塞流3種狀態。因此，根據三相交通流理論，本文在進行聚類分析時預設目標分類數為3類。

圖4繪制了車速數據的聚類分析結果，結果顯示聚類算法能夠很好的識別交通狀態，交通流狀態被劃分為自由流、同步流和寬運動堵塞流。表1列舉了每組數據的層次聚類得到的不同交通狀態下的速度平均值。

3.2 網絡構建

3.2.1 網絡節點的確定

圖5繪制了互信息熵隨延遲時間的變化圖。由圖5可以看出，隨著延遲時間的增加，互信息熵逐漸減少并趨于穩定，根據曲線的變化情況，選取互信息熵減小至較小值并趨于穩定時的點作為相空間重構的延遲時間，取值見表2。

圖6繪制了E1（m）、E2（m）隨嵌入維數的變化圖。由圖可以看出，隨著嵌入維數的增加，E2（m）在值1的上下波動，可認為所研究的時間序列均為確定性過程，E1（m）先增加后趨于平穩，選取E1（m）增加并趨于穩定時的值作為相空間重構的嵌入維數，取值見表2。

3.2.2 連接閾值的確定

圖7繪制了隨著嵌入維數的變化，網絡密度變化率的情況，選擇網絡密度變化率最高的點作為連接閾值的最佳值，因此道路一一日、道路一一周、道路二一日和道路二一周選取的最佳連接閾值分別是20、19、20、24。

3.3 網絡分析

根據選取的閾值將節點之間的距離矩陣轉化為鄰接矩陣，如圖8所示。圖中橫縱坐標表示網絡中的節點序列，藍色點位表示對應節點對之間存在連接，白色點位則表示節點對之間不存在連接。對比道路一和道路二的鄰接矩陣可以看出，道路一的鄰接矩陣圖像中藍色點位區域更為聚集，而道路二的圖像中，藍色點位區域較為分散，且存在一些孤立的藍色點。由此可以得出，不同的道路交通流狀態會導致鄰接矩陣圖像的差異性，進而影響復雜網絡的結構。

根據網絡構建方法和閾值選取結構，構建了交通序列數據復雜網絡。在此基礎上，選擇網絡平均度、介數、聚類系數作為網絡評價指標。度是指網絡節點相關聯的邊的數量，平均度則是所有網絡節點度的平均值。介數是指網絡中的最短路徑中，經過某節點的最短路徑的占比。聚類系數是度量網絡中節點聚集程度的系數，從數學上講，節點vi的局部聚類系數Cvi表示為公式（10）。

式中，evi表示節點vi的鄰域內節點間的連接邊數，即由節點vi以及其鄰域內兩個節點形成的三角形數量，kvi是節點vi的度。

圖9分別繪制了兩條道路不同時間周期的復雜網絡圖。對比不同尺度的時間序列網絡可以看出，一定程度上時間尺度的增加對于網絡分析具有重要意義。隨著時間尺度的增加，兩條道路的時間序列網絡結構特征更加明顯。由圖9（a）（c）可以看出，日周期的交通序列數網絡表現出一定的集群結構特征，網絡中存在兩個較大的集群，而對于周周期的交通序列數據網絡，如圖9（b）（d）所示，網絡的明顯的收斂在一個區域，形成一個大簇。

表3列舉了不同網絡的定量指標，對比道路一和道路二的網絡結構和指標可以看出，道路一交通序列數據網絡的平均度和平均聚類系數更高，網絡的集聚性更加凸顯，而道路二交通序列數據網絡中的孤立節點和孤立集群的數量和比例更高。復雜網絡的結構和指標一定程度上表明：相較于道路二，道路一不同時間段的交通流參數的波動較小，交通運行狀態較為穩定，而道路二的交通運行狀態存在較大波動。穩定的交通流反映在網絡上表現為網絡節點之間的相似度更高，節點之間的聚集性更好；而波動的交通流則容易形成分散的集群或孤立的節點。因此，在對路段進行交通管控時，應重點針對孤立節點和集群對應的時間段，深入分析交通波動誘因，以采集精細化的交通管控手段。

4 結論

交通序列數據是交通流狀態的直接表現，分析和研究交通序列數據對于深入理解復雜的交通系統，制定切實有效的交通管控措施具有重要意義。本文將復雜網絡理論引入交通流研究中并用于交通序列數據分析，提出的基于機器學習層次聚類算法能夠在考慮交通流狀態的基礎上，實現缺失值和異常值的填充；在復雜網絡構建方面，利用相空間重構技術將一維數據轉化為多維矢量點，作為復雜網絡的節點；通過網絡密度確定節點連接閾值，將節點間距離矩陣轉化為鄰接矩陣，并構建成網絡；通過分析網絡結構和指標論證了網絡結構一定程度上可以反映道路交通流狀態。本文研究成果可為交通管理部門提供可行建議，但是如何通過時間序列網絡指標定量的精確識別交通狀態仍是未來研究需要努力的方向。

參考文獻：

［1］武瓊. 基于支持向量回歸的短時交通流預測方法研究與應用[D]. 西安：長安大學， 2016.

[2]趙懷柏， 王逸凡， 宋曉鵬. 基于遺傳算法優化BP神經網絡的交通流預測[J]. 交通與運輸（學術版）， 2017（2）： 32-36.

[3]MA X L， TAO Z M， WANG Y H， et al. Long short-term memory neural network for traffic speed prediction using remote microwave sensor data[J]. Transportation Research Part C： Emerging Technologies， 2015， 54： 187-197. DOI： 10.1016/j.trc.2015.03.014.

[4]STRANO E， VIANA M， da FONTOURA COSTA L， et al. Urban street networks， a comparative analysis of ten European cities[J]. Environment and Planning B： Planning and Design， 2013， 40（6）： 1071-1086. DOI： 10.1068/b38216.

[5]葉彭姚. 城市道路網拓撲結構的復雜網絡特性研究[J]. 交通運輸工程與信息學報， 2012， 10（1）： 13-19. DOI： 10.3969/j.issn.1672-4747.2012.01.003.

[6]LU H P， SHI Y. Complexity of public transport networks[J]. Tsinghua Science & Technology， 2007， 12（2）： 204-213. DOI： 10.1016/S1007-0214（07）70029-9.

[7]許晴， 祖正虎， 徐致靖， 等. 330個中國城市P空間下公交復雜網絡實證研究[J]. 交通運輸系統工程與信息， 2013， 13（1）： 193-198. DOI： 10.16097/j.cnki.1009-6744.2013.01.001.

[8]YANG H H， AN S. Robustness evaluation for multi-subnet composited complex network of urban public transport[J]. Alexandria Engineering Journal， 2021， 60（2）： 2065-2074. DOI： 10.1016/j.aej.2020.12.016.

[9]WANG N， LI D， WANG Q W. Visibility graph analysis on quarterly macroeconomic series of China based on complex network theory[J].Physica A： Statistical Mechanics and Its Applications， 2012， 391（24）： 6543-6555. DOI： 10.1016/j.physa.2012.07.054.

[10]GAO Z K， JIN N D. Complex network from time series based on phase space reconstruction[J]. Chaos： an Interdisciplinary Journal of Nonlinear Science， 2009， 19（3）： 033137. DOI： 10.1063/1.3227736.

[11]MAO S Z， XIAO F Y. Time series forecasting based on complex network analysis[J]. IEEE Access， 2019， 7： 40220-40229. DOI： 10.1109/ACCESS.2019.2906268.

[12]鄒曉芳. 城市快速路交通流故障數據修復方法研究[D]. 北京：北京交通大學， 2014.

[13]苗旭， 王忠宇， 鄒亞杰，等. 改進的固定交通檢測器缺失數據綜合修復方法[J]. 同濟大學學報（自然科學版）， 2019， 47 （10）： 1477-1484. DOI： 10.11908/j.issn.0253-374x.2019.10.013.

[14]姜桂艷， 冮龍暉， 張曉東，等.動態交通數據故障識別與修復方法[J]. 交通運輸工程學報， 2004（01）： 121-125. DOI： 10.3321/j.issn：1671-1637.2004.01.030.

[15]孟力， 畢葉平. 相空間重構文獻綜述可視化分析[J]. 系統仿真學報， 2017， 29（12）： 3167-3175. DOI： 10.16182/j.issn1004731x.joss.201712030.

[16]李媛媛. 基于相空間重構和SVR的短時間交通流預測方法研究[D]. 北京： 北京交通大學， 2018.

[17]CAO L Y. Practical method for determining the minimum embedding dimension of a scalar time series[J].Physica D： Nonlinear Phenomena， 1997， 110（1/2）： 43-50. DOI： 10.1016/S0167-2789（97）00118-8.

[18]TANG J J， WANG Y H， LIU F. Characterizing traffic time series based on complex network theory[J]. Physica A： Statistical Mechanics and Its Applications， 2013， 392（18）： 4192-4201. DOI： 10.1016/j.physa.2013.05.012.

[19]TANG J J， WANG Y H， WANG H， et al. Dynamic analysis of traffic time series at different temporal scales： a complex networks approach[J]. Physica A： Statistical Mechanics and Its Applications， 2014， 405： 303-315. DOI： 10.1016/j.physa.2014.03.038.

[20]KERNER B S. The physics of traffic[J]. Physics World， 1999， 12（8）： 25-30. DOI： 10.1088/2058-7058/12/8/30.