基于多圖時(shí)空?qǐng)D卷積神經(jīng)網(wǎng)絡(luò)的網(wǎng)約車(chē)需求預(yù)測(cè)①

周云彤,熊衛(wèi)華,姜 明

1(浙江理工大學(xué) 機(jī)械與自動(dòng)控制學(xué)院,杭州 310018)

2(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院,杭州 310018)

1 引言

網(wǎng)約車(chē)是當(dāng)今社會(huì)的主要出行方式之一,為人們的生活帶來(lái)了便捷,然而這一行業(yè)也存在許多問(wèn)題,如乘客等待時(shí)間長(zhǎng),司機(jī)空車(chē)率高[1].造成這些問(wèn)題的主要原因是網(wǎng)約車(chē)調(diào)度不合理,過(guò)多的車(chē)輛集中在繁忙區(qū)域?qū)е萝?chē)輛的供給大于需求,而在較為偏遠(yuǎn)的地區(qū),網(wǎng)約車(chē)數(shù)量極少,分布極為稀疏[2].網(wǎng)約車(chē)需求預(yù)測(cè)可以有效應(yīng)對(duì)這一問(wèn)題,通過(guò)預(yù)測(cè)區(qū)域內(nèi)網(wǎng)約車(chē)的需求,提前引導(dǎo)司機(jī)前往不同的區(qū)域,從而避免出現(xiàn)網(wǎng)約車(chē)分布不均勻的問(wèn)題[3].

網(wǎng)約車(chē)需求預(yù)測(cè)是智能交通系統(tǒng)的重要組成部分,也是交通大數(shù)據(jù)分析的一項(xiàng)難題,這是因?yàn)槠涫艿蕉喾N時(shí)空因素的共同影響,單一因素的建模方式很難實(shí)現(xiàn)準(zhǔn)確的預(yù)測(cè).目前研究人員提出了許多方法來(lái)解決這一問(wèn)題,大致可以分為機(jī)器學(xué)習(xí)和深度學(xué)習(xí)兩類,前者需要的訓(xùn)練數(shù)據(jù)較少但準(zhǔn)確率較低,后者則恰好相反.其中機(jī)器學(xué)習(xí)的方法主要有線性回歸[4]和支持向量回歸[5];深度學(xué)習(xí)的方法有卷積神經(jīng)網(wǎng)絡(luò)(CNN)[6]、卷積神經(jīng)網(wǎng)絡(luò)與長(zhǎng)短時(shí)神經(jīng)網(wǎng)絡(luò)(LSTM)相結(jié)合[7]和圖卷積神經(jīng)網(wǎng)絡(luò)(GCN)[8].但這些方法考慮的影響因素不足,仍然無(wú)法避免模型不完善的問(wèn)題.在時(shí)間因素方面,出租車(chē)需求預(yù)測(cè)會(huì)受季節(jié)、節(jié)假日和工作時(shí)間的影響;同時(shí)歷史的出行信息也會(huì)有一定的影響,這是因?yàn)槌丝驮诘竭_(dá)目的地后,大概率會(huì)在一段時(shí)間后從目的地再次出發(fā)前往下一個(gè)區(qū)域.在空間因素方面,出租車(chē)需求預(yù)測(cè)在空間上受到地理位置的限制;同時(shí)不同的地理位置可能具有相似的社會(huì)意義也會(huì)影響出租車(chē)的需求.

針對(duì)上述問(wèn)題,本文提出了一種多圖時(shí)空?qǐng)D卷積網(wǎng)絡(luò)(MGSTGCN),以提高網(wǎng)約車(chē)需求預(yù)測(cè)的準(zhǔn)確性.該網(wǎng)絡(luò)在空間上使用圖卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行特征捕獲,針對(duì)不同地區(qū)的地理位置屬性、交通起止點(diǎn)(OD)屬性和社會(huì)意義相似性建立了3 種圖,隨后進(jìn)行聚合;在時(shí)間上使用長(zhǎng)短期記憶網(wǎng)絡(luò)(LSTM).最后使用了成都網(wǎng)約車(chē)軌跡數(shù)據(jù)和曼哈頓區(qū)出租車(chē)數(shù)據(jù)對(duì)所建立網(wǎng)絡(luò)進(jìn)行驗(yàn)證.

2 算法框架

2.1 出租車(chē)需求預(yù)測(cè)建模

本文采用了交通領(lǐng)域的經(jīng)典處理方法[9],將待處理區(qū)域平均分為多個(gè)網(wǎng)格,若將網(wǎng)格分為9 個(gè),每個(gè)網(wǎng)格由最大坐標(biāo)與最小坐標(biāo)定義,如圖1所示,通過(guò)這樣的方式,研究每個(gè)小格子區(qū)域內(nèi)的出租車(chē)需求.隨后將每個(gè)格子看作圖的一個(gè)頂點(diǎn),用于構(gòu)建出租車(chē)需求預(yù)測(cè)的圖模型.

圖1 網(wǎng)格劃分方法

在空間建模方面,文獻(xiàn)[10]考慮了地理位置因素和OD的影響,本文則在此基礎(chǔ)上研究了不同區(qū)域的社會(huì)屬性對(duì)預(yù)測(cè)問(wèn)題的影響,包括商業(yè)街、大學(xué)城、工業(yè)園等,通過(guò)研究發(fā)現(xiàn),即使相隔距離很遠(yuǎn),具有相似社會(huì)屬性的地區(qū)在交通流上具有高度相似性.最終本文采用地理位置因素、OD 因素以及社會(huì)屬性因素分別構(gòu)筑了地理圖、OD 圖和社會(huì)屬性圖.

在時(shí)間建模方面,則考慮歷史出行特征,通過(guò)LSTM和注意力機(jī)制進(jìn)行時(shí)間特性的捕獲,來(lái)掌握時(shí)間維度上的出租車(chē)需求變化,可以預(yù)測(cè)每對(duì)網(wǎng)格間的需求.

2.2 空間網(wǎng)絡(luò)模型

2.2.1 空間建模

以圖1劃分為例,將每個(gè)網(wǎng)格看作一個(gè)圖的節(jié)點(diǎn),本文在此基礎(chǔ)上建立了3 種圖來(lái)捕獲空間特征,如圖2所示.其中,圖2(a)為地理圖結(jié)構(gòu),將每個(gè)網(wǎng)格的中心點(diǎn)視作網(wǎng)格的地理位置中心,中心點(diǎn)的距離視作地理圖結(jié)構(gòu)的邊權(quán)值.設(shè)中心距離的單位為u,那么網(wǎng)

格8和9 之間距離記作dist(m8,m9)=u,網(wǎng)格8和4 之間距離記作dist(m8,m4)=,距離越近權(quán)值則越小,兩者間的出租車(chē)需求也會(huì)有一定的相似性,可將地理圖范圍集 φi定義為式(1):

其中,L為可設(shè)定閾值.

圖2(b)為OD 圖結(jié)構(gòu),本文使用了OD 矩陣來(lái)對(duì)OD 圖進(jìn)行定義:只要任意兩個(gè)頂點(diǎn)間有出租車(chē)需求存在,那么它們就是相關(guān)的.同時(shí),OD 圖會(huì)受時(shí)間因素的影響,這是因?yàn)樵诓煌臅r(shí)間段內(nèi),兩個(gè)區(qū)域間的OD信息常常是不同的,所以建模時(shí)要考慮到不同時(shí)間下OD 圖的變化情況.

本文假定兩個(gè)地區(qū)社會(huì)屬性相似,相距距離較大,則此時(shí)在地理圖和OD 圖上,這兩個(gè)地區(qū)的關(guān)聯(lián)度較小,但由于社會(huì)屬性的相似性,兩個(gè)地區(qū)的出租車(chē)需求相似性較高.為了應(yīng)對(duì)這種情況,本文設(shè)計(jì)了社會(huì)屬性圖,其結(jié)構(gòu)如圖2(c)所示.本文將每個(gè)網(wǎng)格的社會(huì)屬性分為:工業(yè)、生活、出行、商業(yè)、娛樂(lè)和住宿,每個(gè)柵格的社會(huì)屬性由其所包括的非地理意義點(diǎn)(POI)的屬性所決定.

圖2 空間圖結(jié)構(gòu)

本文爬取了成都部分地區(qū)的POI 點(diǎn),將每個(gè)柵格內(nèi)的POI 點(diǎn)進(jìn)行了社會(huì)意義分類,柵格的社會(huì)屬性與相同屬性最多的POI 點(diǎn)保持一致,隨后在建立圖結(jié)構(gòu)時(shí),應(yīng)用動(dòng)態(tài)時(shí)間規(guī)劃法(DTW),來(lái)量化社會(huì)屬性相似的網(wǎng)格間的相似度,公式如式(2)所示:

其中,Fi∈R1×T表示離開(kāi)第i個(gè)網(wǎng)格的出租車(chē)流出向量,T為向量長(zhǎng)度,由所選定的對(duì)照時(shí)間尺度所決定.得到矩陣S后對(duì)其進(jìn)行歸一化即可得到社會(huì)屬性圖的權(quán)重.

2.2.2 圖模型聚合器

如果將每種圖模型單獨(dú)進(jìn)行訓(xùn)練會(huì)大大提升算法的復(fù)雜度,為避免這一缺點(diǎn),本文在傳統(tǒng)聚合函數(shù)的基礎(chǔ)上進(jìn)行改進(jìn)[11],綜合考慮了3 種圖模型對(duì)預(yù)測(cè)結(jié)果的不同影響程度,設(shè)計(jì)了一種圖聚合器.地理圖的聚合器方式如式(3)所示:

其中,表示時(shí)間t′時(shí)的地理圖嵌入矢量;Wl是可訓(xùn)練的權(quán)重矩陣;而和分別是地理聚合操作之前的mi和mj的特征.同理可進(jìn)行出OD 圖和社會(huì)圖的特征聚合,OD 圖的特征聚合如式(4)所示:

式中,num(mj)表示于mj開(kāi)始或結(jié)束的需求量,Wq是可訓(xùn)練的權(quán)重矩陣.而表示時(shí)間t′下的OD 圖嵌入矢量,和分別是OD 聚合操作之前的mi和mj的特征.

社會(huì)圖的特征聚合如式(5)所示:

式中,S(mi,mj)表示mi和mj的社會(huì)屬性相似度,表示時(shí)間t′下的社會(huì)圖嵌入矢量,Wq是可訓(xùn)練的權(quán)重矩陣和分別是社會(huì)屬性聚合操作之前的mi和mj的特征.

將3 種聚合器加以整合即可得到圖的最終聚合表示:

2.3 時(shí)空網(wǎng)絡(luò)架構(gòu)

MGSTGCN的時(shí)間架構(gòu)部分與LSTM 一樣都有LSTM的輸入門(mén)、忘記門(mén)和輸出門(mén),但均由圖卷積算子而得,且引入了注意力機(jī)制,其中時(shí)間序列為輸入.時(shí)間結(jié)構(gòu)與空間結(jié)構(gòu)相結(jié)合構(gòu)成了MGSTGCN 網(wǎng)絡(luò),MGSTGCN的層結(jié)構(gòu)如圖3所示.

圖3 MGSTGCN 網(wǎng)絡(luò)結(jié)構(gòu)

注意力機(jī)制的引入目的是增強(qiáng)關(guān)鍵節(jié)點(diǎn)的信息,如式(7)所示:

其中,σ (·)為sigmoid 函數(shù),⊙為同或運(yùn)算符,i,f,o,c分別代表輸入門(mén),遺忘門(mén),輸出門(mén)和細(xì)胞狀態(tài)向量.當(dāng)它們中的每一個(gè)都被更新時(shí),有相應(yīng)的可訓(xùn)練權(quán)重W和偏差向量b,fatt代表注意力網(wǎng)絡(luò),可以在增強(qiáng)關(guān)鍵節(jié)點(diǎn)信息的同時(shí)保證信息的完整性,所得為注意力矩陣.注意力矩陣設(shè)為V=(V1,V2,···,Vt,···,VN),Vt為列向量,計(jì)算公式如式(8)所示.

式(8)中,通過(guò)softmax(·)函數(shù)進(jìn)行歸一化,得到注意力矩陣V.Vt在語(yǔ)義上理解為輸出時(shí)刻t時(shí),節(jié)點(diǎn)間的相互依賴程度向量.

3 實(shí)驗(yàn)

3.1 數(shù)據(jù)集處理

本文選用數(shù)據(jù)集為成都市局部區(qū)域的滴滴快專車(chē)平臺(tái)的軌跡數(shù)據(jù)和紐約市曼哈頓區(qū)出租車(chē)數(shù)據(jù)集.

其中成都市數(shù)據(jù)集的時(shí)長(zhǎng)為2016年11月1日至11月30日,該數(shù)據(jù)集來(lái)自于滴滴公司的蓋亞數(shù)據(jù)開(kāi)放計(jì)劃,軌跡點(diǎn)的采集間隔是2-4 s.軌跡點(diǎn)經(jīng)過(guò)了綁路的處理,保證了數(shù)據(jù)都能夠?qū)?yīng)到實(shí)際的道路信息.司機(jī)及訂單信息進(jìn)行了加密脫敏匿名化處理.紐約市曼哈頓區(qū)出租車(chē)數(shù)據(jù)集的時(shí)長(zhǎng)為2018年7月1日至7月30日.本文分別選取前20 天數(shù)據(jù)作為訓(xùn)練集,后10 天數(shù)據(jù)作為測(cè)試集.

3.2 評(píng)估指標(biāo)

本文選取的評(píng)估指標(biāo)為均方根誤差(RMSE)和對(duì)稱平均絕對(duì)百分比誤差(SMAPE),用以評(píng)估預(yù)測(cè)準(zhǔn)確性.RMSE和SMAPE的計(jì)算公式如式(9)和式(10)所示:

3.3 實(shí)驗(yàn)結(jié)果

為證明模型的有效性和準(zhǔn)確性,本文選取了4 種主流模型與本文算法進(jìn)行對(duì)照試驗(yàn),分別是:HA[10]、LSTNet[11]、GCRN[12]、GEML[8]、MGSTGCN.實(shí)驗(yàn)結(jié)果如表1所示.

表1 與4 種主流模型的實(shí)驗(yàn)對(duì)照結(jié)果

同時(shí)為檢驗(yàn)該模型的穩(wěn)定性,本文選取了32,64,128,256,512的網(wǎng)格維度與模型進(jìn)行了對(duì)照實(shí)驗(yàn),以GEML 模型為例,實(shí)驗(yàn)結(jié)果如圖4所示.可以看出在不同的網(wǎng)格維度下,該模型的算法性能均優(yōu)于GEML 模型,且維度越高,劃分越精密,該模型的優(yōu)越性越明顯.

4 結(jié)論

本文提出了多圖時(shí)空?qǐng)D卷積神經(jīng)網(wǎng)絡(luò)來(lái)解決網(wǎng)約車(chē)需求預(yù)測(cè)問(wèn)題,該網(wǎng)絡(luò)將區(qū)域網(wǎng)格看作圖的頂點(diǎn),結(jié)合了地理屬性、出入流屬性和社會(huì)屬性構(gòu)建空間圖模型,結(jié)合歷史出行規(guī)律構(gòu)建時(shí)間模型,并引入了注意力機(jī)制,從而可以有效地預(yù)測(cè)區(qū)域內(nèi)的出租車(chē)需求.成都市局部區(qū)域的滴滴快專車(chē)平臺(tái)的軌跡數(shù)據(jù)和紐約市曼哈頓區(qū)出租車(chē)數(shù)據(jù)集用于訓(xùn)練和測(cè)試,實(shí)驗(yàn)結(jié)果表明,該模型的RMSE和SMAPE指標(biāo)均優(yōu)于其余主流模型,其中相較于GEML 模型,在成都市和曼哈頓區(qū)的數(shù)據(jù)集上,MGSTGCN的RMSE指標(biāo)分別降低了16.03%和15.46%,SMAPE指標(biāo)分別降低了11.57%和4.77%,且隨著網(wǎng)格維數(shù)的增加,本文算法的優(yōu)越性越明顯,可以更有效地進(jìn)行網(wǎng)約車(chē)需求預(yù)測(cè).

進(jìn)一步還需要探索的問(wèn)題是找到更好的網(wǎng)格劃分標(biāo)準(zhǔn),同時(shí)再結(jié)合網(wǎng)約車(chē)的營(yíng)收數(shù)據(jù),擴(kuò)展模型功能,有效提高網(wǎng)約車(chē)的運(yùn)營(yíng)效率和營(yíng)收情況.