本文解讀的是KDD 2020 論文《Hybrid Spatio-Temporal Graph Convolutional Network: Improving Traffic Prediction with Navigation Data》，作者來自高德機器學習團隊。
作者 | 高德機器學習團隊
編輯 | 叢 末
論文下載地址：https://arxiv.org/abs/2006.12715
1
導讀
時空預測在天氣預報、運輸規劃等領域有著重要的應用價值。交通預測作為一種典型的時空預測問題，具有較高的挑戰性。以往的研究中主要利用通行時間這類交通狀態特徵作為模型輸入，很難預測整體的交通狀況，本文提出的混合時空圖卷積網絡，利用導航數據大大提升了時空預測的效果。
日常通勤中的規律往往相對容易挖掘，但交通狀況還會受很多其他因素影響，之前的研究主要利用通行時間這類交通狀態作為特徵，少量研究引入事件，不能很好地預測實際交通流量。
為解決這一問題，本文從高德導航引擎中獲取了「計劃中交通流量」，並將其擴充到機器學習模型當中。
計劃中交通流量來自導航數據，反映了用戶出行意圖中蘊含的未來交通流量。由於擁有海量用戶，高德地圖中的導航規劃數據能夠較為全面地反應正在發生的通行需求，並且信息粒度較事件級別的特徵更精細。
具體來說，規劃的路線產生了計劃中交通流量，而計劃中交通流量可以用來指導對未來通行時間的預測。volf代表當前可獲取的導航路徑在f個時間步後在此路段產生的計劃中交通流量。計劃中交通流量的迅速飆升意味著即將到來的交通擁堵。
圖 1 北京某路段在2019年10月28日早高峰期間通行時間和計劃中交通流量
為了將交通流量這一異質信號整合到通行時間預測模型當中，我們創新性地設計出一種域轉換器（domain transformer）結構，用於將交通流量信息轉化為通行時間信息。
交通流理論中，路段的交通流量和車輛密度呈三角形曲線映射關係，而曲線的參數是因路段而異的。圖2展示了現實世界中的例子。為了利用這一轉換關係，我們設計了將流量轉化為通行時間的轉換器，該轉換器由兩層網絡構成，分別用於提取全局共享信息和學習不同路段的精細化信息。
圖 2 四個不同路段的流量時間曲線
另一方面，由於交通網絡的非歐幾裡得特性，我們利用圖卷積（graph convolution）結構提取空間依賴性特徵，並設計了一種新的鄰接矩陣用於更好地體現路段間的交通鄰近性。
在以往的研究中[6]，鄰接矩陣的權重只按距離衰減，並沒有考慮到路段間固有的交通鄰近性（圖 3 給出了距離近但交通狀態相差較大的例子）。為解決這一問題，我們設計了一種複合鄰接矩陣（compound adjacency matrix），在距離衰減的基礎上進一步引入了路段通行時間的協方差。
圖 3 相鄰道路間擁堵不一定會傳播
本文提出的混合時空圖卷積網絡（Hybrid Spatio-Temporal Graph Convolutional Network，H-STGCN）是綜合利用上述技術的交通預測框架。
在H-STGCN中，轉換器將未來交通流量信號轉化為通行時間信號。路段間參數共享的門控卷積用於提取時間依賴信息。
基於複合鄰接矩陣的圖卷積從合併後的通行時間信號中捕捉空間依賴信息。H-STGCN經由端到端的訓練，可具備基於計劃中交通流量信息預測未來擁堵的能力。利用真實交通數據集進行實驗可驗證，H-STGCN的效果顯著優於各種前沿模型。
2
混合時空圖卷積網絡，獨創域轉換器和複合鄰接矩陣
1、整體框架
圖 4 展示了H-STGCN的整體框架。模型輸入由兩個特徵張量組成，理想未來流量和通行時間張量。和均包含三個維度：空間維度、時間維度、通道維度，分別對應路段、所使用的時間片和特徵。
域轉換器（模塊a）首先將轉化為通行時間信號，輸出未來通行時間張量。接下來，兩個獨立的門控卷積（模塊b）分別作用於和的時間維度以提取更高層級的時域特徵。
將每個路段視為一個節點，基於複合鄰接矩陣的圖卷積（模塊c）作用在合併（concatenation）後的信號上。兩個門控卷積繼續擴大時域上的感知範圍，並最終經由一個全連接層（FC）輸出預測結果。
圖 4 H-STGCN模型框架
2、模型輸入與數據處理
輸入特徵張量的每個切片對應了一個單獨的時間片 （）。每個切片又由兩部分組成：理想未來流量和通行時間。
理想未來流量。作為對真實未來流量這一無法獲取信息的近似，理想未來流量可以通過在線導航引擎獲取。圖 5 示意了高德導航系統的架構。導航過程中，車輛每秒鐘與雲伺服器同步自身坐標，與此同時，為保證用戶獲取到最新的交通狀態信息，雲伺服器對ETA進行幾乎實時的持續更新。
圖 5 高德導航系統架構示意
高德導航引擎中原始數據的形式為
其中是導航進程的索引號，是導航的發起時間，代表規劃路線中的第個路段，是到達的預估時間， 是路線中路段的總數量，是導航進程的總數量。ETA來自機器學習模型的預測（利用歷史軌跡等數據訓練得到）。算法 1 展示了從導航路線集合中推算理想未來流量的方法。
H-STGCN中，與預測時間窗口相對應的理想未來流量和歷史平均流量同時被輸入：
其中是路段的索引號。
通行時間 。通行時間通過完成地圖匹配的GPS點數據整合計算得到。H-STGCN中，通行時間及其與預測時間窗口相對應的歷史均值同時被用於模型的輸入：
其中是路段的索引號。
3、域轉換器
域轉換器由串聯的兩層網絡組成，即逐路段卷積（segmentwise convolution）和路段間共享卷積（shared convolution），圖 4 呈現了這一結構。
圖 6 H-STGCN中的各種卷積運算
共享卷積。路段及時間片間參數共享的卷積層位於域轉換器的頂部，該卷積運算闡釋如圖 6a，旨在捕捉全局的三角形曲線映射關係。記這一層的輸入和輸出為與，則有：
其中為權重，為偏置項，為ELU（Exponential Linear Unit）激活函數。
逐路段卷積。為保證模型能夠充分提取精細到路段級別的特徵，路段參數個性化的卷積層位於域轉換器的底部（共享卷積前面一層），該卷積運算闡釋如圖 6b。記這一層的輸入和輸出為與，則有：
其中，為權重，為偏置項，是ELU激活函數。
4、基於複合鄰接矩陣的圖卷積
複合鄰接矩陣。以往研究[6,7]中的鄰接矩陣假設節點間的接近性簡單地依距離衰減：
其中為路段與的最短路距離，控制衰減速率，為控制矩陣稀疏性的截斷閾值。我們將稱為迪傑斯特拉矩陣（Dijkstra matrix）。在很多場景下，單純的空間接近程度並不能反映真實的交通鄰近性。更具體而言，交通擁堵對交通分流的影響取決於鄰近路段的若干種屬性，包括道路等級、路況等。可見，擁堵的傳播在空間上並不均勻。由此，我們提出了複合鄰接矩陣：
圖卷積 。我們將交通路網視為一個以路段為節點的圖。歸一化圖拉普拉斯（normalized graph Laplacian）矩陣和縮放變換的圖拉普拉斯（scaled graph Laplacian）矩陣分別表示為：
其中為單位陣，為複合鄰接矩陣，對角陣為的度矩陣（degree matrix），是的最大特徵值。圖卷積層通過的切比雪夫多項式（Chebyshev polynomials）參數化。記這一層的輸入和輸出為
則：
其中，是切比雪夫多項式第階項，K是卷積核大小，為權重張量，為偏置項，是ELU激活函數。
5、時域門控卷積
如圖 6c 所示，路段間參數共享的一維卷積將輸入轉化為張量：
其中表示一維卷積運算符。是卷積核，是卷積核的大小，是輸入時序長度，是偏置項。和形狀相同、通道數均為。我們使用GLU（gated linear unit）進一步引入非線性：
「」表示哈達瑪積（Hadamard product）。
6、與STGCN的關係
時空圖卷積網絡（Spatio-Temporal Graph Convolutional Network，STGCN）[7]將空域圖卷積層和時域門控卷積層交替地進行堆疊以同時捕捉時間和空間的依賴性。將H-STGCN的流量特徵分支和鄰接矩陣中的協方差項去掉，則H-STGCN退化為只有單個時空卷積塊（ST-Conv block）的STGCN模型。
7、模型訓練
數據擴充。我們將高斯噪音疊加到流量通道中小於的值上，以提升模型的泛化能力。
優化目標 。對於本文中的多時間步預測，我們使用L1損失函數：
其中是模型的輸出，為真值。
3
基於真實路況測試，各項指標均優於傳統模型
1、數據集
實驗數據集W3-715和E5-2907，分別對應西三環附近的715個路段和東五環附近的2907個路段（如圖 7 所示）。數據集的時間跨度為2018年12月24日至2019年4月21日（其中包含的節假日被移除，共十周數據），保留的時段為每天的06:00至22:00。前八周數據作為訓練集，後兩周作為測試集。
圖 7 實驗路網空間分布
2、對比模型
基線模型，包括歷史均值（HA）、線性回歸（LR）、GBRT、MLP、Seq2Seq、STGCN（包含單個時空卷積塊）。
用於對比實驗的變種模型。
STGCN (Im)：換用複合鄰接矩陣的STGCN（用於和原始的迪傑斯特拉矩陣對比。H-STGCN (1)：將流量特徵張量V全部設成1。3、評價指標
我們在三種測試集上進行模型效果的比對：
全測試集（如4.1節中所描述）。高流量路段的擁堵時期，用C表示。高流量路段的突發擁堵時期，用尾綴NRC表示。4、效果比較
表 1 展示了在全測試集、測試集C、測試集NRC上不同模型的表現。評估標準包括MAE（s/m）、MAPE（%）和RMSE（s/m）。H-STGCN在各項指標上均顯著優於不同的對標模型，在突發擁堵的預測方面優勢尤為明顯。
複合鄰接矩陣 。分析表 1 可知，和STGCN相比，STGCN (Im)在W3-715數據集上有著更低的MAE、MAPE，在E5-2907數據集上有著更低的MAE、MAPE及RMSE，證明了複合鄰接矩陣的有效性。圖 8 以E5-2907數據集為例，對不同鄰接矩陣進行可視化。圖中顏色代表的值為
，(a)為迪傑斯特拉矩陣，(b)為協方差矩陣，(c)為複合鄰接矩陣。
圖 8 E5-2970的各種鄰接矩陣
未來流量特徵和域轉換器。如表 1 所示，和STGCN (Im)相比，H-STGCN有著穩定的更優表現，從而證實了利用未來流量數據帶來的收益。由於域轉換器中逐路段卷積結構的存在，H-STGCN的模型表達能力是強於STGCN (Im)的。為了消除這一影響以針對未來流量特徵帶來的收益做更公平的分析，我們進一步將H-STGCN與H-STGCN (1)進行對比。
在測試集C、測試集NRC上，不難發現未來流量特徵在對擁堵的預測上有顯著更優的表現。如圖 9 所示，隨著預測時間跨度的拉長，未來流量特徵帶來的收益會起主導作用。
圖 9 測試集NRC上效果比對
為了更加直觀地對H-STGCN的原理加以剖析，我們這裡展示一個突發擁堵預測的案例（如圖 10 所示）。這個案例來自2018年4月16日某一高速路段。GT代表真值，HA代表歷史均值，是個時間步以前對當前通行時間的預測值，是對應個時間步後的理想未來流量。
17:30至18:00擁堵加劇的階段，H-STGCN (1)提前多個時間步的預測結果和真值相比有明顯的時間滯後。相比之下，H-STGCN由於有理想未來流量中的信息，甚至有能力在30min以前就對擁堵有著準確的預測。
我們可以這樣理解這一現象：對應的曲線代表了對15min之後交通流量的近似推算，該曲線在17:15就開始拉升了。基於導航引擎中只有當前時刻已經發起的導航行程這一事實，實際的未來流量要比理想未來流量更高。所以，的飆升預示著有較大的交通流量正在湧來，這就使H-STGCN能夠在沒有歷史數據做參考的情況下預知未來的擁堵。
圖 10 突發擁堵預測案例
5、模型可擴展性
模型在W3-715和E5-2097兩數據集的預測時間不超過100ms。為了在實際線上應用場景中平衡推演效率和預測效果，我們將城市路網切分成最多包含幾千個路段的子路網，每個子路網在線上部署一個模型。
4
未來將在主動交通管理方面發揮重要作用
H-STGCN已在高德駕車路線的旅行時間預測（ETA）（見圖 11）中落地[9,10]，並將偏差嚴重的案例數量降低了15%。
H-STGCN首次以數據驅動的方式建模了用戶出行意圖與交通路況演化之間的相互作用，未來可以廣泛的應用在主動式的交通管理領域，例如智能紅綠燈調控[9]、智能道路收費系統[10]等。
圖 11 ETA預測結果的展示
本文提出了一種新的用於通行時間預測的深度學習框架：混合時空圖卷積網絡（H-STGCN），該框架利用從導航數據中推演出的計劃中交通流量提升模型效果。在真實場景數據集上進行的實驗證實H-STGCN和對標的模型相比取得了更優的效果，在突發擁堵的預測上優勢尤為明顯。
混合時空圖卷積網絡提供了一種將物理知識嵌入數據驅動模型的新範式，創新性地應用了複合鄰接矩陣和域轉換器結構，很容易推廣到一般的時空預測任務當中，未來將在智能交通管理等領域發揮重要作用。
主要參考文獻：
[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.wikipedia.org/wiki/Congestion_pricing