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

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

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

1 引言

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

交通路網(wǎng)中的位置點構(gòu)成了復雜的網(wǎng)絡結(jié)構(gòu)，考慮到道路網(wǎng)絡空間中移動物體的屬性，文獻[2]定義了基于時間相似性和空間相似性的軌跡表示方式。文獻[3]基于上述表示方法提出了一種基于軌跡數(shù)據(jù)挖掘方法來預測移動物體位置的模型，具有很好的預測效果。文獻[4]提出了通過隱馬爾可夫模型(Hidden Markov Model,HMM)參數(shù)空間對單個車輛的軌跡模式進行建模的方法。但由于交通路網(wǎng)中網(wǎng)絡復雜的結(jié)構(gòu)造成的用戶軌跡模式復雜多樣，對大量用戶軌跡行為進行建?；蛘咴朴嬎惴治鲂枰浅６嗟馁Y源[5]，通過軌跡模式挖掘用戶未來軌跡的方法需要改進。

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

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

2 模型

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

2.1 卡口上下文分析

圖1 系統(tǒng)框圖

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

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

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

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

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

其中，Context(c) 表示軌跡集T中，與卡口c出現(xiàn)在同一條軌跡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。

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

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

2.1.2卡口上下文分析模型

模型使用基于Negative Sampling的Skip-gram策略[14]對上述網(wǎng)絡進行計算，已知卡口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所示，該網(wǎng)絡的輸入為所要求的嵌入化向量，對于訓練樣本(Context(c0),c i),i=0,1,2,···,neg，定義xc0為嵌入化向量作為網(wǎng)絡的輸入，y0作為網(wǎng)絡的輸出，y0=1表示正例，y0=0表示負例。于是，可將前文所提到的卡口上下文統(tǒng)計概率值的計算定義為關于Context(c0)和c0的函數(shù)，即

2.2 預測模型

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

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

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

2.3 學習算法

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

表1 DBN-SoftMax算法

3 實驗結(jié)果及分析

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

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

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

3.2 算法預測性能

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

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

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

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

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

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

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

3.2.2不同預測策略下的性能表現(xiàn)對比

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

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

3.2.3不同算法的評估對比

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

表3 實驗結(jié)果指標對比

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

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

4 結(jié)束語

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