夏卓群 胡珍珍 羅君鵬 陳月月

1(綜合交通運輸大數(shù)據(jù)智能處理湖南省重點實驗室(長沙理工大學(xué)) 長沙 410114) 2(長沙理工大學(xué)計算機與通信工程學(xué)院 長沙 410114) 3(國防科學(xué)技術(shù)大學(xué)計算機學(xué)院 長沙 410114)

不確定環(huán)境下移動對象自適應(yīng)軌跡預(yù)測方法

夏卓群1,2,3胡珍珍1,2羅君鵬1,2陳月月3

1(綜合交通運輸大數(shù)據(jù)智能處理湖南省重點實驗室(長沙理工大學(xué)) 長沙 410114)2(長沙理工大學(xué)計算機與通信工程學(xué)院 長沙 410114)3(國防科學(xué)技術(shù)大學(xué)計算機學(xué)院 長沙 410114)

已有的軌跡預(yù)測方法難以對移動對象運動軌跡進行準(zhǔn)確地描述,尤其在復(fù)雜且不確定的車載自組織網(wǎng)絡(luò)(vehicular ad hoc network)(也稱車聯(lián)網(wǎng))環(huán)境中.為了解決這一問題，提出基于變分高斯混合模型(variational Gaussian mixture model, VGMM)的環(huán)境自適應(yīng)軌跡預(yù)測方法ESATP(environment self-adaptive prediction method based on VGMM).首先，在傳統(tǒng)高斯混合模型的基礎(chǔ)上使用變分貝葉斯推理近似方法處理混合高斯分布;其次設(shè)計變分貝葉斯期望最大化算法學(xué)習(xí)計算高斯混合模型參數(shù)，有效運用參數(shù)先驗信息得到更高精度預(yù)測模型；最后,針對輸入軌跡數(shù)據(jù)特征，使用參數(shù)自適應(yīng)選擇算法自動調(diào)節(jié)參數(shù)組合，靈活調(diào)整混合高斯分量的個數(shù)和軌跡段大小.實驗結(jié)果表明：所提方法在實驗中表現(xiàn)出較高的預(yù)測準(zhǔn)確性，可應(yīng)用于車輛移動定位產(chǎn)品中.

環(huán)境自適應(yīng)；變分高斯混合模型；參數(shù)自適應(yīng)選擇算法；軌跡預(yù)測

智慧城市建設(shè)的飛速發(fā)展極大地推動了車載自組織網(wǎng)絡(luò)(vehicular ad hoc network, VANET)(也稱車聯(lián)網(wǎng))及相關(guān)技術(shù)的廣泛應(yīng)用.車聯(lián)網(wǎng)是由車輛位置、速度和路線等信息構(gòu)成的巨大交互網(wǎng)絡(luò).車聯(lián)網(wǎng)的誕生及發(fā)展對于車輛主動安全、智能交通管理、城市生活服務(wù)、應(yīng)急救援等應(yīng)用具有極大的幫助，而這些應(yīng)用大都離不開對位置數(shù)據(jù)的分析與預(yù)測.實際交通環(huán)境的不確定性給獲取移動對象實時空間位置帶來了巨大的挑戰(zhàn)，如果運動環(huán)境突然惡化，通訊信號變得微弱，全球定位系統(tǒng)(global positioning system, GPS)的信號會出現(xiàn)短時中斷，致使GPS無法獲取實時位置信息.這將造成車輛軌跡數(shù)據(jù)丟失，影響數(shù)據(jù)在車聯(lián)網(wǎng)內(nèi)傳遞，信息不能在車輛間共享，最終導(dǎo)致嚴(yán)重的交通事故.在此背景下，本文主要解決的科學(xué)問題是：如何在車聯(lián)網(wǎng)動態(tài)環(huán)境中移動網(wǎng)絡(luò)節(jié)點(移動車輛)位置復(fù)雜多變、網(wǎng)絡(luò)拓?fù)漕l繁變化、交通信息的獲取難度增大的情況下，利用車輛歷史軌跡數(shù)據(jù)進行實時軌跡位置預(yù)測，為智能交通控制系統(tǒng)提供決策所需的基礎(chǔ)數(shù)據(jù).

1 相關(guān)工作

移動對象軌跡預(yù)測算法或模型在近幾十年來受到國內(nèi)外眾多專家、學(xué)者的關(guān)注和研究，取得了諸多成果，并被廣泛用于交通、軍事、醫(yī)療及日常生活服務(wù)等多個領(lǐng)域[1-5].如通過分析原始的GPS歷史位置數(shù)據(jù)、預(yù)測交通堵塞區(qū)域[1]；測量個體軌跡信息熵、預(yù)測人類動態(tài)行為[2].MyWay建立預(yù)測系統(tǒng)，分別使用單個用戶行為模型、集體用戶行為模型和結(jié)合個體與集體行為模型對移動用戶下一位置進行預(yù)測[3]，該方法的優(yōu)勢在于只需共享個體移動配置文件，簡潔地表示用戶動作，而不是利用原始軌跡數(shù)據(jù)揭示用戶詳細的運動.根據(jù)機會路徑和目的地原則研究不確定性目的地，提供理想的改道路徑到達主要目的地[4].當(dāng)前，移動對象不確定性軌跡預(yù)測方法主要分為基于模式預(yù)測方法、基于線性模型預(yù)測方法、基于非線性模型預(yù)測方法.基于模式的預(yù)測方法是通過頻繁模式挖掘找出軌跡典型模式，再根據(jù)軌跡模式進行預(yù)測[6-9].Deb等人[6]提出通過挖掘軌跡頻繁模式，找出與數(shù)據(jù)庫中已記錄的最頻繁路徑相匹配的運動模式，進而推斷最可能到達的下一個交叉口.該方法由于沒有考慮噪聲軌跡數(shù)據(jù)的影響，因此預(yù)測精度不高.常用的基于線性模型預(yù)測方法主要有基于貝葉斯模型預(yù)測方法[10-11]、基于Markov模型預(yù)測[12-14]或隱Markov模型預(yù)測方法[15-16]、基于多階Markov模型預(yù)測方法[17-18].Schreier等人[11]提出貝葉斯網(wǎng)絡(luò)中基于操作的長期軌跡預(yù)測和駕駛輔助系統(tǒng)危險程度評估方案，有效避免了車輛碰撞.非線性模型預(yù)測方法是指通過數(shù)學(xué)公式刻畫移動對象的運動軌跡，其中高斯模型[19-21]是常用的非線性預(yù)測模型.Heravi等人[20]結(jié)合線性回歸分析法和高斯過程回歸分析法對長期軌跡進行預(yù)測，經(jīng)證明該方法所提模型參數(shù)少且穩(wěn)定性強，但只適應(yīng)于小規(guī)模數(shù)據(jù)集.針對復(fù)雜運動模式，Wiest等人[21]提出結(jié)合貝葉斯網(wǎng)絡(luò)和高斯混合模型預(yù)測車輛將要行駛的路徑，該方法預(yù)測精度較高且時間開銷較低.在本文的后續(xù)工作中，借鑒其利用貝葉斯網(wǎng)絡(luò)處理混合高斯模型來優(yōu)化模型參數(shù)的方法，靈活調(diào)整混合高斯部件個數(shù).一些學(xué)者利用軌跡的社會關(guān)系[22]、軌跡時空信息[23-24]進行預(yù)測.上述方法大都只考慮歷史軌跡、運動速度、方向、時間、地理特征等因素對預(yù)測精度的影響，很少研究動態(tài)環(huán)境對預(yù)測結(jié)果的影響.本文針對現(xiàn)有預(yù)測方法在動態(tài)環(huán)境中移動對象軌跡預(yù)測精度不高、實時性差的問題提出一種動態(tài)環(huán)境下自適應(yīng)軌跡預(yù)測方法.本文所提方法通過向傳統(tǒng)高斯混合模型引入變分貝葉斯近似推理方法和自適應(yīng)參數(shù)選擇算法，自動調(diào)節(jié)高斯混合模型高斯成分個數(shù)組合以適應(yīng)當(dāng)前環(huán)境，提高預(yù)測模型對復(fù)雜環(huán)境的魯棒性，維持高精度且時間開銷小.

2 移動對象自適應(yīng)軌跡預(yù)測模型

動態(tài)環(huán)境下移動對象運動軌跡預(yù)測，主要包括4個步驟：1)原始位置數(shù)據(jù)獲取，通過車載移動終端收集車輛實時位置信息;2)歷史軌跡數(shù)據(jù)預(yù)處理，通過對歷史軌跡數(shù)據(jù)簡化、聚類和軌跡分段操作，去除噪聲軌跡和提取局部軌跡數(shù)據(jù)特征；3)軌跡數(shù)據(jù)建模，對時空軌跡數(shù)據(jù)進行降維操作、抽取運動模式，構(gòu)建高效預(yù)測模型；4)軌跡在線預(yù)測，依據(jù)軌跡特征關(guān)聯(lián)，分析移動對象運動趨勢并運用預(yù)測模型模擬運動軌跡.

2.1軌跡數(shù)據(jù)預(yù)處理

Fig. 1 Chart of trajectory segment algorithm based on density圖1 基于密度的軌跡分割算法流程圖

由于GPS等移動定位設(shè)備接收到的關(guān)于移動對象位置信息的原始數(shù)據(jù)含有大量噪聲、冗余數(shù)據(jù)，不能直接用來進行軌跡預(yù)測，因此在使用變分高斯混合模型(variational Gaussian mixture model, VGMM)對軌跡數(shù)據(jù)建模之前需要預(yù)先對位置數(shù)據(jù)進行預(yù)處理操作.首先利用K-Means聚類方法對軌跡數(shù)據(jù)進行初步聚類，將數(shù)據(jù)進行分區(qū).鑒于K-Means聚類方法對不規(guī)則形狀集的聚類效果差，對噪聲數(shù)據(jù)敏感，而基于密度的聚類方法對噪聲數(shù)據(jù)的處理比較好.因此本節(jié)接著利用基于密度的聚類方法對軌跡數(shù)據(jù)進一步聚類處理，去除原始軌跡數(shù)據(jù)中的噪聲數(shù)據(jù).基于密度的聚類方法輸入鄰域半徑(Eps)和領(lǐng)域最少數(shù)據(jù)個數(shù)(MinPts)，確定核心點，然后根據(jù)點到核心點的距離將數(shù)據(jù)分類為核心點、噪聲點和邊緣點，因此將噪聲點分離開.其次運用基于密度的軌跡分割算法[9]進一步處理軌跡數(shù)據(jù)，提取局部軌跡數(shù)據(jù)特征，提高算法運行的時間效率.本文所提聚類方法的具體實現(xiàn)過程請讀者參考文獻[25],基于密度的軌跡分割方法采用廣度優(yōu)先搜索策略實現(xiàn)，具體算法流程如圖1所示.

2.2基于VGMM預(yù)測模型訓(xùn)練

(1)

其中，Z表示隱變量，D為觀測數(shù)據(jù)的維度，(μk,Λk)分別為第k個高斯分量的均值矩陣和精度矩陣.

使用VGMM模型對軌跡數(shù)據(jù)建模其實質(zhì)就是要準(zhǔn)確估計模型的參數(shù)，非高斯噪聲模型參數(shù)估計常采用變分貝葉斯近似學(xué)習(xí)方法估計.變分貝葉斯是在傳統(tǒng)貝葉斯推斷與(examinationmaximum)期望最大化(EM)迭代估計算法的基礎(chǔ)上引入變分近似理論而提出的一種學(xué)習(xí)方法，也叫變分貝葉斯期望最大算法(variationBayesianexaminationmaximum,VBEM)，有效地融合了EM迭代算法收斂速度快、求解過程簡單和貝葉斯推斷理論利用已有的先驗信息等優(yōu)點，改善了傳統(tǒng)高斯混合模型采用EM迭代算法計算模型參數(shù)容易陷入局部最優(yōu)解的不足.假設(shè)觀測數(shù)據(jù)集X={x1,x2,…,xN}，N個數(shù)據(jù)是獨立同分布的，已知所有參數(shù)的先驗分布，隱變量和參數(shù)分別由Z={z1,z2,…,zN}和θ={θ1,θ2,…,θN}表示，變分推理對數(shù)邊緣似然函數(shù)可近似表示為[27]

lnp(X)=F(q(Z,θ))+
KL(q(Z,θ)‖p(Z,θ|X))，

(2)

其中：

KL(q(Z,θ)‖p(Z,θ|X))=

式(2)等號右邊第2項KL(q(Z,θ)‖p(Z,θ|X))≥0為q(Z,θ)與p(Z,θ|X)之間的KL散度.要想求得對數(shù)似然函數(shù)的最小值，需要首先計算KL散度的最小值，然而計算KL散度的最小值難度較大且繁瑣，因此，只能計算自由能量F(q(Z,θ))的最大值.

計算隱參數(shù)概率(expectationstep,E-step)

(3)

其中,E(zn k)=rn k.

利用E-step計算得到的隱參數(shù)概率來計算變分高斯混合參數(shù)聯(lián)合概率，迭代這2個步驟直到隱參數(shù)概率達到最大值，并將取得最大概率時的參數(shù)組合為最佳參數(shù)組合進行參數(shù)更新(maximizationstep,M-step)

m0,(β0Λk)-1)W(Λk|w0,v0))]，

(4)

其中，參數(shù)m0表示先驗均值,β0為協(xié)方差矩陣梯度系數(shù)，W0為先驗精度值，v0為威沙特分布自由度初始值.

參數(shù)更新：

通過變分貝葉斯近似推理方法處理高斯混合模型求得觀測數(shù)據(jù)集服從近似高斯混合分布：

(5)

其中，mk，ηk分別為第k個分量的均值、精度，其中ηk為

(6)

(7)

其中:

).

(8)

式(8)為軌跡變分高斯混合回歸模型，基本思想是：1)利用式(7)對軌跡數(shù)據(jù)利用概率密度函數(shù)建模，通過基于密度聚類和分割方法對訓(xùn)練軌跡數(shù)據(jù)進行分析與處理；2)利用變分貝葉斯近似推理迭代計算高斯混合模型參數(shù)，依據(jù)符合變分高斯混合分布數(shù)據(jù)的條件分布得到K個高斯分量的回歸函數(shù)；3)利用式(8)將回歸函數(shù)加權(quán)混合完成軌跡回歸預(yù)測.

3 基于VGMM的環(huán)境自適應(yīng)軌跡預(yù)測算法

3.1工作原理

本文提出的基于VGMM模型的環(huán)境自適應(yīng)軌跡預(yù)測算法以變分高斯混合模型為基礎(chǔ)，抽象出與VGMM模型相對應(yīng)的復(fù)雜軌跡模式，通過運用變分查詢算法解決GMM模型的權(quán)重、均值和精度這3個參數(shù)的估計問題完成軌跡預(yù)測.運用VGMM模型對復(fù)雜軌跡運動模式建模的過程中，首先需要對海量位置數(shù)據(jù)進行分段，將用于訓(xùn)練的軌跡劃分成不同的段，用{Si,i=1,2,…,N}表示.同時，采用網(wǎng)格序列表示軌跡化簡軌跡，用{Oi,i=1,2,…,K}表示.然后，模型訓(xùn)練學(xué)習(xí)，利用變分貝葉斯期望最大化法迭代計算模型參數(shù)得到近似后驗概率分布，設(shè)計歷史軌跡與未來軌跡的條件概率密度函數(shù).最后運用條件概率密度函數(shù)設(shè)計未來軌跡關(guān)于歷史軌跡的回歸預(yù)測函數(shù).軌跡預(yù)測階段，輸入測試軌跡數(shù)據(jù)集，利用模型訓(xùn)練過程中得到的回歸預(yù)測函數(shù)計算預(yù)測值.

3.2參數(shù)自適應(yīng)選擇

基于VGMM模型軌跡預(yù)測模型選擇，與軌跡所在區(qū)域大小密切相關(guān).軌跡預(yù)測模型的精度主要受VGMM模型參數(shù)λ={α,μ,η,v}、軌跡分段的大小segsize這2個因素的影響.在實際應(yīng)用中，由于運動環(huán)境的不確定性，導(dǎo)致移動對象運動狀態(tài)隨時發(fā)生改變，因此相鄰軌跡點的間隔大小不一致，這就導(dǎo)致了由輸入產(chǎn)生軌跡數(shù)據(jù)丟失的問題.為了解決這一問題，本文采用參數(shù)自適應(yīng)選擇算法使得軌跡完整.參數(shù)自適應(yīng)調(diào)整過程如下，圖2為參數(shù)自適應(yīng)選擇算法流程圖:

Fig. 2 Flow of parameters self-adaptive selection algorithm圖2 參數(shù)自適應(yīng)選擇算法流程圖

3.3基于VGMM環(huán)境自適應(yīng)軌跡預(yù)測

ESATP-VGMM包含2個階段：1)訓(xùn)練階段，將經(jīng)過參數(shù)自適應(yīng)選擇算法處理的移動對象歷史軌跡數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)集，發(fā)現(xiàn)軌跡典型運動模式，并以此建立基于變分高斯混合模型的高效預(yù)測模型；2)預(yù)測階段，運用訓(xùn)練階段得到的預(yù)測模型對移動對象未來小段時間內(nèi)運動軌跡進行預(yù)測.基于VGMM的環(huán)境自適應(yīng)軌跡預(yù)測算法偽代碼如算法1所示：

算法1. 基于VGMM的環(huán)境自適應(yīng)軌跡預(yù)測算法.

輸入：訓(xùn)練數(shù)據(jù)集 Ttrain=(X,Y)、測試數(shù)據(jù)集Ttest=(X*,Y*)、軌跡集T={T1,T2,…,Tn}；

輸出：軌跡預(yù)測平均誤差RMSE.

① C=?, F=?;

② 分離軌跡點和噪聲點，軌跡數(shù)據(jù)基于密度的聚類得到m個聚類簇并存放到集合C中,C=Tracluster(T);

③ 發(fā)現(xiàn)隱藏軌跡點和提取軌跡典型運動模式,基于密度的軌跡分割得到軌跡段集合F=Trasegment(C);

④ 參數(shù)自適應(yīng)選擇算法，調(diào)整軌跡段大小trasegsize,補充完整軌跡,得到完整軌跡集S=paraselect(F);

⑤ 將軌跡映射到網(wǎng)格中，轉(zhuǎn)換為軌跡鏈表示transform(S);

⑥ 采用K-Means聚類初始化VGMM模型參數(shù)VGMM_para=K-means(Ttrain);

⑦ 模型訓(xùn)練，使用VBEM算法迭代學(xué)習(xí)估計模型參數(shù)M_para=VBEM(Ttrain,VGMM_para);

⑧ 計算軌跡預(yù)測步數(shù)i=n-d；

⑨ 軌跡預(yù)測，Tpr表示預(yù)測軌跡點，Tre表示真實軌跡點

fori=1tol

Tpr=predict(M)；

e[i]=callRMSE(Tpr,Tre)；

endfor

由于本章對預(yù)測模型學(xué)習(xí)訓(xùn)練都是通過最優(yōu)化邊緣似然來獲取模型所需參數(shù)，而每次的梯度計算都要對協(xié)方差矩陣求逆，因此所提算法的時間復(fù)雜度在模型訓(xùn)練階段為O(n3L)，n為軌跡數(shù)量，L表示梯度計算的次數(shù)，軌跡預(yù)測階段的時間復(fù)雜度與預(yù)測軌跡數(shù)量n有關(guān)，時間復(fù)雜度取值范圍為[O(n2),O(nlogn)].

4 實驗與結(jié)果

本節(jié)將使用真實交通場景中車輛位置數(shù)據(jù)進行一系列的實驗，對所提方法的性能進行評估.

4.1數(shù)據(jù)集與實驗環(huán)境

本實驗數(shù)據(jù)采用微軟亞洲研究院Geolife項目[30]的數(shù)據(jù)集，包含23 667 828個軌跡點，總長度達1 292 951 km.每個軌跡點包含了移動對象的時空位置信息，本文將軌跡數(shù)據(jù)集分成2個子數(shù)據(jù)集，其中訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集的分配比例為9∶1.實驗使用MATLAB 2014a環(huán)境，數(shù)據(jù)庫為SQL Server 2008.實驗硬件平臺為：Intel?CoreTM2 Duo P8700 2.53 GHz CPU，2 GB內(nèi)存，操作系統(tǒng)為Windows 7.為了方便比較不同參數(shù)條件、不同算法的優(yōu)劣，性能評價指標(biāo)使用以下標(biāo)準(zhǔn)，該標(biāo)注廣泛應(yīng)用于多標(biāo)簽分類研究中[31].

(9)

2) 準(zhǔn)確率(accuracy).定義為真正的軌跡點在預(yù)測軌跡點集合中出現(xiàn)的頻次，如果預(yù)測軌跡點就是真實的軌跡點，則p(l)=1，否則p(l)=0.

).

(10)

3) 可信度(reliability).定義為所有的預(yù)測軌跡點中概率最大的點不是真實軌跡點出現(xiàn)的頻次，如果預(yù)測軌跡點是真實的軌跡點，則預(yù)測誤差e(l)=0，否則e(l)=1.

).

(11)

4) 平均精度(averageprecision).給定預(yù)測軌跡點，平均預(yù)測精度定義為

其中，p(i)=1表示預(yù)測點i是真實的軌跡點.

4.2VGMM模型性能評估

本節(jié)對預(yù)測模型VGMM模型的性能進行評估.在軌跡預(yù)測過程中，合適的選擇參數(shù)有助于靈活調(diào)節(jié)參數(shù)組合、優(yōu)化模型性能(比如高斯混合模型混合分量的個數(shù)K、軌跡分段大小segtrasize).本節(jié)主要研究這些參數(shù)是如何影響模型的性能.

首先，研究軌跡段大小β=30的情況下，混合分量個數(shù)K從5增加到20的變化對模型的影響.接下來的實驗主要測驗混合分量個數(shù)對預(yù)測誤差、準(zhǔn)確性、平均精度及可信度的影響.圖3所示，VGMM獲得最好性能，在相同觀測軌跡長度下，其預(yù)測平均誤差在K=15時獲得最小，而且隨著觀察軌跡長度的增加，預(yù)測模型預(yù)測誤差快速下降，高斯混合分量個數(shù)在K=15所在曲線表現(xiàn)出明顯的優(yōu)勢，最小可達到30 m以下.高斯混合元組個數(shù)K對平均精度的影響如圖4所示，相同觀測軌跡長度下預(yù)測模型獲得最大平均預(yù)測精度在K=15時.

Fig. 3 Prediction error under different observable length of input trajectories圖3 不同軌跡長度下混合分量對預(yù)測誤差的影響

Fig .4 Average precision under different observable length of input trajectories圖4 不同輸入歷史軌跡長度下平均精度比較

Fig. 5 Accuracy comparison of different observable length of input trajectories圖5 不同輸入歷史軌跡長度下準(zhǔn)確性比較

如圖5所示，在相同的觀察軌跡長度下，當(dāng)高斯混合元組個數(shù)K從5增加到15，預(yù)測準(zhǔn)確性明顯提高，但當(dāng)K進一步增加，預(yù)測精度開始下降，這表明高斯混合分量個數(shù)為15時，預(yù)測模型的精度最好.從圖6可以觀察到，預(yù)測模型的預(yù)測可信度在軌跡長度length=10時，預(yù)測可信度不高都為10%，隨著軌跡點數(shù)的增加預(yù)測可信度提高；同時在相同的軌跡長度的情況下，預(yù)測可信度隨混合分量的個數(shù)K從5到15逐漸提高，然而Kgt;15之后預(yù)測可信度保持基本不變，從圖6中可以看到K=15的曲線預(yù)測可信度最高，且最高接近80%.混合分量過少時，預(yù)測模型不能將所有的運動模型包括在內(nèi)，導(dǎo)致預(yù)測結(jié)果差，然而混合分量的個數(shù)也不宜過多，混合分量過多會導(dǎo)致模型建立時間增加，甚至可能引起高的時空訓(xùn)練代價.鑒于這些因素，在接下來的實驗中統(tǒng)一設(shè)置高斯混合元組個數(shù)K=15.

Fig. 6 Reliability comparison of different observable length of input trajectories圖6 不同輸入歷史軌跡長度下預(yù)測可信度比較

Fig. 7 Prediction error under different size of trajectory segment圖7 不同軌跡段大小下預(yù)測誤差比較

接下來考慮不同軌跡段大小β(K=15)的情況下進行軌跡預(yù)測，研究其是如何影響預(yù)測模型的性能.如圖7所示，預(yù)測誤差隨軌跡段大小β增大而下降，然而在β=30之后略有上升，這是因為軌跡段大小增大，軌跡段可能包含了不滿足軌跡段劃分條件的軌跡點，因此預(yù)測誤差增加.從圖8～10可以了解到，預(yù)測準(zhǔn)確性、預(yù)測可信度和平均精度隨著β的增加而提高，但是在軌跡段大小β=30之后開始下降,這表明軌跡段大小β應(yīng)該大到能夠放下足夠多的軌跡以至于包含足夠多的運動模式，然而β太大而不能發(fā)現(xiàn)隱藏的軌跡模式，導(dǎo)致預(yù)測精度不高.

Fig. 8 Accuracy with different size of trajectory segment圖8 不同軌跡段大小準(zhǔn)確性比較

Fig. 9 Reliability under different size of trajectory segment圖9 不同軌跡段大小預(yù)測可靠性比較

Fig.10 Average precision with different size of trajectory segment圖10 不同軌跡段大小平均精度比較

4.3與已有預(yù)測模型或方法的比較

Fig. 11 Effect of randomly changing environment to prediction error, prediction reliability, and accuracy圖11 環(huán)境變化對預(yù)測誤差、預(yù)測可信度和準(zhǔn)確性的影響

接下來比較本文所提預(yù)測算法(VGMM-ESATP)與基于高斯混合模型軌跡預(yù)測算法(Gaussian mixture model trajectory prediction, GMTP)[21]和基于Markov模型軌跡預(yù)測算法(Markov model trajectory predic-tion, MTP)[14].GMTP預(yù)測方法是一種利用高斯混合模型對軌跡數(shù)據(jù)建模，然后根據(jù)軌跡概率分布進行軌跡預(yù)測；MTP預(yù)測方法是借鑒Markov鏈無后效性的思想，計算移動對象狀態(tài)轉(zhuǎn)移概率，建立轉(zhuǎn)移概率矩陣，并根據(jù)當(dāng)前的轉(zhuǎn)移概率與已有的轉(zhuǎn)移概率矩陣對比進行軌跡預(yù)測.本文所提方法與GMTP預(yù)測算法的不同之處是本文使用VBEM算法進行模型參數(shù)估計和參數(shù)自適應(yīng)選擇算法靈活調(diào)整參數(shù)組合，該方法能夠彌補GMTP方法參數(shù)估計出現(xiàn)過擬合或者局部最優(yōu)的不足，而且還能改善GMTP方法在非高斯噪聲中預(yù)測精度下降的問題.MTP預(yù)測算法與另外2種預(yù)測方法的差異除了模型不同之外，還缺少軌跡數(shù)據(jù)預(yù)處理操作，因此預(yù)測結(jié)果受噪聲影響較大.本節(jié)仿真數(shù)據(jù)統(tǒng)一使用微軟亞洲研究院Geolife項目的數(shù)據(jù)集，運用4.2節(jié)得到的參數(shù)高斯混合分量個數(shù)K=15和軌跡段大小β=30對模型性能進行比較評價.

1) 動態(tài)環(huán)境下預(yù)測結(jié)果分析.實際交通環(huán)境是隨機變化的而不是恒定不變的，車輛的運動軌跡間隔也不是均勻的，在這種情況下采用傳統(tǒng)高斯混合模型進行預(yù)測很難得到高精度的預(yù)測結(jié)果，因此我們提出基于變分高斯混合模型環(huán)境自適應(yīng)軌跡預(yù)測方法，其能夠自動調(diào)整高斯混合元組的個數(shù)以適應(yīng)不同的環(huán)境.通過分析比較隨機變化環(huán)境下以上所提3種算法的預(yù)測誤差、預(yù)測可信度、準(zhǔn)確性來證明所提方法的優(yōu)勢.設(shè)環(huán)境參考值n從4到-14動態(tài)變化，觀察訓(xùn)練數(shù)據(jù)集大小對預(yù)測結(jié)果的影響.如圖11所示,本文所提預(yù)測算法優(yōu)于GMTP和MTP.從圖11(a)可以看出ESATP預(yù)測方法平均預(yù)測誤差均小于35 m，而GMTP預(yù)測算法的預(yù)測誤差都在40 m以上，MTP的預(yù)測誤差更是在50 m以上.這是因ESATP算法采用變分貝葉斯推理方法和參數(shù)自適應(yīng)選擇算法自動調(diào)整高斯混合元組個數(shù)，降低了模型對環(huán)境的敏感度.圖11(b)表現(xiàn)了動態(tài)環(huán)境對預(yù)測算法的可信度的影響，ESATP的預(yù)測可信度均在90%以上;GMTP次之在83%以上;最差的是MTP算法，其可信度最高只達到83%.圖11(c)隨機變化環(huán)境對預(yù)測準(zhǔn)確性的影響，ESATP預(yù)測準(zhǔn)確率最高且穩(wěn)定；GMTP雖然也很高，但波動比較大不穩(wěn)定;MTP預(yù)測準(zhǔn)確率最低，不超過30%.

Fig. 12 Accuracy comparison in constant environment圖12 恒定環(huán)境下預(yù)測準(zhǔn)確性比較

2) 恒定環(huán)境下預(yù)測結(jié)果分析.比較恒定環(huán)境下ESATP，GMTP和MTP之間的預(yù)測準(zhǔn)確率、預(yù)測誤差和預(yù)測可信度.結(jié)果如圖12～14所示.從圖12和圖14可以得出恒定環(huán)境下不同訓(xùn)練數(shù)據(jù)集ESATP和GMTP的預(yù)測準(zhǔn)確率和預(yù)測可信度非常的接近，這是由于恒定環(huán)境下GMTP和ESATP算法中高斯混合模型分量個數(shù)只受訓(xùn)練數(shù)據(jù)集的影響，因此相同訓(xùn)練數(shù)據(jù)集GMTP與ESATP的預(yù)測準(zhǔn)確率幾乎相同.從圖13可以看到恒定環(huán)境下ESATP，GMTP和MTP的預(yù)測誤差.其中，ESATP的預(yù)測誤差略優(yōu)于GMTP；MTP的預(yù)測誤差還是比較大，這是由于MTP沒有對軌跡數(shù)據(jù)進行聚類處理，沒有考慮軌跡間的相似性問題，因此預(yù)測誤差比其他2種算法的預(yù)測誤差都大.

Fig.13 Error comparison in constant environment圖13 恒定環(huán)境下預(yù)測誤差比較

Fig. 14 Reliability comparison in constant environment圖14 恒定環(huán)境下預(yù)測可信度比較

Fig .15 Prediction time comparison among typical trajectory prediction algorithms圖15 典型軌跡預(yù)測算法時間性能比較

4.4預(yù)測時間比較

為了再進一步驗證所提方法的性能，觀察不同測試軌跡集的算法預(yù)測時間代價.圖15中，ESATP的預(yù)測時間比GMTP的稍長，相比于MTP 算法要低得多.GMTP預(yù)測時間比ESATP小是因為ESATP方法中軌跡分段發(fā)現(xiàn)隱藏運動模式和參數(shù)自適應(yīng)選擇算法自動調(diào)整高斯混合元組個數(shù)以適應(yīng)不斷變化的環(huán)境過程中需要消耗較多的時間，因此，預(yù)測時間要比GMTP高一點.然而，EASTP比MTP算法的預(yù)測時間要少得多是因為EASTP利用高斯函數(shù)能夠一次刻畫多個軌跡點，因此要比MTP的預(yù)測時間小.

5 總 結(jié)

本文針對動態(tài)環(huán)境下很難對目標(biāo)運動軌跡進行準(zhǔn)確地描述，且軌跡數(shù)據(jù)中存在非高斯噪聲，提出基于變分高斯混合模型環(huán)境自適應(yīng)軌跡預(yù)測方法.為了預(yù)測動態(tài)環(huán)境中移動對象軌跡位置，首先運用聚類方法和軌跡分割方法優(yōu)化軌跡源數(shù)據(jù)；其次，通過變分貝葉斯推理-期望最大化算法估計預(yù)測模型參數(shù)，得到更優(yōu)的模型參數(shù)，并結(jié)合參數(shù)自適應(yīng)選擇算法調(diào)整參數(shù)組合，使預(yù)測模型能夠適應(yīng)不同的環(huán)境.實驗結(jié)果表示所提的預(yù)測方法在保持較低的時間開銷的同時預(yù)測精度較高.

在未來的研究工作中，除了考慮環(huán)境等客觀影響因素之外，還將考慮駕駛員個人駕駛習(xí)慣和偏好主觀影響因素對軌跡預(yù)測準(zhǔn)確率的影響，進一步提高預(yù)測精度.

[1]Wang Zuchao, Lu Min, Yuan Xiaoru. Visual traffic jam analysis based on trajectory data[J]. IEEE Trans on Visualization and Computer Graphics, 2013, 19(2): 2159-2168

[2]Song Chaoming, Qu Zehui, Blumm N, et al. Limits of predictability in human mobility[J]. America Association for the Advancement of Science, 2010, 327(5968): 1018-1021

[3]Trasarti R, Guidotti R, Monreale A, et al. Myway: Location prediction via mobility profiling[J]. Information Systems, 2015, 64: 350-367

[4]Horvitz E, Krumm J. Some help on the way: Opportunistic routing under uncertainty[C]Proc of the 2012 ACM Conf on Ubiquitous Computting. New York: ACM, 2012: 371-380

[5]Xu Lingwei, Wu Chunlei, Wang Jingjin. A performance analysis of vehicle-to-vehicle communication system in the Internet of vehicle[J]. Netinfo Security, 2014 (7): 61-64 (in Chinese)(徐凌偉, 吳春雷, 王景景. 車聯(lián)網(wǎng)中車-車通信系統(tǒng)性能分析[J]. 信息網(wǎng)絡(luò)安全, 2014 (7): 61-64)

[6]Deb S, Jia C, Fong S. On-road directional trajectory prediction by junction-based pattern mining from GPS data[C]Proc of Int Conf on Machine Intelligent and Research Advancement. Piscataway, NJ: IEEE, 2013: 253-257

[7]Chen Ling, Lü Mingqi, Ye Qian, et al. A personal route prediction system based on trajectory data mining [J]. Information Sciences, 2011,11(35): 1264-1284

[8]Ying J C, Lee W C, Weng T C, et al. Semantic trajectory mining for location prediction[C]Proc of the 19th ACM SIGSPATIAL Int Conf on Advances in Geographic Information Systems. New York: ACM, 2011: 34-43

[9]Qiao Shaojie, Han Nan, Zhu W, et al. Traplan: An effective three-in-one trajectory-prediction model in transportation networks [J]. IEEE Trans on Intelligent Transportation Systems, 2014,16(3): 1188-1198

[10]Guo Chao, Li Kun, Wang Yongyan, et al. A location index for range query in real-time location system [J].Journal of Computer Research and Development, 2011, 48(10): 1908-1917 (in Chinese)(郭超, 李坤, 王永炎, 等. 面向?qū)崟r定位系統(tǒng)的位置區(qū)域索引[J]. 計算機研究與發(fā)展, 2011, 48(10): 1908-1917)

[11]Schreier M, Willert Volker, Adamy J. Bayesian, maneuver-based, long-term trajectory prediction and criticality assessment for driver assistance system[C]Proc of IEEE Int Conf on Intelligent Transportation System. Piscataway, NJ: IEEE, 2014: 334-341

[12]Qiao Shaojie, Tang Changjie, Jin Huidong, et al. PutModel: Prediction of uncertain trajectories in moving objects databases[J]. Applied Intelligence, 2010, 33(3): 370-386

[13]Li Wen, Xia Shixiong, Liu Feng, et al. Location prediction algorithm based on movement tendency [J]. Journal of Communications, 2014, 2(35): 46-62 (in Chinese)(李雯, 夏士雄, 劉峰, 等. 基于運動趨勢的移動對象位置預(yù)測[J]. 通信學(xué)報, 2014, 2(35): 46-62)

[14]Ziebart B D, Maas A L, Dey A K, et al. Navigate like a cabbie: Probabilistic reasoning from observed context-aware behavior[C]Proc of the 10th Int Conf on Ubiquitous computing. New York: ACM, 2008: 322-331

[15]Guo Limin, Ding Zhiming, Hu Zelin, et al. Uncertain path prediction of moving objects on road networks[J]. Journal of Computer Research and Development, 2010, 47(1): 104-112 (in Chinese)(郭黎敏, 丁治明, 胡澤林, 等. 基于路網(wǎng)的不確定性軌跡預(yù)測[J]. 計算機研究與發(fā)展, 2010, 47(1): 104-112)

[16]Qiao Shaojie, Shen Dayong, Wang Xiaoteng, et al. A self-adaptive parameter selection trajectory prediction approach via hidden Markov models[J]. IEEE Trans on Intelligent Transportation System, 2015, 16(1): 284-296

[17]Qiao Shaojie, Li Tianrui, Han Nan, et al. Self-adaptive trajectory prediction model for moving objects in big data environment [J]. Journal of Software, 2015, 26(11): 2869-2883 (in Chinese)(喬少杰, 李天瑞, 韓楠, 等. 大數(shù)據(jù)環(huán)境下移動對象自適應(yīng)軌跡預(yù)測模型[J]. 軟件學(xué)報, 2015, 26(11): 2869-2883)

[18]Lü Mingqi, Chen Ling, Chen Gencai. Position prediction based on adaptive multi-order Markov model [J]. Journal of Computer Research and Development, 2010, 47(10): 1764-1770 (in Chinese)(呂明琪, 陳嶺, 陳根才. 基于自適應(yīng)多階Markov模型的位置預(yù)測[J]. 計算機研究與發(fā)展, 2010, 47(10): 1764-1770)

[19]Chen Meng, Yu Xiaohui, Liu Yang. Mining moving patterns for prediction next location [J]. Information Systems, 2015, 54(C):156-168

[20]Heravi E J, Khanmohammadi S. Long term trajectory prediction of moving objects using Gaussian process[C]Proc of the 1st IEEE 2011 Int Conf on Robot, Vision and Signal Processsing. Piscataway, NJ: IEEE, 2011: 228-232

[21]Wiest J, H?ffken M, Kre?el U, et al. Probabilistic trajectory prediction with Gaussian mixture models [C]Proc of Intelligent Vehicles Symp. Piscataway, NJ: IEEE, 2012, 5(3): 141-146

[22]Qiao Shaojie, Jin Kun, Han Nan, et al. GMTP: A trajectory prediction algorithm based on Gaussian mixture model [J]. Journal of Software, 2015, 26(5):1048-1063 (in Chinese)(喬少杰, 金琨, 韓楠, 等. GMTP: 基于高斯混合模型的軌跡預(yù)測算法[J]. 軟件學(xué)報, 2015, 26(5): 1048-1063)

[23]Huang C C, Manh H N, Hwang T H. Vehicle trajectory prediction across non-overlapping camera networks[C]Proc of IEEE Int Conf on Connected Vehicles and Expo. Piscataway, NJ: IEEE, 2013: 375-380

[24]Lei P R, Shen T J, Peng W C, et al. Exploring spatial-temporal trajectory model for location prediction [C]Proc of the 12th IEEE Int Conf on Mobile Data Management. Piscataway, NJ: IEEE, 2011: 58-67

[25]Birant D, Kut A. ST-DBSCAN: An algorithm for clustering spatial-temporal data[J]. Data amp; Knowledge Engineering, 2007, 60(1): 208-221

[26]Chan A, Li F W B. Utilizing massive spatiotemporal sample for efficient and accurate trajectory prediction[J]. IEEE Trans on Mobile Computing, 2013,12(12): 2346-2359

[27]Xu Dingjie, Shen Chen, Shen Feng. Variational Bayesian learning for parameter estimation of mixture of Gaussian [J]. Journal of Shanghai Jiao Tong University, 2013, 47(7): 1120-1125 (in Chinese)(徐定杰, 沈忱, 沈鋒. 混合高斯分布的變分貝葉斯學(xué)習(xí)參數(shù)估計[J].上海交通大學(xué)學(xué)報, 2013, 47(7): 1120-1125)

[28]Mishra H K, Sekhar C C. Variational Gaussian mixture models for speech emotion recognition[C]Proc of the 7th IEEE Int Conf on Advances in Pattern Recognition. Piscataway, NJ: IEEE, 2009: 183-232

[29]Nasios N, Bors A G. Variational learning for Gaussian mixture models [J]. IEEE Trans on System Man and Cybernetics—Part B: Cybernetics, 2006, 36(4): 849-862

[30]Zheng Yu, Xie Xing, Ma Weiming. GeoLife: A collaborative social networking service among user, location and trajectory [J]. Bulletin of the Technical Committee on Data Engineering, 2010, 33(2): 32-39

[31]Ye M, Shou D, Lee W C, et al. On the semantic annotation of place in location-based social networks[C]Proc of the 17th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2011: 520-528

XiaZhuoqun, born in 1977. PhD. Associate professor at Changsha University of Science and Technology. His main research interests include wireless networks, VANET, smart grid.

HuZhenzhen, born in 1988. Master candidate at Changsha University of Science and Technology. Her main research interest is intelligence transportation system.

LuoJunpeng, born in 1992. Master candidate at Changsha University of Science and Technology. His main research interest is intelligent transportation.

AdaptiveTrajectoryPredictionforMovingObjectsinUncertainEnvironment

Xia Zhuoqun1,2,3, Hu Zhenzhen1,2, Luo Junpeng1,2, and Chen Yueyue3

1(Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation (Changsha University of Science and Technology), Changsha 410114)2(School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410114)3(College of Computer, National University of Defense Technology, Changsha 410114)

The existing methods for trajectory prediction are difficult to describe the trajectory of moving objects in complex and uncertain environment accurately. In order to solve this problem, this paper proposes an self-adaptive trajectory prediction method for moving objects based on variation Gaussian mixture model (VGMM) in dynamic environment (ESATP). Firstly, based on the traditional mixture Gaussian model, we use the approximate variational Bayesian inference method to process the mixture Gaussian distribution in model training procedure. Secondly, variational Bayesian expectation maximization iterative is used to learn the model parameters and prior information is used to get a more precise prediction model. This algorithm can take a priory information. Finally, for the input trajectories, parameter adaptive selection algorithm is used automatically to adjust the combination of parameters, including the number of Gaussian mixture components and the length of segment. Experimental results perform that the ESATP method in the experiment shows high predictive accuracy, and maintains a high time efficiency. This model can be used in products of mobile vehicle positioning.

environment adaptive; variational Gaussian mixture model (VGMM); parameter adaptive selection algorithm; trajectory prediction

her bachelor and master degrees in computer science and technology from National University of Defense Technology (NUDT), Changsha in 2013 and 2015, respectively. PhD candidate in the College of Computer, NUDT. Her main research interests include mobile sensing and task assignment.

2017-05-08；

2017-08-10

國家自然科學(xué)基金項目(61572514)；湖南省自然科學(xué)基金項目(14JJ7043)；湖南省交通廳科技進步與創(chuàng)新項目(201405)

This work was supported by the National Natural Science Foundation of China (61572514), the Natural Science Foundation of Hunan Province of China (14JJ7043), and the Transportation Department Technological Progress and Innovation Fund of Hunan Province of China (201405).

胡珍珍(1102439691@qq.com)

(xiazhuoqun@sina.com)

TP391