黃官偉,郭 巍
(同濟(jì)大學(xué) 經(jīng)濟(jì)與管理學(xué)院,上海 201804)
目前,許多國家正大力發(fā)展以數(shù)據(jù)為驅(qū)動(dòng)的智能交通系統(tǒng)[1],預(yù)測(cè)區(qū)域內(nèi)乘客打車需求是系統(tǒng)中的一個(gè)重要組成部分[2]。隨著信息技術(shù)在交通領(lǐng)域的廣泛應(yīng)用,網(wǎng)約車的出現(xiàn)解決了傳統(tǒng)出租車市場(chǎng)“打車難”的問題,成為城市居民出行的主要方式之一。精準(zhǔn)的網(wǎng)約車需求預(yù)測(cè),可以更合理地指導(dǎo)車輛調(diào)度、減少乘客等待時(shí)間、提高車輛利用率,進(jìn)而緩解交通擁堵和節(jié)約能源。該任務(wù)的主要挑戰(zhàn)在于同時(shí)捕獲復(fù)雜的時(shí)空依賴關(guān)系,受到交通拓?fù)浣Y(jié)構(gòu)和時(shí)間動(dòng)態(tài)性的影響,使得網(wǎng)約車的需求量具有復(fù)雜的時(shí)空關(guān)聯(lián)。
隨著機(jī)器學(xué)習(xí)和深度學(xué)習(xí)的發(fā)展,已有學(xué)者將其應(yīng)用在交通預(yù)測(cè)領(lǐng)域。K 近鄰算法(KNN)[3]、支持向量回歸(SVM)[4-6]等基于機(jī)器學(xué)習(xí)的算法比較依賴于特征工程,同時(shí)難以計(jì)算高維交通數(shù)據(jù)的時(shí)空相關(guān)性。由于深度學(xué)習(xí)技術(shù)在語音識(shí)別、圖像識(shí)別、自然語言處理等領(lǐng)域表現(xiàn)出具有構(gòu)建復(fù)雜模型和捕獲非線性關(guān)系的優(yōu)勢(shì),使得越來越多學(xué)者借助深度學(xué)習(xí)技術(shù)捕捉交通數(shù)據(jù)的動(dòng)態(tài)特征。Zhang 等人[7]根據(jù)鄰近時(shí)間、周期時(shí)間和趨勢(shì)時(shí)間的交通數(shù)據(jù),使用堆疊的殘差單元序列,構(gòu)建基于卷積的殘差神經(jīng)網(wǎng)絡(luò)(ST-ResNet)。文獻(xiàn)[8-10]融合卷積神經(jīng)網(wǎng)絡(luò)(CNN)和長短時(shí)記憶網(wǎng)絡(luò)(LSTM)構(gòu)建模型,提取交通流的時(shí)空特征。在此基礎(chǔ)上,Yao 等人[11]引入基于門控機(jī)制的局部卷積神經(jīng)網(wǎng)絡(luò),學(xué)習(xí)空間不同位置上的動(dòng)態(tài)相似性;Zheng 等人[12]加入注意力機(jī)制,為不同時(shí)間的交通流數(shù)據(jù)分配不同的權(quán)重;Liu 等人[13]建立了由局部空間、時(shí)間演化、全局相關(guān)3 個(gè)上下文組成的時(shí)空網(wǎng)絡(luò)(CSTN),捕獲環(huán)境信息學(xué)習(xí)需求特征。但是,傳統(tǒng)的卷積神經(jīng)網(wǎng)絡(luò)(CNN)僅適用于標(biāo)準(zhǔn)的網(wǎng)格數(shù)據(jù),不適用于具有圖結(jié)構(gòu)特征的交通數(shù)據(jù)。圖卷積網(wǎng)絡(luò)將歐幾里得空間中傳統(tǒng)的的卷積運(yùn)算,推廣到非歐幾里得空間中的圖網(wǎng)絡(luò)特征運(yùn)算。Yu 等人[14]構(gòu)建時(shí)空?qǐng)D卷積網(wǎng)絡(luò)(STGCN),處理拓?fù)浣Y(jié)構(gòu)復(fù)雜的交通網(wǎng)絡(luò);Zhao 等人[15]利用圖卷積網(wǎng)絡(luò)(GCN)提取路網(wǎng)結(jié)構(gòu),利用門控循環(huán)單元(GRU)學(xué)習(xí)交通數(shù)據(jù)動(dòng)態(tài)變化;Guo 等人[16]將時(shí)空注意力機(jī)制和時(shí)空卷積相結(jié)合,分別捕獲時(shí)間和空間的動(dòng)態(tài)相關(guān)性。然而,在空間維度,需求量通常受鄰近區(qū)域的影響,同時(shí)也會(huì)受遙遠(yuǎn)但相關(guān)性高的區(qū)域的影響,并且這些研究考慮的交通拓?fù)鋱D結(jié)構(gòu)比較單一,難以全面捕獲空間依賴關(guān)系提取需求的空間特征。
針對(duì)上述問題,本文提出了時(shí)空多圖卷積循環(huán)網(wǎng)絡(luò)(STMGCRN),對(duì)城市區(qū)域的網(wǎng)約車需求量進(jìn)行預(yù)測(cè)。該模型建立了距離圖、類別相似圖和需求相關(guān)圖,從3 個(gè)圖中提取不同區(qū)域之間的相關(guān)關(guān)系分別進(jìn)行圖卷積(GCN)。特征融合后,利用門控循環(huán)單元(GRU)學(xué)習(xí)時(shí)間依賴關(guān)系。由于交通信息具有較強(qiáng)的周期性,即在時(shí)間維度,需求量可能會(huì)受到臨近時(shí)間片段,一天前、甚至一周前相同時(shí)間片段的影響,因此整合3 個(gè)時(shí)間狀態(tài)(臨近、一天前、一周前),捕獲需求數(shù)據(jù)的周期依賴關(guān)系,最后加權(quán)融合3 個(gè)模型的輸出,得到最終的預(yù)測(cè)結(jié)果。
定義1城市區(qū)域網(wǎng)格V
本文根據(jù)交通領(lǐng)域常用的城市區(qū)域劃分方法[7,13],依據(jù)經(jīng)緯度,將研究區(qū)域劃分成若干個(gè)大小相等的不相交網(wǎng)格,每個(gè)網(wǎng)格代表城市的一個(gè)子區(qū)域v∈V,V代表所有區(qū)域的集合,如圖1 所示。采用這種劃分方法,則可以用R(i,j)表示第i行第j列的子區(qū)域,便于后續(xù)用矩陣或張量處理網(wǎng)約車需求數(shù)據(jù)。
圖1 城市區(qū)域網(wǎng)格Fig.1 The city region grids
定義2網(wǎng)絡(luò)圖G
本文用無向圖G=(V,E)定義城市區(qū)域。其中V是圖的頂點(diǎn)集合,即城市中的所有網(wǎng)格區(qū)域。V={v1,v2,…,vN},N是區(qū)域的數(shù)量,E是邊的集合,代表區(qū)域間的關(guān)系,邊的權(quán)重代表區(qū)域間的關(guān)系強(qiáng)度,A∈RN×N表示圖的鄰接矩陣。
定義3特征矩陣X
首先將時(shí)間軸劃分成間隔相等的時(shí)間段,網(wǎng)約車需求量定義為乘客在t時(shí)刻o區(qū)域請(qǐng)求出發(fā)的數(shù)量。Xt=∈RN代表所有區(qū)域在t時(shí)刻請(qǐng)求出發(fā)的數(shù)量,則特征矩陣X={X1,X2,…,XT}∈RN×T表示所有區(qū)域的T個(gè)時(shí)間片段的歷史需求量數(shù)據(jù)。其中,T是時(shí)間序列的長度。
因此,本研究是在已知拓?fù)鋱D結(jié)構(gòu)G的基礎(chǔ)上,利用歷史需求量的特征矩陣X,預(yù)測(cè)未來F個(gè)時(shí)間片段的所有區(qū)域的需求矩陣Y={YT+1,YT+2,…,YT+F} ∈RN×F,是一個(gè)多步需求預(yù)測(cè)問題。
STMGCRN模型總體框架如圖2 所示,主要由具有相同網(wǎng)絡(luò)結(jié)構(gòu)的3 個(gè)子模型構(gòu)成。
圖2 STMGCRN模型Fig.2 The Spatial- Temporal Multi- Graph Convolutional Recurrent Network
首先將歷史數(shù)據(jù)沿時(shí)間軸劃分成3 個(gè)長度相等的時(shí)間序列,分別表示臨近時(shí)間的需求量、前一天相同時(shí)間的需求量、上一周相同時(shí)間的需求量,提取時(shí)間的臨近特征和周期特征。
每一個(gè)子模型由多圖卷積循環(huán)網(wǎng)絡(luò)MGCRN 構(gòu)成,如圖3 所示。其基本單元是由多圖卷積和門控循環(huán)單元結(jié)合形成的多圖卷積循環(huán)單元MGCRU。通過學(xué)習(xí)需求的動(dòng)態(tài)變化規(guī)律,來捕獲復(fù)雜的時(shí)空相關(guān)性,進(jìn)而對(duì)時(shí)空依賴關(guān)系進(jìn)行建模。最后將3個(gè)時(shí)空模型的輸出結(jié)果利用參數(shù)矩陣進(jìn)行加權(quán)融合,得到最終的預(yù)測(cè)結(jié)果。
圖3 MGCRN 子模型Fig.3 Multi-graph convolutional recurrent network
1.3.1 關(guān)系圖定義
從不同角度構(gòu)建關(guān)系網(wǎng)絡(luò),準(zhǔn)確描述各區(qū)域之間的不同類別的相關(guān)性是圖卷積的重要工作。通常,區(qū)域之間的需求模式越相似,則相關(guān)性越強(qiáng),反之相關(guān)性越弱。本文定義了距離圖、需求相似圖和類別相關(guān)圖,3 種圖結(jié)構(gòu)描述區(qū)域之間的相關(guān)性。
1.3.1.1 距離圖
根據(jù)Tobler[17]的地理學(xué)第一定律可知,距離近的地圖比距離遠(yuǎn)的相關(guān)性大。基于這一思想,在本文中體現(xiàn)為兩個(gè)地理位置相近的網(wǎng)格,其需求量的相關(guān)性大。因此,本文用距離作為衡量區(qū)域相關(guān)性的一個(gè)因素。將網(wǎng)格中心點(diǎn)視為圖的頂點(diǎn),兩個(gè)相鄰網(wǎng)格間的中心距離記為D0,計(jì)算i和j兩個(gè)區(qū)域間實(shí)際距離Di,j,任意兩個(gè)網(wǎng)格中心的相對(duì)距離為,則距離圖的鄰接矩陣可用相對(duì)距離的倒數(shù)表示,如公式(1):
考慮到區(qū)域之間的距離不同,對(duì)需求量的影響大小不同。當(dāng)距離相關(guān)性較小時(shí),對(duì)需求量幾乎沒有影響。因此,為減少模型復(fù)雜度,當(dāng)兩個(gè)區(qū)域的相關(guān)性小于閾值δD時(shí),則這兩個(gè)區(qū)域視為不相關(guān)。
1.3.1.2 需求相似圖
一般情況下,在城市區(qū)域?qū)用妫藗兊某鲂熊壽E具有規(guī)律性。如果兩個(gè)始發(fā)區(qū)域到其他目的地區(qū)域的訂單量分布比較相似,那么這兩個(gè)區(qū)域之間的相關(guān)性較強(qiáng)。若用表示乘客從i區(qū)域出發(fā)到u區(qū)域的歷史訂單量,則i區(qū)域的流出量定義為Ci=,即從i區(qū)域出發(fā)到其他區(qū)域的訂單量。用Pearson 相關(guān)系數(shù)計(jì)算兩個(gè)區(qū)域之間訂單量的相關(guān)性作為邊的權(quán)重,計(jì)算方法如下:
1.3.1.3 類別相關(guān)圖
區(qū)域的建筑設(shè)施類型和數(shù)量在一定程度上影響網(wǎng)約車的分布,比如寫字樓、火車站、住宅等集中的地區(qū),對(duì)網(wǎng)約車的需求較多。本文用POI(興趣點(diǎn))來衡量區(qū)域的類別屬性,如果兩個(gè)區(qū)域的類別相似度較高,那么其具有一定的關(guān)聯(lián)性。用Pi∈RM表示i區(qū)域的POI,M是POI 的種類數(shù)量,則兩個(gè)區(qū)域間的類別相關(guān)性可用Pearson 相關(guān)系數(shù)計(jì)算得到:
其公式參數(shù)參考需求相似圖。
1.3.2 圖卷積
現(xiàn)有圖卷積方法大致可以分為譜域圖卷積和空域圖卷積。譜域圖卷積是根據(jù)圖譜理論,利用圖傅里葉變換,將圖信號(hào)從空域轉(zhuǎn)換到譜域進(jìn)行卷積操作;而空域圖卷積是直接在拓?fù)鋱D上定義卷積操作,計(jì)算復(fù)雜度較高。因此,本文采用譜域圖卷積方法,圖信號(hào)為每個(gè)網(wǎng)格的需求量數(shù)據(jù)。
圖的拉普拉斯矩陣經(jīng)過對(duì)稱歸一化后可表示為L=IN-D-1/2AD-1/2。其中,IN是單位矩陣;A是圖的鄰接矩陣;D是度矩陣;。拉普拉斯矩陣的特征分解可寫為L=UΛ UT,其中U和Λ是特征向量和特征值對(duì)角矩陣。傳統(tǒng)傅里葉變換的基函數(shù)是拉普拉斯算子的特征函數(shù),而圖上的拉普拉斯算子就是拉普拉斯矩陣。因此,圖傅里葉變換的基函數(shù)對(duì)應(yīng)拉普拉斯矩陣的特征向量,圖的傅里葉反變換公式為,圖的傅里葉變換為Tx,則圖卷積公式如下:
其中,x是圖上信號(hào)(2.1 中定義的需求量的特征矩陣);g是空域內(nèi)的卷積核;gθ是頻域內(nèi)的卷積核;*G表示圖卷積運(yùn)算;F是圖的傅里葉變換;F-1是圖的傅里葉反變換;☉是hadamard 乘積。
然而,在處理大規(guī)模圖數(shù)據(jù)時(shí),拉普拉斯矩陣的特征值分解消耗時(shí)間過多,參數(shù)復(fù)雜度較大,因此采用Chebyshev 多項(xiàng)式近似求解[18]:
其中,K是卷積核的感知域大??;βk是Chebyshev 多項(xiàng)式系數(shù),βk∈是縮放后的拉普拉斯矩陣;λmax是最大的特征值;是k階Chebyshev 多項(xiàng)式。這種方法通過空間關(guān)系提取每個(gè)節(jié)點(diǎn)到其(K-1)階鄰居的信息并進(jìn)行特征融合。
本文的多圖卷積模型如圖4 所示,采用4 階Chebyshev 多項(xiàng)式的圖卷積建模,即通過每個(gè)節(jié)點(diǎn)的三階鄰域來捕獲空間特征進(jìn)行自身的特征更新,公式如下:
圖4 空間相關(guān)性模型MGCNFig.4 The spatial correlation model MGCN
g(x(l),Ai)代表第l層通過提取區(qū)域拓?fù)鋱D的空間關(guān)系,得到圖卷積的輸出特征。其中,Ai是定義的3 種關(guān)系圖的鄰接矩陣Ai∈{AD,AC,AP}。本文使用ReLU作為激活函數(shù),針對(duì)每個(gè)時(shí)間片段,x(l) ∈RN是第l層的輸入,W(l)和b(l)分別是第l層訓(xùn)練過程中的權(quán)重矩陣和偏置向量。因此,每個(gè)節(jié)點(diǎn)都通過其0~3 階鄰居的信息進(jìn)行自身的特征更新,得到下一層的輸出x(l+1)。在此基礎(chǔ)上,通過堆疊2 層圖卷積,最大程度地?cái)U(kuò)大卷積核的感受野半徑,從而捕獲更多的空間依賴關(guān)系:
通過以上步驟,可以分別得到3 個(gè)關(guān)系圖的卷積運(yùn)算結(jié)果f(x(l),Ai),最后需要對(duì)這些結(jié)果進(jìn)行加權(quán)融合:
其中,☉代表hadamard乘積;WD、WC、WP是特征融合的權(quán)重矩陣;φ(x(l),A)是融合后的輸出結(jié)果。
長短期記憶(LSTM)[19]和門控循環(huán)單元(GRU)[20]是常用的處理時(shí)間序列問題的循環(huán)神經(jīng)網(wǎng)絡(luò)。GRU 作為LSTM 的一種變體,在相同數(shù)據(jù)集上的表現(xiàn)和LSTM 相差不大,但由于GRU 訓(xùn)練參數(shù)少,收斂速度更快,可以加速迭代進(jìn)程,甚至可以增強(qiáng)模型的泛化能力,所以本文使用基于GRU 的循環(huán)神經(jīng)網(wǎng)絡(luò)來捕獲時(shí)間依賴關(guān)系,如圖5 所示。
圖5 時(shí)間相關(guān)性模型GRUFig.5 The temporal correlation model GRU
在每個(gè)時(shí)間片段,將圖卷積得到的每個(gè)節(jié)點(diǎn)的空間鄰域信息,輸入到GRU 門控循環(huán)單元中。在門控循環(huán)單元的傳遞中,通過重置門和更新門可以有效地結(jié)合上一時(shí)刻的累積歷史信息和當(dāng)前時(shí)刻的信息,同時(shí)將隱藏狀態(tài)和歷史數(shù)據(jù)經(jīng)過多圖卷積后的結(jié)果作為輸入,可以繼續(xù)保持節(jié)點(diǎn)的空間依賴關(guān)系,公式如下:
其中,ht-1是t-1 時(shí)刻的隱藏層狀態(tài);xt是t時(shí)刻的輸入;br、bz和bh是偏置向量;[ ]是張量拼接操作,即將上一時(shí)刻的隱藏層狀態(tài)和當(dāng)前時(shí)刻的輸入拼接起來作為圖卷積的輸入特征;*代表矩陣相乘操作;☉代表hadamard 乘積;σ是sigmoid 激活函數(shù);rt是重置門;決定上一時(shí)刻隱藏層狀態(tài)ht-1中有多少保留在當(dāng)前記憶內(nèi)是更新門,決定記憶細(xì)胞內(nèi)有多少信息保留到當(dāng)前隱藏狀態(tài)ht,余下部分用上一時(shí)刻的隱藏層狀態(tài)ht-1進(jìn)行更新。
本文輸入的時(shí)間序列主要包含臨近時(shí)間序列、前一天時(shí)間序列、上一周時(shí)間序列3 部分,。臨近時(shí)間序列是指與預(yù)測(cè)區(qū)間直接相鄰的時(shí)間序列,前一天、上一周時(shí)間序列分別是指在前一天或是上一周和預(yù)測(cè)區(qū)間相同的時(shí)間序列:
假設(shè)將一天均等地劃分為P個(gè)時(shí)間片段,每個(gè)時(shí)間序列包含T個(gè)時(shí)間片段的歷史數(shù)據(jù),to代表當(dāng)前時(shí)間片段,Xto-1代表上一個(gè)時(shí)間片段的所有區(qū)域的歷史訂單量數(shù)據(jù),Xrecent、Xday和Xweek分別表示臨近、前一天和上一周的時(shí)間序列。例如,預(yù)測(cè)區(qū)間是11 月8 日12:00-13:00,則臨近時(shí)間序列為11 月8日11:00-12:00 的每個(gè)片段的訂單量,前一天時(shí)間序列和上一周時(shí)間序列分別是11 月7 日12:00-13:00、11 月1 日12:00-13:00 的每個(gè)片段的歷史訂單量。這3 個(gè)序列體現(xiàn)了需求量數(shù)據(jù)的臨近特征和周期特征。
構(gòu)建3 個(gè)時(shí)空?qǐng)D卷積模型分別捕獲需求量數(shù)據(jù)的特征,得到的3 個(gè)輸出結(jié)果對(duì)最終需求量預(yù)測(cè)值的影響程度不同,因此利用參數(shù)矩陣進(jìn)行特征融合,得到最終的預(yù)測(cè)值:
本文的數(shù)據(jù)集是由滴滴出行“蓋亞”數(shù)據(jù)開放計(jì)劃提供的西安市2016 年10 月1 日~2016 年11月30 日二環(huán)局部區(qū)域軌跡數(shù)據(jù)[21],軌跡點(diǎn)采集間隔為2~4 s,字段包括訂車編號(hào)、司機(jī)編號(hào)、時(shí)間戳、經(jīng)緯度等。將西安市區(qū)劃分成邊長為1 km 的正方形網(wǎng)格,POI 數(shù)據(jù)由高德地圖API 得到,主要以餐飲服務(wù)、風(fēng)景名勝、公司企業(yè)、交通設(shè)施服務(wù)、科教文化服務(wù)和商務(wù)住宅為統(tǒng)計(jì)標(biāo)準(zhǔn)。3 個(gè)子模型的超參數(shù)完全相同,時(shí)間間隔是10 min,關(guān)系圖閾值δD=0.25、δC=0.1、δP=0.3,多項(xiàng)式階數(shù)K=4,歷史時(shí)間序列的長度T=6,預(yù)測(cè)的時(shí)間序列長度F=6。沿著時(shí)間軸按照6:2:2 的比例劃分出訓(xùn)練集、驗(yàn)證集和測(cè)試集。
本文選取交通預(yù)測(cè)領(lǐng)域常用的均方根誤差(RMSE)與平均絕對(duì)誤差(MAE)作為模型的評(píng)價(jià)指標(biāo),來衡量預(yù)測(cè)的準(zhǔn)確性。
其中,M為數(shù)據(jù)個(gè)數(shù),Yi和分別表示真實(shí)值和預(yù)測(cè)值。
實(shí)驗(yàn)選取4 種模型與本文算法進(jìn)行對(duì)比。分別是:圖注意力(GAT)[22]、長短期記憶(LSTM)[19]、圖卷積(GCN)[18]、門控循環(huán)單元(GRU)[20]。實(shí)驗(yàn)結(jié)果見表1??梢钥闯?,本文提出的STMGCRN模型的算法性能均優(yōu)于其它4 種模型。
表1 需求預(yù)測(cè)模型的性能比較Tab.1 Performance comparison of demand forecasting models
GAT 是一種將注意力機(jī)制引入圖卷積模型中的方法,利用注意力機(jī)制在卷積過程中對(duì)鄰域節(jié)點(diǎn)區(qū)別對(duì)待;LSTM 是一種克服了一般循環(huán)神經(jīng)網(wǎng)絡(luò)的長期依賴問題的方法,將歷史網(wǎng)約車需求量數(shù)據(jù)輸入模型,進(jìn)行多步預(yù)測(cè);GCN 是一種基于Chebyshev 多項(xiàng)式的圖卷積方法,為保持公平性,該方法和GRU 方法均與本文中使用相同的參數(shù)設(shè)置。
本文提出了一種時(shí)空多圖卷積循環(huán)網(wǎng)絡(luò)(STMGCRN)來對(duì)網(wǎng)約車需求進(jìn)行多步預(yù)測(cè)。該模型定義了城市區(qū)域網(wǎng)絡(luò)圖,構(gòu)建距離圖、需求相似圖和類別相關(guān)圖,來描述各區(qū)域之間的空間相關(guān)性,學(xué)習(xí)時(shí)間序列的動(dòng)態(tài)變化來捕獲需求量數(shù)據(jù)的時(shí)間相關(guān)性,從而根據(jù)復(fù)雜的時(shí)空依賴關(guān)系,預(yù)測(cè)每個(gè)區(qū)域內(nèi)網(wǎng)約車的需求。在滴滴出行提供的數(shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn),結(jié)果表明,在常用的交通領(lǐng)域評(píng)價(jià)指標(biāo)上,STMGCRN模型的算法性能均優(yōu)于其它模型,可以進(jìn)行更為精準(zhǔn)的預(yù)測(cè)。但是,網(wǎng)約車的需求量也會(huì)受到其它外部因素的影響,在未來的研究中需要考慮人口數(shù)量、天氣等更多元化的信息,探究其與需求量之間的關(guān)系,進(jìn)一步提高模型預(yù)測(cè)的準(zhǔn)確率。