混合時空圖卷積網絡:更精準的時空預測模型

2020-12-22 騰訊網

時空預測在天氣預報、運輸規劃等領域有著重要的應用價值。交通預測作為一種典型的時空預測問題,具有較高的挑戰性。以往的研究中主要利用通行時間作為模型輸入,很難預測整體的交通狀況,本文提出的混合時空圖卷積網絡,利用導航數據大大提升了時空預測的效果(本文作者高德機器學習團隊,論文已被收錄到KDD2020)。

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

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

計劃中交通流量來自導航數據,反映了用戶出行意圖中蘊含的未來交通流量。由於擁有海量用戶,高德地圖中的導航規劃數據能夠較為全面地反應正在發生的通行需求,並且信息粒度較事件級別的特徵更精細。

具體來說,規劃的路線產生了計劃中交通流量,而計劃中交通流量可以用來指導對未來通行時間的預測。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的效果顯著優於各種前沿模型。

混合時空圖卷積網絡,獨創域轉換器和複合鄰接矩陣

整體框架

圖 4 展示了H-STGCN的整體框架。模型輸入由兩個特徵張量組成,理想未來流量

和通行時間張量

均包含三個維度:空間維度、時間維度、通道維度,分別對應路段、所使用的時間片和特徵。

域轉換器(模塊a)首先將

轉化為通行時間信號,輸出未來通行時間張量

。接下來,兩個獨立的門控卷積(模塊b)分別作用於

的時間維度以提取更高層級的時域特徵。

將每個路段視為一個節點,基於複合鄰接矩陣的圖卷積(模塊c)作用在合併(concatenation)後的信號

上。兩個門控卷積繼續擴大時域上的感知範圍,並最終經由一個全連接層(FC)輸出預測結果。

圖 4 H-STGCN模型框架

模型輸入與數據處理

輸入特徵張量

的每個切片對應了一個單獨的時間片

)。每個切片又由兩部分組成:理想未來流量和通行時間。

理想未來流量。作為對真實未來流量這一無法獲取信息的近似,理想未來流量

可以通過在線導航引擎獲取。圖 5 示意了高德導航系統的架構。導航過程中,車輛每秒鐘與雲伺服器同步自身坐標,與此同時,為保證用戶獲取到最新的交通狀態信息,雲伺服器對ETA進行幾乎實時的持續更新。

圖 5 高德導航系統架構示意

高德導航引擎中原始數據的形式為

其中

是導航進程的索引號,

是導航

的發起時間,

代表規劃路線中的第

個路段,

是到達

的預估時間,

是路線中路段的總數量,

是導航進程的總數量。ETA來自機器學習模型的預測(利用歷史軌跡等數據訓練得到)。算法 1 展示了從導航路線集合中推算理想未來流量的方法。

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

其中

是路段的索引號。

通行時間。通行時間

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

其中

是路段的索引號。

域轉換器

域轉換器

由串聯的兩層網絡組成,即逐路段

卷積(segmentwise

convolution)和路段間共享

卷積(shared

convolution),圖 4 呈現了這一結構。

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

共享

卷積。路段及時間片間參數共享的

卷積層

位於域轉換器的頂部,該卷積運算闡釋如圖 6a,旨在捕捉全局的三角形曲線映射關係。記這一層的輸入和輸出為

,則有:

其中

為權重,

為偏置項,

為ELU(Exponential Linear Unit)激活函數。

逐路段

卷積。為保證模型能夠充分提取精細到路段級別的特徵,路段參數個性化的

卷積層

位於域轉換器的底部(共享

卷積前面一層),該卷積運算闡釋如圖 6b。記這一層的輸入和輸出為

,則有:

其中,為權重,

為偏置項,

是ELU激活函數。

基於複合鄰接矩陣的圖卷積

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

其中

為路段

的最短路距離,

控制衰減速率,

為控制矩陣稀疏性的截斷閾值。我們將

稱為迪傑斯特拉矩陣(Dijkstra matrix)。在很多場景下,單純的空間接近程度並不能反映真實的交通鄰近性。更具體而言,交通擁堵對交通分流的影響取決於鄰近路段的若干種屬性,包括道路等級、路況等。可見,擁堵的傳播在空間上並不均勻。由此,我們提出了複合鄰接矩陣

圖卷積。我們將交通路網視為一個以路段為節點的圖。歸一化圖拉普拉斯(normalized graph Laplacian)矩陣

和縮放變換的圖拉普拉斯(scaled graph Laplacian)矩陣

分別表示為:

其中

為單位陣,

為複合鄰接矩陣,對角陣

的度矩陣(degree matrix),

的最大特徵值。圖卷積層

通過

的切比雪夫多項式(Chebyshev polynomials)參數化。記這一層的輸入和輸出為

則:

其中,

是切比雪夫多項式第

階項,K是卷積核大小,

為權重張量,

為偏置項,

是ELU激活函數。

時域門控卷積

如圖 6c 所示,路段間參數共享的一維卷積將輸入

轉化為張量:

其中

表示一維卷積運算符。是卷積核,

是卷積核的大小,

是輸入時序長度,

是偏置項。

形狀相同、通道數均為

。我們使用GLU(gated linear unit)進一步引入非線性:

」表示哈達瑪積(Hadamard product)。

與STGCN的關係

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

模型訓練

數據擴充。我們將高斯噪音疊加到流量通道中小於

的值上,以提升模型的泛化能力。

優化目標。對於本文中的多時間步預測,我們使用L1損失函數:

其中

是模型的輸出,

為真值。

基於真實路況測試,各項指標均優於傳統模型

數據集

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

圖 7 實驗路網空間分布

對比模型

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

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

STGCN (Im):換用複合鄰接矩陣的STGCN(用於和原始的迪傑斯特拉矩陣對比。

H-STGCN (1):將流量特徵張量V全部設成1。

評價指標

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

全測試集(如4.1節中所描述)。

高流量路段的擁堵時期,用C表示。

高流量路段的突發擁堵時期,用尾綴NRC表示。

效果比較

表 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 突發擁堵預測案例

模型可擴展性

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

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

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

相關焦點

  • 深蘭科技動作識別-人體骨架時空圖卷積網絡的可學習邊與權
    本文將重點介紹論文中關於動作識別的時空圖卷積的可學習邊與權重,及其劃分策略。一、空間圖卷積神經網絡在深入研究成熟的ST-GCN之前,團隊首先要在一個幀內查看Graph CNN模型。而通過在p(x)中編碼矩形網格,可以實現圖像域上的標準卷積,在(Dai et al.2017)中找到該構思的更詳細的說明和其他應用。圖一然後,定義圖上的卷積操作:通過將以上形式擴展到把輸入特徵圖換成採用空間圖V_t的方式。
  • CVPR2020 Oral | 動態多尺度圖表達3D人體骨架運動,實現精準預測...
    這種新的動態多尺度圖神經網絡(DMGNN),實現了更精準的運動預測。基於人類先驗,多尺度圖由一種預定義的物理性質的連接作為初始化,在模型的訓練過程中被自適應地調整;針對網絡不同層中的人體特徵,多尺度圖呈現動態變化,靈活地描述不同層級中的人體表達。  模型框架
  • 圖神經網絡的「前世今生」
    >GSTM -- 圖時空網絡圖一: GNN的分類網絡Embedding與GNN的異同網絡embedding旨在在保留網絡拓撲結構和節點信息的基礎之上, 在低維向量空間之中對網絡節點進行表示.GAT模型將attention機制引入圖卷積模型, 為更重要的節點分配更大的權重.正常的圖卷積神經網絡卷積核的參數都是共享的, 這種就是所謂的分心模型. 他預設了輸入節點對不同的輸出節點的影響是相同的.但是從我們人的認知模型出發, 輸入節點對不同的輸出節點影響肯定是不同的.
  • 從圖(Graph)到圖卷積(Graph Convolution):漫談圖神經網絡 (二)
    在從圖(Graph)到圖卷積(Graph Convolution): 漫談圖神經網絡 (一)中,我們簡單介紹了基於循環圖神經網絡的兩種重要模型,在本篇中,我們將著大量筆墨介紹圖卷積神經網絡中的卷積操作。接下來,我們將首先介紹一下圖卷積神經網絡的大概框架,藉此說明它與基於循環的圖神經網絡的區別。
  • 卷積神經網絡預測模型:提前24個月預測ENSO
    通過不斷探索,研究團隊選取相對成熟的卷積神經網絡進行ENSO 預測。近年來,卷積神經網絡在多個方向得到應用,在語音識別、人臉識別、通用物體識別等方面均有突破。在人工智慧領域,它是比較成熟的方法,並且有很多的開源程序和網站,可以直接使用。「卷積神經網絡的優點是可以處理大量數據。其實,這既是優點,也是缺點。
  • 今日Paper | CausalML;隱式函數;慢動作視頻重建;交叉圖卷積網絡等
    基於混合成像系統的慢動作視頻重建交叉圖卷積網絡(Cross-GCN):使用k順序特徵交互來增強圖卷積網絡選擇核網絡  CausalML:用於因果機器學習的Python包作者通過神經網絡從輸入數據提取基於三維張量表達的多尺度特徵,並將該張量與嵌入原始形狀的歐式空間進行對齊,然後從張量提取的深層特徵進行分類。實驗表明文章提出的模型根據全局和局部形狀結構做出決策,能夠得到更準確的重建結果。文章的方法能夠提供連續的輸出,可以處理多種拓撲,可以從缺失或者稀疏的輸入數據生成完整的形狀,並且可以重建3D人體並保留表面細節。
  • 用於視頻回歸任務的長期循環卷積網絡
    簡而言之,作者嘗試了各種CNNs架構來跨時間組件融合信息,並學習時空特徵。2、3d CNN這種方法背後的邏輯非常直觀,因為卷積中的第三維可以對應於時間域,從而可以直接從一個網絡學習時空特徵。3、長期循環卷積網絡(LRCN)2016年,一組作者提出了用於視覺識別和描述的端到端可訓練類架構。其主要思想是使用CNNs從視頻幀學習視覺特徵,使用LSTMs將圖像嵌入序列轉換為類標籤、句子、概率或任何您需要的東西。因此,我們用CNN對原始的視覺輸入進行處理,CNN的輸出被輸入到一堆遞歸序列模型中。
  • 人工智慧不只能看「平面世界」 還能觀察四維時空
    測出來的數字會改變,但這種改變是可預測的。同樣地,兩個攝影師從兩個不同的有利位置拍攝一個物體會產生不同的圖像,但那些圖像是可以相互關聯的。規範等變確保物理學家的現實模型保持一致,不管他們選擇什麼視角或者測量單位。規範等變卷積神經網絡對數據也做了同樣的假設。
  • AI質檢又出"神仙模型" 百度飛槳 PP-YOLO更準、更快、體積更小
    具體策略如下:Image Mixup(圖像混合):以隨機權重將兩張圖片混合起來,提高網絡在空間上的抗幹擾能力。以下圖為例,將任意兩張圖片加權疊加作為輸入,訓練過程中使用的損失為兩張圖片的損失乘以各自權重的加和。
  • 「海澱區時空一張圖」正式上線
    如果沒有「時空一張圖」提供信息,井蓋復原將需要七個步驟耗時至少一天……效率提升的背後得益於9月下旬「海澱區時空一張圖」1.0版的上線。由中科大腦公司承建的「海澱區時空一張圖」是海澱城市大腦的三大核心支撐平臺之一,承載著未來數字孿生海澱的建設任務,可視化還原城市變化和空間形態,仿真和推演城市未來發展走向。
  • 自然語言處理中的卷積深度語義匹配模型簡介
    下面就讓我們來看看卷積深度語義結構模型和深度匹配模型是怎樣的原理吧。1. 卷積深度語義結構模型在深度語義結構模型的基礎上,有人通過考慮詞間的順序提出了卷積深度語義結構模型。與DSSM類似,C-DSSM採用了相同的詞哈希技術,將查詢與文檔中的每個單詞表示為一個3萬維的向量,然後對每個固定長度(如長度為3)。
  • 表徵圖數據絕不止圖神經網絡一種方法
    連結預測:以往,我們並不知道缺乏哪些連結或未來會形成哪些連結。從宏觀上說,連結預測任務旨在預測網絡結構如何隨著現有的成員形成新的連結、斷開連接而演化。例如,在「蛋白質-蛋白質」交互網絡中,連結預測可以確定蛋白質之間新的交互。
  • 表徵圖數據,絕不止圖神經網絡一種方法
    雖然現在深度神經網絡在物體識別、圖像分類和自然語言處理領域都取得了巨大的成功。然而,「設計出最優的神經網絡,學習並輸出任意的圖」仍然是一個熱門的研究課題。本文是一篇出自倫敦大學學院的圖表徵學習綜述,詳細介紹了圖核、卷積、圖神經網絡、圖嵌入、概率模型共五類圖表徵學習方法的起源與發展,並對圖數據表徵學習方法的最新進展和未來發展方向進行總結和討論。
  • 需求預測模型精準「預報」
    中國石油網消息(特約記者王雲濤)截至11月25日,中國石油規劃總院共完成天然氣市場預測分析及建議報告10餘份,及時提交天然氣銷售周度、月度預測報告30餘期、預測數據4000餘條,持續加強冬季天然氣生產運行支撐保障工作。
  • 清華大學圖神經網絡綜述:模型與應用
    這篇文章對圖神經網絡進行了廣泛的總結,並做出了以下貢獻:文章詳細介紹了圖神經網絡的經典模型。主要包括其原始模型,不同的變體和幾個通用框架。文章將圖神經網絡的應用系統地歸類為結構化場景、非結構化場景和其他場景中,並介紹了不同場景中的主要應用。本文為未來的研究提出四個未解決的問題。文章對每個問題進行了詳細分析,並提出未來的研究方向。
  • 再見卷積神經網絡,使用Transformers創建計算機視覺模型
    這類神經網絡的感受域取決於過濾器的大小和使用的卷積層的數量。增加這些超參數的值會增加模型的複雜性,會產生消失梯度甚至無法訓練的模型。殘差連接和擴展的卷積也被用於增加這些模型的接受域,但是卷積在文本上操作的方式總是在它能夠捕獲的接受域上存在限制和權衡。
  • 涵蓋海澱區1.9億平方米建築面積 「時空一張圖」正在做什麼?
    效率提升的背後得益於「海澱區時空一張圖」的上線——大城管APP後臺通過調用「海澱區時空一張圖」城市部件基礎圖層信息(井蓋權屬信息)與案件信息進行數據掛接,自動研判出丟失井蓋的權屬信息。緊接著,後臺將案件工單自動派發到相應處置部門將井蓋復原,省去中間多項環節。
  • 精度45.9%,推理速度72.9FPS,百度飛槳推出工業級目標檢測模型
    具體策略如下:Image Mixup(圖像混合):以隨機權重將兩張圖片混合起來,提高網絡在空間上的抗幹擾能力。以下圖為例,將任意兩張圖片加權疊加作為輸入,訓練過程中使用的損失為兩張圖片的損失乘以各自權重的加和。