面向路網交通流態勢預測的圖神經網絡模型

姜 山，丁治明，徐馨潤，嚴 瑾

1.中國科學院 軟件研究所，北京100190

2.中國科學院大學，北京100190

3.大規模流數據集成與分析技術北京市重點實驗室，北京100190

+通信作者E-mail:zhiming@iscas.ac.cn

城市道路網中的交通流態勢預測問題是應急管理科學和城市管理科學等眾多領域的核心問題之一。路網交通流態勢預測是一個典型的時空時序數據預測問題，交通流數據被分布在城市道路網絡各個固定卡口的數據采集設備以固定時間間隔連續采集。相鄰設備采集的數據記錄以及不同時間戳下的數據記錄具有某種時空相關性。因此，有效地捕捉道路網絡中觀測數據間的時空相關性是解決交通流態勢預測問題的關鍵。

近年來，卷積神經網絡（convolutional neural network，CNN）[1-2]模型與算法已經廣泛地被用于計算機視覺任務和模式識別任務等領域，神經網絡以其獨特的數據經驗優勢和其卷積核的領域相關性優勢，在交通流預測問題中得到了學界的普遍關注，有大量學者研究并提出了用于交通流預測的循環神經網絡及其多種改進版本[3-5]。然而，CNN 的計算通常被限定在歐式空間。對于歐式空間以外的非歐式空間數據的處理，傳統的CNN 就顯得乏力。由于非歐式空間下的圖結構數據具有很強的數據建模與表達能力，越來越受到關注，比如，文獻[6-8]就提出了基于圖數據結構的圖卷積神經網絡（graph convolutional neural network，GCNN）模型與算法，GCNN 模型一經提出就受到了學界和工業界的廣泛重視。此外，文獻[9]提出了一種能預測結構化數據序列的深度學習模型，即圖卷積循環網絡（graph convolutional recurrent network，GCRN）。該模型結合CNN 對圖形進行空間結構特征提取，并采用循環神經網絡[10]（recurrent neural network，RNN）對時序數據的動態特征進行提取，但是不能很好地拓展到更大尺度的時間預測窗口。進一步地，文獻[11]針對交通領域的時間序列預測問題，提出了一種新的時空圖卷積網絡學習框架，基于圖形結構建立了具有完整卷積結構的圖神經網絡模型，其在較少參數的情況下，能夠有效保證訓練速度，但是該方法對圖的卷積核鄰域尺寸的支持不夠靈活。文獻[12]提出了一種用于時空圖建模的新型圖神經網絡模型，該模型能夠準確地捕獲數據中隱藏的空間依賴關系。此外，文獻[13]將圖小波代替圖拉普拉斯的特征向量作為基底，通過小波變換和卷積定理定義卷積算子，提出的模型能夠實現節點的分類預測，但無法對交通數據的時空特征和動態相關性進行同時建模。

一個時序預測模型與算法不僅要考慮某感興趣路段的歷史觀測數據，還需要考慮相鄰路網觀測對其的累積影響效應。因此，本文提出了基于圖小波卷積網絡的路網交通流態勢預測模型與方法。首先，基于圖小波卷積算子，設計了面向路網交通流態勢預測的圖小波神經網絡模塊，對交通數據的時空相關性和動態相關性進行建模；其次，通過引入注意力機制構建時空注意力模型，以捕獲交通網絡上的動態時空相關性；最后，通過疊加多層圖小波神經網絡模塊從交通網絡圖節點鄰域中捕獲空間相關性。

1 路網交通流態勢預測與圖小波卷積

1.1 路網交通流態勢預測

1.1.1 交通路網圖模型

以城市路網交通流探測傳感器i安裝位置為節點，以vi表示，并且以相鄰路段上的傳感器j為鄰居節點vj，構建交通路網圖模型G，定義如下：

其中，V表示節點集合，在路網中表示交通流探測傳感器集合，且|V|=N。E表示圖G中邊的集合，元素ei=＜vi,vj＞∈E表示節點vi和節點vj有聯結關系。在路網圖構建過程中，通常以節點vi鄰域范圍內鄰居節點構建邊或聯結。A∈RN×N為圖G的鄰接矩陣。本文構建的交通路網圖G是無向圖模型。在圖G中，每個傳感節點vi以相同頻率p采集m個測量屬性值（如車流量和行駛平均速度等），即在每個時間片t下每個節點vi共收集m維度的特征向量xi∈Rm。

1.1.2 路網交通流預測

交通路網圖G中每個節點以相同的頻率進行數據采集，每個節點包含m維測量屬性值，即在時間步t下圖G中每個節點vi觀測屬性值屬于m維特征向量。對于道路網絡圖G，在給定歷史觀測序列值(xt,xt-1,…,xt-H+1)T∈RN×m×H和預測時間窗口F大小的情況下，交通流態勢預測問題定義如下：

其中，xt∈RN×m是圖G中全部節點在時間t下的特征觀測矩陣，xt每一行代表某節點的特征觀測向量，f為映射函數，F為預測窗口長度。

1.2 圖小波卷積

（1）圖譜卷積

利用多個卷積核對輸入數據進行特征提取，各卷積層中每個神經元都與前一層位置臨近區域的多個神經元相連接，以捕獲空間相關性，卷積操作區域的大小取決于卷積核的尺寸。面向圖結構的圖譜卷積定義如下：

其中，x表示圖G的節點信號，即xt。ζθ表示卷積濾波核。*G為卷積操作算符。矩陣L=D-A是圖G的拉普拉斯矩陣，D∈RN×N是圖G的度矩陣，并且規范化之后的拉普拉斯矩陣L=IND-1/2AD-1/2，IN∈RN×N為單位矩陣。U是拉普拉斯矩陣L進行特征值分解后相應的特征向量矩陣，即L=UΛUT。Λ∈RN×N是由L特征分解后的特征值對角矩陣。表示圖傅里葉變換，矩陣U為傅里葉變換基。

（2）圖小波卷積

圖小波卷積用圖小波基替代L特征值分解后的特征向量基[13]（傅里葉變換基UT），并通過圖小波變換和卷積定理定義圖小波卷積算子。基于圖小波變換的圖小波卷積定義如下：

其中，Ψs=UGsUT=(Ψs1,Ψs2,…,ΨsN)，s為擴散尺度因子，Ψsi表示以節點i為中心并以s為尺度向鄰居節點擴散，為熱擴散核函數[14]，λi為L特征分解后特征值。為了計算方便，本文采用。為了不對圖G的拉普拉斯矩陣L進行特征分解，本文采用Hammond等人[15]提出的基于切比雪夫多項式近似算法有效近似Ψs和Ψ-1s，從而有效避免了對矩陣L的特征分解計算，近似求解算法復雜度為O(K×|E|)，K為多項式階數，|E|為圖G的邊數。近似算法如下：

其中，τ為圖信號，即表示矩陣L的K階切比雪夫多項式，為矩陣L的最大特征值。多項式階數K值越大計算越精確，但會帶來較高的計算復雜度，通常情況下K的取值范圍為3～10 之間。與圖譜卷積相比，圖小波卷積計算復雜度更低；多為稀疏矩陣，運算效率較高；圖小波卷積具有局部特性[16]，擴散尺度因子s控制著節點的鄰域范圍。

2 圖小波神經網絡模型

2.1 圖小波神經網絡模型總體結構

時空圖小波卷積網絡的總體架構如圖1 所示。時空圖小波卷積網絡由時空動態相關性捕獲模型和時空相關性捕獲模型串聯組成時空塊，再串聯堆疊多個時空塊，最后接入到一個多層感知機[17]（multilayer perceptron，MLP）模型輸出層。在時空圖小波卷積網絡的總體架構中，時空動態相關性捕獲模型由空間注意力模型和時間注意力模型組成，空間注意力模型通過引入空間注意力機制捕獲空間動態相關依賴特征，空間注意力模型基于注意力機制構造時間注意力矩陣捕獲交通流數據的時間動態相關依賴特征；時空相關性捕獲模型由圖小波卷積和1 維擴張因果卷積組成，圖小波卷積用以提取圖節點間的空間特征，1 維擴張因果卷積用以提取時間維度上各觀測值的時間相關性特征。從本質上講，圖小波神經網絡是一種多層圖譜卷積神經網絡，其核心是利用小波變換代替傅里葉變換來定義圖卷積運算符。

Fig.1 Architecture of spatial-temporal graph wavelets convolutional networks圖1 時空圖小波卷積網絡的總體架構圖

2.2 時空動態相關性捕獲模型

圖小波卷積運算能夠捕獲節點間的空間相關性特征，并以此建模圖節點間的信息流向和匯集的影響力，但是只能建模有限尺度鄰域內節點間的靜態依賴特征。在交通網絡中，節點間相互影響具有長時空的動態相關性，比如相鄰節點在不同時間發生了不同程度的堵車以及不同節點同一時段交通流量狀況都有著時空關聯性。為了建模節點間的動態相關性，引入注意機制模型[18]分別對時間和空間的動態相關性進行建模，并構建了時空動態相關性模型，對時空動態相關性進行建模。

（1）空間注意力模型

為了建模交通網絡圖節點間的空間動態相關性，在空間維度上定義空間注意力模型，如下：

其中，Zs∈RN×N為空間注意力矩陣，為規范化后的空間注意力矩陣，h為激活函數（如ReLU（rectified linear unit）），(i,j)表示圖節點i,j間的連接強度，通過設定合理的閾值大小可以動態調整空間注意力矩陣。是網絡的第l層輸入特征信號，為第l層時間序列長度，Fl為第l層特征維度；若l為0，則表示第一層，其對應的輸入為以及偏置bs∈RN×N待訓練學習的參數。

（2）時間注意力模型

為了建模交通網絡圖節點間的時間動態相關性，在時間維度上定義時間注意力模型，如下：

2.3 時序相關性捕獲模型

為了能夠捕獲時序數據間的時間相關性，采用一維擴張因果卷積（dilated causal convolution，DCC）提取節點的時間相關特征。在擴張因果卷積網絡中，隨著層數的增加，接受域（或稱感受野）變大，在當前時間步上所做的推論只包含歷史信息。假設給定一個輸入序列x*∈RH，則一維擴張因果卷積定義如下：

其中，*D表示擴張因果卷積操作算符，k∈RK為濾波核，K表示擴張因果卷積濾波核大小，d為擴張率（或擴張因子）。通過將擴張因果卷積層與擴張因子按遞增順序疊加，模型的感受野會指數級增長。這使得擴張因果卷積網絡能夠以較少的層捕獲較長的序列，從而有效節省了計算資源。

2.4 圖小波網絡交通流預測算法訓練步驟

基于圖小波神經網絡的交通流預測前向訓練步驟如下：

步驟1給定道路網絡圖G和各節點的歷史觀測數據集，并設定歷史時間窗口長度H和預測時間窗口長度F，將歷史時間窗口H對應的時序數據作為訓練樣本{xi}=(xt,xt-1,…,xt-H+1)T∈RN×m×H，將預測時間窗口長度F對應的時序數據作為訓練樣本的學習目標{yi}。

步驟2將數據集以6∶2∶2 的比例隨機分割為訓練集、驗證集和測試集（其中，訓練集用于模型擬合的數據樣本，驗證集用于“調優”模型的超參數設置，訓練集和驗證集數據均參與訓練過程，測試集數據僅對訓練調優后的模型進行測試驗證），并對數據進行零均值歸一化處理，以減小尺度因素對樣本均衡性的影響，使模型更容易收斂到最優解。此外，在訓練過程中對數據集進行了隨機Shuffle 操作，以提升模型的泛化性能。

步驟3利用公式計算Ψs和

步驟4串聯堆疊兩個時空塊（每個時空塊由時空動態相關性捕獲模型和時空相關性捕獲模型串聯組成）構造時空圖小波卷積網絡模型。輸入數據{xi}∈RN×m×H，計算Zt=fZt({xi})時間注意力矩陣，并規范化為，計算；計算空間注意力矩陣，并規范化為，計算

步驟5利用公式進行空間特征提取運算，利用公式對輸入數據進行時間特征提取運算。

步驟6將由多個串聯堆疊的時空塊進行特征提取后的數據接入到多層感知機MLP[17]中，MLP 將特征進行融合輸出，輸出結果作為時空圖小波卷積網絡模型的前向傳播輸出。

步驟7以均方誤差為優化損失函數，采用Adam一階優化算法進行梯度反向傳播優化，迭代學習得到模型的參數數值。

步驟8基于已經訓練得到的最優模型參數，進行路網交通流態勢預測，得到預測時間窗口F內的各節點交通流狀態。

3 結果與分析

3.1 實驗環境及數據預處理

（1）實驗數據集

選用公開數據集PeMSD-4 和PeMSD-8 作為時空圖小波卷積神經網絡模型的驗證數據[19]。實驗中，將PeMSD-4 和PeMSD-8 數據聚合為5 min 間隔的數據記錄。PeMSD-4 中記錄了某高速公路307 個傳感器兩個月的交通參數，具體包括交通流量、平均速度和平均車道占有量。PeMSD-8 中記錄了某高速公路170 個傳感器兩個月的交通參數。

（2）實驗環境

實驗基礎硬件平臺為：Intel?Xeon?Gold 5218 CPU@2.30 GHz，NVIDIA GeForce GTX 2080 GPU，顯存32 GB。采用Adam 優化器進行優化，學習率為0.000 1。為了提升計算效率，將Ψs和Ψ-1s中小于閾值0.000 1 的元素設置為0。訓練過程中如果存在連續200 個迭代步驟中驗證集的損失無明顯變化的情況，則表示完成模型訓練。

（3）模型評估度量與對照基線

在實驗過程中，選用平均絕對誤差（mean absolute errors，MAE）、平均絕對百分比誤差（mean absolute percentage errors，MAPE）和均方根誤差（root mean squared errors，RMSE）三種度量指標來評估模型，指標越小表示模型越精確，并選用STGCN-Cheb（spatiotemporal graph convolutional networks with Chebyshev polynomials approximation）、STGCN-1st（spatio-temporal graph convolutional networks with 1storder approximation）、ASTGCN（attention based spatial-temporal graph convolutional network）和MSTGCN（multi-component spatial-temporal graph convolution networks）模型[11,20]作為本文模型實驗對比基線。同時，為了和傳統非深度學習模型進行比較，本文選取了歷史平均（historical average，HA）預測方法和VAR（vector auto-regressive）[21]預測方法作為傳統基線模型。在HA 中，根據前12 個時間片的平均值來預測下一個值。

3.2 實驗結果與分析

基于PeMSD-4 和PeMSD-8 數據集，驗證本文提出的面向路網交通流態勢預測的時空圖小波卷積網絡模型的性能，并與多個基線進行比較。

圖2 和圖3 分別展示了不同模型在數據集PeMSD-4和PeMSD-8上的平均性能對比結果。從圖2中可以明顯看出，在PeMSD-4 數據集上，提出的時空圖小波卷積網絡模型均方根誤差RMSE、平均絕對誤差MAE 和平均絕對百分比誤差MAPE 均比其他4 個基線模型的平均性能低。其中時空圖小波卷積網絡模型的RMSE 比STGCN-1st、STGCN-Cheb、MSTGCN和ASTGCN 分別低15.92%、11.47%、6.31%和2.93%，時空圖小波卷積網絡模型的MAE 比STGCN-1st、STGCN-Cheb、MSTGCN 和ASTGCN 分別低17.35%、16.40%、9.10%和2.81%，MAPE 數值比STGCN-1st、STGCN-Cheb、MSTGCN 和ASTGCN 分別低24.08%、18.45%、18.04%和3.50%。

Fig.2 Average performance comparison of different models on PeMSD-4圖2 不同模型在數據集PeMSD-4 上平均性能比較

Fig.3 Average performance comparison of different models on PeMSD-8圖3 不同模型在數據集PeMSD-8 上平均性能比較

從圖3 中可以明顯看出，在PeMSD-8 數據集上，時空圖小波卷積網絡模型平均性能均比其他4 個基線模型的平均性能低。時空圖小波卷積網絡模型的RMSE、MAE 和MAPE 均比最佳基線模型ASTGCN分別低2.08%、0.68%和6.26%。與基線模型STGCN-1st的平均性能相比，時空圖小波卷積網絡模型的RMSE、MAE 和MAPE 分別低15.42%、18.71%和41.05%。與傳統模型相比，從圖2 和圖3 中可以明顯看出，時空圖小波卷積網絡模型具有明顯的性能優勢。

從圖2 和圖3 的平均性能結果可以看出，以圖小波變換為基礎的圖小波卷積運算、擴張因果卷積運算和基于注意力機制的時空注意力模型構建的時空圖卷積網絡模型，不僅能夠很好地提取時空相關性特征，還能夠建模時空動態相關性特征。因此，本文提出的時空圖卷積網絡模型更適合用作交通路網的交通流態勢的預測與分析任務。

基于圖小波卷積的神經網絡模型，除了能夠提高預測精度外，圖小波卷積中的小波變換矩陣更具稀疏性。統計了在PeMSD-4 和PeMSD-8 數據集上的圖小波變換矩陣與傅里葉變換矩陣非零元素個數和密度，分別如表1 和表2 所示。

在PeMSD-4數據集中，共有307個節點，因此圖小波變換矩陣和傅里葉變換矩陣UT∈R307×307。表1 中第一行統計了變換矩陣間的非0 元素占比（密度），可以明顯看出圖小波變換矩陣以及圖小波逆變換矩陣Ψs均比傅里葉變換矩陣UT和傅里葉逆變換矩陣U稀疏。因此，基于圖小波變換定義的卷積運算更有效率。表2 中，分別統計了在PeMSD-8數據集（共有170 個節點）上的圖小波變換矩陣的非零元素個數與傅里葉變換矩陣UT∈R170×170的非零元素個數，可以看出，圖小波變換矩陣比傅里葉變換矩陣UT稀疏，其中的密度占比比UT的密度占比低約88.36%。通過統計PeMSD-4 和PeMSD-8 數據集上的圖小波變換矩陣與傅里葉變換矩陣的稀疏性，發現基于圖小波變換定義的卷積運算更具稀疏性，這將有助于提高模型訓練時的計算效率。

Table 1 Count of non-zero elements of different transformation matrices on PeMSD-4表1 不同變換矩陣在PeMSD-4 上的非零元素計數

Table 2 Count of non-zero elements of different transformation matrices on PeMSD-8表2 不同變換矩陣在PeMSD-8 上的非零元素計數

4 結束語

針對交通路網中交通流態勢預測問題，提出了一種基于圖的交通流預測深度學習模型。實驗發現，該模型不僅能夠很好地捕捉時空相關性特征，還能夠建模時空動態相關性特征；同時，該模型的預測精度優于所選的基準模型；此外，本文模型中的卷積運算更具稀疏性，相較于傳統圖卷積運算更具有計算效率。因此，提出的模型極易推廣至更一般的時空圖結構序列預測場景中。

交通路網中的交通流態勢預測，實際上會受到許多外部因素的影響，如氣象條件、突發事件等。因此，在未來工作中，一方面，考慮將外部因素引入模型，進一步提高預測精度；另一方面，將提出的交通流預測深度學習模型應用到新的城市路網交通流數據上，進一步驗證和測試模型的性能。