基于時(shí)空圖神經(jīng)網(wǎng)絡(luò)的交通擁堵預(yù)測技術(shù)

劉華 林立春 楊麗萍 洪東

隨著全球定位和物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，道路上各種傳感器采集的路網(wǎng)數(shù)據(jù)規(guī)模不斷擴(kuò)大。交管部門亟須針對已有的路網(wǎng)數(shù)據(jù)預(yù)測車輛未來的位置和區(qū)域分布，對道路前方可能發(fā)生的交通擁堵進(jìn)行預(yù)警，并幫助駕駛員選擇合適路線，從而緩解城市擁堵。文章采用時(shí)空圖神經(jīng)網(wǎng)絡(luò)（STGNN）挖掘交通流量數(shù)據(jù)的潛在因果關(guān)系，對交通路網(wǎng)嵌入空間依賴和時(shí)間依賴進(jìn)行建模分析。實(shí)驗(yàn)結(jié)果表明，該方案能更有效地預(yù)測未來的交通流量，防止發(fā)生擁堵。

時(shí)空圖神經(jīng)網(wǎng)絡(luò);交通流量;STGNN;擁堵預(yù)測

U491.1+13A411473

0 引言

近年來，通過對交通大數(shù)據(jù)的分析挖掘預(yù)測未來的交通趨勢，已引起智能交通系統(tǒng)領(lǐng)域研究人員的廣泛關(guān)注。準(zhǔn)確預(yù)測未來的交通情況具有很多優(yōu)勢，它不僅可以幫助市民繞行擁擠的道路，而且可以提前安排高效的出行。由于大城市的交通每時(shí)每刻都在發(fā)生變化，相同位置的交通數(shù)據(jù)在不同時(shí)刻，如在工作日和周末會(huì)觀察到不同的車流量;相同時(shí)刻的交通數(shù)據(jù)在不同位置也不相同，如在居民區(qū)和商圈附近也會(huì)觀察到不同的車流量。因此，在交通數(shù)據(jù)中存在復(fù)雜的時(shí)空關(guān)系，這使得進(jìn)行精確交通擁堵預(yù)測的任務(wù)極具挑戰(zhàn)性。

早期的各種統(tǒng)計(jì)和機(jī)器學(xué)習(xí)技術(shù)，如整合移動(dòng)平均自回歸模型（ARIMA）、歷史平均模型（HA）、支持向量回歸（SVR）和卡爾曼濾波模型，已廣泛用于交通預(yù)測。最近幾年，圖神經(jīng)網(wǎng)絡(luò)（GNN）在模擬現(xiàn)實(shí)交通中取得了很好的效果，它通過采用不同的特征聚集方案，將圖中相鄰節(jié)點(diǎn)之間的空間依賴性進(jìn)行編碼并融入其中。圖卷積神經(jīng)網(wǎng)絡(luò)（GCN）[1-3]應(yīng)用頻譜卷積來學(xué)習(xí)結(jié)構(gòu)依賴性和特征信息。Hamilton等[4]在GraphSAGE中進(jìn)一步給出了空間域圖卷積的通用框架，為圖神經(jīng)網(wǎng)絡(luò)的研究打開了新的大門。后來有研究者把交通流模型轉(zhuǎn)化為有向圖上的擴(kuò)散過程，并引入了擴(kuò)散卷積循環(huán)神經(jīng)網(wǎng)絡(luò)（DCRNN），使用雙向隨機(jī)游走對空間依賴建模，使用循環(huán)神經(jīng)網(wǎng)絡(luò)捕獲時(shí)間的動(dòng)態(tài)性。最近越來越多的研究者利用時(shí)空圖卷積網(wǎng)絡(luò)（STGCN）[5-8]來解決交通領(lǐng)域的時(shí)間序列預(yù)測問題，使用卷積網(wǎng)絡(luò)對空間和時(shí)間依賴關(guān)系進(jìn)行建模。

在研究中發(fā)現(xiàn)，已有的模型無法明確捕獲交通網(wǎng)絡(luò)中目標(biāo)節(jié)點(diǎn)的不同鄰域節(jié)點(diǎn)對其的影響，同時(shí)基于循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN）的模型也無法完成長期預(yù)測中的時(shí)間依賴性。為了解決上述挑戰(zhàn)問題，本文給出一種高效的時(shí)空聚集方案來明確捕獲不同鄰域節(jié)點(diǎn)對目標(biāo)節(jié)點(diǎn)流量的影響，并疊加時(shí)間點(diǎn)的嵌入，進(jìn)而計(jì)算不同時(shí)間點(diǎn)之間的時(shí)間依賴性。與現(xiàn)有的流量預(yù)測模型相比，使用該方法可以顯著提高預(yù)測的性能。

1 交通路網(wǎng)時(shí)空定義

交通網(wǎng)絡(luò)用圖形G=V，E表示，其中V是表示交叉路口節(jié)點(diǎn)的集合，E∈RV×V是圖的鄰接矩陣，如果節(jié)點(diǎn)i和j通過道路連接，則Ei，j=1，否則為0。

每個(gè)節(jié)點(diǎn)還包含交通流量、速度、占用率等路口的某些特征。不同節(jié)點(diǎn)上的交通流量隨時(shí)間不斷變化，采集的時(shí)間點(diǎn)之間的間隔一般為10 s至5 min。設(shè)定節(jié)點(diǎn)u在時(shí)間點(diǎn)t處的交通特征表示為Iu∈Rd，其中d表示路口特征維度;I∈RV×d代表時(shí)間點(diǎn)t時(shí)所有節(jié)點(diǎn)的流量特征;時(shí)間點(diǎn)t處的圖表示為時(shí)間點(diǎn)圖G，所有時(shí)間點(diǎn)圖在結(jié)構(gòu)上彼此相同。流量預(yù)測框架采用一系列T時(shí)間點(diǎn)圖并將其節(jié)點(diǎn)特征I<1>，I<2>，……，I作為輸入，并預(yù)測在接下來的N個(gè)時(shí)間點(diǎn)O，O，……，O上的節(jié)點(diǎn)流量強(qiáng)度。

2 基于時(shí)空圖神經(jīng)網(wǎng)絡(luò)的交通預(yù)測方案

本節(jié)主要闡述利用時(shí)空圖神經(jīng)網(wǎng)絡(luò)進(jìn)行交通預(yù)測的方案，該方案可以有效地捕獲道路交叉節(jié)點(diǎn)之間的時(shí)空依賴關(guān)系。如圖1所示為簡化的交通流時(shí)空依賴關(guān)系示意圖。對此，設(shè)計(jì)了交通時(shí)空圖和位置編碼方案，分別用于執(zhí)行時(shí)空聚集和捕獲交通數(shù)據(jù)的周期性。在此基礎(chǔ)上還定義了兩種不同的時(shí)空聚集模型，即歷史模型和當(dāng)天模型，并給出了最終的嵌入和訓(xùn)練方法。交通預(yù)測方案的整體架構(gòu)如圖2所示，圖中以預(yù)測星期一早上8：00-9：00的交通流量為例，歷史模型取最近一周早上7：00-8：00的交通流數(shù)據(jù)，當(dāng)天模型取星期一早上7：00-8：00的交通流數(shù)據(jù)。

時(shí)空圖：為了捕獲交通節(jié)點(diǎn)中不同時(shí)間點(diǎn)之間復(fù)雜的時(shí)空依賴關(guān)系，在連續(xù)時(shí)間點(diǎn)圖的相同節(jié)點(diǎn)之間引入時(shí)間點(diǎn)連接邊（圖2），其中相同顏色的小圓圈表示相同的節(jié)點(diǎn)。為了學(xué)習(xí)節(jié)點(diǎn)的嵌入，在一個(gè)時(shí)空圖上執(zhí)行時(shí)空聚集，該圖由來自預(yù)測窗口的前T個(gè)時(shí)間點(diǎn)圖和時(shí)間點(diǎn)之間的連接邊所組成。

位置編碼：從一天中的不同時(shí)段提取大量的交通特征，需要在模型中對不同時(shí)間段的相對位置進(jìn)行編碼。為了遵循機(jī)器翻譯中廣泛使用的相對定位概念，本文使用具有正弦函數(shù)的位置編碼來提供不同時(shí)間點(diǎn)的位置信息。由于必須確保每天的正弦函數(shù)在當(dāng)天內(nèi)完成一個(gè)完整的周期，因此任何持續(xù)時(shí)間段都可以表示為正弦曲線的重復(fù)部分，如正弦曲線在每天上午的時(shí)間段（7：05-8：00）將具有相同的模式。當(dāng)然，還可能存在每周流量模式，如具有相同流量的特定日期，同時(shí)還需要查看模式是來自工作日還是來自周末。為了捕獲這種每周模式，增加一個(gè)每周完整的正弦函數(shù)。式（1）實(shí)現(xiàn)了最終的位置編碼。

M=sin2πt24×ds+sin2πt24×7×ds（1）

其中t表示給定的時(shí)間點(diǎn);ds表示1 h內(nèi)觀察到的數(shù)據(jù)樣本數(shù)。這個(gè)方法還可以擴(kuò)展到按月捕獲完整周期的正弦波。

時(shí)空聚集：本文設(shè)計(jì)了一種時(shí)空聚集方案，將空間和時(shí)間依賴性進(jìn)行編碼并嵌入到交通節(jié)點(diǎn)中，它具有三個(gè)組成部分，分別是空間依賴性建模、時(shí)間依賴性建模、時(shí)空嵌入連接建模。接下來將詳細(xì)介紹。

2.1 空間依賴性建模

在現(xiàn)實(shí)交通網(wǎng)絡(luò)中可以觀察到，所有高階鄰域?qū)τ谀繕?biāo)節(jié)點(diǎn)的重要性并不相同，因此應(yīng)該捕獲不同跳鄰域節(jié)點(diǎn)所攜帶的不同信息。式（2）表示在每個(gè)時(shí)間點(diǎn)圖中分別對不同鄰域中的節(jié)點(diǎn)執(zhí)行信息聚集。

Ik=G-1kNkI

Pu=∑Ki=1QkIi，u（2）

Ik表示時(shí)間點(diǎn)t處的第k跳鄰域中的度歸一化均值;其中Nk表示第k跳鄰域集;Nki，j=1僅當(dāng)節(jié)點(diǎn)i和j恰好相距k跳時(shí)，否則為0;Gk是Nk的度矩陣。

Pu表示節(jié)點(diǎn)u在時(shí)間點(diǎn)t處的空間嵌入，通過對距離節(jié)點(diǎn)u長達(dá)K跳的不同跳鄰域集的歸一化均值進(jìn)行加權(quán)聚集計(jì)算后獲得。其中Qk是可學(xué)習(xí)的權(quán)重參數(shù)，用來捕獲時(shí)間點(diǎn)t處的第k跳鄰域的影響，不同跳鄰域的顯式聚集嵌入有助于區(qū)分不同跳鄰域節(jié)點(diǎn)的流量強(qiáng)度對目標(biāo)節(jié)點(diǎn)的影響。

2.2 時(shí)間依賴性建模

為了捕獲不同時(shí)間點(diǎn)圖之間的時(shí)間依賴性，采用聚集較早時(shí)間點(diǎn)的時(shí)空嵌入來計(jì)算，Xu表示節(jié)點(diǎn)u在時(shí)間點(diǎn)t處的時(shí)間聚集依賴。計(jì)算方法如式（3）所示，其中Xu表示節(jié)點(diǎn)u在時(shí)間點(diǎn)i處的時(shí)間嵌入;Q是時(shí)間點(diǎn)i處的可學(xué)習(xí)權(quán)重;ReLU是神經(jīng)網(wǎng)絡(luò)的激活函數(shù)。

Xu=ReLU（∑t-1i=1（QXu）（3）

2.3 時(shí)空嵌入連接建模

把目標(biāo)節(jié)點(diǎn)和節(jié)點(diǎn)u的時(shí)空嵌入連接起來，計(jì)算出節(jié)點(diǎn)u在時(shí)間點(diǎn)t處的時(shí)空嵌入，表示為Xu。計(jì)算方法如式（4）所示。

Xu=ReLUQyIu||Pu||Xu+M（4）

其中Qy是時(shí)間點(diǎn)t處的可學(xué)習(xí)權(quán)重參數(shù);|表示向量拼接操作;而M表示時(shí)間點(diǎn)t處的位置編碼。在式（4）中，時(shí)間點(diǎn)t處的時(shí)間嵌入Xu捕獲了從第1個(gè)時(shí)間點(diǎn)到t-1個(gè)時(shí)間點(diǎn)的交通流量時(shí)間依賴性，而空間嵌入Pu捕獲了節(jié)點(diǎn)u的不同跳鄰域的信息。另外，通過將時(shí)間點(diǎn)t處的位置編碼值合并到節(jié)點(diǎn)嵌入中，還可以保留交通數(shù)據(jù)的周期性信息。交通數(shù)據(jù)的周期性特點(diǎn)又可以分類為每日模式、每周模式、每月模式等，大多數(shù)研究人員主要關(guān)注每日模式下的交通數(shù)據(jù)，在本文中采用兩種不同的模型，即當(dāng)天模型和歷史模型，從而實(shí)現(xiàn)更有效的學(xué)習(xí)交通模式。

在歷史模型中，設(shè)定最近a天，節(jié)點(diǎn)u在時(shí)間點(diǎn)t處的歷史交通特征表示為Ihu∈Ra，本文設(shè)置a=7來獲取一周交通數(shù)據(jù)的特征。當(dāng)天模型僅需考慮當(dāng)天時(shí)間點(diǎn)t的交通流量，使用Icu∈R來表示當(dāng)天交通特征。在加入歷史模型和當(dāng)天模型的數(shù)據(jù)后，最終的時(shí)空嵌入連接如式（5）所示。

XXFu=X<1>Hu||…||XHu||X<1>Cu||…||XCu

XFu=QF·XXFu（5）

式中：XHu和XCu分別表示節(jié)點(diǎn)u在時(shí)間點(diǎn)t處的歷史模型和當(dāng)天模型下的時(shí)空嵌入;QF為可學(xué)習(xí)權(quán)重參數(shù)。

3 實(shí)驗(yàn)結(jié)果分析

為了證明本文提出的模型的有效性，使用三個(gè)公開可用的美國公路交通數(shù)據(jù)集PeMSD4、PeMSD7和PeMSD8進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)機(jī)器是Windows10計(jì)算機(jī)（Intel Core i7-9 700處理器，內(nèi)存16 G），實(shí)驗(yàn)軟件使用Python3.9和深度學(xué)習(xí)框架MXNet1.5。為了報(bào)告不同模型之間的性能比較，選擇平均絕對誤差（MAE），均方根誤差（RMSE）和平均絕對百分比誤差（MAPE）作為評估指標(biāo)。實(shí)驗(yàn)結(jié)果如表1所示。

在表1中很容易觀察到，在PeMSD4、PeMSD7和PeMSD8三個(gè)評估指標(biāo)的預(yù)測中，本文的模型均優(yōu)于另外兩種模型。顯然，通過提出的時(shí)空圖神經(jīng)網(wǎng)絡(luò)嵌入方案，能夠更準(zhǔn)確地捕獲復(fù)雜的時(shí)空關(guān)系，從而取得了較好的性能。

4 結(jié)語

本文提出的時(shí)空嵌入模型可以匯總不同節(jié)點(diǎn)的空間相互關(guān)系，通過加權(quán)時(shí)空聚集方式獲取時(shí)間相關(guān)性，提高了交通流量周期性預(yù)測的效率和準(zhǔn)確率。由于測試數(shù)據(jù)集只包含流量數(shù)據(jù)，沒有考慮外部因素，實(shí)際的交通數(shù)據(jù)集還應(yīng)包括交通肇事、道路施工、大型活動(dòng)、極端天氣等，因此實(shí)驗(yàn)結(jié)果僅從單一維度進(jìn)行測試和驗(yàn)證，后續(xù)需要結(jié)合多維數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。

[1]徐冰冰，岑科廷，黃俊杰，等.圖卷積神經(jīng)網(wǎng)絡(luò)綜述[J].計(jì)算機(jī)學(xué)報(bào)，2020，43（5）：755-780.

[2]閆 旭，范曉亮，鄭傳潘，等.基于圖卷積神經(jīng)網(wǎng)絡(luò)的城市交通態(tài)勢預(yù)測算法[J].浙江大學(xué)學(xué)報(bào)（工學(xué)版），2020，54（6）：1 147-1 155.

[3]洪照雄.基于多圖神經(jīng)網(wǎng)絡(luò)的城市交通流預(yù)測方法[D].杭州：浙江工業(yè)大學(xué)，2020.

[4]W.Hamilton，Z.Ying，J.Leskovec.Inductive representation learning onlarge graphs[C].Advances in neural information processing systems，2017.

[5]馮 寧，郭晟楠，宋 超，等.面向交通流量預(yù)測的多組件時(shí)空圖卷積網(wǎng)絡(luò)[J].軟件學(xué)報(bào)，2019，30（3）：759-769.

[6]宋 超.時(shí)空網(wǎng)絡(luò)上的圖卷積模型及其應(yīng)用研究[D].北京：北京交通大學(xué)，2020.

[7]榮 斌，武志昊，劉曉輝，等.基于時(shí)空多圖卷積網(wǎng)絡(luò)的交通站點(diǎn)流量預(yù)測[J].計(jì)算機(jī)工程，2020，46（5）：26-33.

[8]金仲明.基于時(shí)空圖神經(jīng)網(wǎng)絡(luò)的交通預(yù)測[J].軟件和集成電路，2019（7）：36-37.