基于圖卷積門控循環網絡的個體地鐵出行預測

翁小雄，覃鎮林，張鵬飛

(華南理工大學 土木與交通學院，廣東 廣州 510630)

0 引 言

隨著城市智能化的推進，準確預測個體出行行為對于進一步理解人類移動性越來越重要。尤其是地鐵的個體出行，基于其出行信息進行預測分析能夠帶來大量潛在價值的應用，如運營調度和個性化信息推送。當前預測個體出行預測的研究根據采用的數據不同可以分成兩種。一種是基于個體出行的GPS數據[1-2]。這類研究需要將出行范圍劃分成大量網格，而且由于GPS數據本身噪聲較大以及不同的網格數量會導致不一致的誤差，這類研究的個體出行預測精度一般不高。另一種是基于IC卡刷卡數據。這種數據的出行范圍確定，噪聲較小，更適合用作個體出行預測的研究。這類研究通常對個體出行數據進行時間序列建模，采用的方法主要有馬爾科夫鏈[3]，多項邏輯模型[4]，n-gram模型等[5]。然而，這些模型僅僅對時間序列進行建模，只考慮出序列中與時間相關的周期性規律，而忽略了個體出行的空間信息。

地鐵的個體出行不僅存在周期性出行的規律，還會因為地理位置限制而導致個體基于同一種活動目的地出行選擇了不同的站點上車。為了進一步理解個體出行的內在移動性規律，充分全面地考慮個體出行時空特性，筆者結合圖卷積神經網絡(graph convolutional network, GCN)和門控循環單元(gating recurrent unit, GRU)的網絡模型，提出圖卷積門控循環網絡(graph convolutional network-gating recurrent unit, GCN-GRU)進行個體地鐵出行預測。該模型結構如圖1，在嵌入層和圖卷積層對出行特征進行提取，然后在時空特征向量門控層實現時空特征融合，再通過門控循環層實現時空特征的學習，最后通過全連接層推斷出預測結果。

圖1 卷積門控循環網絡

1 問題定義和空間特征構建

1.1 個體地鐵出行預測的問題定義

研究的個體地鐵出行預測主要通過建立模型輸入一定時間段內的歷史出行記錄來預測下一行程目的地。為了正式定義個體出行預測的任務，筆者首先引入兩個基本概念。

其一為出行元組，可以通過一個四元組來描述一次出行為：Q(o,d,w,t)。

其中：o、d、w、t分別為一次出行的出發站、目的站、星期幾和入站時間。沒有將出站時間納入分析的原因是出站時間并不由出行個體的行為模式所決定，而主要是由地鐵系統來決定的，例如地鐵發車時刻和地鐵站內客流擁擠度等。由于其具有高度不確定性，對預測下一次出行的目的站不能提供有效信息，故不予以考慮。根據出行元組的定義，進一步定義出行序列為：

Sm={Q1,Q2,…,Qm}

(1)

其二為地鐵系統網絡，用G來表示。筆者使用未加權圖G(V,Z) 描述地鐵系統網絡的拓撲結構，并將每個站點定義為一個節點，其中V是節點的集合，V={v1,v2,…,vn}，n是節點數，而Z是所有相鄰的兩個節點之間的邊的集合。為了描述兩個節點之間的連接情況，使用0和1分別表示相連和不相連的鄰接矩陣A∈Rn×n來表示整個地鐵網絡的連接。

對于給定的出行序列Sm={Q1,Q2,…,Qm}和已知最后一次出行的部分信息，(om+1,wm+1,tm+1)以及鄰接矩陣A，個體出行預測任務可以轉化成對映射F建模以實現輸入這些信息到輸出最后一次出行的目的站點的預測，其數學定義如下：

dm+1=F[A;Sm;(om+1,wm+1,tm+1)]

(2)

1.2 個體出行序列的空間特征

為了從空間角度描述關于個體出行序列，構造個體出行的空間特征是一個至關重要的問題。筆者首先提出了一種通過獨熱編碼(one-hot)[6]實現的OD表示形式，用來量化OD的空間信息，定義其為出行矩陣并表示為：

Ti=[HO,HD]

(3)

式中：HO、HD分別為O、D的獨熱編碼向量，假設G有n個地鐵站點，則它們分別是n維向量。

通過給出出行矩陣的定義，進一步得到空間移動矩陣B，空間移動矩陣指的是在給定出行序列Sm時，對序列所包含的所有出行矩陣T1,T2,…,Tm在時間維度上進行累加，表示個體在單位出行序列中以各個地鐵站作為出發站或者目的站的出行頻率：

(4)

2 圖卷積門控循環網絡模型

2.1 圖卷積提取空間特征

與傳統的卷積神經網絡(CNN)相比，GCN在處理非歐式數據方面具有更好的性能，例如社交網絡[7]，個性分類[8]和道路網絡交通流量[9]。在地鐵系統網絡中，由于活動地點的確定和固定交通設施的限制，個人出行受到地理和系統結構的限制，這意味著從一個車站進入的個人不可避免地會從另一個車站離開。因此，地鐵出行數據具有顯著的非歐拓撲特征。根據空間移動矩陣的定義，在研究的問題中構建個體出行序列的空間特征時需要添加最后一個起點的信息：

(5)

由于在實際的模型對輸入進行處理的時候，需要反映數據內部的相對關系而具體的數值并不重要。故對空間移動矩陣進一步歸一化處理，得到空間移動概率矩陣為：

E=softmax[mask (B)]

(6)

式中：softmax函數的作用是進行平滑歸一化處理，并且分別作用于O和D兩個方向。mask的作用在于將B中數值為零的位置置換成一個很大的負數(負無窮大)，使得E經過softmax函數后，原來數值為零的位置仍然保持為零，僅僅對數值不為零的位置進行了歸一化。空間移動概率矩陣，表示為個體在單位出行序列中以各個地鐵站作為出發站或者目的站的出行概率。然后，使用兩層圖卷積實現將E轉化為更抽象的空間特征U為：

(7)

U=Gf[tanh(GfEW1)]W2

(8)

圖卷積網絡本質上是一個消息傳遞模型，它將節點的信息傳播到其相鄰節點。如圖2，每一層圖卷積操作可以將非零值的頂點的信息傳播到鄰接的頂點。圖2表示2層圖卷積運算，即表示每個節點都可以獲取2跳以內的相鄰節點的信息。這意味著空間移動概率矩陣可以通過圖卷積層映射成與出行范圍有關的抽象特征表示。然后，使用式(7)中一樣的帶mask的softmax函數來計算移動范圍概率矩陣J。

圖2 卷積層運算

J=softmax[mask(U)]

(9)

空間移動概率矩陣相當于對長度為m的出行序列在時間維度進行降維，得到個體在各個站點作為出發站或目的站的概率。而移動范圍概率矩陣則進一步從個體以作為出發站或者目的站的具體的站點的概率分布，變成該站點包含其鄰居站點所在區域的概率分布。

2.2 時空特征嵌入

由式(1)給定的四元組出行屬性，具備了離散和分類的特性，由于將其直接輸入神經網絡模型進行處理時，模型更偏向將其當成連續的屬性進行識別，因此需要引入詞嵌入的方法進行處理。詞嵌入已經大規模應用于自然語言處理的序列分類任務[10]，將分類數據轉成低維向量更有利于神經網絡計算數據之間的語義關聯。因此，采用詞嵌入的方法將四元組數據轉換成向量，其運算可以看作是分類數據的熱獨編碼形式右乘一個嵌入矩陣為：

Vo=HO×MO

(10)

Vd=HD×MD

(11)

Vw=Hw×Mw

(12)

Vt=Ht×Mt

(13)

式中：H為數據對應獨熱編碼向量；M則是對應的嵌入矩陣，該矩陣所有參數通過梯度下降進行學習。該部分對應圖1的嵌入層。

在采用循環神經網絡進行訓練時，網絡往往容易學到關于數據中周期性的規律，比如個體的通勤出行。這些規律的抽象語義主要通過式(10)和式(11)嵌入到向量Vo和Vd中，這兩個向量可以認為是模型訓練過程中生成的關于出行的時間特征。為了使模型能學習個體出行的空間特性，通過將J沿O和D方向分解，分別右乘對應的嵌入矩陣則可得到空間特征的嵌入向量，計算過程為：

VsO=JO×MO

(14)

VsD=JD×MD

(15)

個體出行的時間特性和空間特性在一定程度上是互斥的。時間特性意味著個體出行在時間上的周期性規律，而空間特性意味著出行受到空間的制約而不得不進行近鄰站點的選擇上車。因此，筆者使用一種近似于門控循環單元的方法對關于兩種特性的向量進行了融合，具體過程如圖3。圖3的計算過程為：

g=σ[Wg(Vt,Vst)+bg]

(16)

Ct=tanh(WtVt+bt)

(17)

Cst=tanh(WstVst+bst)

(18)

Vstl=(1-g)⊙Ct+g⊙Cst

(19)

式中：⊙為哈達瑪積;Vt為輸入o或d的時間特征的向量(Vo或Vd)；Vst為輸入o或d的空間特征的向量(VsO或VsD)；g為控制兩種特征信息比例的門控系數矩陣，通過式(17)和式(18)生成關于Vt和Vs的關聯信息向量并通過式(19)進行融合而得到時空特征向量Vstl。該部分對應圖3的時空特征門控層。

圖3 時空特征向量門控層運算

2.3 時空特征學習

對個體的出行序列進行時序處理采用門控循環單元(GRU)，該方法被廣泛應用于交通流預測中[11]。在提取關于個體周期性出行的規律的同時，由式(19)得到時空特征向量，使得模型可以進一步學習數據中的個體出行的空間特性。連接通過式(12)，式(13)和式(19)得到的嵌入向量和時空特征向量作為該模塊的輸入，具體運算如圖4。圖4中的計算公式為：

ri=σ[Wr(xi,hi-1)+br]

(20)

zi=σ[Wz(xi,hi-1)+bz]

(21)

(22)

(23)

圖4 門控循環層運算

2.4 模型預測

在通過門控循環層而得到第m個隱向量后，將該向量與最后一次出行(w,t)的嵌入向量和o的時空特征向量相連，使用全連接層輸出模型的預測矩陣：

(24)

式中：ReLU(·)為線性整流函數。該部分對應圖1的全連接層。

3 實 驗

3.1 數據集和評價指標

模型性能通過廣州地鐵羊城通刷卡數據進行驗證。該數據記錄的時間跨度為2017年4月2日至2017年6月30日。由于APM線的數據無法獲得，數據中總共有9條地鐵線路和157個地鐵站。

從過去的研究的經驗中，深度循環網絡模型的訓練通常需要海量的訓練樣本。為了有效學習數據中的個體出行模式，選取了月平均出行30次以上的乘客出行記錄。然后隨機選取了20 000個乘客的出行記錄來構建數據集。根據出行元組的定義取得每一條記錄的出行屬性，然后將所有乘客的出行序列按8∶2的比例分為訓練集和測試集。此外，通過廣州地鐵2017年的地圖構造鄰接矩陣。

(25)

式中：1≤i≤M-m+1 ，長度為M的出行序列可以產生M-m+1個長度為m的子序列。

個體地鐵出行預測任務選取準確率作為評價指標來判斷模型性能效果為：

(26)

式中：T和N分布為預測準確的樣本數和預測錯誤的樣本數。

3.2 模型參數設置和性能評估

提出的模型的出行元組(o,d,w,t)的嵌入向量的維度大小分別為20，20，1，2，循環網絡的隱藏層維度大小為128，圖卷積的隱藏層維度大小為4，訓練樣本的批大小設置為2 048，優化器選擇Adam和學習率設置為0.001。模型訓練的損失函數設置為交叉熵函數。

為了驗證提出的圖卷積門控循環網絡，將該模型與目前文獻中的地鐵出行預測模型Markov，RNN，LSTM和GRU進行性能對比。各個模型的準確率如表1，其中對比模型的設置如下：

表1 模型性能比較

1)Markov：對于給定的出行序列，計算每一個站作為o到每一個站作為d的條件概率，即(o,d)的轉移矩陣，然后根據最后一次出行的o查詢轉移矩陣得到作為d最大概率的站為預測的地鐵站。

2)RNN：經典的循環神經網絡，輸入到輸出之間沒有門控機制，通過對每一時間步的輸入連接上一個時間步的隱向量進入一個帶tanh激活函數的線性層而得到下一個時間步的隱向量。

3)LSTM：長短期記憶網絡，帶門控機制，輸入到輸出之間通過輸入門，遺忘門和輸出門的運算，得到下一個時間步的隱向量。

4)GRU：詳見2.3節。

通過表1的實驗結果可以看出，對比傳統的Markov模型，提出的GCN-GRU模型在3種不同序列長度的數據集的平均準確率提高了11.61%。Markov模型沒有將關于星期和出行時間的信息輸入處理，而且不能如深度學習通過梯度下降來進行全樣本的學習個體出行規律，故預測效果較差。其次對比RNN，GCN-GRU的平均準確率提升了2.69%，主要因為RNN對于出行序列處理沒有采用高效的門控機制，沒有充分掌握對個體出行的周期性規律。采用了門控機制的LSTM和GRU在性能上相差較小，都比RNN平均高出大約2%，但GRU在平均準確率上比LSTM略高出0.2%。最后，GCN-GRU比GRU的平均準確率高出0.71%，說明該模型在捕獲到個體出行的時間特性的基礎上，還能進一步對空間特性進行學習。

3.3 模型空間特性檢驗

為了檢驗提出的模型關于空間特性的學習，需要進一步對模型魯棒性進行檢驗。首先，通過實驗探索模型輸入(o,d)和(o,d,w,t)的嵌入向量的不同差異，如圖5。該結果顯示只嵌入(o,d)僅比嵌入(o,d,w,t)低大約2%的平均準確率，因此可以認為關于地鐵出行模式的語義信息主要通過(o,d)的嵌入矩陣進行表征。

圖5 兩種嵌入方式作為輸入的模型性能對比

因此，筆者主要從(o,d)的角度構造一種基于空間特性的出行模式的人造數據，并將不同比例的真實數據替換成該人造數據。這種基于空間特性的出行模式表示為：假設每個個體有兩個不同的出行活動，然后每個活動有兩個相鄰的出發站和一個目的站，而且對應的(o,d)組合數量相同，而最后一次出行也基于這兩個活動之一，但出發站為該活動對應的兩個出發站的鄰接站點。這兩個活動在前m個出行有相同的個數，一共有4個不同的出發站和2個不同的目的站，第m+1個出行的出發站和這4個出發站不同。生成一個該出行模式的數據樣本的算法如下：

算法1：空間特性出行數據生成

輸入：鄰接矩陣A,地鐵站總數n,出行序列長度m

輸出：一個數據樣本(Sm,tripm+1)

Tris←?,Pairs←?,Sm←?

fori∈{1,2,…,n} do

a1,a2,…,as是Ai中元素為1的下標

ifs≥1 then

k∈{1,2,…,s} do

Pairs插入元素(i,ak)

end for

end if

ifs≥2 then

forj∈{1,2,…,s-1} do

Tris插入元素(i,aj,aj+1)

end for

end if

end for

從{6,7,…,23}隨機選取t1,t2

從{0,1,…,6}隨機選取w

從Tris隨機選取Rtri

從Paris隨機選取Rpair

fori∈{1,2,…,m} do

ifi是奇數 then

Sm插入元素(Rtri1,Rpair1,w,t1)

else

Sm插入元素(Rtri2,Rpair2,w,t2)

end if

ifw+1≥7 then

w=w+1-7

end if

Sm中所有元素隨機打亂順序

tripm+1←(Rtri3,Rpair2,w,t1)

輸出樣本(Sm,tripm+1)

與真實數據中主要的時間特性的出行數據相比，空間特性數據不具有明顯的周期性規律，而算法1的過程更是特化了個體出行受到地理限制的性質，即在基于同一種活動目的地出行中，出行者在決定該次出行時，極有可能會從兩個相鄰的站點選擇一個與當前位置最近的站點上車，然后前往同一個目的站。這種信息通常干擾模型識別較為規律性的出行模式，即一種活動只有一對出發站-目的站。因此，通過將不同比例的真實數據替換成該類型的數據，可以對個體出行預測模型的魯棒性進行檢驗。在魯棒性實驗中，個體出行序列長度設為40。

根據表2的實驗結果，人造數據所占比例≤0.4時會對模型進行干擾，導致模型性能下降。而當該比例≥0.6后，即數據集以空間特性的出行數據為主時，兩個模型的性能都開始上升，但兩個模型的性能差異也越來越大。當數據集全是空間特性的出行數據時，GRU出現大約21.09%的下降，說明GRU的性能更依賴于時間特性的數據。GCN-GRU在各個不同的人造數據的比例下表現優于GRU，說明當有足夠多的空間特性的數據樣本時，能更穩定地學習到數據中的空間特性，反映出其在個體出行預測任務中具有更好的魯棒性。

表2 魯棒性分析

4 結 論

構建了個體出行的空間特征，并使用圖卷積網絡進行空間特征的處理，結合門控循環網絡學習個體出行的時間特征，解決了地理限制對地鐵出行影響的個體出行預測問題。通過在真實數據和人造數據的實驗中，得出以下結論：

1)個體地鐵出行存在和時間相關的周期性規律，并且受到地理位置的約束，提出的方法可以同時學習這兩部分信息，在真實數據集上的表現優于只對時間特性建模的模型。

2)在使用詞嵌入的方法對出行特征進行處理時，關于個體出行模式的語義信息主要通過循環神經網絡對出行序列的(o,d)的嵌入矩陣的學習。

3)通過構造特化出行空間特性的數據并按不同比例對真實數據進行替換和混合，驗證了提出的模型可以學習出行數據中的空間特性，比只對時間特性建模的模型具有更好的魯棒性。