日常通勤中的規(guī)律往往相對容易挖掘，但交通狀況還會受很多其他因素影響，之前的研究主要利用通行時間作為特征，少量引入事件，不能很好地預測實際交通流量。

為解決這一問題，本文從高德導航引擎中獲取了「計劃中交通流量」，并將其擴充到機器學習模型當中。

計劃中交通流量來自導航數(shù)據(jù)，反映了用戶出行意圖中蘊含的未來交通流量。由于擁有海量用戶，高德地圖中的導航規(guī)劃數(shù)據(jù)能夠較為全面地反應正在發(fā)生的通行需求，并且信息粒度較事件級別的特征更精細。

具體來說，規(guī)劃的路線產(chǎn)生了計劃中交通流量，而計劃中交通流量可以用來指導對未來通行時間的預測。volf代表當前可獲取的導航路徑在f個時間步后在此路段產(chǎn)生的計劃中交通流量。計劃中交通流量的迅速飆升意味著即將到來的交通擁堵。

圖 1  北京某路段在2019年10月28日早高峰期間通行時間和計劃中交通流量

為了將交通流量這一異質(zhì)信號整合到通行時間預測模型當中，我們創(chuàng)新性地設計出一種域轉(zhuǎn)換器（domain transformer）結(jié)構(gòu)，用于將交通流量信息轉(zhuǎn)化為通行時間信息。

交通流理論中，路段的交通流量和車輛密度呈三角形曲線映射關系，而曲線的參數(shù)是因路段而異的。圖2展示了現(xiàn)實世界中的例子。為了利用這一轉(zhuǎn)換關系，我們設計了將流量轉(zhuǎn)化為通行時間的轉(zhuǎn)換器，該轉(zhuǎn)換器由兩層網(wǎng)絡構(gòu)成，分別用于提取全局共享信息和學習不同路段的精細化信息。

圖 2  四個不同路段的流量時間曲線

另一方面，由于交通網(wǎng)絡的非歐幾里得特性，我們利用圖卷積（graph convolution）結(jié)構(gòu)提取空間依賴性特征，并設計了一種新的鄰接矩陣用于更好地體現(xiàn)路段間的交通鄰近性。

在以往的研究中[6]，鄰接矩陣的權重只按距離衰減，并沒有考慮到路段間固有的交通鄰近性（圖 3 給出了距離近但交通狀態(tài)相差較大的例子）。為解決這一問題，我們設計了一種復合鄰接矩陣（compound adjacency matrix），在距離衰減的基礎上進一步引入了路段通行時間的協(xié)方差。

圖 3  相鄰道路間擁堵不一定會傳播

本文提出的混合時空圖卷積網(wǎng)絡（Hybrid Spatio-Temporal Graph Convolutional Network，H-STGCN）是綜合利用上述技術的交通預測框架。

在H-STGCN中，轉(zhuǎn)換器將未來交通流量信號轉(zhuǎn)化為通行時間信號。路段間參數(shù)共享的門控卷積用于提取時間依賴信息。

基于復合鄰接矩陣的圖卷積從合并后的通行時間信號中捕捉空間依賴信息。H-STGCN經(jīng)由端到端的訓練，可具備基于計劃中交通流量信息預測未來擁堵的能力。利用真實交通數(shù)據(jù)集進行實驗可驗證，H-STGCN的效果顯著優(yōu)于各種前沿模型。

混合時空圖卷積網(wǎng)絡，獨創(chuàng)域轉(zhuǎn)換器和復合鄰接矩陣

整體框架

圖 4 展示了H-STGCN的整體框架。模型輸入由兩個特征張量組成，理想未來流量和通行時間張量。和均包含三個維度：空間維度、時間維度、通道維度，分別對應路段、所使用的時間片和特征。

域轉(zhuǎn)換器（模塊a）首先將轉(zhuǎn)化為通行時間信號，輸出未來通行時間張量。接下來，兩個獨立的門控卷積（模塊b）分別作用于和的時間維度以提取更高層級的時域特征。

將每個路段視為一個節(jié)點，基于復合鄰接矩陣的圖卷積（模塊c）作用在合并（concatenation）后的信號上。兩個門控卷積繼續(xù)擴大時域上的感知范圍，并最終經(jīng)由一個全連接層（FC）輸出預測結(jié)果。

圖 4  H-STGCN模型框架   

模型輸入與數(shù)據(jù)處理

輸入特征張量的每個切片對應了一個單獨的時間片 （）。每個切片又由兩部分組成：理想未來流量和通行時間。

理想未來流量 。作為對真實未來流量這一無法獲取信息的近似，理想未來流量可以通過在線導航引擎獲取。圖 5 示意了高德導航系統(tǒng)的架構(gòu)。導航過程中，車輛每秒鐘與云服務器同步自身坐標，與此同時，為保證用戶獲取到最新的交通狀態(tài)信息，云服務器對ETA進行幾乎實時的持續(xù)更新。

圖 5  高德導航系統(tǒng)架構(gòu)示意

高德導航引擎中原始數(shù)據(jù)的形式為

其中是導航進程的索引號，是導航的發(fā)起時間，代表規(guī)劃路線中的第個路段，是到達的預估時間， 是路線中路段的總數(shù)量，是導航進程的總數(shù)量。ETA來自機器學習模型的預測（利用歷史軌跡等數(shù)據(jù)訓練得到）。算法 1 展示了從導航路線集合中推算理想未來流量的方法。

H-STGCN中，與預測時間窗口相對應的理想未來流量和歷史平均流量同時被輸入：

其中是路段的索引號。

通行時間 。通行時間通過完成地圖匹配的GPS點數(shù)據(jù)整合計算得到。H-STGCN中，通行時間及其與預測時間窗口相對應的歷史均值同時被用于模型的輸入：

其中是路段的索引號。

域轉(zhuǎn)換器

域轉(zhuǎn)換器由串聯(lián)的兩層網(wǎng)絡組成，即逐路段卷積（segmentwise  convolution）和路段間共享卷積（shared  convolution），圖 4 呈現(xiàn)了這一結(jié)構(gòu)。

圖 6  H-STGCN中的各種卷積運算

共享卷積。路段及時間片間參數(shù)共享的卷積層位于域轉(zhuǎn)換器的頂部，該卷積運算闡釋如圖 6a，旨在捕捉全局的三角形曲線映射關系。記這一層的輸入和輸出為與，則有：

其中為權重，為偏置項，為ELU（Exponential Linear Unit）激活函數(shù)。

逐路段卷積。為保證模型能夠充分提取精細到路段級別的特征，路段參數(shù)個性化的卷積層位于域轉(zhuǎn)換器的底部（共享卷積前面一層），該卷積運算闡釋如圖 6b。記這一層的輸入和輸出為與，則有：

其中，為權重，為偏置項，是ELU激活函數(shù)。

基于復合鄰接矩陣的圖卷積

復合鄰接矩陣。以往研究[6,7]中的鄰接矩陣假設節(jié)點間的接近性簡單地依距離衰減：

其中為路段與的最短路距離，控制衰減速率，為控制矩陣稀疏性的截斷閾值。我們將稱為迪杰斯特拉矩陣（Dijkstra matrix）。在很多場景下，單純的空間接近程度并不能反映真實的交通鄰近性。更具體而言，交通擁堵對交通分流的影響取決于鄰近路段的若干種屬性，包括道路等級、路況等?？梢姡瑩矶碌膫鞑ピ诳臻g上并不均勻。由此，我們提出了復合鄰接矩陣：

圖卷積 。我們將交通路網(wǎng)視為一個以路段為節(jié)點的圖。歸一化圖拉普拉斯（normalized graph Laplacian）矩陣和縮放變換的圖拉普拉斯（scaled graph Laplacian）矩陣分別表示為：

其中為單位陣，為復合鄰接矩陣，對角陣為的度矩陣（degree matrix），是的最大特征值。圖卷積層通過的切比雪夫多項式（Chebyshev polynomials）參數(shù)化。記這一層的輸入和輸出為

則：

其中，是切比雪夫多項式第階項，K是卷積核大小，為權重張量，為偏置項，是ELU激活函數(shù)。

時域門控卷積

如圖 6c 所示，路段間參數(shù)共享的一維卷積將輸入轉(zhuǎn)化為張量：

其中表示一維卷積運算符。是卷積核，是卷積核的大小，是輸入時序長度，是偏置項。和形狀相同、通道數(shù)均為。我們使用GLU（gated linear unit）進一步引入非線性：

“”表示哈達瑪積（Hadamard product）。

與STGCN的關系

時空圖卷積網(wǎng)絡（Spatio-Temporal Graph Convolutional Network，STGCN）[7]將空域圖卷積層和時域門控卷積層交替地進行堆疊以同時捕捉時間和空間的依賴性。將H-STGCN的流量特征分支和鄰接矩陣中的協(xié)方差項去掉，則H-STGCN退化為只有單個時空卷積塊（ST-Conv block）的STGCN模型。

模型訓練

數(shù)據(jù)擴充 。我們將高斯噪音疊加到流量通道中小于的值上，以提升模型的泛化能力。

優(yōu)化目標 。對于本文中的多時間步預測，我們使用L1損失函數(shù)：

其中是模型的輸出，為真值。

基于真實路況測試，各項指標均優(yōu)于傳統(tǒng)模型

數(shù)據(jù)集

 

實驗數(shù)據(jù)集W3-715和E5-2907，分別對應西三環(huán)附近的715個路段和東五環(huán)附近的2907個路段（如圖 7 所示）。數(shù)據(jù)集的時間跨度為2018年12月24日至2019年4月21日（其中包含的節(jié)假日被移除，共十周數(shù)據(jù)），保留的時段為每天的06:00至22:00。前八周數(shù)據(jù)作為訓練集，后兩周作為測試集。

                圖 7  實驗路網(wǎng)空間分布

 

對比模型

 

基線模型，包括歷史均值（HA）、線性回歸（LR）、GBRT、MLP、Seq2Seq、STGCN（包含單個時空卷積塊）。

 

用于對比實驗的變種模型。

 

• STGCN (Im)：換用復合鄰接矩陣的STGCN（用于和原始的迪杰斯特拉矩陣對比。
• H-STGCN (1)：將流量特征張量V全部設成1。

 

評價指標

 

我們在三種測試集上進行模型效果的比對：

 

• 全測試集（如4.1節(jié)中所描述）。
• 高流量路段的擁堵時期，用C表示。
• 高流量路段的突發(fā)擁堵時期，用尾綴NRC表示。

 

效果比較

 

表 1 展示了在全測試集、測試集C、測試集NRC上不同模型的表現(xiàn)。評估標準包括MAE（s/m）、MAPE（%）和RMSE（s/m）。H-STGCN在各項指標上均顯著優(yōu)于不同的對標模型，在突發(fā)擁堵的預測方面優(yōu)勢尤為明顯。

      

復合鄰接矩陣 。分析表 1 可知，和STGCN相比，STGCN (Im)在W3-715數(shù)據(jù)集上有著更低的MAE、MAPE，在E5-2907數(shù)據(jù)集上有著更低的MAE、MAPE及RMSE，證明了復合鄰接矩陣的有效性。圖 8 以E5-2907數(shù)據(jù)集為例，對不同鄰接矩陣進行可視化。圖中顏色代表的值為，(a)為迪杰斯特拉矩陣，(b)為協(xié)方差矩陣，(c)為復合鄰接矩陣。

 

圖 8 E5-2970的各種鄰接矩陣

未來流量特征和域轉(zhuǎn)換器。如表 1 所示，和STGCN (Im)相比，H-STGCN有著穩(wěn)定的更優(yōu)表現(xiàn)，從而證實了利用未來流量數(shù)據(jù)帶來的收益。由于域轉(zhuǎn)換器中逐路段卷積結(jié)構(gòu)的存在，H-STGCN的模型表達能力是強于STGCN (Im)的。為了消除這一影響以針對未來流量特征帶來的收益做更公平的分析，我們進一步將H-STGCN與H-STGCN (1)進行對比。

在測試集C、測試集NRC上，不難發(fā)現(xiàn)未來流量特征在對擁堵的預測上有顯著更優(yōu)的表現(xiàn)。如圖 9 所示，隨著預測時間跨度的拉長，未來流量特征帶來的收益會起主導作用。

 圖 9 測試集NRC上效果比對

為了更加直觀地對H-STGCN的原理加以剖析，我們這里展示一個突發(fā)擁堵預測的案例（如圖 10 所示）。這個案例來自2018年4月16日某一高速路段。GT代表真值，HA代表歷史均值，是個時間步以前對當前通行時間的預測值，是對應個時間步后的理想未來流量。

17:30至18:00擁堵加劇的階段，H-STGCN (1)提前多個時間步的預測結(jié)果和真值相比有明顯的時間滯后。相比之下，H-STGCN由于有理想未來流量中的信息，甚至有能力在30min以前就對擁堵有著準確的預測。

我們可以這樣理解這一現(xiàn)象：對應的曲線代表了對15min之后交通流量的近似推算，該曲線在17:15就開始拉升了?；趯Ш揭嬷兄挥挟斍皶r刻已經(jīng)發(fā)起的導航行程這一事實，實際的未來流量要比理想未來流量更高。所以，的飆升預示著有較大的交通流量正在涌來，這就使H-STGCN能夠在沒有歷史數(shù)據(jù)做參考的情況下預知未來的擁堵。

圖 10 突發(fā)擁堵預測案例

 

模型可擴展性

 

模型在W3-715和E5-2097兩數(shù)據(jù)集的預測時間不超過100ms。為了在實際線上應用場景中平衡推演效率和預測效果，我們將城市路網(wǎng)切分成最多包含幾千個路段的子路網(wǎng)，每個子路網(wǎng)在線上部署一個模型。

未來將在主動交通方面發(fā)揮重要作用

H-STGCN已在高德駕車路線的旅行時間預測（ETA）（見圖 11）中落地[9,10]，并將偏差嚴重的案例數(shù)量降低了15%。

 

H-STGCN首次以數(shù)據(jù)驅(qū)動的方式建模了用戶出行意圖與交通路況演化之間的相互作用，未來可以廣泛的應用在主動式的交通管理領域，例如智能紅綠燈調(diào)控[9]、智能道路收費系統(tǒng)[10]等。

               

圖 11 ETA預測結(jié)果的展示

 

本文提出了一種新的用于通行時間預測的深度學習框架：混合時空圖卷積網(wǎng)絡（H-STGCN），該框架利用從導航數(shù)據(jù)中推演出的計劃中交通流量提升模型效果。在真實場景數(shù)據(jù)集上進行的實驗證實H-STGCN和對標的模型相比取得了更優(yōu)的效果，在突發(fā)擁堵的預測上優(yōu)勢尤為明顯。

 

混合時空圖卷積網(wǎng)絡提供了一種將物理知識嵌入數(shù)據(jù)驅(qū)動模型的新范式，創(chuàng)新性地應用了復合鄰接矩陣和域轉(zhuǎn)換器結(jié)構(gòu)，很容易推廣到一般的時空預測任務當中，未來將在智能交通管理等領域發(fā)揮重要作用。

主要參考文獻：

[1] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. 2018. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting.

[2] YishengLv, YanjieDuan, WenwenKang, Zhengxi Li, Fei-Yue Wang, etal. 2015. Traffic flow prediction with big data: A deep learning approach. IEEE Trans. Intelligent Transportation Systems 16, 2 (2015), 865–873.

[3] Bing Yu, Haoteng Yin, and Zhanxing Zhu. 2018. Spatio-Temporal Graph Convolutional Neural Network: A Deep Learning Framework for Traffic Forecasting. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI).

[4] JingruiHe, WeiShen, Phani Divakaruni, Laura Wynter, and Rick Lawrence. 2013. Improving Traffic Prediction with Tweet Semantics. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI). 1387–1393.

[5] Binbing Liao, Jingqing Zhang, Chao Wu, Douglas McIlwraith, Tong Chen, Shengwen Yang, Yike Guo, and Fei Wu. 2018. Deep Sequence Learning with Auxiliary Information for Traffic Prediction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM.

[6] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. 2018. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting.

[7] Bing Yu, Haoteng Yin, and Zhanxing Zhu. 2018. Spatio-Temporal Graph Convolutional Neural Network: A Deep Learning Framework for Traffic Forecasting. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI).

[8] Moshe Ben-Akiva, Michel Bierlaire, Haris Koutsopoulos, and Rabi Mishalani. 1998. DynaMIT: A simulation-based system for traffic prediction. In DACCORD Short Term Forecasting Workshop. Delft, The Netherlands, 1–12.

[9] Wei, H., Zheng, G., Yao, H. and Li, Z., 2018. Intellilight: A reinforcement learning approach for intelligent traffic light control. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.

[10] https://en./wiki/Congestion_pricing