基于卡口上下文和深度置信網絡的車輛軌跡預測模型研究

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

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

②(海口市氣象局 海口571199)

1 引言

隨著城市的迅速發展，交通擁堵逐漸成為人們出行面臨的重要問題。如何通過應用技術手段解決這個問題已成為研究熱點。車輛軌跡預測不僅可從道路網絡的拓撲結構進行分析，還可從車輛軌跡數據中挖掘重要節點[1]。軌跡預測可以被理解為基于可觀察的用戶數據和交通網絡拓撲來推斷可能的缺失軌跡節點與未來軌跡節點。缺失的軌跡節點包含重要的路徑信息，因此推斷出缺失的軌跡節點具有重要的研究價值。

交通路網中的位置點構成了復雜的網絡結構，考慮到道路網絡空間中移動物體的屬性，文獻[2]定義了基于時間相似性和空間相似性的軌跡表示方式。文獻[3]基于上述表示方法提出了一種基于軌跡數據挖掘方法來預測移動物體位置的模型，具有很好的預測效果。文獻[4]提出了通過隱馬爾可夫模型(Hidden Markov Model,HMM)參數空間對單個車輛的軌跡模式進行建模的方法。但由于交通路網中網絡復雜的結構造成的用戶軌跡模式復雜多樣，對大量用戶軌跡行為進行建模或者云計算分析需要非常多的資源[5]，通過軌跡模式挖掘用戶未來軌跡的方法需要改進。

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

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

2 模型

本文針對車輛軌跡數據中節點序列的時序特性和交通路網數據中車輛的空間關聯性，提出的系統框圖如圖1所示。首先，根據車輛軌跡數據和交通路網數據進行卡口向量化表示，得到能夠表征時空關聯性的卡口向量集和用戶軌跡向量集；然后，通過軌跡上下文分析將用戶軌跡向量集映射到上下文空間，得到影響其未來軌跡選擇的影響因子；最后將回歸預測與權重聚類相結合，對軌跡進行預測，輸出車輛未來位置。

2.1 卡口上下文分析

圖1 系統框圖

軌跡數據中最主要的屬性就是卡口之間的時空關聯性，考慮到車輛軌跡中交通卡口之間存在的卡口上下文關系，將用戶軌跡作為輸入，通過滑動窗口提取卡口的軌跡上下文，再使用One-hot對每一個卡口進行編碼，最后使用上下文分析模型得到卡口的上下文語義向量。

2.1.1統計概率模型

交通卡口與軌跡之間的關系也與自然語言中單詞和句子的關系類似，通過統計學概率模型來度量軌跡中卡口之間的關聯性，實現使用嵌入化向量表征交通路網中卡口間復雜的時空關聯性，定義嵌入化向量的長度為 embedSize。使用統計概率模型來計算句子中某一個詞語與其他詞語的關聯性，將其定義為

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

引入上述模型，交通卡口與其軌跡中其他卡口的關聯性可以定義為

其中，Context(c) 表示軌跡集T中，與卡口c出現在同一條軌跡t j的前后共 2n個卡口，即 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。

接著，利用最大對數似然對軌跡集建模，設計了一個目標函數

在此模型中，對于每一條軌跡里面的所有卡口c，均都希望p(Context(c)|c)達到最大，進而對于整個數據集來說，最大化目標函數L便成了統計概率模型對軌跡數據集進行建模的首要目標。

2.1.2卡口上下文分析模型

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

2.2 預測模型

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

RBM是一種特殊類型的馬爾科夫隨機場，它是一個無向圖模型，其中可見變量v通過無向加權與隨機隱藏單元h連接。由于隱藏變量或可見變量之間沒有連接，所以它們是受限的。該模型通過一個能量函數E=(v,h;θ)定 義了v,h上的概率分布。假設它是一個2元RBM，它可以寫成

圖2 DBN-SoftMax網絡結構示意圖

2.3 學習算法

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

表1 DBN-SoftMax算法

3 實驗結果及分析

3.1 數據集

本文實驗所使用的數據為中國某省會城市監測設備采集的真實數據，包括從2017年9月—2017年11月該城市路網交通卡口所監控的真實過車記錄。在數據量方面，該城市每天產生的過車數據基本在106級別，經過初級的處理之后得到結構化的數據，包括車牌號、過車時間、交通卡口編號、交通卡口的經度和緯度等信息。與傳統的GPS車輛位置數據不同，此數據集為定點拍攝，車輛在固定位置被記錄，不用再進行熱點位置聚類。數據樣例如表2表示，由于數據敏感性，經緯度數據不做展示。

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

3.2 算法預測性能

3.2.1不同嵌入化維度下的性能對比

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

圖3展示了嵌入化維度和上下文長度兩個參數的選取對模型最后準確率的影響，由圖3中可以看出，在對路網卡口進行建模時，選取不同的嵌入化維度對模型訓練的收斂速度有很大的影響，同時，也對最后的準確率有一定的影響。嵌入化維度越大，準確率越高，使用卡口上下文向量來提取軌跡中節點之間的語義關系具有一定的作用，且語義向量的長度能夠體現語義特征的容量，預測性能較好。

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

表2 數據樣例

圖3 對比不同上下文長度下、不同嵌入化維度下的模型準確率

圖4 不同上下文長度下模型的F1值和訓練時間

3.2.2不同預測策略下的性能表現對比

對上一節中軌跡節點嵌入化維度數據，分別使用DBN-SoftMax,NN-SoftMax和RBF SVM模型進行性能分析對比。并對比了不同的DBN層數在軌跡預測任務中的表現，以選取最佳的DBN深度(depth)參數。選取嵌入化維度為128，訓練集的軌跡長度為6的軌跡數據進行對比試驗，結果如表3所示。

表3展示了模型預測結果的準確率(precision)、召回率(recall)、F1值、訓練時間和測試時間，其中表現性能最好的模型已通過加黑體標識，即DBNSoft Max層數為4層時。上述實驗表明，DBN網絡層數的加深能夠對軌跡預測任務的性能有顯著的提升；并且，使用1層的DBN作為特征提取網絡，能夠顯著超過4層前饋神經網絡所達到的預測效果。另外，從表3中可以看出，DBN-Soft Max和NNSoft Max相對于RBF SVM在模型的訓練上耗費了太多時間，但是，其在對新數據進行預測分析時的速度非常快，這點在模型應用方面有巨大優勢。

3.2.3不同算法的評估對比

基于以上的參數選取以及實驗數據集，使用Markov[18],LSTM[19]和MMM[20]基線算法與本文所提算法進行對比，利用評價指標對上述4個算法進行了評估，選取近176000條長度為4的交通車輛真實軌跡進行下一個位置點的軌跡預測，各算法實驗效果如圖5所示。

表3 實驗結果指標對比

圖5 對比不同上下文長度下不同算法的ROC曲線

從圖5可知，在不同的上下文條件下，本文提出的DBN-Soft Max算法的ROC曲線更靠近左上，這意味著本文所提算法對車輛軌跡預測獲得了更好的結果。DBN-Soft Max算法因其在軌跡特征方面的優秀性能而具有較高的預測準確率，并且在不同的歷史軌跡下均具有良好表現，而其他基線算法在較少的歷史軌跡作為數據時表現欠佳。基于卡口上下文分析的車輛軌跡預測模型相比其他算法具有更好的預測效果，并且在歷史信息較少的前提下，算法仍能具有較好的表現。

4 結束語

本文利用交通軌跡數據中軌跡節點存在的上下文關系特性，提出一種基于對卡口上下文進行特征提取的交通車輛軌跡預測的方法。首先，利用實際軌跡中節點存在的上下文關系，構建軌跡節點的向量空間，運用節點的向量集表征節點間的交通時空關系；其次，該模型利用DBN提取軌跡局部空間特性；最后，該模型使用權重聚類，對結果進行了優化。實驗結果表明該模型不僅能夠有效地提取軌跡特征，并且在拓撲結構復雜的路網中也能得到較好的預測結果。在未來的工作中，將考慮更多、更復雜的數據對軌跡預測效果的影響，如果能夠同時采集到車輛用戶數據，將結合用戶個人信息與交通路網數據進行分析建模，從而更加準確地預測車輛軌跡。