基于環(huán)境約束的不確定車輛軌跡預(yù)測方法

張?；?/p>

摘要：

針對現(xiàn)有預(yù)測算法很少考慮環(huán)境因素，預(yù)測精度不高的問題，提出了一種基于環(huán)境約束的不確定軌跡數(shù)據(jù)預(yù)測算法（EGTP）。首先獲取歷史軌跡數(shù)據(jù)所處的環(huán)境信息，利用環(huán)境信息和軌跡數(shù)據(jù)構(gòu)造一個新的軌跡參考點(diǎn)，模擬帶有環(huán)境信息的車輛不確定軌跡數(shù)據(jù)；然后基于高斯混合模型，對軌跡參考點(diǎn)數(shù)據(jù)和歷史軌跡數(shù)據(jù)進(jìn)行訓(xùn)練；最后在訓(xùn)練的基礎(chǔ)上利用軌跡參考點(diǎn)和歷史軌跡數(shù)據(jù)對車輛軌跡實(shí)時預(yù)測。由于考慮了出行的環(huán)境因素，預(yù)測結(jié)果更符合現(xiàn)實(shí)情景。實(shí)驗(yàn)驗(yàn)證了該算法在實(shí)時性和預(yù)測準(zhǔn)確度上較其它算法有所提高。

關(guān)鍵詞：

環(huán)境約束；不確定軌跡；軌跡預(yù)測；軌跡參考點(diǎn)；高斯混合模型

DOIDOI：10.11907/rjdk.172248

中圖分類號：TP306

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2018）001004402

Abstract：In view of the existing prediction algorithms seldom consider environmental factors predicting accuracy， proposes a prediction algorithm for uncertain trajectory based on environmental constraints （egtp）， the main steps include： first， the historical data acquisition environment information， the combined data structure by using the trajectory reference point to simulate the environment information of the vehicle with uncertain trajectory； then Gauss mixture model trained on the trajectory reference point data and historical data based on the trajectory reference point and historical data using realtime prediction of vehicle trajectory. Considering the environmental factors of travel，the prediction results more realistic scenarios.Finally， the experimental results show that the algorithm is accurate in predicting real time and degree than the other algorithms are improved.

Key Words：environmental constraints； uncertain trajectory；trajectory prediction；trajectory reference point；GMM

0引言

衛(wèi)星定位技術(shù)、無線通信技術(shù)和地理信息技術(shù)的迅速發(fā)展，使定位設(shè)備在車載以及移動終端上得到廣泛應(yīng)用。安裝在公交車輛、出租車以及其它車輛上的GPS設(shè)備記錄著城市交通、人群移動的動態(tài)變化[1]，將不同時刻的車輛位置信息收集起來就可構(gòu)成多條完整的軌跡序列數(shù)據(jù)，可以利用這些歷史軌跡數(shù)據(jù)對車輛未來軌跡進(jìn)行預(yù)測。本文提出一種基于預(yù)測模型的車輛行駛軌跡預(yù)測方法。

對移動對象不確定軌跡預(yù)測有三方面：①將移動軌跡按照時間進(jìn)行分段研究[2]；②基于歷史軌跡數(shù)據(jù)推薦各種最優(yōu)路徑[3]；③挖掘歷史軌跡的頻繁模式預(yù)測未來軌跡[4]，其中研究成果主要集中在頻繁模式挖掘上，通過挖掘軌跡頻繁模式規(guī)劃出最優(yōu)路徑并進(jìn)行預(yù)測。與此同時，還有利用多種預(yù)測模型對軌跡進(jìn)行預(yù)測，如貝葉斯網(wǎng)絡(luò)[5]、混合馬爾科夫模型[6]、隱馬爾科夫模型[7]、高斯混合模型[89]等方法。陳勐[6]考慮到大部分人的移動模式都是有規(guī)律的，利用混合馬爾可夫模型對行人要到達(dá)的下一地點(diǎn)進(jìn)行預(yù)測。喬少杰等[7]通過將海量軌跡數(shù)據(jù)進(jìn)行分區(qū)，根據(jù)輸入軌跡自動選取參數(shù)的方法，提出了基于隱馬爾可夫模型的自適應(yīng)軌跡預(yù)測模型。

雖然利用時空軌跡對軌跡預(yù)測做了大量研究，但大部分都是利用歷史軌跡進(jìn)行預(yù)測，忽略了環(huán)境對預(yù)測結(jié)果的影響。本文考慮環(huán)境因素，利用參考點(diǎn)攜帶環(huán)境信息，結(jié)合高斯混合模型對車輛軌跡進(jìn)行預(yù)測。

1基本概念

本文的數(shù)據(jù)模型中，移動對象數(shù)據(jù)集D由n條軌跡組成，每條軌跡由多個地點(diǎn)串聯(lián)而成，用 D={Trj1，Trj2，…，Trjn}表示，軌跡的數(shù)量定義為|D|。

定義1定義具有環(huán)境特征的不確定移動軌跡形式為Trj=，{pi=|1<=i<=n}，其中Ci為當(dāng)時所處的環(huán)境類別，為空間位置點(diǎn)的經(jīng)緯度，ti（i=0，…，n）是相應(yīng)時間戳。

定義2定義軌跡參考點(diǎn) TRP（Trajectory Reference Point）。軌跡參考點(diǎn)由P={P1，P2，…Pn}表示，Pi=（（xi，yi），ER），其中（xi，yi）是位置坐標(biāo)值，ER為環(huán)境參考信息。P的位置坐標(biāo)由歷史軌跡坐標(biāo)計(jì)算得到， ER值從歷史數(shù)據(jù)中獲取。

定義3預(yù)測誤差 PE（Prediction Error）采用均方根誤差RMSE計(jì)算，預(yù)測軌跡點(diǎn)與軌跡參考點(diǎn)的集合空間誤差：

式（1）中：（x′i，y′i）為預(yù)測軌跡點(diǎn)，（Pix，Piy）為軌跡參考點(diǎn)，k為得到的預(yù)測軌跡點(diǎn)數(shù)量。

2基于GMM的不確定軌跡預(yù)測模型

2.1不確定軌跡處理

為了提高預(yù)測精度，使預(yù)測結(jié)果更符合環(huán)境條件，在進(jìn)行軌跡預(yù)測前需對軌跡數(shù)據(jù)進(jìn)行處理，本文通過高斯混合模型聚類實(shí)現(xiàn)這一過程。首先通過軌跡點(diǎn)包含的信息值把歷史軌跡粗聚類，然后利用GMM對歷史軌跡數(shù)據(jù)重新聚類。其中利用KMeans算法初步計(jì)算出模型中的參數(shù)，接著根據(jù)得出的模型參數(shù)初步確定聚類簇的數(shù)量K，最后利用EM（最大似然估計(jì)）算法迭代優(yōu)化KMeans初步聚類結(jié)果，最終得到 K個聚簇。

2.2TRP創(chuàng)建

由于獲得的車輛軌跡數(shù)據(jù)往往不確定，為了確定預(yù)測模型的可靠性，采用TRP值代替獲取的軌跡值。TRP由訓(xùn)練得到，能彌補(bǔ)不確定軌跡由于各種因素導(dǎo)致的誤差。軌跡參考點(diǎn)中信息值的計(jì)算公式為：

式（2）中：pL（d0）為信息參考值，是信號距離為d0的路徑損耗值；n為信息值的環(huán)境約束，主要包括天氣情況、路面狀況、交通狀況等，是利用空間向量模型將環(huán)境因素?cái)?shù)值化的值；σ表示均值為0的高斯隨機(jī)變量。

TRP創(chuàng)建過程：①初始化軌跡參考點(diǎn)集TRP和集合C′；②將原始軌跡按照環(huán)境約束進(jìn)行粗聚類；③將粗聚類后的軌跡數(shù)據(jù)重新聚類；④依次訪問軌跡聚類簇C，將當(dāng)前正在訪問的簇Ci標(biāo)記為“visited”；⑤根據(jù)時間窗大小對正在訪問的軌跡簇Ci進(jìn)行柵格化，得到n個子軌跡集；⑥遍歷子軌跡集中的軌跡點(diǎn)N；⑦根據(jù)子軌跡集中軌跡點(diǎn)坐標(biāo)計(jì)算出中心點(diǎn)坐標(biāo)；⑧將步驟⑦得到的中心點(diǎn)坐標(biāo)作為TRP的坐標(biāo)點(diǎn)位置，將坐標(biāo)中包含的環(huán)境信息值的平均值作為TRP的ER值；⑨判斷Cj是否已被標(biāo)記“visited”，如果已標(biāo)記，則結(jié)束軌跡參考點(diǎn)創(chuàng)建，否則，執(zhí)行步驟④。

2.3帶有環(huán)境約束的高斯回歸預(yù)測模型

將原始軌跡數(shù)據(jù)Ttrain=（x，y）用作訓(xùn)練數(shù)據(jù)，軌跡參考點(diǎn)P=（P1，P2，…，Pn），設(shè)輸入數(shù)據(jù)為x，輸出數(shù)據(jù)為y，將測試數(shù)據(jù)記為Ttest=（x′，y′）?；貧w預(yù)測模型計(jì)算步驟如下：①利用高斯模型計(jì)算輸入TRP和訓(xùn)練輸出的條件概率Py|p，并根據(jù)條件概率計(jì)算公式計(jì)算出輸出值y；②利用高斯模型計(jì)算出訓(xùn)練輸出y和預(yù)測輸出y′的聯(lián)合概率 P（y′y），訓(xùn)練輸出的邊緣概率Py及條件概率 P（y′|y）；③利用條件概率密度函數(shù)計(jì)算出預(yù)測輸出的條件期望預(yù)測值；④得出具有環(huán)境約束的車輛軌跡回歸預(yù)測模型公式如下：

為混合權(quán)重。

2.4軌跡在線預(yù)測算法實(shí)現(xiàn)

本文提出的帶有環(huán)境約束的不確定軌跡預(yù)測算法如下：

輸入：訓(xùn)練軌跡數(shù)據(jù)集

測試軌跡數(shù)據(jù)集

RMSEthres //誤差閾值

輸出：預(yù)測軌跡序列

T={s1，s2，…sd}；//已知軌跡序列

D={s1，s2，…sn}；//粗聚類后軌跡序列

Pa_F=K（Ttrain）；//初始化模型參數(shù)

F=EM（Pa_F，Ttest）；//迭代求取模型參數(shù)

TRP=CJ_trp（F）；//創(chuàng)建軌跡參考點(diǎn)

M=train（F，TRP）；//模型訓(xùn)練

k=n-d；

for i=1 to k

trj=pred（m）；//預(yù)測未來連續(xù)k步軌跡

PE[i]=sRMSE（trj，trjr）；//trj為預(yù)測軌跡，trjr為真實(shí)軌跡

End

RMSE=（∑ki=1PE[i]）/k；求取誤差均值

RMSE

TRP=TRP；

（trj）={trj1，trj2，…trjn}；

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

本文采集了40 453條MIT停車場[10]車輛軌跡數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)。其中訓(xùn)練軌跡數(shù)量為39 453條，測試軌跡數(shù)量為1 000條，環(huán)境情況模擬為晴天和雨雪兩種。將本文算法和基于高斯混合模型軌跡預(yù)測算法、基于馬爾科夫模型預(yù)測算法在準(zhǔn)確性和時間代價上作比較，如圖1、圖2，實(shí)驗(yàn)證明，本算法更有優(yōu)勢。

圖1為測試集合下所有軌跡預(yù)測誤差的平均值。從圖中可以看出，隨著軌跡數(shù)量的增加，EGTP算法的預(yù)測誤差最小，算法預(yù)測精度較高且比較穩(wěn)定。

從圖2可以看出，隨著測試軌跡數(shù)量的增加，3種算法的預(yù)測時間都有所增加，但是EGTP的預(yù)測時間要比GMTP高一些，比MTP算法要低，這是因?yàn)镋GTP算法在預(yù)測時考慮了環(huán)境因素，并且建立虛擬參考點(diǎn)也要消耗一些時間。但是在真實(shí)場景中，環(huán)境一般是穩(wěn)定的，所以EGTP的時間代價相對較低。

4結(jié)語

本文提出了一種基于環(huán)境約束的軌跡預(yù)測算法，針對不同環(huán)境導(dǎo)致預(yù)測精度不高的問題，充分考慮了各種現(xiàn)實(shí)因素，在軌跡點(diǎn)中加入了環(huán)境特征，使預(yù)測出的軌跡更符合實(shí)際，更能描述行為趨勢。

參考文獻(xiàn)：

[1]張紅，王曉明，過秀成，等.出租車GPS軌跡大數(shù)據(jù)在智能交通中的應(yīng)用[J].蘭州理工大學(xué)學(xué)報，2016，42（1）：109114.

[2]YOON H， SHAHABI C. Robust timereferenced segmentation of moving object trajectories[C].Eighth IEEE International Conference on Data Mining. IEEE Computer Society， 2008：11211126.

[3]郭黎敏，丁治明，胡澤林，等.基于路網(wǎng)的不確定性軌跡預(yù)測[J].計(jì)算機(jī)研究與發(fā)展，2010， 47（1）：104112.

[4]喬少杰，沈志強(qiáng).PathExplorer：基于頻繁模式的不確定性軌跡預(yù)測系統(tǒng)[J]. 計(jì)算機(jī)研究與發(fā)展，2012，49（suppl.）：413417.

[5]LI WANGAO， ZHAO XUEMEI， SUN DECHANG. Prediction of trajectory based on modified Bayesian inference[J]. Journal of Computer Applications， 2013，33（7）：19601963.

[6]陳勐.軌跡預(yù)測與意圖挖掘問題研究[D].濟(jì)南：山東大學(xué)，2016.

[7]喬少杰，李天瑞，韓楠，等.大數(shù)據(jù)環(huán)境下移動對象自適應(yīng)軌跡預(yù)測模型[J].軟件學(xué)報，2015，26（11）：28692883.

[8]DAI J， YANG B， GUO C， et al. Personalized route recommendation using big trajectory data[C].IEEE， International Conference on Data Engineering. IEEE， 2015：543554.

[9]喬少杰，金琨，韓楠，等.一種基于高斯混合模型的軌跡預(yù)測算法[J].軟件學(xué)報，2015，26（5）：10481063.

[10]MIT[EB /OL]. http：//www.ee.cuhk.edu.hk/xgwang/MITtrajsingle.html/，2007.

（責(zé)任編輯：杜能鋼）