施 晉,毛嘉莉,金澈清

(華東師范大學(xué) 數(shù)據(jù)科學(xué)與工程學(xué)院,上海 200062)

隨著機(jī)動(dòng)車保有量的激增,城市交通擁堵的狀況加劇惡化,從而導(dǎo)致出行效率低下、資源浪費(fèi)、空氣污染等一系列問題,城市治堵已刻不容緩.合理引導(dǎo)出行路線可以在一定程度上緩解這一問題.隨著定位技術(shù)的發(fā)展與導(dǎo)航軟件的普及,越來越多的司機(jī)依賴導(dǎo)航軟件來規(guī)劃出行路線.旅行時(shí)間預(yù)測,即預(yù)測行駛路線的實(shí)際通行時(shí)間,可以幫助司機(jī)制定行程,避開擁堵路段,在交通管理、拼車、車輛派單等應(yīng)用中具有重要意義.

定位技術(shù)的普及產(chǎn)生了移動(dòng)對(duì)象的海量軌跡數(shù)據(jù),例如出租車、公交車等車輛的行駛軌跡.最直接的旅行時(shí)間預(yù)測方法是通過匹配相似歷史軌跡數(shù)據(jù)來預(yù)測給定路線的旅行時(shí)間.此算法又可分為兩類:一類是直接通過歷史軌跡預(yù)測整段軌跡,但是易受到軌跡偏態(tài)分布性的影響,當(dāng)綜合天氣、節(jié)假日等因素時(shí),部分待預(yù)測軌跡可能無法找到可匹配的近似軌跡;另一類是將軌跡編碼為路網(wǎng)上連續(xù)的子路段,通過分別預(yù)測單個(gè)路段的旅行時(shí)間來估算給定路線的時(shí)間開銷,如圖1(b)所示.將軌跡映射到路段后,如果每個(gè)路段有足夠多的軌跡,可以有效緩解軌跡稀疏的問題.但是對(duì)各路段單獨(dú)預(yù)測會(huì)忽略了路段間上下游的信息,因此可能在一定程度上放大誤差.

Fig.1圖1

車輛的旅行時(shí)間容易受到多重因素影響,包括路段依賴、時(shí)空相關(guān)性及其他外部因素.

1) 路段依賴主要由交通信號(hào)控制引起.例如,當(dāng)行駛路線中存在綠波帶控制的路段時(shí),旅行時(shí)間會(huì)大幅減小;此外,在路口右轉(zhuǎn)的等待時(shí)間比直行等待時(shí)間短;

2) 時(shí)空相關(guān)性體現(xiàn)在城市的擁堵路段,工作日早晚高峰的擁堵路段區(qū)域不同;節(jié)假日期間的擁堵路段區(qū)域與工作日的也不同;

3) 其他外部因素包括天氣狀況、司機(jī)的駕駛習(xí)慣、實(shí)時(shí)路況信息等.

由于上述因素之間相互作用關(guān)系復(fù)雜,因此旅行時(shí)間預(yù)測一直具有挑戰(zhàn)性.鑒于軌跡數(shù)據(jù)是不定長度的時(shí)間序列,傳統(tǒng)方法難以有效整合上述因素與軌跡數(shù)據(jù).神經(jīng)網(wǎng)絡(luò)模型是一種有效的方法.長短期記憶網(wǎng)絡(luò)(long short term memory network,簡稱LSTM network)在每個(gè)時(shí)間點(diǎn)共享參數(shù),適于處理任意長度的時(shí)間序列.Wang等人[1]使用 LSTM 提取軌跡的時(shí)間依賴,并結(jié)合外部因素建模預(yù)測旅行時(shí)間.但是該方法依然存在不足:如圖1(a)所示,該算法將原始軌跡點(diǎn)均勻采樣成等距離的軌跡點(diǎn)作為輸入,可能會(huì)丟失部分路口的轉(zhuǎn)彎信息.例如,p4→p5→p6將被視作一條道路,從而在建模過程中引入錯(cuò)誤的特征.

鑒于此,本文提出了基于路段編碼優(yōu)化的深度旅行時(shí)間預(yù)測框架(road-segment encoding deep travel time estimation framework,簡稱REDTTE).REDTTE框架包括兩個(gè)階段.

(1) 針對(duì)使用原始軌跡(以經(jīng)緯度坐標(biāo)表示)作為輸入而引起誤差的問題,擬通過對(duì)路段建模并使用路段向量映射(road segment vectorization,簡稱RSV)模型將路段映射到低維向量中,保留路段間上下游依賴關(guān)系;

(2) 針對(duì)不定長序列數(shù)據(jù)難以處理以及外部特征較難引入的問題,結(jié)合神經(jīng)網(wǎng)絡(luò)模型能夠處理不定長序列并且能夠捕捉軌跡時(shí)空特征的優(yōu)勢,設(shè)計(jì)了長短期記憶網(wǎng)絡(luò)和卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network,簡稱CNN)的混合模型對(duì)(LSTM-CNN-LSTM,簡稱LCL)預(yù)測旅行時(shí)間.

本文的貢獻(xiàn)主要有以下幾點(diǎn).

(1) 受到詞嵌入(word embedding)技術(shù)的啟發(fā),設(shè)計(jì)了RSV模型,融合神經(jīng)網(wǎng)絡(luò)語言模型的處理思路至路段編碼,將路段映射到低維向量保留路段間的依賴關(guān)系.映射過程中,使用Skip-Gram模型對(duì)路段序列進(jìn)行學(xué)習(xí),確保具有上下游關(guān)系的路段向量間距離較近,無上下游關(guān)系的路段向量距離較遠(yuǎn).本文首次通過將深度表征學(xué)習(xí)引入改進(jìn)路段的編碼方式,并將其應(yīng)用于旅行時(shí)間的預(yù)測;

(2) 基于路段向量的編碼模式,設(shè)計(jì)了LCL模型用于預(yù)測旅行時(shí)間.該模型通過輸入組件將路段向量與其他外部特征(天氣、節(jié)假日)進(jìn)行整合,通過LSTM與CNN的混合神經(jīng)網(wǎng)絡(luò)分別提取時(shí)間、空間特征,在數(shù)據(jù)允許的情況下,還能將路況信息、道路限速信息、車輛型號(hào)等信息引入模型,提升預(yù)測精度;

(3) 結(jié)合RSV與LCL模型,提出了旅行時(shí)間預(yù)測框架REDTTE.通過使用出租車的軌跡數(shù)據(jù)訓(xùn)練REDTTE框架,驗(yàn)證了該框架的有效性.此外,基于真實(shí)數(shù)據(jù)集合的對(duì)比實(shí)驗(yàn)結(jié)果表明,本文所提方法比對(duì)比算法的預(yù)測精度更高.

本文第1節(jié)介紹基于深度學(xué)習(xí)理論的軌跡序列處理技術(shù)及旅行時(shí)間預(yù)測的相關(guān)工作.第2節(jié)形式化定義相關(guān)概念,并介紹REDTTE的總體框架.第3節(jié)詳細(xì)介紹框架中兩個(gè)模型.第4節(jié)介紹本文所提方法在出租車軌跡數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)結(jié)果.第5節(jié)總結(jié)全文并指出未來的工作思路.

1 相關(guān)工作

本節(jié)回顧基于深度學(xué)習(xí)理論的軌跡序列處理方法以及現(xiàn)有的旅行時(shí)間預(yù)測方法.

1.1 基于深度學(xué)習(xí)的軌跡序列處理技術(shù)

深度學(xué)習(xí)已廣泛應(yīng)用在圖像處理、自然語言處理等多個(gè)領(lǐng)域.近年來,不少研究工作利用深度學(xué)習(xí)理論處理軌跡數(shù)據(jù),其中最為普遍的是卷積神經(jīng)網(wǎng)絡(luò)與循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network,簡稱RNN).

CNN通過卷積、池化等操作,可以提取網(wǎng)格結(jié)構(gòu)數(shù)據(jù)中的空間特征[2].部分工作將軌跡數(shù)據(jù)轉(zhuǎn)換為網(wǎng)格數(shù)據(jù)使用CNN進(jìn)行處理,有效提升了路段行駛速度與人流量預(yù)測的精度[3,4].RNN是專門處理時(shí)間序列數(shù)據(jù)的神經(jīng)網(wǎng)絡(luò)模型[5].Dong使用RNN構(gòu)建了一個(gè)自編碼器用于提取軌跡序列中的時(shí)間依賴特征,并分析司機(jī)的駕駛行為,在司機(jī)數(shù)量估算和軌跡分類上取得了較高的準(zhǔn)確率[6].然而,傳統(tǒng)的 RNN模型僅由一個(gè)隱層記錄歷史信息,當(dāng)輸入序列過長時(shí)會(huì)產(chǎn)生梯度消失以及梯度爆炸問題[7],導(dǎo)致難以處理長時(shí)間的依賴關(guān)系.LSTM 模型通過引入記憶單元存儲(chǔ)相關(guān)的歷史數(shù)據(jù),有效緩解了難以捕捉長期依賴的問題[8].Song使用多層LSTM網(wǎng)絡(luò)模型提取軌跡數(shù)據(jù)上的時(shí)間依賴關(guān)系,用于預(yù)測城市的出行模式[9].

1.2 旅行時(shí)間預(yù)測

早期的旅行時(shí)間預(yù)測工作主要基于線圈傳感器所采集的數(shù)據(jù),記錄車輛通過一個(gè)路段的行駛時(shí)間進(jìn)行建模,來預(yù)測車輛的旅行時(shí)間[10-12].然而,由于線圈傳感器僅僅部署在城市的部分路段上,這類算法難以預(yù)測整個(gè)城市路網(wǎng)車輛的旅行時(shí)間.現(xiàn)有的工作大多使用浮動(dòng)車的歷史軌跡對(duì)旅行時(shí)間進(jìn)行預(yù)測,根據(jù)軌跡數(shù)據(jù)的處理方式不同,可以劃分為基于路段的旅行時(shí)間預(yù)測與基于路徑的旅行時(shí)間預(yù)測.

· 基于路段的旅行時(shí)間預(yù)測:將軌跡切分成路段,可以緩解軌跡稀疏帶來的影響.Jenelius針對(duì)低采樣率的軌跡數(shù)據(jù)使用概率建模,并用極大似然估計(jì)進(jìn)行參數(shù)估計(jì).考慮到外部因素的影響,模型將旅行時(shí)間視為一個(gè)多變量的正態(tài)分布[13].Yang通過時(shí)空相關(guān)的隱馬爾可夫模型對(duì)路段的時(shí)空依賴關(guān)系進(jìn)行建模,對(duì)路段的旅行時(shí)間分布進(jìn)行預(yù)測[14].該類算法未考慮結(jié)合多源的外部特征(如天氣、日期等)來提高算法的預(yù)測精度;

· 基于路徑的旅行時(shí)間預(yù)測:Rahmani根據(jù)浮動(dòng)車的歷史軌跡數(shù)據(jù)提出了一種非參數(shù)的方法,通過對(duì)歷史軌跡的時(shí)間加權(quán)作為旅行時(shí)間估計(jì)結(jié)果[15].然而,直接基于歷史軌跡時(shí)間估計(jì)旅行時(shí)間會(huì)面臨軌跡稀疏問題.當(dāng)待預(yù)測的行駛路線缺少與其對(duì)應(yīng)的歷史軌跡時(shí),該方法難以給出一個(gè)精確解.部分研究工作使用k近鄰搜索和加權(quán)平均的思想,通過查找相似的軌跡來減輕軌跡稀疏帶來的影響[16,17].Wang等人使用張量對(duì)映射到路段的軌跡數(shù)據(jù)進(jìn)行建模,同時(shí),利用張量分解重建技術(shù)引入路段間上下文關(guān)系的特征[18].

基于樹的模型可以整合多源的外部特征,Lam使用梯度提升決策樹(gradient boosting decision tree,簡稱GBDT)、隨機(jī)森林(random forest,簡稱RF)等多種樹模型預(yù)測旅行時(shí)間[19].Wang利用樹模型整合外部特征,結(jié)合時(shí)空相關(guān)的概率圖模型預(yù)測旅行時(shí)間[20].這兩個(gè)方法提高了預(yù)測精度,但因軌跡序列的長度不固定,傳統(tǒng)的機(jī)器學(xué)習(xí)模型難以處理這類數(shù)據(jù).同時(shí),軌跡數(shù)據(jù)是時(shí)空相關(guān)數(shù)據(jù),這些模型不能有效提取數(shù)據(jù)中的時(shí)空依賴特征.

Wang等人提出了DeepTTE模型,結(jié)合CNN和LSTM提取軌跡數(shù)據(jù)的時(shí)空特征,并且整合Attention機(jī)制預(yù)測旅行時(shí)間[1].然而,由于該方法直接使用原始軌跡數(shù)據(jù)進(jìn)行建模,在訓(xùn)練過程中無法學(xué)習(xí)到路網(wǎng)的相關(guān)特征,容易引入錯(cuò)誤特征.可以通過將軌跡映射到路段的方式引入路網(wǎng)特征,然而路段如果采用序號(hào)編碼無法反映路段間的上下游關(guān)系,需要對(duì)其進(jìn)一步編碼.這與自然語言處理中的語言模型的處理思路類似.早期的自然語言處理中,大多采用 one-hot編碼對(duì)單詞進(jìn)行表示.由于這一方法存在的巨大缺陷,Bengio提出使用三層神經(jīng)網(wǎng)絡(luò)對(duì)語言模型進(jìn)行建模[21],Collobert使用神經(jīng)網(wǎng)絡(luò)語言模型生成詞向量,并在詞性標(biāo)注、短語識(shí)別、語義角色標(biāo)注等任務(wù)中表現(xiàn)良好[22].為了提升神經(jīng)網(wǎng)絡(luò)語言模型在大型語料庫中的效果和性能,Mikolov提出了Skip-Gram模型[23],并推動(dòng)了詞嵌入技術(shù)在這一領(lǐng)域的發(fā)展.由于基于負(fù)采樣的Skip-Gram模型能夠快速訓(xùn)練,并且在大規(guī)模的數(shù)據(jù)集中具有較好的編碼效果,本文考慮將其引入用于路段編碼的表示優(yōu)化.在此基礎(chǔ)上,采用LCL模型通過LSTM模型處理路段向量這一時(shí)間序列數(shù)據(jù),并提取路段間的深層依賴關(guān)系,相比DeepTTE需先通過CNN提取軌跡點(diǎn)的轉(zhuǎn)彎行駛等信息,本文的方法不會(huì)放大軌跡點(diǎn)的定位誤差,因而有效提升了旅行時(shí)間預(yù)測精度.

2 概念定義與整體框架

2.1 概念定義

軌跡數(shù)據(jù)通過采集車輛行駛過程中的GPS數(shù)據(jù)獲得.

定義1(軌跡).一條軌跡Tra是帶有時(shí)間屬性的位置點(diǎn)序列,表示為Tra={p1,p2,…,pm},其中,每個(gè)位置點(diǎn)包含經(jīng)、緯度信息以及記錄該位置點(diǎn)的時(shí)間戳,pi=(lngi,lati,timei).

由于軌跡數(shù)據(jù)以一定的時(shí)間間隔采集,且GPS定位技術(shù)本身也存在誤差,僅憑車輛的軌跡數(shù)據(jù)難以還原車輛真實(shí)的行駛情況.在對(duì)軌跡數(shù)據(jù)的預(yù)處理階段,常結(jié)合路網(wǎng)數(shù)據(jù)對(duì)原始軌跡進(jìn)行地圖匹配,將車輛軌跡映射到路網(wǎng)中的真實(shí)路段.

定義2(路網(wǎng)).一個(gè)城市的路網(wǎng)以有向圖表示,即G=(V,R),其中:V為頂點(diǎn)集合,表示道路交叉口;R={r}為連接頂點(diǎn)之間路段的集合,其中,每個(gè)路段r包含路段標(biāo)識(shí)符信息r.id以及路段長度r.dis.

將軌跡映射到路段后,軌跡點(diǎn)依次經(jīng)過的路段序列可用來描述整條軌跡的信息.

定義3(路段序列).一個(gè)路段序列RS是通過地圖匹配將歷史軌跡序列Tra映射到一個(gè)有序路段序列RS={r1,r2,…,rn},其中,在一個(gè)路段上的連續(xù)軌跡點(diǎn)被映射到同一個(gè)路段r.

如果使用路段序列對(duì)軌跡進(jìn)行編碼,各路段由其對(duì)應(yīng)的id標(biāo)識(shí),此編碼丟失了路段之間的上下游關(guān)系,同時(shí),也難以將其作為模型的輸入進(jìn)行訓(xùn)練.所以,我們使用路段向量序列對(duì)輸入軌跡進(jìn)行編碼.

定義4(路段向量序列).路段向量集合是通過一定的映射方式f將路網(wǎng)中路段集合{r}映射到一個(gè)向量集合{rv};而路段向量序列RV則是由路段序列RS對(duì)各路段使用f映射獲得的向量序列,表示為RV={rv1,rv2,…,rvn}.

將路段向量序列與其他外部特征使用模型進(jìn)行融合作為輸入特征,并以該段軌跡的旅行時(shí)間作為標(biāo)簽,旅行時(shí)間預(yù)測問題可以轉(zhuǎn)換為一個(gè)監(jiān)督學(xué)習(xí)的問題.

定義5(旅行時(shí)間預(yù)測).給定一段軌跡Tra={p1,p2,…,pm},對(duì)這段軌跡的旅行時(shí)間T(T=pmtime-p1time)進(jìn)行預(yù)測,同時(shí)確保預(yù)測值T與真實(shí)值間的誤差最小化.此外,軌跡數(shù)據(jù)的時(shí)間戳僅用于結(jié)果的驗(yàn)證,在預(yù)測過程中會(huì)將其去除.

2.2 總體框架

REDTTE框架包括3部分:軌跡預(yù)處理、模型訓(xùn)練、在線預(yù)測,如圖2所示.

在軌跡預(yù)處理階段,通過地圖匹配,將歷史軌跡數(shù)據(jù)映射為路段序列,該序列將作為RSV模型訓(xùn)練的輸入;

在模型訓(xùn)練階段,主要針對(duì)RSV以及LCL模型進(jìn)行兩階段訓(xùn)練.第1階段的訓(xùn)練過程中,將軌跡序列輸入到RSV模型進(jìn)行訓(xùn)練,使得路網(wǎng)中每一個(gè)道路id映射到一個(gè)低維向量.RSV模型訓(xùn)練完畢后,對(duì)路段序列所有路段使用該模型進(jìn)行映射;第2階段訓(xùn)練LCL模型的3個(gè)組件:首先,通過特征嵌入方式將路段向量與天氣、節(jié)假日等外部特征相結(jié)合,作為模型的輸入;輸入組件對(duì)輸入特征進(jìn)行整合后,將輸入的特征序列通過深度特征提取組件的LSTM和CNN模型獲取時(shí)空相關(guān)特征;最后,由LSTM和均勻池化組成的預(yù)測組件預(yù)測旅行時(shí)間進(jìn)行;根據(jù)預(yù)測結(jié)果與真實(shí)值的誤差,LCL模型的訓(xùn)練可通過反向傳播調(diào)整模型參數(shù);

在線預(yù)測階段,使用訓(xùn)練好的模型參數(shù)進(jìn)行預(yù)測.可以直接輸入預(yù)測軌跡,也可以使用路段序列作為輸入.除軌跡數(shù)據(jù)以外,預(yù)測階段同樣需要輸入外部特征.天氣和節(jié)假日等外部特征可以通過天氣預(yù)報(bào)等信息提前獲得.REDTTE框架輸入的序列數(shù)據(jù)本質(zhì)上是路段數(shù)據(jù),因此,REDTTE框架也可以結(jié)合路況信息作為外部特征來提升預(yù)測精度.

Fig.2 REDTTE’s global architecture圖2 REDTTE整體框架圖

3 模型概述

3.1 路段向量映射

將歷史軌跡通過地圖匹配方式轉(zhuǎn)換為路段序列RS={r1,r2,…,rn},其中每個(gè)路段有對(duì)應(yīng)的路段序號(hào)r.id以及長度r.dis.由于僅靠路段序號(hào)無法辨識(shí)路段之間的上下游依賴關(guān)系,該編碼方式在一定程度上丟失了重要軌跡的信息.同時(shí),若直接將序號(hào)作為模型的輸入,模型可能會(huì)認(rèn)為序號(hào)相近的路段具有上下游關(guān)系,而這與事實(shí)不符.因此,需要一種方法將路段映射到低維的向量中.

one-hot編碼是一種簡單的映射方法.如后文圖4所示,輸入一個(gè)L維的向量,L為類別的數(shù)量,其中大部分項(xiàng)值為 0,只有與序號(hào)對(duì)應(yīng)的項(xiàng)值為 1,表示當(dāng)前路段.但這一編碼方式無法描述相鄰路段關(guān)聯(lián)性.另一種編碼方式使用每個(gè)路段中心點(diǎn)的經(jīng)、緯度坐標(biāo)來表示一個(gè)路段,但是該編碼無法識(shí)別雙向車道的上下游路段.

詞嵌入技術(shù)將詞匯映射到低維向量,語義相近的詞所對(duì)應(yīng)的向量的距離較近,這與本任務(wù)的目標(biāo)較為貼切,因此我們?cè)?RSV模型中引入基于負(fù)采樣 Skip-Gram模型對(duì)路段進(jìn)行映射,其主要思想是:對(duì)于一個(gè)輸入路段,預(yù)測其前后T個(gè)路段.這實(shí)質(zhì)上是一個(gè)多標(biāo)簽(multi-label)問題,可以通過負(fù)采樣生成負(fù)樣本的方式轉(zhuǎn)變成回歸問題.

首先,對(duì)路段序列使用滑動(dòng)窗口模型生成訓(xùn)練樣本,如圖3所示.對(duì)一個(gè)路段序列使用滑動(dòng)窗口技術(shù),當(dāng)窗口指針指向r4向量,窗口大小為2時(shí)生成4個(gè)正樣本.

隨后構(gòu)造中心路段的偽鄰居路段作為負(fù)樣本,負(fù)樣本的生成根據(jù)每個(gè)路段出現(xiàn)的頻次加權(quán)采樣生成,出現(xiàn)頻率越高的路段越容易被采樣生成負(fù)樣本.路段被采樣到的概率如下:

其中,freq(ri)函數(shù)用于統(tǒng)計(jì)路段出現(xiàn)的頻次,這里引入了拉普拉斯修正防止部分路段因缺失數(shù)據(jù)而不被采樣.

Fig.3 Example of sliding window model圖3 滑動(dòng)窗口模型示意圖

樣本打分模型應(yīng)能根據(jù)映射到的隱層信息,對(duì)正負(fù)樣本給予正確的判斷,即判斷出正確的具有上下游關(guān)系的路段,因此需要模型對(duì)輸入的樣本對(duì)進(jìn)行打分.

圖4為樣本打分模型,主要分為輸入層、隱層和輸出層.輸入層為中心路段和鄰近路段(或偽鄰近路段)的one-hot編碼,分別為rc和rn.隱層h通過輸入層和矩陣WLH計(jì)算獲得,即h=f(r)=σ(WLHx+b),其中:b為該層的偏置向量;σ為激活函數(shù),通常使用sigmoid函數(shù)σ(x)=1/(1+e-x).中心路段和鄰近路段分別采用不同的參數(shù)映射到隱層,即.通過矩陣將輸入映射到隱層向量后,對(duì)兩個(gè)隱層向量進(jìn)行按元素相乘操作,并通過激活函數(shù)限制其大小,最后對(duì)向量進(jìn)行求和,得到一個(gè)分?jǐn)?shù)yscore.模型訓(xùn)練完成后,中心路段的隱層為所求的低維向量,而輸入層到隱層的映射f就是所求的映射.

Fig.4 Scoring model圖4 樣本打分模型

RSV模型同時(shí)對(duì)輸入的正負(fù)樣本進(jìn)行打分,并控制其比例為1:k.每次迭代,對(duì)輸入的一個(gè)正樣本對(duì)和k個(gè)負(fù)樣本對(duì)同時(shí)使用打分模型進(jìn)行打分.打分模型的輸入為(ri,rj),模型需要最大化正樣本分?jǐn)?shù)的同時(shí)最小化負(fù)樣本的分?jǐn)?shù),目標(biāo)函數(shù)為

其中,Nei(ri)表示ri的相鄰路段,Neg(ri)表示對(duì)ri負(fù)采樣生成的所有路段.條件概率表示為

f為將道路id映射到路段向量的函數(shù),g為輔助函數(shù),兩函數(shù)映射后的向量維數(shù)相同,σ(x)為sigmoid函數(shù).可以看出,目標(biāo)函數(shù)存在大量的連乘.為便于計(jì)算,這里對(duì)L取對(duì)數(shù),目標(biāo)函數(shù)變?yōu)?/p>

通過將歷史軌跡的路段向量通過RSV模型進(jìn)行訓(xùn)練,可以得到一個(gè)f將道路id映射到道路向量rvi中.通過對(duì)映射到向量空間的路段向量進(jìn)一步觀察發(fā)現(xiàn):具有上下游關(guān)系的路段映射到向量空間后,向量間的距離比沒有上下游關(guān)系的路段向量更近.因此,通過RSV編碼能夠很好地保留路段間的上下游依賴信息.

3.2 混合神經(jīng)網(wǎng)絡(luò)

LCL模型的框架如圖5所示,模型分為3個(gè)組件:輸入組件主要用于結(jié)合外部特征、路段序列及其統(tǒng)計(jì)量(如出發(fā)時(shí)間、路段長度等)生成下一階段模型的輸入;深度特征提取組件主要用于提取輸入數(shù)據(jù)中的時(shí)空特征;預(yù)測組件根據(jù)提取出的高維度特征,結(jié)合LSTM模型和均勻池化層對(duì)旅行時(shí)間進(jìn)行預(yù)測.

Fig.5 LCL architecture圖5 LCL模型框架圖

3.2.1 輸入組件

前面使用RSV模型將每個(gè)路段id映射到一個(gè)路段向量中,因此,將每個(gè)路段序列映射為路段向量序列RV={rv1,rv2,…,rvn,rve}作為特征組件的部分輸入.其中,為了標(biāo)志軌跡序列的結(jié)尾,幫助模型對(duì)軌跡終點(diǎn)的判斷,引入零向量rve作為每條軌跡的終止向量.由于交叉路口的特征通常由兩個(gè)路口進(jìn)行表示(例如圖1(b)中的RS2→RS3表示左轉(zhuǎn),RS3→RS4表示右轉(zhuǎn)),因此,這里將兩個(gè)路段向量合并為一個(gè)向量作為輸入,即RVcombine={(rv1,rv2),(rv2,rv3),…,(rvn,rve)},合并后的向量長度與輸入的向量序列長度一致(為n).考慮到軌跡在不同路段的行駛距離是一個(gè)重要因素,尤其對(duì)于起始路段以及終止路段.起始及終止路段通常位于道路的中間部分,直接使用路段長度會(huì)增大模型估計(jì)的旅行時(shí)間.鑒于此,輸入組件計(jì)算目標(biāo)軌跡在每個(gè)路段上的長度disi,并將其作為特征輸入.

模型的輸入組建將一些外部因素(如天氣、節(jié)假日等)與路段向量相結(jié)合,其中,天氣數(shù)據(jù)包含最高溫、最低溫、天氣狀況.與此同時(shí),由于旅行時(shí)間預(yù)測的請(qǐng)求通常帶有出發(fā)時(shí)間,而出發(fā)時(shí)間是一個(gè)很重要的影響因素,考慮將一天劃分成28 800個(gè)時(shí)間槽作為特征輸入,每個(gè)時(shí)間槽對(duì)應(yīng)了3s的時(shí)間間隔.由于城市的交通狀況具有一定的周期性,通常周期為一周[16],因此引入每周的天數(shù)作為輸入的特征.

上述特征除了最低溫度和最高溫度外都是類別變量,不能直接將其作為 LSTM的輸入,采用Gal的特征嵌入方法將類別特征轉(zhuǎn)換為低維向量[20].類別特征c∈[C]通過參數(shù)矩陣WCE映射到空間RE中.其中,C為類別的數(shù)量,E為低維向量的維數(shù),通常情況下,E<

輸入組件最后將以上特征進(jìn)行整合,作為模型組件的輸入,表示為X={X1,X2,…,Xn},其中,Xi={rvi,rvi+1,disi,weather,time,…}.此外,司機(jī)畫像、車輛型號(hào)等信息同樣可以通過特征嵌入的方式進(jìn)行引入,實(shí)時(shí)的路況信息和道路限速信息的引入方式與路段長度的引入方式一致.

3.2.2 深度特征提取組件

深度特征提取組件由兩層模型組成:第 1層循環(huán)神經(jīng)網(wǎng)絡(luò)通過特征提取的方式挖掘路段向量之間的隱含關(guān)系,例如左轉(zhuǎn)、右轉(zhuǎn)、直行等特征;第 2層卷積層能夠挖掘更高層次的路段依賴關(guān)系,同時(shí)提取出更豐富的特征,如綠波帶.

鑒于使用路段向量對(duì)軌跡進(jìn)行編碼,獲得的路段向量序列長度是不固定的,為提取路段向量之間的前后依賴,考慮使用循環(huán)神經(jīng)網(wǎng)絡(luò)提取這部分的依賴特征.

LSTM 的整體結(jié)構(gòu)如圖6所示,它包括輸入層、隱層和輸出層,每個(gè)時(shí)間點(diǎn)共享同一個(gè)參數(shù).當(dāng)前時(shí)間點(diǎn)的隱層是由上一個(gè)時(shí)間點(diǎn)的隱層和當(dāng)前時(shí)間點(diǎn)的輸入所決定的.這樣的結(jié)構(gòu)使 LSTM 能夠保存前序時(shí)刻輸入的特征,從而提取輸入數(shù)據(jù)中的時(shí)間依賴關(guān)系,并處理不定長度的輸入序列.由于隱層的參數(shù)受到當(dāng)前輸入和前一個(gè)時(shí)間點(diǎn)隱層的共同影響,因此無法通過普通的反向傳播算法進(jìn)行訓(xùn)練,采用隨時(shí)間的反向傳播算法(back propagation through time,簡稱BPTT)對(duì)模型進(jìn)行訓(xùn)練.

Fig.6 LSTM structure圖6 LSTM網(wǎng)絡(luò)結(jié)構(gòu)

圖6是LSTM的內(nèi)部結(jié)構(gòu)圖,與RNN相比多了一個(gè)記憶單元Ct,用于記憶歷史信息.LSTM的內(nèi)部結(jié)構(gòu)主要由遺忘門、輸入門、輸出門組成.

· 遺忘門用于在原始記憶單元中丟失部分信息,根據(jù)上一時(shí)間點(diǎn)的隱層信息以及當(dāng)前的輸入,通過激活函數(shù)輸出遺忘元素的概率:

· 輸入門通過類似的結(jié)構(gòu)篩選出輸入數(shù)據(jù)中需保存至記憶單元的數(shù)據(jù),并將其與通過遺忘門之后的記憶單元的數(shù)據(jù)相加作為記憶單元的輸出:

· 最后,隱層的數(shù)據(jù)通過輸出門的數(shù)據(jù)與新的記憶單元的數(shù)據(jù)進(jìn)行逐點(diǎn)相乘計(jì)算得到:

在實(shí)際訓(xùn)練過程中,將特征組件得到的特征序列X={X1,X2,…,Xn}依次輸入到第1層的LSTM中,并將隱層數(shù)據(jù)提取出來作為下一層模型的輸入.

通過 LSTM提取上下路段間的時(shí)間依賴后,LCL模型通過卷積神經(jīng)網(wǎng)絡(luò)挖掘多個(gè)路段間的依賴關(guān)系來豐富特征的多樣性,同時(shí)挖掘出路段間更深層次的聯(lián)系(如綠波帶等信息).

考慮將卷積層引入,用以提取空間特征.由于輸入的隱層序列是一維的序列,因此使用一維的卷積核對(duì)序列進(jìn)行卷積操作.卷積的操作如圖7所示,以大小為kn=4的卷積核為例,其中,填充向量pad用于保證輸出序列的長度和輸入序列的長度一致,個(gè)數(shù)為kn-1.我們加入了與輸入的隱層h1同維數(shù)填充零向量,卷積層的輸入為,那么其輸出為,其中,每個(gè)元素表示為

Fig.7 Conv1d diagram圖7 Conv1d示意圖

3.2.3 預(yù)測組件

LSTM 模型不僅可以用于特征提取,其輸出同樣可以用于回歸、分類等任務(wù).在預(yù)測組件中,模型將上一層卷積層的輸出作為第3層LSTM的輸入.為了在旅行時(shí)間的預(yù)測過程中考慮到所有的路段,該層LSTM依舊使用與第1層的LSTM一致的多對(duì)多網(wǎng)絡(luò)結(jié)構(gòu),并將隱層的信息作為均勻池化層的輸入.

由于最后輸出的序列長度與輸入的路段序列長度相同,但旅行時(shí)間預(yù)測的目標(biāo)是一個(gè)實(shí)值,因此使用均勻池化將LSTM隱層的輸出映射為一個(gè)實(shí)值作為最終預(yù)測的旅行時(shí)間:

3.2.4 損失函數(shù)

鑒于長度越長的軌跡預(yù)測誤差時(shí)間越大,直接使用MAE作為損失函數(shù)會(huì)使模型更加偏重于旅行時(shí)間較長的軌跡.為保證模型同時(shí)優(yōu)化短途和長途的軌跡,采用相對(duì)百分誤差的絕對(duì)值(mean absolute percentage error,簡稱MAPE)作為模型的損失函數(shù):

根據(jù)損失函數(shù)提供的梯度信息,模型參數(shù)可以通過反向傳播不斷學(xué)習(xí)調(diào)整.

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

為了驗(yàn)證 REDTTE框架的有效性,本文基于出租車軌跡數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)以及各模塊的有效性驗(yàn)證實(shí)驗(yàn).通過與 AVG,KNN等傳統(tǒng)旅行時(shí)間預(yù)測算法的對(duì)比實(shí)驗(yàn),驗(yàn)證深度學(xué)習(xí)模型處理旅行時(shí)間預(yù)測問題的優(yōu)越性.通過與 DeepTTE算法的對(duì)比實(shí)驗(yàn)來驗(yàn)證 REDTTE模型結(jié)構(gòu)的有效性.此外,為驗(yàn)證路段向量編碼以及深度特征提取組件的有效性,分別執(zhí)行了與PLCL(point LCL)及LC算法的對(duì)比實(shí)驗(yàn).

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 數(shù)據(jù)集

· 軌跡數(shù)據(jù):本文使用滴滴開放的蓋亞計(jì)劃(https://outreach.didichuxing.com/research/opendata/)數(shù)據(jù)集.該數(shù)據(jù)集提取成都2016年11月30天的車輛軌跡數(shù)據(jù),包含10億GPS坐標(biāo)點(diǎn)、400多萬條軌跡.由于數(shù)據(jù)集每天采取不同的哈希函數(shù)對(duì)司機(jī)ID進(jìn)行脫敏,因此,實(shí)驗(yàn)中無法使用司機(jī)ID作為外部特征;

· 路網(wǎng)數(shù)據(jù):為了保證數(shù)據(jù)的一致性,路網(wǎng)數(shù)據(jù)使用成都市 2016年的 OpenStreetMap(https://www.openstreetmap.org)數(shù)據(jù),對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行地圖匹配后獲得5 856條路段;

· 外部因素:成都市的天氣數(shù)據(jù)通過爬蟲抓取,包含天氣狀況(晴天、雨天等4種天氣狀態(tài))、最低氣溫與最高氣溫等信息.

4.1.2 實(shí)驗(yàn)環(huán)境

本文使用python語言完成全部實(shí)驗(yàn)的編寫,并使用基于python的深度學(xué)習(xí)框架Pytorch 0.3框架實(shí)現(xiàn)了部分模型的編寫.硬件環(huán)境為160G內(nèi)存,兩個(gè)8核的Intel Xeon Silver 4110處理器以及一個(gè)NVIDIA Tesla K80 GPU.模型的訓(xùn)練與測試均在GPU上進(jìn)行.

4.1.3 評(píng)測指標(biāo)

為了更全面地評(píng)估框架預(yù)測旅行時(shí)間的效果,本文使用了 4種評(píng)測指標(biāo):平均絕對(duì)值誤差(mean absolute error,簡稱 MAE)、均方根誤差(root mean square error,簡稱 RMSE)、MAPE(見公式(13))、MAE/D.

由于MAE會(huì)受到路徑長度的影響,即越長的路徑旅行時(shí)間越長,因此誤差可能就會(huì)越大.考慮將MAE與軌跡長度的比值,即MAE/D,作為衡量算法在每公里的預(yù)測誤差時(shí)間.

4.1.4 參數(shù)設(shè)置

· RSV:考慮到部分路段長度較短,在采樣的過程中軌跡可能會(huì)跳過這些路段,因此,基于實(shí)驗(yàn)數(shù)據(jù)集將滑動(dòng)窗口大小設(shè)置為 3,正負(fù)樣本的采樣比為1:5.映射到向量空間的維度設(shè)為10維,為加快訓(xùn)練速度,訓(xùn)練過程中采取了批梯度下降,批量設(shè)為50,初始學(xué)習(xí)速率設(shè)為0.025,樣本訓(xùn)練一個(gè)周期;

· LCL:輸入組件部分,將每周的天數(shù)映射到3維的向量,小時(shí)映射到10維的向量,時(shí)間槽映射到40維的向量.深度特征提取組件的LSTM的隱層維數(shù)為84,CNN的通道數(shù)為36,卷積核大小為4.預(yù)測組件的LSTM與上一層的LSTM參數(shù)一致.

為加速模型的訓(xùn)練,我們對(duì)數(shù)據(jù)集進(jìn)行分批訓(xùn)練,模型的批量為64,初始的學(xué)習(xí)速率為0.002,模型訓(xùn)練10個(gè)周期.

4.1.5 對(duì)比算法

· Avg算法是作為旅行時(shí)間預(yù)測對(duì)比的一種基準(zhǔn)算法,算法將一天以 10分鐘的間隔劃分成 144個(gè)時(shí)間槽.通過計(jì)算軌跡長度與對(duì)應(yīng)出發(fā)時(shí)間的歷史軌跡平均速度的比值作為旅行時(shí)間.在計(jì)算過程中同樣考慮到了每周的天數(shù)帶來的影響,例如,周一的旅行時(shí)間會(huì)考慮歷史的周一在該時(shí)間槽內(nèi)出發(fā)的軌跡的平均速度;

· KNN算法是一種非參數(shù)的算法,算法根據(jù)待查詢軌跡的起點(diǎn)和終點(diǎn)查詢與其起點(diǎn)和終點(diǎn)相近的歷史軌跡,根據(jù)鄰近軌跡與查詢軌跡的出發(fā)時(shí)間和節(jié)假日、軌跡長度等信息,對(duì)鄰近軌跡的旅行時(shí)間進(jìn)行加權(quán)和作為最后預(yù)測的旅行時(shí)間.在實(shí)驗(yàn)過程中,選取了k=10作為具體的參數(shù),當(dāng)算法查詢不到足夠數(shù)量的鄰近點(diǎn)時(shí),會(huì)同時(shí)擴(kuò)大起點(diǎn)和終點(diǎn)的搜索范圍,直到找到足夠的鄰近軌跡;

· PLCL(point LCL)將LCL模型的輸入由路段向量序列替換為每個(gè)路段的中心經(jīng)緯度坐標(biāo)點(diǎn),其余的參數(shù)及特征設(shè)置與LCL一致;

· LC為LCL模型的簡化版本,LC模型去掉了第3層的LSTM,將卷積層的輸出直接連接池化層,輸出最后的旅行時(shí)間.除此之外,其余參數(shù)特征與LCL一致;

· DeepTTE[1]是當(dāng)前主流的旅行時(shí)間預(yù)測算法.算法使用經(jīng)、緯度作為模型的輸入,利用混合神經(jīng)網(wǎng)絡(luò)分別提取軌跡數(shù)據(jù)的時(shí)空依賴.同時(shí),通過Attention機(jī)制以及特征嵌入的方式將外部因素引入.這里,我們使用算法開放的源代碼與算法表現(xiàn)最優(yōu)的參數(shù),并在實(shí)驗(yàn)數(shù)據(jù)集下進(jìn)行微調(diào)優(yōu)化.模型使用的外部特征與LCL使用的外部特征一致.

4.2 實(shí)驗(yàn)效果

為了展示路段向量的表示效果,選取成都青羊區(qū)的部分區(qū)域進(jìn)行可視化展示.圖8所示為RV1,RV2兩個(gè)路段向量的示意圖.其中,橫縱坐標(biāo)分別表示經(jīng)緯度.圖中反映了該區(qū)域的路網(wǎng)情況,以顏色的深淺表示對(duì)應(yīng)路段的路段向量與示意路段向量間的距離.黑色表示距離為零,顏色越淡表示距離越遠(yuǎn).從圖中可以看出:路段向量的表示方式保留了路段上下游的依賴關(guān)系,與目標(biāo)向量具有上下游關(guān)系的路段,其路段向量距離較近,而不具有上下游關(guān)系的路段向量則距離較遠(yuǎn).

Fig.8 Schematic plot for road vector圖8 路段向量示意圖

為了驗(yàn)證算法的準(zhǔn)確率,將數(shù)據(jù)集中前23天的數(shù)據(jù)作為模型的訓(xùn)練數(shù)據(jù),后7天的數(shù)據(jù)作為驗(yàn)證數(shù)據(jù).表1為算法及對(duì)比算法在該數(shù)據(jù)集下各項(xiàng)指標(biāo)的預(yù)測結(jié)果,可以看出,本文提出的方法在各項(xiàng)誤差指標(biāo)中均擁有最低的誤差.

Table1 Error comparison表1 誤差對(duì)比

通過 PLCL和 LCL的誤差對(duì)比可以發(fā)現(xiàn):將路段向量替換為經(jīng)緯度坐標(biāo)后,模型的誤差值上升,這證明了RSV算法的有效性.同樣,通過LC和其他算法的誤差對(duì)比可以發(fā)現(xiàn),直接使用深度特征提取組件的輸出預(yù)測旅行時(shí)間具有較高的準(zhǔn)確率.通過LC及PLCL與DeepTTE的對(duì)比可以發(fā)現(xiàn):使用REDTTE的部分模型結(jié)構(gòu)預(yù)測旅行時(shí)間具有較好的效果,甚至在部分指標(biāo)的對(duì)比中優(yōu)于DeepTTE的表現(xiàn).

為了驗(yàn)證DeepTTE,LCL,LC及PLCL算法在不同影響因素下的敏感性以及預(yù)測精度,分別統(tǒng)計(jì)了不同軌跡長度以及不同出發(fā)時(shí)間對(duì)上述算法的影響.圖9為不同軌跡長度對(duì)上述算法的影響,橫坐標(biāo)為軌跡的長度,縱坐標(biāo)為MAPE.可以發(fā)現(xiàn):在路段長度較短時(shí),真實(shí)的旅行時(shí)間往往較短,小的偏差會(huì)導(dǎo)致MAPE值增大.因此,上述算法均在較短的軌跡上具有較大的MAPE值.

Fig.9 Influence of trajectory distance on each algorithm圖9 軌跡長度對(duì)各算法的影響

為評(píng)測出發(fā)時(shí)間對(duì)各算法的影響,分別對(duì)比工作日與節(jié)假日的 MAE和 MAPE兩個(gè)指標(biāo)的算法效果.如圖10、圖11所示,其中,橫坐標(biāo)是以小時(shí)為單位劃分的時(shí)段,縱坐標(biāo)為對(duì)應(yīng)的各項(xiàng)指標(biāo)值.

Fig.10 Influence of start time (weekday) on each algorithm圖10 出發(fā)時(shí)間對(duì)各算法的影響(工作日)

Fig.11 Influence of start time (weekend) on each algorithm圖11 出發(fā)時(shí)間對(duì)各算法的影響(節(jié)假日)

可以看出:在工作日的早晚高峰期間,算法的誤差普遍偏高.通過對(duì)早晚高峰期的數(shù)據(jù)分析,可以發(fā)現(xiàn)旅行時(shí)間在這一時(shí)間段擁有較高的方差,因此難以做到準(zhǔn)確的預(yù)測.產(chǎn)生這一現(xiàn)象的主要原因是:早晚高峰期間道路情況多變,各模型因未引入路況信息作為外部特征,難以捕捉實(shí)時(shí)變化的道路擁堵狀況.在節(jié)假日期間,由于路況復(fù)雜多變,各算法的誤差要大于工作日的預(yù)測誤差.

4.3 性能測試

旅行時(shí)間預(yù)測通常應(yīng)用于實(shí)時(shí)性需求較強(qiáng)的環(huán)境中,因此其運(yùn)行效率是一個(gè)重要的參考指標(biāo).為了驗(yàn)證算法的執(zhí)行效率以及分布式場景下的可擴(kuò)展性,通過在 GPU上運(yùn)行算法,設(shè)立了不同的批次模擬并行環(huán)境.同時(shí),考慮到設(shè)備性能波動(dòng)而產(chǎn)生的時(shí)間誤差,實(shí)驗(yàn)分別在不同批次下對(duì) 100萬條軌跡進(jìn)行查詢,并統(tǒng)計(jì)其平均時(shí)間開銷.查詢實(shí)驗(yàn)的硬件環(huán)境與第4.1.2節(jié)的實(shí)驗(yàn)環(huán)境一致.

圖12為算法在 64,80,96,112,128批次下平均單條軌跡的查詢時(shí)間效果圖,橫軸為批次大小,縱軸為單條軌跡的平均查詢時(shí)間.從實(shí)驗(yàn)結(jié)果可以看出:算法對(duì)于單條軌跡的響應(yīng)時(shí)間均為毫秒級(jí),具有較高的實(shí)時(shí)性;并且隨著批次的增多,平均單條軌跡的查詢時(shí)間隨著線性減少.這是因?yàn)樗惴ㄔ谶\(yùn)行過程中僅需要進(jìn)行路段序列的映射以及 LCL模型的推斷(inference),且整體模型可以離線存儲(chǔ)至內(nèi)存中.因此,算法能夠在大規(guī)模分布式環(huán)境下進(jìn)行拓展.

Fig.12 Average query time for a single trajectory on different batch size圖12 不同批次下單條軌跡的平均查詢時(shí)間

5 結(jié)束語

針對(duì)傳統(tǒng)的旅行時(shí)間預(yù)測模型難以引入多源特征的問題,本文提出了一種兩階段的旅行時(shí)間預(yù)測框架REDTTE.框架的第1階段通過引入Skip-Gram模型將路段映射到向量空間,可以有效地捕捉路段之間的依賴關(guān)系;第 2階段針對(duì)路段向量序列的特性,整合天氣日期(工作日/節(jié)假日)等外部特征,設(shè)計(jì)了深度模型用于預(yù)測旅行時(shí)間.基于海量軌跡數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明,REDTTE框架因能較好提取路段間上下游依賴關(guān)系而具有較高的旅行時(shí)間預(yù)測精度.考慮到在節(jié)假日與工作日的早晚高峰時(shí)期模型的預(yù)測誤差較高,未來擬通過對(duì)路況建模,預(yù)測未來路段序列中每個(gè)路段的速度信息,將其與路段向量共同輸入以提高模型的預(yù)測精度.