翁小雄，覃鎮(zhèn)林，張鵬飛

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

0 引 言

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

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

圖1 卷積門控循環(huán)網(wǎng)絡(luò)

1 問題定義和空間特征構(gòu)建

1.1 個體地鐵出行預(yù)測的問題定義

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

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

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

Sm={Q1,Q2,…,Qm}

(1)

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

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

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

(2)

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

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

Ti=[HO,HD]

(3)

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

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

(4)

2 圖卷積門控循環(huán)網(wǎng)絡(luò)模型

2.1 圖卷積提取空間特征

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

(5)

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

E=softmax[mask (B)]

(6)

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

(7)

U=Gf[tanh(GfEW1)]W2

(8)

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

圖2 卷積層運算

J=softmax[mask(U)]

(9)

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

2.2 時空特征嵌入

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

Vo=HO×MO

(10)

Vd=HD×MD

(11)

Vw=Hw×Mw

(12)

Vt=Ht×Mt

(13)

式中：H為數(shù)據(jù)對應(yīng)獨熱編碼向量；M則是對應(yīng)的嵌入矩陣，該矩陣所有參數(shù)通過梯度下降進行學(xué)習(xí)。該部分對應(yīng)圖1的嵌入層。

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

VsO=JO×MO

(14)

VsD=JD×MD

(15)

個體出行的時間特性和空間特性在一定程度上是互斥的。時間特性意味著個體出行在時間上的周期性規(guī)律，而空間特性意味著出行受到空間的制約而不得不進行近鄰站點的選擇上車。因此，筆者使用一種近似于門控循環(huán)單元的方法對關(guān)于兩種特性的向量進行了融合，具體過程如圖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為控制兩種特征信息比例的門控系數(shù)矩陣，通過式(17)和式(18)生成關(guān)于Vt和Vs的關(guān)聯(lián)信息向量并通過式(19)進行融合而得到時空特征向量Vstl。該部分對應(yīng)圖3的時空特征門控層。

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

2.3 時空特征學(xué)習(xí)

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

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

(20)

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

(21)

(22)

(23)

圖4 門控循環(huán)層運算

2.4 模型預(yù)測

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

(24)

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

3 實 驗

3.1 數(shù)據(jù)集和評價指標(biāo)

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

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

(25)

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

個體地鐵出行預(yù)測任務(wù)選取準(zhǔn)確率作為評價指標(biāo)來判斷模型性能效果為：

(26)

式中：T和N分布為預(yù)測準(zhǔn)確的樣本數(shù)和預(yù)測錯誤的樣本數(shù)。

3.2 模型參數(shù)設(shè)置和性能評估

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

為了驗證提出的圖卷積門控循環(huán)網(wǎng)絡(luò)，將該模型與目前文獻中的地鐵出行預(yù)測模型Markov，RNN，LSTM和GRU進行性能對比。各個模型的準(zhǔn)確率如表1，其中對比模型的設(shè)置如下：

表1 模型性能比較

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

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

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

4)GRU：詳見2.3節(jié)。

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

3.3 模型空間特性檢驗

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

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

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

算法1：空間特性出行數(shù)據(jù)生成

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

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

Tris←?,Pairs←?,Sm←?

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

a1,a2,…,as是Ai中元素為1的下標(biāo)

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是奇數(shù) 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)

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

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

表2 魯棒性分析

4 結(jié) 論

構(gòu)建了個體出行的空間特征，并使用圖卷積網(wǎng)絡(luò)進行空間特征的處理，結(jié)合門控循環(huán)網(wǎng)絡(luò)學(xué)習(xí)個體出行的時間特征，解決了地理限制對地鐵出行影響的個體出行預(yù)測問題。通過在真實數(shù)據(jù)和人造數(shù)據(jù)的實驗中，得出以下結(jié)論：

1)個體地鐵出行存在和時間相關(guān)的周期性規(guī)律，并且受到地理位置的約束，提出的方法可以同時學(xué)習(xí)這兩部分信息，在真實數(shù)據(jù)集上的表現(xiàn)優(yōu)于只對時間特性建模的模型。

2)在使用詞嵌入的方法對出行特征進行處理時，關(guān)于個體出行模式的語義信息主要通過循環(huán)神經(jīng)網(wǎng)絡(luò)對出行序列的(o,d)的嵌入矩陣的學(xué)習(xí)。

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