基于卡口上下文和深度置信網(wǎng)絡(luò)的車(chē)輛軌跡預(yù)測(cè)模型研究

李 暾 朱耀堃 吳欣虹 肖云鵬 吳海峰

①(重慶郵電大學(xué)軟件工程學(xué)院 重慶 400065)

②(?？谑袣庀缶?海口571199)

1 引言

隨著城市的迅速發(fā)展，交通擁堵逐漸成為人們出行面臨的重要問(wèn)題。如何通過(guò)應(yīng)用技術(shù)手段解決這個(gè)問(wèn)題已成為研究熱點(diǎn)。車(chē)輛軌跡預(yù)測(cè)不僅可從道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行分析，還可從車(chē)輛軌跡數(shù)據(jù)中挖掘重要節(jié)點(diǎn)[1]。軌跡預(yù)測(cè)可以被理解為基于可觀察的用戶(hù)數(shù)據(jù)和交通網(wǎng)絡(luò)拓?fù)鋪?lái)推斷可能的缺失軌跡節(jié)點(diǎn)與未來(lái)軌跡節(jié)點(diǎn)。缺失的軌跡節(jié)點(diǎn)包含重要的路徑信息，因此推斷出缺失的軌跡節(jié)點(diǎn)具有重要的研究?jī)r(jià)值。

交通路網(wǎng)中的位置點(diǎn)構(gòu)成了復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，考慮到道路網(wǎng)絡(luò)空間中移動(dòng)物體的屬性，文獻(xiàn)[2]定義了基于時(shí)間相似性和空間相似性的軌跡表示方式。文獻(xiàn)[3]基于上述表示方法提出了一種基于軌跡數(shù)據(jù)挖掘方法來(lái)預(yù)測(cè)移動(dòng)物體位置的模型，具有很好的預(yù)測(cè)效果。文獻(xiàn)[4]提出了通過(guò)隱馬爾可夫模型(Hidden Markov Model,HMM)參數(shù)空間對(duì)單個(gè)車(chē)輛的軌跡模式進(jìn)行建模的方法。但由于交通路網(wǎng)中網(wǎng)絡(luò)復(fù)雜的結(jié)構(gòu)造成的用戶(hù)軌跡模式復(fù)雜多樣，對(duì)大量用戶(hù)軌跡行為進(jìn)行建?；蛘咴朴?jì)算分析需要非常多的資源[5]，通過(guò)軌跡模式挖掘用戶(hù)未來(lái)軌跡的方法需要改進(jìn)。

基于軌跡節(jié)點(diǎn)相關(guān)性分析的預(yù)測(cè)是通過(guò)分析用戶(hù)軌跡節(jié)點(diǎn)序列之間的相關(guān)性來(lái)實(shí)現(xiàn)的。文獻(xiàn)[6]將用戶(hù)軌跡與網(wǎng)絡(luò)軌跡節(jié)點(diǎn)時(shí)間相似度指標(biāo)相結(jié)合以提高軌跡預(yù)測(cè)的有效性，盡管該方法很好地利用了軌跡節(jié)點(diǎn)的相關(guān)性，但是其并沒(méi)有將時(shí)間相關(guān)性和空間相關(guān)性結(jié)合起來(lái)，進(jìn)而忽略了時(shí)空特性對(duì)用戶(hù)在選擇道路時(shí)產(chǎn)生的影響。文獻(xiàn)[7]基于用戶(hù)群體軌跡在時(shí)間和空間上的相似性，以預(yù)測(cè)節(jié)點(diǎn)未來(lái)的位置。文獻(xiàn)[8]提出了一種基于特征提取和噪聲消除的交通模式預(yù)測(cè)框架，通過(guò)結(jié)合特征提取和噪聲消除來(lái)提高預(yù)測(cè)算法的性能。盡管這些方法能夠提高數(shù)據(jù)對(duì)軌跡信息的表達(dá)能力，但是在預(yù)測(cè)用戶(hù)軌跡和分析用戶(hù)行為模式方面非常耗時(shí)。軌跡模式分析中采用聚類(lèi)的分析思路是當(dāng)前的一大研究熱點(diǎn)[9,10]，文獻(xiàn)[11]提出了一種基于決策圖和數(shù)據(jù)場(chǎng)的軌跡聚類(lèi)方法，通過(guò)自動(dòng)確定聚類(lèi)參數(shù)并有效地執(zhí)行軌跡聚類(lèi)來(lái)發(fā)現(xiàn)軌跡數(shù)據(jù)中的熱點(diǎn)。文獻(xiàn)[12]提出了一種挖掘雙向道路網(wǎng)中密集交通流模式的新技術(shù)，通過(guò)基于軌跡點(diǎn)密度的聚類(lèi)發(fā)現(xiàn)高密度流量區(qū)。

針對(duì)上述問(wèn)題，本文提出了一種基于軌跡特征分析的軌跡預(yù)測(cè)方法。首先，引入自然語(yǔ)言處理領(lǐng)域中詞嵌入的思想提取交通路網(wǎng)中卡口之間的關(guān)聯(lián)性；其次，采用深度置信網(wǎng)絡(luò)(Deep Belief Network,DBN)學(xué)習(xí)軌跡矩陣的隱藏特征，使用線(xiàn)性回歸網(wǎng)絡(luò)學(xué)習(xí)當(dāng)前已有卡口向量特征與未來(lái)卡口向量特征之間的關(guān)聯(lián)關(guān)系；最后，在回歸預(yù)測(cè)部分采用了一種權(quán)值聚類(lèi)的方法，使得模型預(yù)測(cè)的泛化能力有顯著提升。

2 模型

本文針對(duì)車(chē)輛軌跡數(shù)據(jù)中節(jié)點(diǎn)序列的時(shí)序特性和交通路網(wǎng)數(shù)據(jù)中車(chē)輛的空間關(guān)聯(lián)性，提出的系統(tǒng)框圖如圖1所示。首先，根據(jù)車(chē)輛軌跡數(shù)據(jù)和交通路網(wǎng)數(shù)據(jù)進(jìn)行卡口向量化表示，得到能夠表征時(shí)空關(guān)聯(lián)性的卡口向量集和用戶(hù)軌跡向量集；然后，通過(guò)軌跡上下文分析將用戶(hù)軌跡向量集映射到上下文空間，得到影響其未來(lái)軌跡選擇的影響因子；最后將回歸預(yù)測(cè)與權(quán)重聚類(lèi)相結(jié)合，對(duì)軌跡進(jìn)行預(yù)測(cè)，輸出車(chē)輛未來(lái)位置。

2.1 卡口上下文分析

圖1 系統(tǒng)框圖

軌跡數(shù)據(jù)中最主要的屬性就是卡口之間的時(shí)空關(guān)聯(lián)性，考慮到車(chē)輛軌跡中交通卡口之間存在的卡口上下文關(guān)系，將用戶(hù)軌跡作為輸入，通過(guò)滑動(dòng)窗口提取卡口的軌跡上下文，再使用One-hot對(duì)每一個(gè)卡口進(jìn)行編碼，最后使用上下文分析模型得到卡口的上下文語(yǔ)義向量。

2.1.1統(tǒng)計(jì)概率模型

交通卡口與軌跡之間的關(guān)系也與自然語(yǔ)言中單詞和句子的關(guān)系類(lèi)似，通過(guò)統(tǒng)計(jì)學(xué)概率模型來(lái)度量軌跡中卡口之間的關(guān)聯(lián)性，實(shí)現(xiàn)使用嵌入化向量表征交通路網(wǎng)中卡口間復(fù)雜的時(shí)空關(guān)聯(lián)性，定義嵌入化向量的長(zhǎng)度為 embedSize。使用統(tǒng)計(jì)概率模型來(lái)計(jì)算句子中某一個(gè)詞語(yǔ)與其他詞語(yǔ)的關(guān)聯(lián)性，將其定義為

其中，C ontext(w)表 示詞w的上下文，即w的周邊的詞集合，此時(shí)，p(Context(w)|w)值的大小就能表征詞w與C ontext(w)之間關(guān)聯(lián)性的強(qiáng)弱，其表征的是上下文Context(w)出現(xiàn)后，詞w出現(xiàn)的概率值。與此同時(shí)，為了減少計(jì)算量，根據(jù)n-gram model[13]中n–1階的Markov假設(shè)，認(rèn)為一個(gè)詞出現(xiàn)的概率就只與它前面n個(gè)詞相關(guān)，即：Context(w i)={w i?n,w i?n+1,···,w i?1}。

引入上述模型，交通卡口與其軌跡中其他卡口的關(guān)聯(lián)性可以定義為

其中，Context(c) 表示軌跡集T中，與卡口c出現(xiàn)在同一條軌跡t j的前后共 2n個(gè)卡口，即 Context(c i)={c i?n,c i?n+1,···,c i?1,c i+1,···,c i+n?1,c i+n},c j,c∈t j。

接著，利用最大對(duì)數(shù)似然對(duì)軌跡集建模，設(shè)計(jì)了一個(gè)目標(biāo)函數(shù)

在此模型中，對(duì)于每一條軌跡里面的所有卡口c，均都希望p(Context(c)|c)達(dá)到最大，進(jìn)而對(duì)于整個(gè)數(shù)據(jù)集來(lái)說(shuō)，最大化目標(biāo)函數(shù)L便成了統(tǒng)計(jì)概率模型對(duì)軌跡數(shù)據(jù)集進(jìn)行建模的首要目標(biāo)。

2.1.2卡口上下文分析模型

模型使用基于Negative Sampling的Skip-gram策略[14]對(duì)上述網(wǎng)絡(luò)進(jìn)行計(jì)算，已知卡口c0，需要預(yù)測(cè)Context(c0)， 因此對(duì)于給定的卡口上下文C ontext(c0)，卡口c0就 是一個(gè)正樣本，其他不在C ontext(c0)中的卡口就是負(fù)樣本，通過(guò)采樣的方法可采樣出 neg個(gè)負(fù)樣本，得到一個(gè)訓(xùn)練樣本(Context(c0),c i),i=0,1,2,···,neg；其中，i=0設(shè) 為正例，i=1,2,···,neg設(shè)為負(fù)例。如圖1所示，該網(wǎng)絡(luò)的輸入為所要求的嵌入化向量，對(duì)于訓(xùn)練樣本(Context(c0),c i),i=0,1,2,···,neg，定義xc0為嵌入化向量作為網(wǎng)絡(luò)的輸入，y0作為網(wǎng)絡(luò)的輸出，y0=1表示正例，y0=0表示負(fù)例。于是，可將前文所提到的卡口上下文統(tǒng)計(jì)概率值的計(jì)算定義為關(guān)于Context(c0)和c0的函數(shù)，即

2.2 預(yù)測(cè)模型

近年來(lái)，許多深度學(xué)習(xí)的研究表明，在對(duì)圖像和音頻的分類(lèi)、識(shí)別等任務(wù)中，可通過(guò)分層訓(xùn)練神經(jīng)網(wǎng)絡(luò)來(lái)獲得更好的效果[15–17]。DBN是深度學(xué)習(xí)模型中常用和有效的方法之一，它是一堆受限玻爾茲曼機(jī)(Restricted Boltzmann Machine,RBM)，每個(gè)RBM只有一個(gè)隱藏層，學(xué)習(xí)單元對(duì)一個(gè)RBM的激活被用作堆棧中下一個(gè)RBM的輸入數(shù)據(jù)。Hinton等人[15]提出了一種快速貪婪學(xué)習(xí)DBN的方法，該方法1次學(xué)習(xí)1層。

RBM是一種特殊類(lèi)型的馬爾科夫隨機(jī)場(chǎng)，它是一個(gè)無(wú)向圖模型，其中可見(jiàn)變量v通過(guò)無(wú)向加權(quán)與隨機(jī)隱藏單元h連接。由于隱藏變量或可見(jiàn)變量之間沒(méi)有連接，所以它們是受限的。該模型通過(guò)一個(gè)能量函數(shù)E=(v,h;θ)定 義了v,h上的概率分布。假設(shè)它是一個(gè)2元RBM，它可以寫(xiě)成

圖2 DBN-SoftMax網(wǎng)絡(luò)結(jié)構(gòu)示意圖

2.3 學(xué)習(xí)算法

本算法中，在卡口嵌入化階段(intersections embedding)的時(shí)間復(fù)雜度為O(N)；在路網(wǎng)特征提取階段(DBN-Soft Max model)的時(shí)間復(fù)雜度為O(Nlg(N))；在權(quán)重聚類(lèi)階段(weight clustering),K-means的時(shí)間復(fù)雜度為O((k×d×i)N)， 其中，k為聚類(lèi)中心數(shù)量，d為權(quán)重wi的維度，i為迭代次數(shù)。因此，通過(guò)以上分析，整個(gè)算法的時(shí)間復(fù)雜度為O(N)+O(Nlg(N))+O((k×d×i)N)～O(Nlg(N))。

表1 DBN-SoftMax算法

3 實(shí)驗(yàn)結(jié)果及分析

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

本文實(shí)驗(yàn)所使用的數(shù)據(jù)為中國(guó)某省會(huì)城市監(jiān)測(cè)設(shè)備采集的真實(shí)數(shù)據(jù)，包括從2017年9月—2017年11月該城市路網(wǎng)交通卡口所監(jiān)控的真實(shí)過(guò)車(chē)記錄。在數(shù)據(jù)量方面，該城市每天產(chǎn)生的過(guò)車(chē)數(shù)據(jù)基本在106級(jí)別，經(jīng)過(guò)初級(jí)的處理之后得到結(jié)構(gòu)化的數(shù)據(jù)，包括車(chē)牌號(hào)、過(guò)車(chē)時(shí)間、交通卡口編號(hào)、交通卡口的經(jīng)度和緯度等信息。與傳統(tǒng)的GPS車(chē)輛位置數(shù)據(jù)不同，此數(shù)據(jù)集為定點(diǎn)拍攝，車(chē)輛在固定位置被記錄，不用再進(jìn)行熱點(diǎn)位置聚類(lèi)。數(shù)據(jù)樣例如表2表示，由于數(shù)據(jù)敏感性，經(jīng)緯度數(shù)據(jù)不做展示。

為了使軌跡數(shù)據(jù)能夠真實(shí)反映交通路網(wǎng)的時(shí)空關(guān)系以及車(chē)輛用戶(hù)行車(chē)習(xí)慣，本實(shí)驗(yàn)針對(duì)數(shù)據(jù)特性做了預(yù)處理。首先，由于拍攝數(shù)據(jù)存在一些重復(fù)、冗余的軌跡數(shù)據(jù)，對(duì)這部分?jǐn)?shù)據(jù)進(jìn)行了去重處理；其次，針對(duì)少數(shù)不良行車(chē)行為，如套牌車(chē)現(xiàn)象，對(duì)每條軌跡內(nèi)的卡口位置進(jìn)行速度篩選。通過(guò)將不良行車(chē)數(shù)據(jù)進(jìn)行過(guò)濾，獲得數(shù)據(jù)集包括176000條軌跡，軌跡包含6到10個(gè)交通卡口不等，總共965個(gè)交通卡口，采用留出法將數(shù)據(jù)集劃分互不相交的訓(xùn)練集和測(cè)試集，訓(xùn)練集為140800條軌跡，測(cè)試集為剩下的35200條軌跡。

3.2 算法預(yù)測(cè)性能

3.2.1不同嵌入化維度下的性能對(duì)比

為了比較不同的交通卡口嵌入化維度在預(yù)測(cè)模型(DBN-SoftMax)中的表現(xiàn)，分別對(duì)比了不同的上下文長(zhǎng)度下不同的嵌入化維度的性能，以選取最佳的嵌入化維度和上下文長(zhǎng)度，并從側(cè)面驗(yàn)證了本文提出的交通卡口表示方法對(duì)軌跡預(yù)測(cè)的有效性，結(jié)果如圖3所示。

圖3展示了嵌入化維度和上下文長(zhǎng)度兩個(gè)參數(shù)的選取對(duì)模型最后準(zhǔn)確率的影響，由圖3中可以看出，在對(duì)路網(wǎng)卡口進(jìn)行建模時(shí)，選取不同的嵌入化維度對(duì)模型訓(xùn)練的收斂速度有很大的影響，同時(shí)，也對(duì)最后的準(zhǔn)確率有一定的影響。嵌入化維度越大，準(zhǔn)確率越高，使用卡口上下文向量來(lái)提取軌跡中節(jié)點(diǎn)之間的語(yǔ)義關(guān)系具有一定的作用，且語(yǔ)義向量的長(zhǎng)度能夠體現(xiàn)語(yǔ)義特征的容量，預(yù)測(cè)性能較好。

從圖4可知，當(dāng)嵌入化維度取值為128維時(shí)，不同的上下文長(zhǎng)度的準(zhǔn)確率(accuracy)和訓(xùn)練時(shí)間(training time)，隨著上下文長(zhǎng)度的增加都在增加，但是隨著上下文長(zhǎng)度的增加，模型訓(xùn)練時(shí)間增幅比較大，所以選擇上下文長(zhǎng)度為4可以得到較好的實(shí)驗(yàn)表現(xiàn)。

表2 數(shù)據(jù)樣例

圖3 對(duì)比不同上下文長(zhǎng)度下、不同嵌入化維度下的模型準(zhǔn)確率

圖4 不同上下文長(zhǎng)度下模型的F1值和訓(xùn)練時(shí)間

3.2.2不同預(yù)測(cè)策略下的性能表現(xiàn)對(duì)比

對(duì)上一節(jié)中軌跡節(jié)點(diǎn)嵌入化維度數(shù)據(jù)，分別使用DBN-SoftMax,NN-SoftMax和RBF SVM模型進(jìn)行性能分析對(duì)比。并對(duì)比了不同的DBN層數(shù)在軌跡預(yù)測(cè)任務(wù)中的表現(xiàn)，以選取最佳的DBN深度(depth)參數(shù)。選取嵌入化維度為128，訓(xùn)練集的軌跡長(zhǎng)度為6的軌跡數(shù)據(jù)進(jìn)行對(duì)比試驗(yàn)，結(jié)果如表3所示。

表3展示了模型預(yù)測(cè)結(jié)果的準(zhǔn)確率(precision)、召回率(recall)、F1值、訓(xùn)練時(shí)間和測(cè)試時(shí)間，其中表現(xiàn)性能最好的模型已通過(guò)加黑體標(biāo)識(shí)，即DBNSoft Max層數(shù)為4層時(shí)。上述實(shí)驗(yàn)表明，DBN網(wǎng)絡(luò)層數(shù)的加深能夠?qū)壽E預(yù)測(cè)任務(wù)的性能有顯著的提升；并且，使用1層的DBN作為特征提取網(wǎng)絡(luò)，能夠顯著超過(guò)4層前饋神經(jīng)網(wǎng)絡(luò)所達(dá)到的預(yù)測(cè)效果。另外，從表3中可以看出，DBN-Soft Max和NNSoft Max相對(duì)于RBF SVM在模型的訓(xùn)練上耗費(fèi)了太多時(shí)間，但是，其在對(duì)新數(shù)據(jù)進(jìn)行預(yù)測(cè)分析時(shí)的速度非?？?，這點(diǎn)在模型應(yīng)用方面有巨大優(yōu)勢(shì)。

3.2.3不同算法的評(píng)估對(duì)比

基于以上的參數(shù)選取以及實(shí)驗(yàn)數(shù)據(jù)集，使用Markov[18],LSTM[19]和MMM[20]基線(xiàn)算法與本文所提算法進(jìn)行對(duì)比，利用評(píng)價(jià)指標(biāo)對(duì)上述4個(gè)算法進(jìn)行了評(píng)估，選取近176000條長(zhǎng)度為4的交通車(chē)輛真實(shí)軌跡進(jìn)行下一個(gè)位置點(diǎn)的軌跡預(yù)測(cè)，各算法實(shí)驗(yàn)效果如圖5所示。

表3 實(shí)驗(yàn)結(jié)果指標(biāo)對(duì)比

圖5 對(duì)比不同上下文長(zhǎng)度下不同算法的ROC曲線(xiàn)

從圖5可知，在不同的上下文條件下，本文提出的DBN-Soft Max算法的ROC曲線(xiàn)更靠近左上，這意味著本文所提算法對(duì)車(chē)輛軌跡預(yù)測(cè)獲得了更好的結(jié)果。DBN-Soft Max算法因其在軌跡特征方面的優(yōu)秀性能而具有較高的預(yù)測(cè)準(zhǔn)確率，并且在不同的歷史軌跡下均具有良好表現(xiàn)，而其他基線(xiàn)算法在較少的歷史軌跡作為數(shù)據(jù)時(shí)表現(xiàn)欠佳?；诳谏舷挛姆治龅能?chē)輛軌跡預(yù)測(cè)模型相比其他算法具有更好的預(yù)測(cè)效果，并且在歷史信息較少的前提下，算法仍能具有較好的表現(xiàn)。

4 結(jié)束語(yǔ)

本文利用交通軌跡數(shù)據(jù)中軌跡節(jié)點(diǎn)存在的上下文關(guān)系特性，提出一種基于對(duì)卡口上下文進(jìn)行特征提取的交通車(chē)輛軌跡預(yù)測(cè)的方法。首先，利用實(shí)際軌跡中節(jié)點(diǎn)存在的上下文關(guān)系，構(gòu)建軌跡節(jié)點(diǎn)的向量空間，運(yùn)用節(jié)點(diǎn)的向量集表征節(jié)點(diǎn)間的交通時(shí)空關(guān)系；其次，該模型利用DBN提取軌跡局部空間特性；最后，該模型使用權(quán)重聚類(lèi)，對(duì)結(jié)果進(jìn)行了優(yōu)化。實(shí)驗(yàn)結(jié)果表明該模型不僅能夠有效地提取軌跡特征，并且在拓?fù)浣Y(jié)構(gòu)復(fù)雜的路網(wǎng)中也能得到較好的預(yù)測(cè)結(jié)果。在未來(lái)的工作中，將考慮更多、更復(fù)雜的數(shù)據(jù)對(duì)軌跡預(yù)測(cè)效果的影響，如果能夠同時(shí)采集到車(chē)輛用戶(hù)數(shù)據(jù)，將結(jié)合用戶(hù)個(gè)人信息與交通路網(wǎng)數(shù)據(jù)進(jìn)行分析建模，從而更加準(zhǔn)確地預(yù)測(cè)車(chē)輛軌跡。