(18) 基於時空多圖卷積網路的網約車需求預測

交通預見未來（18）：基於時空多圖卷積網路的網約車需求預測

1、文章資訊

《Spatiotemporal Multi-Graph Convolution Network for Ride-hailing Demand Forecasting》。

2019 AAAI大會的一篇論文，被引5次。

2、摘要

區域級需求預測是網約車服務的一項重要任務。區域間具有複雜的時空依賴性，現有的方法主要側重於對空間相鄰區域之間的歐式相關關係進行建模，而我們發現，距離可能較遠的區域之間的非歐式相關關係對於準確預測也至關重要。為此本文提出了時空多圖卷積網路（ST-MGCN）。首先將區域間的非歐式成對相關關係編碼為多個圖，然後利用多圖卷積對這些相關關係進行建模。為了利用全域性上下文資訊對時間相關性進行建模，我們進一步提出了上下文門控迴圈神經網路，該網路利用上下文感知的門控機制對不同的歷史觀測值進行重新加權。我們在兩個真實的大型網約車需求資料集上評估了所提出的模型，與最先進的基準模型相比，該模型提高了10%以上。

3、簡介

區域級網約車需求預測的目標是根據歷史觀測，預測城市區域未來的需求。這一任務的挑戰性主要在於複雜的時空相關性。一方面，不同區域之間存在複雜的依賴關係。例如，一個區域的需求通常受其空間相鄰鄰居的影響，同時與具有相似上下文環境的遙遠區域相關。另一方面，不同的時間觀測值之間也存在非線性依賴關係。對某一時刻的預測通常與各種歷史觀測結果相關聯，如一小時前、一天前甚至一週前。

在時空相關性建模中，有兩個重要的方面被忽略了。首先，這些方法主要針對不同區域間的歐氏相關關係進行建模，但我們發現非歐氏兩兩相關關係對準確預測也至關重要。圖1顯示了一個示例。對於區域1，除了鄰域2，它還可能與一個遙遠的區域3相關具有相似功能的，即，它們都在學校和醫院附近。此外，區域1還可能受到區域4的影響，區域4透過公路與區域1直接相連。其次，在這些方法中，當使用RNN對時間相關性進行建模時，每個區域都是獨立處理的，或者只基於區域性資訊。然而，我們認為全域性和上下文資訊也很重要。例如，全域性網約車需求的增加/減少通常表明一些事件的發生，這些事件將影響未來的需求。

為了解決這些問題，我們提出了一種新的深度學習模型，稱為時空多圖卷積網路（ST-MGCN）。主要貢獻如下：

在網約車需求預測中，我們識別出區域間的非歐式相關關係，並提出使用多個圖對其進行編碼。然後，我們進一步利用提出的多圖卷積來顯式地建模這些相關性。

提出了基於上下文門控的RNN （CGRNN）模型，在時序依賴關係建模時引入全域性上下文資訊。

4、文獻綜述

（1）城市計算中的時空預測

非歐式結構化資料也存在於城市計算中。通常，基於站點的預測任務，比如基於站點的計程車需求預測，基於站點的腳踏車流量預測，是非歐式的，因為資料格式不再是矩陣，卷積神經網路變得不那麼有用了。人工特徵工程或圖卷積網路是處理非歐式結構資料的最新技術。與以往的研究不同，ST-MGCN將區域間的成對關係編碼為語義圖。雖然ST-MGCN是為基於區域的預測而設計的，但區域間關係的不規則性使其成為非歐式資料的預測問題。然而，這些方法都沒有明確地對區域間的非歐式成對關係建模。在這項工作中，ST-MGCN利用提出的多圖卷積融合相關區域的特徵，能夠從不同角度關聯區域的需求值進行預測。

（2）圖卷積

（3）Channel-wise attention對channel做注意力機制

Channel-wise attention提出的初衷是學習每個channel的權重，以便找到最重要的channel，並透過給出更高的權重來強調它們。

Fpool是一個全域性平均池化操作，它將每個通道總結為一個標量Zc，其中c是通道索引。然後利用注意力運算對向量z進行非線性變換，生成自適應權值s， W1和W2相應的權重，δσ是分別ReLU和sigmoid函式。然後，透過channel方向的點積將權值s應用於輸入。最後，基於學習權值對輸入通道進行縮放。在本文中，我們採用了Channel-wise attention的思想，並將其推廣到一系列圖之間的時間依賴關係建模中。

5、主體內容

（一）區域級別的網約車需求預測

將全網需求網格化，利用過去T個時段預測T+1個時段。所提出的模型ST-MGCN的系統架構如圖2所示。我們將區域間三種關係型別表示為多個圖，圖的頂點表示區域，邊表示區域間的成對關係。首先，時間上，我們使用提出的上下文門控迴圈神經網路（CGRNN）考慮全域性上下文資訊，對不同時間的觀測結果進行彙總，將多個時間步融合為一個時間步。然後，空間上，應用多圖卷積來捕捉區域間不同型別的相關性。最後，利用全連線層進行特徵融合轉化為預測。

（二）空間依賴關係建模

所謂多圖卷積，是指對空間上的多種相關關係分別進行圖卷積，再進行特徵融合。

在本節中，我們將展示如何使用多個圖來編碼區域之間不同型別的相關性，以及如何使用所提出的多圖卷積來對這些關係建模。我們用圖對區域間的三種相關性進行了建模，包括（1）鄰域圖，編碼空間鄰近性，（2）區域功能相似圖，它對區域周圍興趣點的相似性進行編碼，（3）交通連通性圖，它編碼了遙遠地區之間的連通性。

（1）領域圖

區域的鄰域是根據空間鄰近性來定義的。我們在一個3×3的網格中，將一個區域與其相鄰的8個區域連線起來，構造出圖形。

（2）功能相似圖

在對一個區域進行預測時，可以直觀地參考與此區域功能類似的其他區域。區域功能可以用其周圍每個類別的POIs來表徵，兩個頂點（區域）之間的邊定義為POI相似性：

Pvi和Pvj分別為區域vi和vj的POI向量，其維數等於POI類別的數量，每個條目表示區域內特定POI類別的數量。

（3）交通連通性圖

在進行時空預測時，交通系統也是一個重要因素。直觀地說，那些地理上遙遠但方便到達的區域可以相互關聯。這些連線是由高速公路、高速公路或地鐵等公共交通誘導的。這裡，我們將這些道路直接相連的區域定義為“連通”，對應的邊定義為：

為vi與vj之間連通性的指標函式。注意，為了避免冗餘關聯，鄰域圖被從連通圖中刪除，這也會導致稀疏圖。

（4）利用多圖卷積對時空依賴關係進行建模

利用構建的上述三種類型的圖，我們使用如下公式進行卷積，f（A；θi）表示拉普拉斯矩陣。

在實際過程中，f（A；θi）選為拉普拉斯運算元L的K階多項式函式，圖3顯示了圖卷積層示例。K表示vi透過K步能夠到達vj。在卷積運算方面，k定義了空間特徵提取時感知域的大小。

基於多圖卷積的空間依賴關係建模並不侷限於上述三種類型的區域關係，它可以很容易地擴充套件到其他區域關係以及其他時空預測問題的建模。它透過區域間的關係提取特徵，對空間依賴關係進行建模。在K較小的情況下，特徵提取將重點放在較近的區域，增加K值或疊加多個卷積層的最大程度將增加感知域，從而鼓勵模型捕獲更多的全域性依賴關係。

（三）時間相關的建模

即透過多步處理，將多個時間步的資訊融合到一張圖上。這一塊比較難理解，首先解釋一下維度關係。對於圖4左上角的T×|V|×P，T 代表T個時間步，其中每個時間步為一個方塊，該方塊的高即V代表所有的節點，寬即P代表每個節點graph embedding 出來的高維表示。

圖4左下角和圖4左上角其實是一樣的資料，只不過，左下角的資料是對每個時間步加了權重，所以他畫的有的方塊厚有的方塊薄，即所謂的channel-wise attention，而其中所使用的權重，便是根據channel-wise attention中的公式6、7、8得到的，比較複雜（公式6圖卷積，公式7對圖卷積結果進行池化，池化結果利用公式8得到權重）。

圖4右邊他說的共享權重的RNN，其實就是將多張圖經過RNN融合成一張圖。按道理，對於每個節點，使用過去T個時間步預測未來T+1個時間步，應該訓練一個RNN，50個節點要訓練50個RNN，但是文章為了簡化模型，對所有節點應用一個RNN模型，右邊中間的黑色方塊，是把RNN展開了，代表T個時間步，最後輸出一個時間步，即融合為一張圖。（其實共享權重的RNN效果肯定是不如對每個節點訓練一個RNN效果好的，但是文章中說了這樣做的原因：區域間共享RNN是為所有區域找到一個通用的聚合規則，從而促進模型的泛化，降低模型的複雜度）