金高銘，劉 安，孫玉娥，于金剛

1(蘇州大學 計算機科學與技術學院，江蘇 蘇州 215006)

2(蘇州大學 軌道交通學院，江蘇 蘇州 215137)

3(中國科學院 沈陽計算技術研究所，沈陽 110168)

E-mail：anliu@suda.edu.cn

1 引 言

交通狀況預測在許多城市計算系統(tǒng)中發(fā)揮著重要作用，如道路規(guī)劃應用和交通擁堵控制系統(tǒng)等.但由于道路網絡上的大多數交通數據(如交通流量和速度)受到復雜時空因素的影響，交通預測具有很大的挑戰(zhàn)性.交通預測的目的是利用道路網絡上觀測到的歷史交通數據來預測未來的交通狀態(tài).現(xiàn)有工作中研究的歷史交通數據類型?？煞譃閮纱箢悾焊咚俟穫鞲衅鲾祿?，例如PeMS數據集[1-3]；城市交通數據，例如Taxi-NYC數據集[4-7].高速公路傳感器數據通常是由數十個傳感器在一段時間內的歷史記錄組成，包含了車流量的大小信息.而城市交通數據通常采集自電子應用程序，常見形式是出租車訂單，包含了起止位置以及時間.除數據本身形式的不同，兩者對地理空間的依賴上也有較大差別.高速公路的空間構成相對較簡單，而且車流通常只會在高速公路網絡中流動；城市區(qū)域中路網較為復雜，車流的分布較為隨機.本文將主要關注城市交通數據，從而研究復雜的城市路網對交通預測的影響，而非較為簡單的高速公路網.

近年來相關工作通常將交通預測建模為圖問題，主要是由于路網構成了天然的非歐幾里得圖[3]，其中道路或路口可被視為圖節(jié)點.然而，現(xiàn)實世界中的路網通常包含了大量的道路，導致了圖的巨大化和復雜化.目前大多數研究都使用了簡化的自定義圖作為替代方案.例如現(xiàn)有工作常使用均勻網格或主干道路來將整個路網劃分成多個區(qū)域[8]，并將這些區(qū)域視為圖節(jié)點，從而稀疏化大規(guī)模路網.如圖1左側所示，整個城市地圖被劃分為多個區(qū)域，而這些區(qū)域中的每一個都會成為圖中的節(jié)點，節(jié)點之間的鄰接關系由這些區(qū)域在真實地理空間的相鄰關系決定；圖1右側為底層復雜路網按照所屬區(qū)域上色后得到的圖像，其中每條道路可以視為一個節(jié)點，共同構成了一個復雜的路網圖.在工作[4-7]中，歷史交通數據由簡化圖之上的觀察結果組成，受到隱馬爾科夫模型的啟發(fā)，本文將區(qū)域節(jié)點構成的簡化圖稱為觀測圖，將道路節(jié)點構成的復雜圖稱為隱藏圖.隱藏圖中的各類隱藏狀態(tài)會隨著時間的流逝而變化，體現(xiàn)為觀測圖上的各種特征的不斷變化.

圖1 出租車區(qū)域與底層分區(qū)域后路網對比Fig.1 Taxi zones vs partitioned road network

目前大多數工作只關注上層的觀測圖，而忽略了下層的隱藏圖.具體來說，在利用圖神經網絡(Graph Neural Network，GNN)捕獲區(qū)域間的空間相關性時，現(xiàn)有的方法[4-7]通常使用基于距離的啟發(fā)式規(guī)則來構建鄰接矩陣，描述區(qū)域之間的鄰接性.然而，對于許多交通特征(如流量或速度)而言，對區(qū)域之上的觀察結果只是區(qū)域中隱藏數據的簡單聚合.這意味著當兩個區(qū)域在空間維度上相鄰但在路網維度上相距較遠時，人工構建的鄰域矩陣將引入明顯的噪聲.

圖2對觀測圖和隱藏圖之間的關系進行了說明.上方為觀測圖，由a，b，c，d共4個區(qū)域構成，下方的隱藏圖由代表道路的線段組成.其中深色和淺色柱狀圖分別代表了駛入某個區(qū)域/道路的車流量和駛出某個區(qū)域/道路的車流量.觀測圖中的柱狀圖是由下方隱藏圖中對應區(qū)域的流量疊加得到.如圖2中所示，區(qū)域d與c共享一條道路，同時與b共享4條道路，盡管它們在地理空間上都是相鄰的，但很有可能區(qū)域b中的交通狀況會對c造成更多影響.這種不同的影響在人工構造的鄰接矩陣中很難被描述，導致了額外的噪聲被不可避免的引入到預測過程中.此外，注意力機制[9]常常被用于描述源信息集合上的重要性分布，但由于在觀測圖與隱藏圖之間數十倍的規(guī)模差距，現(xiàn)有的注意力機制很難被直接應用于描述隱藏圖中節(jié)點如何影響觀測圖節(jié)點.

圖2 觀測圖和隱藏圖Fig.2 Observed and hidden graph

綜上所述，現(xiàn)有工作的不足總結如下；1)現(xiàn)有工作通常使用自定義的區(qū)域圖來建模問題，這導致了人工噪聲的引入；2)由于路網的龐大和復雜，直接使用底層路網圖來建模問題非常困難；3)現(xiàn)有的注意力機制無法很好的幫助提高預測性能.

為了解決上述問題，本文提出了一種新的模型，即區(qū)域-道路時空圖網絡(Region to Road Spatial-Temporal Graph Networks，R2RSTGN)，通過同時學習觀測區(qū)域圖和隱藏道路網絡圖之間的時空相關性來預測交通狀況.本文的模型被設計成一個編碼器-解碼器結構.在編碼器模塊中采用壓縮的多頭注意機制(Compressed Multi-head Attention，CMA)來測量觀測圖和隱藏圖之間的相關性.CMA分別考慮隱藏路網圖的靜態(tài)和動態(tài)特征來捕捉上下層圖之間的關系.在CMA的幫助下，模型計算了輸入特征和道路維度注意力的隱藏表示，并將注意力作為殘差用于解碼器模塊.在解碼器模塊中，模型使用序列模型將聚集的隱圖特征作為觀測圖的輸出進行預測.

綜上所述，本文中做出了以下貢獻：

1)將交通預測問題的數據結構建模為觀察圖和隱藏圖，使用細粒度的真實道路網絡來提高預測性能.

2)設計了一種注意力壓縮機制來學習觀察圖和隱藏圖之間的靜態(tài)和動態(tài)相關性，并提供了一個可解釋的預測結果.

3)在兩個真實的數據集上進行了實驗.實驗結果表明，對比其他同類工作，本文模型具有更優(yōu)的預測性能.

本文的其余部分組織如下：第2部分介紹相關工作；第3部分定義了具有圖結構的流量預測問題；第4部分介紹模型細節(jié)；第5部分給出了實驗結果以及分析；第6部分總結全文.

2 相關工作

2.1 時空預測

交通預測已經被廣泛研究了數十年.與早期工作中經常出現(xiàn)的如自回歸綜合移動平均法(ARIMA)和支持向量回歸法(SVR)相比，基于長短期記憶神經網絡(LSTM)及其變體的深度學習模型取得了令人矚目的成就.LSTM[10]在學習時間相關性方面表現(xiàn)出優(yōu)越的性能.ST-ResNet[11]使用基于卷積的殘差網絡對人群流量的周期時間特征進行建模.DeepTransport[12]使用多個LSTM層，從大而異構的數據中學習人類移動和運輸模式.MDL[11]將卷積神經網絡(CNN)應用于節(jié)點網絡和邊網絡，并共同訓練以理解其中的相關性.ST-3DNet[4]創(chuàng)新性的引入了3D卷積，可以有效地從空間和時間維度提取特征，分別使用了兩個組件來建模局部時間模式和長期時間模式.

2.2 圖神經網絡與注意力機制

近年來，許多工作利用圖卷積神經網絡(Graph Convolutional Neural Networks，GCNNs)對圖結構數據進行了大量的研究.ST-GCN[2]首先使用GCNNs捕獲交通預測問題的非歐空間相關性.LRGCN[13]提出了一種新的路徑嵌入方法，并考慮了時間相鄰圖之間的時間依賴性.STDN[9]在流量預測中使用周期性轉移注意力來處理長期的時間轉移.GMAN[3]應用注意機制來模擬歷史和未來時間步之間的關系.DSAN[14]提出了多空間注意機制來過濾無關噪聲.以上所有利用GCNNs對城市交通數據的研究都沒有考慮到底層復雜的道路網絡，而只是將地圖劃分為不同的區(qū)域作為節(jié)點來構造圖，故無法直接應用解決本文的問題.

3 問題定義

如圖1所示，本文將城市的整個路網劃分為若干區(qū)域，此時可以得到兩個圖.

定義1.(觀測圖)Go=〈Vo，Eo〉，其中v∈Vo為區(qū)域，e=(u，v)∈Eo表示區(qū)域u與區(qū)域v在地理空間上相鄰.顯然圖Go是無向圖.

定義2.(隱藏圖)Gh=〈Vh，Eh〉，其中v∈Vh為道路，e=(u，v)∈Eh表示道路u與道路v連通.出于簡化目的，此處的聯(lián)通不考慮方向性，故圖Gh也是無向圖.

與文獻[4-7]的做法類似，本文將時間劃分為時間片，并統(tǒng)計每個時間片上車流的信息，于是得到轉移流與聚合流的定義：

定義3.(轉移流)用Xtj∈|Vo|×|Vo|來表示在時間片tj中觀測圖Go上的輸入信號.具體來說，Xtj中每個元素表示了從區(qū)域u出發(fā)且停止于區(qū)域v的車流量.

定義4.(聚合流)用Ytk∈|Vo|×2來表示在時間片tk中觀測圖Go上的觀測信號.具體來說，表示了在此時間片內所有從區(qū)域v出發(fā)的流量；表示了在此時間片內所有到達區(qū)域v的流量.

利用上述定義，可以將交通預測的問題描述為：

4 解決方案

4.1 框架總述

R2RSTGN的架框架圖3所示.首先，模型通過編碼器模塊學習從觀察信號到隱藏狀態(tài)的映射函數.編碼器模塊采用壓縮多頭注意力(CMA)來同時考慮靜態(tài)道路嵌入與動態(tài)時間嵌入.然后，本文使用了帶殘差的注意力機制來捕獲和傳遞復雜的時空相關性，最后使用GCN來聚合最終輸出.

圖3 模型框架Fig.3 Architecture of R2RSTGN

4.2 帶壓縮注意力機制的編碼器

由于交通工具的運行被限制在實際的交通網絡之上(如汽車專用道和自行車專用道)，區(qū)域間的交通流量很大程度實際上是由路網本身的結構決定的.所以一種非常自然的想法是利用注意力機制來描述交通流量對道路的傾向性.然而，區(qū)域網絡與道路網絡之間數十倍以上的體量差距，使得在兩者間共享的注意力機制的訓練低效且困難.

為了解決這個問題，本文提出了壓縮的多頭注意力機制CMA.在CMA中，模型使用了圖卷積神經網絡來提取區(qū)域網絡以及道路網絡的空間特征.

給定一個無向圖G，其對稱規(guī)范化拉普拉斯矩陣由Lsys=D-1/2LD-1/2∈R|V|×|V|，L=D-A給出，其中D，A，V分別是圖G的對角度矩陣，鄰接矩陣和頂點集.一個基本的圖卷積運算表示如下：

其中U∈R|V|×|V|是Lsys的特征向量矩陣，∧是Lsys的特征值的對角矩陣，Θ(∧)是可學習的卷積核，x，y是輸入輸出圖信號.出于精度和效率方面的考慮[15]，本文在具體實現(xiàn)過程中使用Cheby-Net變體.記圖G和信號X之間的GCN操作為G?x.

道路嵌入R∈R|Vh|×Rh表示了道路在路網圖結構中所擁有的空間信息，是模型學習的目標之一，其初始值由隨機初始化得到，并在每輪訓練之后更新.

R′=Gh?R

(1)

(2)

其中vo∈Vo表示觀測圖中某一個區(qū)域節(jié)點，T表示矩陣的轉置，Mv∈R|Vh|為遮罩矩陣用于過濾掉無效信息，只保留對應的區(qū)域信息，定義為：

(3)

需要說明的是，對于所有區(qū)域，R′在一輪訓練過程中只需要被計算一次，原因是靜態(tài)道路特征不應該隨時間變化.

(4)

其中σ是非線性激活函數，‖是廣播拼接操作.

接下來，對于一個在時間片tj中的觀測區(qū)域vo，可以通過對所有的動態(tài)道路隱狀態(tài)采用K并行多頭注意力機制來得到一個帶權和，以作為其空間隱含表示svo，tj：

(5)

(6)

注意力得分由區(qū)域的隱藏狀態(tài)和動態(tài)道路隱藏狀態(tài)使用softmax計算：

(7)

其中相關性函數score采用了[9]的做法，利用縮放點積來計算：

(8)

4.3 道路級注意力機制

(9)

(10)

(11)

接下來利用道路維度注意力可以計算殘差，用于給后續(xù)的解碼器模塊傳遞無損的原始信息.不同于傳統(tǒng)的直接拼接殘差，從原始輸入中挑選更加重要的部分可以減少引入的誤差.具體來說，本文使用了一個閾值Q來過濾了那些不重要的路段信息，并將剩余部分組成了殘差residualvo，tj∈R|Vo|×Rh：

(12)

(13)

有關閾值Q的選取會在實驗部分討論.

4.4 解碼器

基于上述CMA模塊，模型通過捕捉空間特征得到空間表.接下來，通過使用帶有道路注意力的順序模型來捕獲時域中的相關性.

由CMA得到空間表示s=sv1，sv1，…，sv|Vo|，其中svo，tj∈svo是區(qū)域vo在時間片tj上的空間表示.在這里，首先應用門控循環(huán)單元(Gated Recurrent Unit，GRU)[16]，定義如下：

(14)

zvo，tj=σ(Wzsvo，tj+Uzhvo，tj-1)

(15)

(16)

rvo，tj=σ(Wrsvo，tj+Urhvo，tj-1)

(17)

(18)

(19)

5 實 驗

5.1 數據集

本文在兩個大規(guī)模公開真實數據集上評估模型：

· Taxi-NYC來自出租車數據平臺NYC-TLC(1)https：//www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page.使用的是從2019年3月1日～2019年4月31日之間位于紐約市曼哈頓的出租車訂單記錄.記錄中包含訂單起始時間和訂單起始地點.前40天作為訓練數據，其余20天作為測試數據.Taxi-NYC還提供了如圖1所示的出租車區(qū)域地理信息文件，其中包含69個出租車區(qū)域及其邊界信息.

· Bike-NYC來自紐約出租車共享系統(tǒng)citibike(2)https：//www.citibikenyc.com/system-data獲得.使用的是從2019-03-01～2019-04-31年間在紐約市曼哈頓收集的記錄.記錄上有起止時間和起止地點.前40天作為訓練數據，其余20天作為測試數據.

· 使用來自紐約市曼哈頓的OpenStreetMap(OSM)(3)https：//www.openstreetmap.org的地圖數據.原始地圖數據包含9884條道路.

5.2 預處理

首先檢查了出租車區(qū)域的鄰接性，并選擇了其中的64個，因為其他5個區(qū)域在地理空間上沒有任何一個區(qū)域與其相鄰.然后根據與這些區(qū)域的所屬關系從所有道路中保留了8141條道路，并劃分為64組，如圖1左側所示.最后，將NY-TaxiC和NYC-Bike中的所有出行記錄按照區(qū)域圖和時間間隔聚合為2880行64×64列的轉移流數據和2880行64列的聚合流數據.需要注意的是，OSM的原始道路圖是一個有4579個十字路口作為頂點和9884個道路作為邊的圖.但由于本文重點關注的是道路特征，因此將原始圖中的邊(即道路)構建為頂點，將頂點(即十字路口)構建為邊，將原始圖轉換為新的線狀圖[17].轉換方法的研究已經比較成熟了，故本文省略了轉換的細節(jié).

5.3 實驗參數設置討論

遵循已有的相關工作[14]，本文選取12作為輸入和輸出觀測序列的長度，選取6小時作為時間片的大小.在訓練過程中采用Adam優(yōu)化器[15]，初始學習率為0.001.

如數據預處理部分介紹的，觀測圖頂點數為|Vo|=64，隱藏圖頂點數為|Vh|=8141.使用Rh=128作為道路隱向量的嵌入長度，注意力頭數量為K=4.

本文用以下基線方法評價R2RSTGN：1)自回歸綜合移動平均(Auto-Regressive Integrated Moving Average，ARIMA)；2)支持向量回歸(Support Vector Regression，SVR)；3)前饋長短期記憶網絡(FC-LSTM)是一種采用全連接LSTM層的編譯碼模型，曾在序列預測方面取得了突破進展；4)時空圖卷積網絡(Spatio-Temporal Graph Convolutional Network，STGCN)[2]采用了帶有卷積操作的卷積序列學習層；5)圖多注意網絡(Graph Multi-Attention Network，GMAN)[3]在編解碼器結構中應用圖多注意網絡；6)動態(tài)選擇注意力網絡(Dynamic Switch-Attention Network，DSAN)使用了多空間矩陣分解.對于ARIMA、SVR和FC-LSTM，本文使用了工作[7]中介紹的相同設置.對于模型STGCN、GMAN和DSAN，分別使用對應原文建議的默認設置.

5.4 實驗結果

對表1給出了模型在未來30分鐘(1步)、3小時(6步)、6小時(12步)中在Taxi-NYC和Bike-NYC數據集聚合流的預測結果.使用均方根誤差(Root Mean Squared Error RMSE)作為評價指標.從表中可以看到，深度學習方法比傳統(tǒng)的時間序列方法(ARIMA、SVR)表現(xiàn)得更好，因為傳統(tǒng)方法完全忽略了空間和其他復雜的上下文特征.

表1 不同方法間的預測性能對比Table 1 Prediction performance comparison of different approaches

FC-LSTM使用了長短期記憶網絡，相比傳統(tǒng)模型能在時間維度上捕捉更多的相關性；STGCN創(chuàng)新性地將圖卷積應用于交通預測問題，但是缺少過濾機制的殘差傳遞過程使其易受數據中噪聲影響.具有復雜架構的模型(GMAN、DSAN、R2RSTGN)在STGCN的基礎上加入了注意力機制來學習空間和時間特征之間的綜合關系，明顯優(yōu)于其他模型.本文提出的R2RSTGN比所有對比模型取得了更好的預測性能，在兩個數據集上都取得了最低的RMSE.

5.5 有效性分析

本節(jié)研究了CMA模塊在R2RSTGN模型中的有效性.R2RSTGN列表的一些變體如下：

1)R2R-FNN：在這種變體中，整個CMA模塊被兩個簡單的前饋網絡所取代.第1個參數為w∈(Rh+Th)×|Vo|的網絡將道路嵌入和時間嵌入的連接映射為動態(tài)嵌入.第2個參數W∈2|Vo|×|Vo|的網絡將輸入X和動態(tài)道路嵌入的連接映射到后續(xù)隱藏嵌入.

2)R2R-NGCN：這個變體的區(qū)別是所有CMA中的GCN操作都被去除.

3)R2R-NR：在這個變體中從CMA中計算得到的道路注意力不會通過殘差進入后續(xù)的解碼器.

上述幾個變體的表現(xiàn)如圖4與圖5所示.R2R-FNN由于使用了簡單的全連接層來替代CMA，導致完全忽視了路網的空間結構，在所有變體中表現(xiàn)最差.其次較差的是R2R-NGCN，證明了圖卷積運算對于提取空間特征是必不可少的.R2R-NR的性能比R2RSTGN稍差，主要是由于缺少了帶過濾的殘差機制.

圖4 不同變體的預測性能對比Fig.4 Variants performance comparision

5.6 道路注意力分析

道路的注意力得分可以顯示某個時間片上道路的重要性，選取了2019年4月3日中3個時間段上模型輸出的注意力得分進行了可視化，如圖5所示.

圖中的注意力值歸一化到[0，1]之間，表示當前時間片上每條道路對整個觀測的相對重要性.圖中顏色越深代表其道路獲得注意力值越高.可以觀察到圖5(a)中的道路整體顏色比圖5(c)的要深，雖然圖5(a)對應的是午夜時間，應該是比較空曠的.一個重要的原因是顏色深淺表明了相對的重要性，而不是交通熱度；在午夜道路整體更加空曠，導致了許多路段的之間的差異性減少從而體現(xiàn)的同樣重要.另一方面，圖5(c)的注意力圖在高峰時段的顏色更加不均勻的，顯示少量路段具有較高的重要性，一個合理的推斷是當時很少有關鍵道路對整個地圖上的觀察有顯著的影響.這些數據為模型預測提供了可解釋性，有助于路線規(guī)劃等問題的解決.

圖5 不同時段的道路注意力可視化Fig.5 Roads attention visualization at different times

5.7 模型參數探討

在接下來的實驗中，本文研究了超參數對模型的影響.首先，對控制道路嵌入生成殘差的閾值Q進行實驗.圖6(a)給出了Taxi-NYC和Bike-NYC的1步(30分鐘)預測的RMSE.可以觀察到，RMSE都隨著閾值的增加而減少，并且在閾值增加到1之前達到了最小值.當RMSE達到Taxi-NYC和Bike-NYC的最小值時，閾值Q約為0.7和0.6.可以得到以下幾個推論：1)在閾值設置為0時，殘差部分退化為最簡單的連接殘差，閾值設置為1時，殘差完全消失，而采用一個適當的過濾閾值能有效提高模型預測的精度，說明原始數據中攜帶了較多噪聲，不適合不加區(qū)分的生成殘差；2)出租車模型中最優(yōu)閾值的選取相比自行車模型更高，這是因為駕駛路網有更高的擁堵發(fā)生率，所以每條道路的重要性更不均衡.實際上，閾值可以看作是一種噪聲濾波器，模型用它來去除低頻噪聲，提取路網的重要特征.本文還對道路嵌入的隱藏狀態(tài)大小進行了實驗，結果如圖6(b)所示，道路嵌入的高維數對預測更有效.隨著隱藏維度的增大，精度提高逐步減少但模型訓練時間快速增加，因此本文使用H=150作為隱藏維度的大小.

圖6 參數Q、H對預測性能的影響Fig.6 Performances by Q and H

6 結論以及未來工作

本文通過將空間數據結構建模為觀察圖和隱藏圖，研究了流量預測問題，并提出了一種新穎的區(qū)域-道路時空圖網絡模型R2RSTGN來解決此問題.為了捕捉兩個圖之間的相互作用，模型使用一個具有圖卷積運算的壓縮注意力模塊來提取空間特征.同時，利用閾值結合道路維度注意力來濾除原始輸入數據中的噪聲從而產生殘差，并將殘差連接到序列解碼器以提高模型預測精度.在兩個真實數據集上的大量實驗證明了R2RSTGN的性能.

下一步的工作包括探索更有效的方法來增強道路嵌入表示和預測性能.另外，更復雜的圖網絡變體也值得研究.