高建 毛鶯池 李志濤

摘 要：針對(duì)不同時(shí)間道路車流量變化下軌跡預(yù)測(cè)誤差變化大的問題，提出基于概率分布模型的高斯混合 時(shí)間序列模型（GMTSM），對(duì)海量車輛歷史軌跡進(jìn)行模型回歸和路段車流量的分析以實(shí)現(xiàn)車輛軌跡預(yù)測(cè)。首先，針對(duì)均勻網(wǎng)格劃分方法容易造成相關(guān)軌跡點(diǎn)分裂的問題，提出迭代式網(wǎng)格劃分來實(shí)現(xiàn)軌跡點(diǎn)的數(shù)量均衡;其次，訓(xùn)練并結(jié)合高斯混合模型（GMM）和時(shí)間序列分析中的差分自回歸滑動(dòng)平均模型（ARIMA）;然后，為了避免GMTSM中子模型自身的不穩(wěn)定性對(duì)預(yù)測(cè)結(jié)果產(chǎn)生干擾，對(duì)子模型的預(yù)測(cè)進(jìn)行誤差分析，動(dòng)態(tài)計(jì)算子模型的權(quán)重;最后，依據(jù)動(dòng)態(tài)權(quán)重組合子模型實(shí)現(xiàn)軌跡預(yù)測(cè)。實(shí)驗(yàn)結(jié)果表明，GMTSM在路段車流量突變情況下，平均預(yù)測(cè)準(zhǔn)確率為90.3%;與相同參數(shù)設(shè)置下的高斯混合模型和馬爾可夫模型相比，GMTSM預(yù)測(cè)準(zhǔn)確性提高了55%左右。GMTSM不僅能在正常情況下準(zhǔn)確預(yù)測(cè)車輛軌跡，而且能有效提高道路車流量變化情況下的軌跡預(yù)測(cè)準(zhǔn)確率，適用于現(xiàn)實(shí)路況環(huán)境。

關(guān)鍵詞：智能交通;迭代網(wǎng)格劃分;軌跡預(yù)測(cè);模型可靠性;軌跡相似性

中圖分類號(hào)：?TP391.4

文獻(xiàn)標(biāo)志碼：A

Trajectory prediction based on Gauss mixture time series model

GAO Jian*， MAO Yingchi， LI Zhitao

College of Computer and Information， Hohai University， Nanjing Jiangsu 211100， China

Abstract：?Considering the large change of trajectory prediction error caused by the change of road traffic flow at different time， a Gauss Mixture Time Series Model （GMTSM） based on probability distribution model was proposed. The model regression of mass vehicle historical trajectories and the analysis of road traffic flow were carried out to realize vehicle trajectory prediction. Firstly， aiming at the problem that the uniform grid partition method was easy to cause the splitting of related trajectory points， an iterative grid partition method was proposed to realize the quantity balance of trajectory points. Secondly， Gaussian Mixture Model （GMM） and AutoRegressive Integrated Moving Average model （ARIMA） in time series analysis were trained and combined together. Thirdly， in order to avoid the interference of the instability of GMTSM hybrid models sub-models on the prediction results， the weights of sub-models were dynamically calculated by analyzing the prediction errors of the sub-models. Finally， based on the dynamic weight， the sub-models were combined together to realize trajectory prediction. Experimental results show that the average prediction accuracy of GMTSM is 92.3% in the case of sudden change of road traffic flow. Compared with Gauss mixed model and Markov model under the same parameters， GMTSM has prediction accuracy increased by about 55%. GMTSM can not only accurately predict vehicle trajectory under normal circumstances， but also effectively improve the accuracy of trajectory prediction under road traffic flow changes， which is applicable to the real road environment.

Key words：?intelligent transportation; iterative grid partition; trajectory prediction; model reliability; trajectory similarity

0 引言

隨著交通工具的發(fā)展和出行規(guī)模的擴(kuò)大，用戶出行需求日益多樣化，如何解決用戶面臨的交通擁堵、交通不安全等問題是所有城市需要共同解決的問題。隨著無線通信設(shè)備和全球定位系統(tǒng)（Global Positioning System， GPS）設(shè)備的發(fā)展，獲取用戶出行的位置信息并非難事，對(duì)這些軌跡數(shù)據(jù)進(jìn)行挖掘是當(dāng)今研究熱點(diǎn)。

在時(shí)空軌跡數(shù)據(jù)挖掘中，對(duì)移動(dòng)對(duì)象未來位置預(yù)測(cè)是當(dāng)今熱點(diǎn)研究方向之一，有廣闊的應(yīng)用場(chǎng)景，具體如下：

1）基于位置的推薦。當(dāng)一名用戶通過社交網(wǎng)絡(luò)分享了自己當(dāng)前的位置，如果軌跡預(yù)測(cè)模型能夠預(yù)測(cè)到該用戶將要到達(dá)的區(qū)域，那么我們可以向該用戶推薦必要信息，如餐飲信息、商場(chǎng)折扣信息等。

2）車輛之間未來軌跡共享，緩解交通堵塞。隨著智能城市的發(fā)展，很多城市安裝了監(jiān)控系統(tǒng)，交通路況被實(shí)時(shí)記錄下來。軌跡預(yù)測(cè)模型可以實(shí)時(shí)預(yù)測(cè)車輛未來的運(yùn)行軌跡，交通部門可以預(yù)知未來的交通狀況，同時(shí)，用戶可以根據(jù)其他車輛的預(yù)測(cè)路線調(diào)整自己的路線，起到緩解交通壓力的作用。

3）防止車輛碰撞?！肚嗪＝痪l(fā)布2018年“春運(yùn)”期間全省交通安全出行提示》中指出交通路口是車輛碰撞的高發(fā)地帶，如果通過路口的用戶提前預(yù)知其他車輛將來的軌跡，那么就可以提醒用戶在通過路口時(shí)注意自己的開車路線，防止車輛碰撞發(fā)生。

移動(dòng)對(duì)象未來位置受個(gè)人和集體移動(dòng)模式影響。例如，去上班的路徑選擇主要受個(gè)人移動(dòng)模式影響;去陌生的地方時(shí)，采用地圖導(dǎo)航或詢問他人等方式選擇路徑，主要受集體移動(dòng)模式影響?，F(xiàn)有位置預(yù)測(cè)方法只采用個(gè)人或集體的一種移動(dòng)模式，具有局限性，沒有考慮到軌跡影響因子（如時(shí)間、天氣、季節(jié)等）。

如圖1所示，存在4條軌跡，S1=〈p1，p2，p3〉，S2=〈p5，p2，p3〉，S3=〈p1，p4，p5〉，S4=〈p5，p6〉，其中pi（1≤i≤9）是線性軌跡鏈中的軌跡點(diǎn)。當(dāng)一輛車經(jīng)過p1、p4，包含位置序列〈p1，p4〉的歷史軌跡中出現(xiàn)次數(shù)最多的下一個(gè)位置將作為預(yù)測(cè)結(jié)果。在4條軌跡中，位置序列〈p1，p4〉和歷史軌跡S3部分匹配，因此選擇p5為下一個(gè)位置點(diǎn)。用戶從區(qū)域B到區(qū)域A，在車流量非高峰期間，選擇路線S4;在車流量高峰期間，點(diǎn)p5所在路口禁止右轉(zhuǎn)，選擇路線S2。因此，穩(wěn)定、準(zhǔn)確的軌跡預(yù)測(cè)模型需要考慮時(shí)間因素。

現(xiàn)有移動(dòng)對(duì)象軌跡預(yù)測(cè)方法包括貝葉斯推理、馬爾可夫鏈、隱馬爾可夫模型、神經(jīng)網(wǎng)絡(luò)方法以及狀態(tài)預(yù)測(cè)方法。Killijian等[1]考慮到歷史狀態(tài)的影響，提出高階的馬爾可夫鏈模型，擴(kuò)展了馬爾可夫鏈的流動(dòng)性。李萬高等[2]提出了一種改進(jìn)的貝葉斯推理算法（Modified Bayesian Inference， MBI），解決了有限的歷史軌跡數(shù)據(jù)問題，MBI建立的馬爾可夫模型量化了相關(guān)的相鄰的位置，劃分歷史軌跡能得到更多精確馬爾可夫模型。

現(xiàn)有的軌跡預(yù)測(cè)方法中只對(duì)歷史位置信息進(jìn)行分析，很少將時(shí)間因素考慮在內(nèi)。文獻(xiàn)[3]對(duì)不同時(shí)間段的車流情況建立車輛移動(dòng)模式（Vehicular Mobility Pattern，VMP）進(jìn)行軌跡預(yù)測(cè)，這種方法雖然進(jìn)行了時(shí)間箱的分割，但是很難找到合適大小的時(shí)間箱適配所有的移動(dòng)模式。Zheng等[4]提出將空間預(yù)測(cè)數(shù)據(jù)和時(shí)序預(yù)測(cè)異構(gòu)數(shù)據(jù)融合的方法，將道路結(jié)構(gòu)、興趣點(diǎn)分布等空間信息運(yùn)用在半監(jiān)督學(xué)習(xí)框架中，但預(yù)測(cè)效果不佳。

本文通過對(duì)現(xiàn)有軌跡預(yù)測(cè)模型的分析，結(jié)合道路車流量分析，提出基于高斯混合 時(shí)間序列模型（Gauss Mixture Time Series Model， GMTSM）的軌跡預(yù)測(cè)方法。主要內(nèi)容有：1）針對(duì)均勻網(wǎng)格劃分方法容易造成相關(guān)軌跡點(diǎn)分裂問題，提出迭代式網(wǎng)格劃分，實(shí)現(xiàn)軌跡點(diǎn)的數(shù)量均衡。2）訓(xùn)練并結(jié)合了高斯混合模型（Gaussian Mixture Model， GMM）和時(shí)間序列分析中的差分自回歸滑動(dòng)平均模型（Autoregressive Integrated Moving Average model， ARIMA）。3）為了避免GMTSM混合模型中子模型自身不穩(wěn)定性對(duì)預(yù)測(cè)結(jié)果產(chǎn)生干擾，通過對(duì)子模型的預(yù)測(cè)誤差分析，動(dòng)態(tài)計(jì)算子模型的權(quán)重。4）通過實(shí)驗(yàn)驗(yàn)證GMTSM的準(zhǔn)確性和穩(wěn)定性。

1 軌跡預(yù)測(cè)模型分析

移動(dòng)對(duì)象的軌跡預(yù)測(cè)需要考慮自身因素、道路車流量因素、時(shí)間天氣因素等多種因素?，F(xiàn)有的軌跡預(yù)測(cè)模型主要分為以下三類：基于運(yùn)動(dòng)模型的軌跡預(yù)測(cè)、基于歷史數(shù)據(jù)挖掘的軌跡預(yù)測(cè)和基于混合方法的軌跡預(yù)測(cè)。

1.1 基于運(yùn)動(dòng)模型的軌跡預(yù)測(cè)

移動(dòng)對(duì)象的運(yùn)動(dòng)信息包括運(yùn)動(dòng)速度、運(yùn)動(dòng)方向和運(yùn)動(dòng)時(shí)間等。很多模型通過構(gòu)造線性運(yùn)動(dòng)函數(shù)預(yù)測(cè)移動(dòng)對(duì)象的運(yùn)動(dòng)信息。線性模型雖然高效，但不符合現(xiàn)實(shí)生活中移動(dòng)對(duì)象非線性運(yùn)動(dòng)情況，導(dǎo)致預(yù)測(cè)誤差大。若通過不斷更新移動(dòng)對(duì)象運(yùn)動(dòng)信息的方法降低預(yù)測(cè)誤差，模型預(yù)測(cè)效率會(huì)下降。因此，線性模型軌跡預(yù)測(cè)不適合實(shí)際應(yīng)用。

針對(duì)線性模型軌跡預(yù)測(cè)的缺陷，有學(xué)者提出了基于非線性模型的軌跡預(yù)測(cè)方法。文獻(xiàn)[5]中改進(jìn)線性軌跡預(yù)測(cè)模型，提出了一種并行的軌跡序列模式挖掘方法，結(jié)合了三個(gè)關(guān)鍵技術(shù)：前綴投影、并行表示、候選序列修剪。其中：利用前綴投影技術(shù)對(duì)搜索空間進(jìn)行分解，減少候選軌跡序列;并行公式集成了數(shù)據(jù)并行公式和任務(wù)并行公式來劃分計(jì)算，并以高效的方式將它們分配給多個(gè)處理器，從而降低跨處理器的通信成本。Tao等[6]提出一種支持任何運(yùn)動(dòng)模型的預(yù)測(cè)算法，基于未知模型對(duì)任何軌跡模式進(jìn)行位置預(yù)測(cè)，但得到的運(yùn)動(dòng)函數(shù)僅適用于短時(shí)間的數(shù)據(jù)預(yù)測(cè)，無法預(yù)測(cè)長(zhǎng)時(shí)間的數(shù)據(jù)。

1.2 基于歷史數(shù)據(jù)挖掘的軌跡預(yù)測(cè)

基于運(yùn)動(dòng)模型的預(yù)測(cè)方法是建立線性或非線性函數(shù)進(jìn)行預(yù)測(cè)，但預(yù)測(cè)誤差大、預(yù)測(cè)時(shí)間短，考慮到運(yùn)動(dòng)模型沒有充分用到移動(dòng)對(duì)象的歷史數(shù)據(jù)，基于歷史軌跡數(shù)據(jù)的預(yù)測(cè)算法被提出。通過對(duì)歷史軌跡數(shù)據(jù)的學(xué)習(xí)，觀察移動(dòng)對(duì)象頻繁活動(dòng)區(qū)域，挖掘數(shù)據(jù)隱含的規(guī)律。

基于歷史數(shù)據(jù)的軌跡預(yù)測(cè)方法有貝葉斯網(wǎng)絡(luò)、隱馬爾可夫模型、神經(jīng)網(wǎng)絡(luò)以及高斯混合模型等。喬少杰等[7]在多種運(yùn)動(dòng)形式下建立GMM來實(shí)現(xiàn)移動(dòng)對(duì)象復(fù)雜運(yùn)動(dòng)形式下的概率分布進(jìn)行軌跡預(yù)測(cè);同時(shí)，喬少杰等[8]還提出了基于隱馬爾可夫模型的自適應(yīng)軌跡預(yù)測(cè)模型，通過發(fā)現(xiàn)不連續(xù)的隱藏狀態(tài)進(jìn)行長(zhǎng)期的軌跡預(yù)測(cè)。

Best等[9]提出了貝葉斯預(yù)測(cè)模型實(shí)現(xiàn)對(duì)人體運(yùn)動(dòng)的預(yù)測(cè)，但不適合快速移動(dòng)對(duì)象預(yù)測(cè)。Xue等[3]提出了變階的馬爾可夫模型（Variable-order Markov Model， VMM），利用車輛互聯(lián)的關(guān)系對(duì)車輛網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析，挖掘車輛之間的移動(dòng)模式;但只是對(duì)交通狀況信息的獲取，不能針對(duì)車輛使用者作出軌跡預(yù)測(cè)。

移動(dòng)軌跡數(shù)據(jù)包含空間信息和時(shí)間信息，Lei等[10]通過獲取移動(dòng)對(duì)象在空間和時(shí)間上的運(yùn)動(dòng)行為建立時(shí)空軌跡模型，該模型建立軌跡后綴樹，樹上每個(gè)節(jié)點(diǎn)記錄了下一個(gè)位置的空間信息和時(shí)間信息，實(shí)現(xiàn)了空間位置的預(yù)測(cè)，同時(shí)預(yù)測(cè)預(yù)定時(shí)間到達(dá)的概率。Gao等[11]充分考慮時(shí)間信息對(duì)軌跡的影響，使用貝葉斯公式進(jìn)行位置點(diǎn)預(yù)測(cè)，實(shí)驗(yàn)結(jié)果顯示，時(shí)間信息的引入可以提高預(yù)測(cè)準(zhǔn)確性。

1.3 基于混合方法的軌跡預(yù)測(cè)

不同移動(dòng)對(duì)象表現(xiàn)的運(yùn)動(dòng)規(guī)律性不完全相同，隨著時(shí)間的變化，同一個(gè)移動(dòng)對(duì)象在不同時(shí)間段內(nèi)的運(yùn)動(dòng)模式也存在差別。同時(shí)，由于移動(dòng)對(duì)象具有獨(dú)特的生活方式和訪問偏好，對(duì)歷史位置的訪問呈現(xiàn)冪律分布現(xiàn)象，只有少量位置被頻繁訪問，大多數(shù)位置訪問次數(shù)稀少。針對(duì)不同移動(dòng)對(duì)象、不同時(shí)間段以及不同位置需要混合多種預(yù)測(cè)方法進(jìn)行預(yù)測(cè)。

Jeung等[12]采用分時(shí)預(yù)測(cè)的方式，提出依據(jù)預(yù)測(cè)時(shí)間選擇不同預(yù)測(cè)方法的新思路;李昇智等[13]提出基于混合多步Markov模型的位置預(yù)測(cè)方法，將原始軌跡轉(zhuǎn)化為區(qū)域軌跡，對(duì)各多步模型進(jìn)行融合;Wiest等[14]提出結(jié)合貝葉斯網(wǎng)絡(luò)和高斯混合模型（Variational Gaussian Mixture Model， VGMM）預(yù)測(cè)車輛行駛路徑，該方法預(yù)測(cè)精度較高且時(shí)間開銷較低;夏卓群等[15]提出基于VGMM環(huán)境自適應(yīng)方法（Environment Self-Adaptive Prediction Method based on VGMM， ESATP），使用參數(shù)自適應(yīng)選擇算法自動(dòng)調(diào)節(jié)參數(shù)組合，靈活調(diào)整混合高斯分量的個(gè)數(shù)和軌跡段大小。

綜上所述，基于混合方法的軌跡預(yù)測(cè)通過分析移動(dòng)對(duì)象運(yùn)動(dòng)模式進(jìn)行不同方法的選擇，對(duì)實(shí)時(shí)性要求高的移動(dòng)對(duì)象軌跡預(yù)測(cè)適用性較弱。同時(shí)，這些混合方法沒有考慮到移動(dòng)對(duì)象流量變化對(duì)軌跡的影響，不能在任何時(shí)間保持穩(wěn)定的預(yù)測(cè)效果。因此，本文提出GMTSM，對(duì)歷史軌跡數(shù)據(jù)和歷史車流量數(shù)據(jù)分析建模，在保證預(yù)測(cè)準(zhǔn)確性的基礎(chǔ)上，保持預(yù)測(cè)長(zhǎng)期穩(wěn)定性。

2 軌跡預(yù)測(cè)框架

馬爾可夫模型、卡爾曼濾波模型和高斯混合模型都是常用的軌跡預(yù)測(cè)模型。一階馬爾可夫只考慮當(dāng)前軌跡點(diǎn)對(duì)未來軌跡點(diǎn)的影響，不能充分利用歷史軌跡點(diǎn)數(shù)據(jù)，預(yù)測(cè)準(zhǔn)確率比較低;高階馬爾可夫預(yù)測(cè)模型增加了模型計(jì)算復(fù)雜度，不適用于海量軌跡數(shù)據(jù)的訓(xùn)練學(xué)習(xí);卡爾曼濾波對(duì)長(zhǎng)時(shí)間（如10s以上）的軌跡預(yù)測(cè)會(huì)由于預(yù)測(cè)誤差的變大而嚴(yán)重影響預(yù)測(cè)準(zhǔn)確性，并且模型復(fù)雜性增加，僅當(dāng)處理的軌跡數(shù)據(jù)無噪聲點(diǎn)時(shí)預(yù)測(cè)效果比較有效。

高斯混合模型（GMM）是一種基于非參數(shù)的概率模型，對(duì)具有噪聲點(diǎn)的軌跡數(shù)據(jù)預(yù)測(cè)效果較好。概率模型進(jìn)行軌跡預(yù)測(cè)的優(yōu)勢(shì)是：避免了軌跡數(shù)據(jù)離散性質(zhì)的弊端，可以依據(jù)概率模型的精確度評(píng)判模型的預(yù)測(cè)誤差。但是單獨(dú)使用高斯混合模型進(jìn)行軌跡預(yù)測(cè)，解決不了不同時(shí)間點(diǎn)預(yù)測(cè)誤差差別較大的問題。

針對(duì)道路車流量數(shù)據(jù)變化大、隨機(jī)性強(qiáng)、非線性等特點(diǎn)， 采用時(shí)間序列分析中的差分自回歸滑動(dòng)平均模型（ARIMA）對(duì)道路車流量進(jìn)行預(yù)測(cè)。ARIMA模型優(yōu)勢(shì)是對(duì)數(shù)據(jù)序列的形式?jīng)]有限制，訓(xùn)練需要有限的樣本序列，車流量樣本序列具有時(shí)序性和自相關(guān)性，為數(shù)據(jù)建模提供了足夠信息，可以建立高精度的預(yù)測(cè)模型。ARIMA模型解決了交通流量預(yù)測(cè)存在的問題。

GMM是一種概率模型，能根據(jù)不同軌跡概率的比較確定預(yù)測(cè)軌跡;ARIMA則通過對(duì)不同路段車流量的預(yù)測(cè)得到各個(gè)路段車流量的比值，可以轉(zhuǎn)化為車流量概率比。如果將GMM概率值和ARIMA概率值直接相加操作，可以解決不同維度信息不易混合的問題，不會(huì)出現(xiàn)文獻(xiàn)[16]所提到的固定時(shí)間劃分帶來的預(yù)測(cè)不連續(xù)問題;同時(shí)，采用概率模型描述運(yùn)動(dòng)軌跡的方式，可避免軌跡數(shù)據(jù)離散性質(zhì)的弊端，依據(jù)概率模型精度度量概率模型預(yù)測(cè)誤差。

本文提出GMTSM軌跡預(yù)測(cè)模型框架如圖2所示。首先將數(shù)據(jù)通過兩個(gè)單模型訓(xùn)練，分別是迭代網(wǎng)格劃分后的GMM和數(shù)據(jù)平穩(wěn)化后的ARIMA模型;然后通過對(duì)單模型的誤差分析調(diào)整模型權(quán)重，對(duì)模型進(jìn)行加權(quán)融合;最終使用融合后的模型進(jìn)行軌跡預(yù)測(cè)。主要研究?jī)?nèi)容有：1）針對(duì)均勻網(wǎng)格劃分方法容易造成相關(guān)軌跡點(diǎn)分裂和劃分尺度不明確的問題，提出迭代式網(wǎng)格劃分，實(shí)現(xiàn)軌跡點(diǎn)初始聚類，并完成子模型訓(xùn)練學(xué)習(xí)。2）為了避免GMTSM中子模型自身不穩(wěn)定性對(duì)預(yù)測(cè)結(jié)果產(chǎn)生干擾，通過對(duì)子模型的預(yù)測(cè)誤差進(jìn)行分析，計(jì)算子模型的可靠性，動(dòng)態(tài)改變子模型的權(quán)重。

3 軌跡預(yù)測(cè)建模與實(shí)現(xiàn)

軌跡預(yù)測(cè)模型GMTSM首先對(duì)移動(dòng)軌跡數(shù)據(jù)采用迭代網(wǎng)格劃分進(jìn)行軌跡鏈序列化，以便于建模處理;其次進(jìn)行兩個(gè)單模型的訓(xùn)練，分別為GMM和ARIMA模型;然后對(duì)兩個(gè)模型進(jìn)行誤差分析，計(jì)算模型的權(quán)重;最后依據(jù)權(quán)重融合單模型，構(gòu)造預(yù)測(cè)模型。

3.1 迭代網(wǎng)格劃分

移動(dòng)軌跡數(shù)據(jù)具有離散性和數(shù)據(jù)量大的特點(diǎn)，為了實(shí)現(xiàn)軌跡鏈序列化，通常采用均勻網(wǎng)格劃分的方法對(duì)軌跡數(shù)據(jù)進(jìn)行聚類處理。移動(dòng)對(duì)象的相關(guān)軌跡空間被均勻劃分到n×n大小相等的網(wǎng)格中，將映射到網(wǎng)格中的軌跡點(diǎn)連接形成軌跡鏈。但是，均勻網(wǎng)格劃分存在以下兩種問題：1）劃分尺度沒有明確依據(jù)，需要對(duì)軌跡數(shù)據(jù)的采樣頻率、活動(dòng)范圍和運(yùn)動(dòng)速度等因素進(jìn)行分析。2）軌跡數(shù)據(jù)相關(guān)點(diǎn)容易分離到不同網(wǎng)格，造成數(shù)據(jù)分裂問題，增大數(shù)據(jù)分類誤差。如圖3所示，軌跡 TR 1、 TR 2的軌跡點(diǎn)被劃分到不同網(wǎng)格中，得到3個(gè)聚類{C1，C2，C3}。通過計(jì)算歐氏距離判斷兩條軌跡的相似性，原本相似性比較高的軌跡 TR 1、 TR 2在均勻網(wǎng)格劃分下相似性比較低，造成了軌跡相關(guān)點(diǎn)割裂。

迭代網(wǎng)格劃分對(duì)高密度樣本區(qū)域進(jìn)行層次劃分，劃分層次的不斷深入可以提高軌跡點(diǎn)覆蓋網(wǎng)格的精度。迭代式劃分對(duì)樣本分布進(jìn)行高密度的細(xì)分，使網(wǎng)格單元格尺寸得到一個(gè)合適值，實(shí)現(xiàn)單元格數(shù)據(jù)量的均衡，并在劃分的網(wǎng)格上形成軌跡點(diǎn)初始聚類，排除了噪聲數(shù)據(jù)，避免了關(guān)聯(lián)數(shù)據(jù)的割裂問題。如圖4所示。

迭代網(wǎng)格劃分的優(yōu)點(diǎn)是：

1）排除大量離群軌跡點(diǎn)，減少噪聲數(shù)據(jù)干擾。

2）高密度區(qū)域迭代劃分，減少網(wǎng)格數(shù)據(jù)量計(jì)算時(shí)間。

3）迭代劃分結(jié)果使單元格數(shù)據(jù)量達(dá)到均衡狀態(tài)，保證軌跡序列的有效性。

本文提出的迭代網(wǎng)格劃分（Data-Iterative-Grid-Partition， DIGP）算法描述如算法1。

算法1?? DIGP算法。

輸入? 軌跡數(shù)據(jù)集合D;網(wǎng)格劃分初始參數(shù)s;單元格內(nèi)軌跡點(diǎn)數(shù)量閾值num;

輸出? 迭代劃分的網(wǎng)格集合G。

程序前

BE GIN? //移動(dòng)對(duì)象軌跡點(diǎn)被初始化為s×s長(zhǎng)方形

Rects=initial_Partition（D）;

//每一個(gè)分割的長(zhǎng)方形重復(fù)迭代分割{g0，i | 0≤i≤（s×s）}

for each gi in Rects：

N=count_Points（g0，i）;

//計(jì)算g0，i內(nèi)軌跡點(diǎn)

if? N>=num then? //大于或等于閾值num

TmpG=Iterative-Grid-Partition（G，g0，i，num）;

//IGP迭代

G.push（TmpG）;

//在迭代網(wǎng)格分區(qū)集G中添加TmpG

el se

G.push（g0，i）;

//將gi存入G

END

程序后

軌跡空間初始化為s×s個(gè)大小相同的矩形網(wǎng)格，初始劃分得到的網(wǎng)格記為g0，i（0≤i≤（s×s））。通過閾值num判斷單元格是否需要進(jìn)一步劃分，如果網(wǎng)格滿足迭代劃分條件，通過調(diào)用迭代劃分函數(shù)Iterate-Grid-Partition（IGP）實(shí)現(xiàn)遞歸劃分。IGP函數(shù)體現(xiàn)了DIGP“迭代劃分”的特點(diǎn)，它的實(shí)現(xiàn)如下：

算法2? IGP算法。

輸入? 劃分結(jié)果網(wǎng)格G;待劃分單元格gi;單元格內(nèi)軌跡點(diǎn)數(shù)量閾值num;

輸出? 經(jīng)過迭代劃分后的網(wǎng)格集合G。

程序前

BE GIN

for each gi， j in gi

gi+1， j=Partition（gi， j）

//將待劃分的單元格四等分

N=count_Points（gi+1， j）;

//計(jì)算gi+1， j中軌跡點(diǎn)數(shù)

if? N≥num then

Iterate-Grid-Partition（G， gi+1， j， num）;

//遞歸對(duì)gi+1， j進(jìn)行劃分

el se

G.push（gi+1， j）;

END

程序后

其中，參數(shù)gi， j表示一個(gè)網(wǎng)格，i表示劃分次數(shù)， j表示單元格的劃分排序。每次將待劃分的網(wǎng)格進(jìn)行四等分劃分，劃分后的單元格被標(biāo)識(shí)為gi+1， j（0≤j≤3）。

3.2 基于高斯混合模型的訓(xùn)練

高斯混合模型（GMM）是多個(gè)加權(quán)的高斯模型對(duì)樣本概率密度分布進(jìn)行估計(jì)的概率模型，每一個(gè)高斯模型都可以稱為一類或一種模式。聚類過程中數(shù)據(jù)點(diǎn)的生成需要滿足以下條件：

1）每個(gè)軌跡點(diǎn)隨機(jī)來自于歷史軌跡的迭代劃分區(qū)域。

2）軌跡點(diǎn)映射到網(wǎng)格的概率為wi，且滿足∑ m i=1 wi=1，m為單元格個(gè)數(shù)，也是初始聚類的個(gè)數(shù)，m值采用迭代網(wǎng)格劃分算法得到。

為了準(zhǔn)確地描述一條軌跡，將移動(dòng)對(duì)象軌跡數(shù)據(jù)的空間信息按X、Y方向劃分，實(shí)現(xiàn)軌跡線性化。如圖5所示，通過對(duì)X、Y方向分別進(jìn)行建模（螺旋狀線），最后得到軌跡鏈（直線）。

軌跡鏈 S i={（ x i， y i，ti） | 1≤i≤n}的概率由對(duì)X和Y方向特征矢量的高斯概率混合計(jì)算得到，如式（1）和（2）所示：

p（x | λ）=∑ m i=1 ωiGP（ x n | ?μ x，i， Σ x，i）

（1）

p（y | λ）=∑ m i=1 ωiGP（ y n | ?μ y，i， Σ y，i）

（2）

其中：GP（ x n | ?μ x，i， Σ x，i）表示X方向上軌跡特征矢量 x n符合高斯過程的概率函數(shù);Y方向上同理。將軌跡鏈劃分到X、Y方向上的d維矢量表示為 X =（ x 1， x 2，…， x d）T和 Y =（ y 1， y 2，…， y d）T，d是軌跡鏈中軌跡點(diǎn)數(shù)量，概率函數(shù)定義如式（3）和（4）：

GP（ x i | ?μ ， Σ ）=

1? （2π）d | ?Σ ?| ???exp - 1 2 （ x i- μ ）T Σ -1（ x i- μ ）

（3）

GP（ y i | ?μ ， Σ ）=

1? （2π）d | ?Σ ?| ???exp - 1 2 （ y i- μ ）T Σ -1（ y i- μ ）

（4）

其中： x i、? y i分別表示橫坐標(biāo)、縱坐標(biāo)數(shù)據(jù)集合;? μ 、 Σ 表示樣本數(shù)據(jù)在X方向上經(jīng)過高斯過程得到的均值和協(xié)方差矩陣，均值 μ =[E（ x 1）， E（ x 2）， …， E（ x d）]T，協(xié)方差矩陣 Σ =（Cij）d×d，Cij=Cov（ x i， y j）;Y方向上同理。

GMM的聚類問題較為復(fù)雜，本文采用最大期望（Expectation Maximization，EM）方法實(shí)現(xiàn)參數(shù)求解。EM方法中迭代周期分為兩個(gè)步驟，計(jì)算期望（E-step）和最大化（M-step），執(zhí)行迭代直到收斂。對(duì)于軌跡 TR =（ x n， y n），在E-step中，迭代網(wǎng)格劃分得到GMM的初始聚類參數(shù)，第k個(gè)高斯模型在X方向生成的概率公式如式（5）所示，Y方向上同理。

p（i |? x n，λ）= ωip（ x n | i，λ） p（ x n | λ） = ωiGP（ x n | ?μ ?x ，i， Σ x，i） ∑ M k=1 ωkGP（ x n | ?μ x，k， Σ x，k）

（5）

在M-step中，基于E-step計(jì)算出的樣本概率值，通過最大期望方法確定第k個(gè)高斯模型的參數(shù)，如式（6）所示，求出的參數(shù)值作為式（5）的參數(shù)，進(jìn)行下個(gè)迭代周期的計(jì)算，重復(fù)迭代過程直到收斂。

ω′i= 1 T ∑ N n=1 p（i | ?x n，λ）

μ ′i= ∑ N n=1 p（i | ?x n，λ） x n ∑ N n=1 p（i | ?x n，λ）

Σ ′i= ∑ N n=1 p（i | ?x n，λ） x 2n ∑ N n=1 p（i | ?x n，λ） - μ ′2i

（6）

其中：E-step是對(duì)每個(gè)高斯模型參數(shù)的估計(jì);M-step的實(shí)現(xiàn)基于E-step估計(jì)的參數(shù)，M-step得到的值作為E-step中的參數(shù)參與計(jì)算，確定高斯模型參數(shù)，不斷迭代上述步驟，直到參數(shù)波動(dòng)很小，近似達(dá)到極值。

EM方法求解結(jié)果是參數(shù)的極值，與參數(shù)初始值相關(guān)性強(qiáng)，為了獲得合適的求解結(jié)果，提升算法的收斂速度，文獻(xiàn)[7]采用k-means方法獲得求解參數(shù)初值，但是，k-means方法不能根據(jù)數(shù)據(jù)分布情況自動(dòng)確定聚類個(gè)數(shù)，聚類個(gè)數(shù)的選擇對(duì)聚類結(jié)果有較大的影響。針對(duì)上述問題，使用迭代網(wǎng)格劃分的算法對(duì)軌跡進(jìn)行聚類，將聚類結(jié)果作為EM方法的初始值，可以達(dá)到數(shù)據(jù)均衡的效果。

訓(xùn)練數(shù)據(jù)集Dtrain=（ x ， y ）， x 表示輸入數(shù)據(jù)， y 表示輸出數(shù)據(jù)。測(cè)試數(shù)據(jù)集可表示為Dtest=（ x *， y *）， x *表示輸入的測(cè)試數(shù)據(jù)， y *表示輸出的預(yù)測(cè)值。則GMM概率密度函數(shù)如式（7）：

p（ y * | ?y ）=∑ m i=1 Φi（ y ）F（ y ，? μ i， Σ i）

（7）

其中：m是聚類個(gè)數(shù); F（ y * | ?y ，? μ i， Σ i）是模型回歸函數(shù);Φi（ y ）= ωiGP（ y ，? μ iy， Σ iy） ∑ M i=1 ωiGP（ y ，? μ iy， Σ iy） 表示軌跡點(diǎn)所在聚類的權(quán)重;ωi是第i個(gè)高斯權(quán)重，∑ M i=1 ωi=1;? μ i=E[ y * | ?y ]= μ iy*+ Σ iy*y Σ -1iyy（ y - μ iy）表示均值， Σ i= Σ iy*- Σ iy*y Σ -1iy*y Σ iyy*表示方差。

GMM首先對(duì)訓(xùn)練軌跡數(shù)據(jù)進(jìn)行聚類分析;然后通過EM算法獲得模型參數(shù)，符合正態(tài)分布的條件，得到m個(gè)高斯分量回歸函數(shù);最后通過式（7）得到軌跡概率模型。

3.3 基于時(shí)間序列模型的訓(xùn)練

ARIMA模型是差分運(yùn)算與自回歸移動(dòng)平均模型（ARMA）模型的組合，ARMA（p，q）模型適用于平穩(wěn)的時(shí)間序列，而在道路車流量預(yù)測(cè)應(yīng)用中，軌跡數(shù)據(jù)的時(shí)間序列是非平穩(wěn)的，需要通過差分運(yùn)算將非平穩(wěn)時(shí)間序列轉(zhuǎn)化為平穩(wěn)時(shí)間序列。ARMA（p，q）模型與差分運(yùn)算組合形成ARIMA（p，q，r）模型，AR是自回歸，p為自回歸項(xiàng)數(shù);MA為移動(dòng)平均，q為移動(dòng)平均項(xiàng)數(shù);r為時(shí)間序列成為平穩(wěn)時(shí)所作的差分次數(shù)。模型結(jié)構(gòu)如式（8）：

Φ（B）rxt=Θ（B）εt

E（εt）=0; Var（εt）=σ2ε，E（εtεs）=0，s≠t

E（xsεt）=0;s

（8）

記為ARIMA（p，d，r）模型。其中，▽為差分算子，一階差分指序列中連續(xù)相鄰兩項(xiàng)之差，即xt=xt-xt-1; r階差分是對(duì)r-1階差分再進(jìn)行差分運(yùn)算，即rxt=r-1xt-r-1xt-1;B為延遲算子，Φ（B）=1-φ1B-φ2B2-…-φpBp表示p階自回歸系數(shù)多項(xiàng)式;Θ（B）=1-θ1B-θ2B2-…-θqBq表示q階移動(dòng)平均系數(shù)多項(xiàng)式。

當(dāng)ARIMA（p，d，r）模型默認(rèn)q=0時(shí)，避免了參數(shù)求解過程中不確定性識(shí)別的復(fù)雜過程，降低了模型的時(shí)間開銷，因此本文設(shè)定q=0。

路段車流量的預(yù)測(cè)分為下面四個(gè)步驟：

1）從數(shù)據(jù)庫選取短時(shí)的動(dòng)態(tài)車流量數(shù)據(jù)作為樣本序列。

2）通過相關(guān)圖和偏相關(guān)圖對(duì)車流量序列進(jìn)行平穩(wěn)性檢驗(yàn)，對(duì)于非平穩(wěn)性時(shí)間序列，則采用差分方法將原始序列進(jìn)行平穩(wěn)化處理，變?yōu)槠椒€(wěn)序列。

3）對(duì)初步選取的ARIMA（p，d，r）模型進(jìn)行參數(shù)估計(jì)，包括對(duì)參數(shù)的顯著性檢驗(yàn)和隨機(jī)性檢驗(yàn)。本文使用最小二乘法進(jìn)行參數(shù)估計(jì)，利用貝葉斯信息準(zhǔn)則（Bayesian Information Criterion， BIC）進(jìn)行模型階次的確定。準(zhǔn)則BIC的定義為BIC（p）=N lg σ2+p（lg N）/N，其中，N表示訓(xùn)練數(shù)據(jù)的總量;σ2表示模型的方差;p表示模型階次的上限。

4）為了實(shí)現(xiàn)對(duì)車流量的動(dòng)態(tài)預(yù)測(cè)，需要采集實(shí)時(shí)的車流量數(shù)據(jù)并更新數(shù)據(jù)庫，最后重復(fù)步驟1）～3）。

ARIMA模型預(yù)測(cè)流程如圖6所示。

3.4 模型預(yù)測(cè)誤差分析

城市道路交通比較復(fù)雜，用戶路徑的選擇受到上下班高峰期、天氣、節(jié)假日等多種外界因素影響，同時(shí)也受自己主觀意愿影響，任何軌跡預(yù)測(cè)模型都存在預(yù)測(cè)誤差。

定義1? 軌跡預(yù)測(cè)誤差。軌跡預(yù)測(cè)模型將車輛歷史軌跡數(shù)據(jù)集和車流量歷史數(shù)據(jù)集作為輸入，將車輛未來軌跡作為輸出，其中，預(yù)測(cè)的軌跡鏈（虛線）和實(shí)際軌跡鏈（實(shí)線）之間存在的偏離度為預(yù)測(cè)誤差，如圖7所示。

均方根誤差（Root Mean Squared Error， RMSE）用來衡量觀測(cè)值同真實(shí)值之間的偏差，與平均絕對(duì)誤差（Mean Absolute Deviation， MAE）相比，RMSE相當(dāng)于L2范數(shù)，而MAE相當(dāng)于L1范數(shù)，次數(shù)越高，計(jì)算結(jié)果對(duì)于較大值表現(xiàn)越突出，而忽略較小值。

因此，RMSE對(duì)異常值更敏感（即有一個(gè)預(yù)測(cè)值與真實(shí)值相差很大，那么RMSE就會(huì)很大），本文選擇RMSE作為模型的誤差計(jì)算。均方根誤差如式（9），（xi，yi）是真實(shí)軌跡點(diǎn)坐標(biāo)，（x′i，y′i）是預(yù)測(cè)軌跡點(diǎn)坐標(biāo)，N為預(yù)測(cè)的軌跡點(diǎn)數(shù)。

RMSE=? 1 N ∑ N i=1 （x′i-xi）2+（y′i-yi）2

（9）

定義2? 預(yù)測(cè)誤差密度。表示單位時(shí)間內(nèi)偏離度的均方根誤差大小，記為預(yù)測(cè)誤差密度（unit Time Prediction Error Density， TPED）。TPED用于計(jì)算預(yù)測(cè)軌跡與實(shí)際軌跡之間的幾何空間誤差，如式（10）所示，N是軌跡點(diǎn)數(shù)，T是模型開始進(jìn)行回歸學(xué)習(xí)到下一時(shí)刻預(yù)測(cè)結(jié)束所消耗的時(shí)間。

TPED= 1 NT? ∑ N i=1? （x′i-xi）2+（y′i-yi）2

（10）

在給定時(shí)刻t，模型在某一個(gè)軌跡點(diǎn)的失效概率稱為失效分布函數(shù)F（t），該函數(shù)反映了預(yù)測(cè)誤差的趨勢(shì)，如式（11）：

F（t）=∫10 RMSEi T·∑ N i=1 RMSEi? dt

（11）

其中： RMSEi ∑ N i=1 RMSEi 表示某一軌跡點(diǎn)在整個(gè)回歸周期的誤差概率，T表示模型訓(xùn)練的一個(gè)回歸周期，將二者相除，得到失效概率密度分布函數(shù)。通過將失效概率密度分布函數(shù)積分，得到模型在該軌跡點(diǎn)的失效概率分布。

3.5 模型權(quán)重計(jì)算

式（11）定義了模型的誤差分布函數(shù)F（t），它可以呈現(xiàn)模型的預(yù)測(cè)誤差分布，實(shí)現(xiàn)未來模型預(yù)測(cè)誤差的計(jì)算。式（12）引入了模型可靠性R（R表示模型準(zhǔn)確預(yù)測(cè)的概率），在規(guī)定時(shí)間內(nèi)，模型預(yù)測(cè)誤差越小可靠性越大。

R=1-F（t）

（12）

本文通過微軟亞洲研究院T-Driver項(xiàng)目[17-18]的數(shù)據(jù)得出GMM和ARIMA在正常情況和突發(fā)情況（節(jié)假日）下模型可靠性與TPED的關(guān)系，如表1。

從表1可以看出兩種模型的可靠性隨著預(yù)測(cè)誤差的增大而降低，模型可靠性與TPED呈負(fù)相關(guān)關(guān)系。在正常情況下，GMM的可靠性在0.80～0.95，準(zhǔn)確性比較高;在突發(fā)情況下，GMM預(yù)測(cè)誤差變大，可靠性也大幅度減低，只有0.20～0.40，因此GMM在突發(fā)情況下可靠性比較差。ARIMA只是對(duì)車流量的預(yù)測(cè)，在兩種情況下，預(yù)測(cè)誤差變化比較小，可靠性比較穩(wěn)定，保持在0.80～0.95，但時(shí)間序列模型不能實(shí)現(xiàn)對(duì)車輛軌跡的預(yù)測(cè)。為了在兩種情況下實(shí)現(xiàn)準(zhǔn)確的軌跡預(yù)測(cè)，本文將兩種模型進(jìn)行混合，并且通過可靠性動(dòng)態(tài)分配它們的權(quán)重。

本文采用文獻(xiàn)[19]提出的模型相似性，記為SI（Ri，Rj），其中i≠j。Ri、Rj分別是兩種模型的可靠性，DI（Ri，Rj）= | Ri-Rj | 表示不同模型之間可靠性的差異程度，并且SI（Ri，Rj）和DI（Ri，Rj）滿足正態(tài)分布。模型相似性如式（13），可靠性分析結(jié)果之間的距離越大，則兩個(gè)模型的相似度越小。

SI（Ri，Rj）=e-DI（Ri，Rj）

（13）

兩個(gè)模型的相互支持程度可表示為：

A（Mi）= 1 n-1 ∑ n j=1， j≠i SI（Ri，Rj）

（14）

兩個(gè)模型結(jié)果之間的相互支持程度分別作為各模型的動(dòng)態(tài)權(quán)重，可表示為：

ωi= A（Mi） ∑ n i=1 A（Mi）

（15）

本文將GMTSM、GMM和ARIMA三種模型之間的相似度計(jì)算的權(quán)重（式（15）得到的權(quán)重）和GMM、ARIMA兩種子模型可靠性得到的權(quán)重（每個(gè)子模型可靠性與所有子模型可靠性之和的比值）進(jìn)行混合模型可靠性比較。數(shù)據(jù)來源于微軟亞洲研究院T-Driver數(shù)據(jù)，分別在法定節(jié)假日期間采集的三組數(shù)據(jù)集（D1，D2，D3）上進(jìn)行比較，如表2所示。

從表2可以看出，通過計(jì)算GMTSM、GMM和ARIMA三種模型之間的相似度求得子模型權(quán)重比直接通過子模型可靠性得到權(quán)重的混合模型可靠性要高，因此，本文選用三個(gè)模型的相似度進(jìn)行權(quán)重的計(jì)算。

3.6 預(yù)測(cè)模型實(shí)現(xiàn)

高斯混合 時(shí)間序列模型的軌跡概率公式定義式（16）：

p（ x n， y n | λ）=ω′1 （ ∑ m i=1 ωiGP（ x n， y n | ?μ i， Σ i） ） +??? ω′2 （ ∑ m i=1 ωiARIMA（p，d，0） ）

（16）

其中：ω′1+ω′2≠1， S d+1 =f（ S d， S d-1，…， S d-k+1）， S d+1 =f（ S d， S d-1，…， S d-k+1）的值是基于三種模型（GMTSM、GMM和ARIMA）相似度求得，因此子模型的權(quán)重之和不等于1。

GMTSM混合模型采用線性回歸的思想理論對(duì)時(shí)空軌跡數(shù)據(jù)進(jìn)行處理，采用軌跡點(diǎn)迭代的方式進(jìn)行長(zhǎng)距離預(yù)測(cè)。首先，模型輸入當(dāng)前時(shí)刻位置信息進(jìn)行第1步的預(yù)測(cè)，表示為 S d+1 =f（ S d， S d-1，…， S d-k+1）;然后，將第1步預(yù)測(cè)軌跡點(diǎn)存入歷史軌跡數(shù)據(jù)集合，實(shí)現(xiàn)第2步軌跡預(yù)測(cè);依此類推，第n步（d+n位置）預(yù)測(cè)軌跡鏈表示為 S d+n =f（ S d+n-1， S d+n-2，…， S d+n-k）。其中，{ S 1， S 2，…， S d | ?S i=（xi，yi，ti）}為真實(shí)有序的歷史軌跡鏈，k為回歸預(yù)測(cè)過程輸入的歷史軌跡長(zhǎng)度。軌跡位置預(yù)測(cè)需要將上一步預(yù)測(cè)值作為歷史軌跡點(diǎn)數(shù)據(jù)，迭代預(yù)測(cè)移動(dòng)對(duì)象未來位置。GMTSM預(yù)測(cè)流程如圖8所示。

GMTSM通過對(duì)歷史軌跡聚類和建模，進(jìn)行回歸預(yù)測(cè)，將訓(xùn)練數(shù)據(jù)集Dtrain={（xi，yi）}Ni=1=（X，Y）分為Dx={（xi-1，Δxi）}Ni=2和Dy={（yi-1，Δyi）}Ni=2分別處理。已知軌跡位置序列為{x1，x2，…，xd}，GMTSM軌跡預(yù)測(cè)具體工作原理如下：

步驟1? 步驟在X和Y方向?qū)σ苿?dòng)對(duì)象分別進(jìn)行預(yù)測(cè)建模，得到各自軌跡預(yù)測(cè)的回歸函數(shù)f，以X方向?yàn)槔?，表示為xd+1 =f（xd，xd-1，…，xd-k+1）。預(yù)測(cè)下一個(gè)位置點(diǎn)xd+1，其中，xd+1 =fx（x）+εx，d，通過Δx={Δx2，Δx3，…，Δxd}求出下一個(gè)位置增量Δxd+1=xd-xd-1，ε為軌跡噪聲，ε～N（0，σ2），計(jì)算公式如式（17）：

Δxd+1 =fx（Δx）+εx，d

（17）

步驟2? 利用真實(shí)數(shù)據(jù)值x=[x1，x2，…，xd-1]，Δx=[Δx2，Δx3，…，Δxd]，預(yù)測(cè)xd+1=xd+Δxd+1的值，得到d+1位置點(diǎn)在X方向的坐標(biāo)為：xd+1=xd+Δxd+1，得到回歸方程式（18）：

Δxd+1 =fx（Δx）=∑ M i=1 Φi（x）f?? ^?? i（Δx）

（18）

其中：f?? ^?? i（Δx）=Ki（x*，x）（Ki（x，x）+σ2I）-1Δx， Φi（x）= ωiGP（Δx;0，Ki（x，x）） ∑ M i=1 ωiGP（Δx;0，Ki（x，x）） 。

步驟3? 從軌跡鏈 TR ={ S 1， S 2，…， S n}提取部分歷史軌跡{ S 1， S 2，…， S d}，通過回歸方程得到d+1時(shí)刻X和Y方向上的預(yù)測(cè)增量Δxd+1 、Δyd+1 ，得到位置點(diǎn)的預(yù)測(cè)值式（19）：

S d+1 = （xd+1 ，yd+1 ，td+1）=（（xd，Δxd+1 ），（yd+Δyd+1 ），td+1）

（19）

步驟4

通過步驟3得到的第i個(gè)聚類中的 S d+1 的值記為 S d+1 i，利用式（20）比較不同聚類形成的多條預(yù)測(cè)軌跡鏈，選擇概率最大的記為最終軌跡鏈 S d+1，如式（20）：

Sd+1= max{Sd+1 i}=max { ω′1 （ ∑ m i=1 ωiGP（ x n， y n | ?μ i， Σ i） ） +ω′2 （ ∑ m i=1 ωiARIMA（p，d，0） ）}

（20）

本文提出的基于高斯混合 時(shí)間序列模型的軌跡預(yù)測(cè)算法如算法3所示。

算法3? GMTSM算法。

輸入? 訓(xùn)練歷史軌跡數(shù)據(jù)集D;

輸出? 模型預(yù)測(cè)軌跡鏈 S 。

程序前

Be gin

data=ReadFile（filename）;

//獲得歷史軌跡序列

CM=DIGP（D）;

//迭代網(wǎng)格劃分，獲得聚類

set_parameter（ω， μ ， Σ ）;

//混合模型參數(shù)初始化

wh ile（True）：

E_step（CM，ω， μ ， Σ ）;

//EM算法參數(shù)預(yù)計(jì)過程

M_step（CM， ω， μ ， Σ ）;

// EM算法最大化過程

flg=Judge（ω， μ ， Σ ）;

//判斷參數(shù)是否達(dá)到規(guī)定閾值

if （flg）

BREAK;

G=GP（ω， μ ， Σ ，CM）;

//獲得高斯混合模型G

rolmean=Rollmean（N）;

//獲得車流量平均數(shù)

rolstd=Rollstd（N）;

dftest=Adfuller（N， rolstd， rolmean）;

//用adf檢驗(yàn)平穩(wěn)性

dfoutput=Series（dftest[0：4]）;

ts_log=Log（N）

moving_avg=Rollmean（ts_log）;

decomposition=Decompose（N， moving_avg）;

P=ARIMA（N）;

//獲得時(shí)間序列模型P

fo r i in K

//K為預(yù)測(cè)的時(shí)刻數(shù)量

Dω=Train（G，P，i）;

//子模型的權(quán)重訓(xùn)練x

S =predict（G，P， Dω）;

//預(yù)測(cè)軌跡鏈

END

程序后

4 實(shí)驗(yàn)驗(yàn)證和分析

4.1 實(shí)驗(yàn)環(huán)境

本文的實(shí)驗(yàn)數(shù)據(jù)是微軟亞洲研究院T-Driver項(xiàng)目GPS采集的軌跡數(shù)據(jù)，含有2009年北京一萬多輛出租車一周的軌跡數(shù)據(jù)。該數(shù)據(jù)集的軌跡數(shù)據(jù)由一系列時(shí)間戳表示，每個(gè)點(diǎn)包含經(jīng)度、緯度、時(shí)間和車輛編號(hào)信息。實(shí)驗(yàn)過程中，將數(shù)據(jù)分為工作日數(shù)據(jù)組和非工作日數(shù)據(jù)組兩類，D1、D2、D3組為工作日軌跡數(shù)據(jù)，D4、D5、D6組為非工作日軌跡數(shù)據(jù)，實(shí)驗(yàn)中所用的參數(shù)見表3。

為了對(duì)本文提出的GMTSM進(jìn)行性能上的檢驗(yàn)，從三個(gè)條件選擇對(duì)比算法：

1）概率模型。概率模型在軌跡預(yù)測(cè)上具有一定優(yōu)勢(shì)，GMTSM是一種概率模型，通過概率模型之間的對(duì)比分析，可以展示GMTSM的混合優(yōu)勢(shì)。

2）混合模型?；旌夏Ｐ蛯?duì)軌跡預(yù)測(cè)達(dá)到優(yōu)勢(shì)互補(bǔ)的效果，GMTSM是一種混合模型，通過混合模型之間預(yù)測(cè)效果的對(duì)比，可以分析GMTSM將車流量預(yù)測(cè)考慮到軌跡預(yù)測(cè)中產(chǎn)生的效果。

3）非概率、非混合模型。選擇一種與GMTSM不同類型的軌跡預(yù)測(cè)模型，可以檢測(cè)GMTSM子模型選擇的可行性，同時(shí)分析GMTSM預(yù)測(cè)效果的穩(wěn)定性。

實(shí)驗(yàn)部分選取了高斯混合 時(shí)間序列模型（GMTSM）、高斯混合模型（GMM）、貝葉斯網(wǎng)絡(luò)-高斯混合模型（VGMM）和變階隱馬爾可夫模型（VMM）四種模型進(jìn)行對(duì)比分析，分別從預(yù)測(cè)誤差密度、預(yù)測(cè)時(shí)間、抗干擾性分析以及不同時(shí)長(zhǎng)的預(yù)測(cè)四個(gè)方面作對(duì)比分析。

4.2 預(yù)測(cè)誤差密度分析

本節(jié)實(shí)驗(yàn)實(shí)現(xiàn)了四種模型在工作日數(shù)據(jù)組（D1、D2、D3）和非工作日數(shù)據(jù)組（D4、D5、D6）下對(duì)軌跡預(yù)測(cè)誤差密度的對(duì)比分析，每組數(shù)據(jù)包含100～1000條測(cè)試數(shù)據(jù)。實(shí)驗(yàn)對(duì)軌跡預(yù)測(cè)誤差密度進(jìn)行比較，比較結(jié)果如圖9所示。

從圖9得出以下結(jié)論：

1）在工作日數(shù)據(jù)組（D1、D2、D3）下，四種模型的預(yù)測(cè)誤差密度均在25～50m/s，預(yù)測(cè)效果都比較穩(wěn)定。

2）在非工作日數(shù)據(jù)組（D4、D5、D6）下，GMM、VMM和VGMM均出現(xiàn)預(yù)測(cè)誤差密度變幅比較大的現(xiàn)象，誤差密度在60～110m/s，而GMTSM模型的預(yù)測(cè)誤差密度仍保持40m/s左右，相比其他三種模型準(zhǔn)確度平均提高了50%～60%。原因是：非工作日期間，GMM和VGMM只學(xué)習(xí)車輛歷史軌跡數(shù)據(jù)，沒有考慮到因車流量突變情況導(dǎo)致歷史軌跡數(shù)據(jù)的可信度降低;VMM雖然考慮到交通流量的變化，但是通過出租車的相互通信來尋找車輛規(guī)律，提供當(dāng)前交通擁堵情況，不能預(yù)測(cè)所有車輛的軌跡;GMTSM對(duì)歷史軌跡進(jìn)行學(xué)習(xí)，并且對(duì)道路車流量進(jìn)行預(yù)測(cè)，提前預(yù)測(cè)到非工作日道路的車流量情況，動(dòng)態(tài)調(diào)整子模型權(quán)重進(jìn)行線路的概率選取，在道路車流量突變情況下也能準(zhǔn)確預(yù)測(cè)軌跡。

本文同時(shí)給出了在道路維修或新道路啟用等突發(fā)情況下模型的軌跡預(yù)測(cè)情況，如圖10所示。在實(shí)驗(yàn)測(cè)試路段，30s之后進(jìn)入街道維修路段。從圖10可知，在道路維修突發(fā)情況下，GMTSM出現(xiàn)剛開始預(yù)測(cè)誤差密度變大，后來逐漸變小的現(xiàn)象。因?yàn)镚MTSM在模型參數(shù)自動(dòng)更新后，檢測(cè)到某些路段車流量為零的情況時(shí)，會(huì)調(diào)整混合模型中的子模型權(quán)重，按車流量變化的方向進(jìn)行預(yù)測(cè)，并訓(xùn)練最新的歷史軌跡數(shù)據(jù)進(jìn)行重新學(xué)習(xí)，從而降低了預(yù)測(cè)誤差密度。而其他三種模型只是根據(jù)車輛歷史軌跡進(jìn)行預(yù)測(cè)，不能識(shí)別突發(fā)情況信息，導(dǎo)致交通情況的誤判。

4.3 預(yù)測(cè)時(shí)間比較分析

在車輛軌跡預(yù)測(cè)應(yīng)用系統(tǒng)中，軌跡預(yù)測(cè)模型輸出時(shí)間十分重要，為了計(jì)算軌跡預(yù)測(cè)模型的時(shí)間代價(jià)，本節(jié)實(shí)驗(yàn)比較了四種模型在工作日和非工作日不同數(shù)據(jù)組下的時(shí)間消耗。在實(shí)驗(yàn)過程中，模型建立時(shí)間和預(yù)測(cè)時(shí)間單獨(dú)計(jì)算，模型建立時(shí)間是對(duì)子模型的構(gòu)建和混合模型的初始化時(shí)間，不包括軌跡迭代網(wǎng)格劃分的時(shí)間;模型預(yù)測(cè)時(shí)間包括子模型可靠性分析和混合模型預(yù)測(cè)值的輸出時(shí)間。實(shí)驗(yàn)結(jié)果如圖11所示。

從圖11可以得出以下結(jié)論：

1）四種模型預(yù)測(cè)時(shí)間都隨著軌跡數(shù)據(jù)量的增大而增加，在正常線路下，30min內(nèi)車的軌跡條數(shù)在400條左右，四種模型的預(yù)測(cè)時(shí)間消耗均在10s左右，保證了預(yù)測(cè)的實(shí)時(shí)性。

2）不同數(shù)據(jù)組下，GMTSM的時(shí)間消耗比其他三種模型多5s左右，原因在于：GMTSM由兩種子模型混合而成，子模型需要進(jìn)行單獨(dú)預(yù)測(cè)。為了實(shí)現(xiàn)數(shù)據(jù)動(dòng)態(tài)性，需要進(jìn)行模型參數(shù)更新，經(jīng)實(shí)驗(yàn)得出，高斯混合模型為5min更新一次，時(shí)間序列模型每3h更新一次，預(yù)測(cè)準(zhǔn)確性較高。雖然預(yù)測(cè)時(shí)間和軌跡數(shù)量正相關(guān)，但是，相對(duì)于軌跡預(yù)測(cè)準(zhǔn)確性的重要性，消耗的時(shí)間在可接受的范圍內(nèi)。訓(xùn)練數(shù)據(jù)集中最大的訓(xùn)練軌跡數(shù)量為1000條時(shí)，混合模型的建立及軌跡預(yù)測(cè)總時(shí)間為30s，說明GMTSM實(shí)時(shí)性較好。

4.4 抗干擾性分析

GPS采集的數(shù)據(jù)存在噪聲，會(huì)對(duì)軌跡預(yù)測(cè)模型產(chǎn)生干擾。本文選取工作日的軌跡數(shù)據(jù)進(jìn)行抗干擾性分析，結(jié)果如圖12所示。

因?yàn)槌鼼MTSM外的三種模型在非工作日數(shù)據(jù)組下誤差比較高，進(jìn)行抗干擾性分析意義不大，所以只選取工作日數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。

1）在相同的參數(shù)設(shè)置下，GMTSM的預(yù)測(cè)誤差密度比其他三種模型都要低，原因在于：GMTSM對(duì)軌跡點(diǎn)初始化聚類使用了迭代網(wǎng)格劃分，達(dá)到了數(shù)據(jù)量均衡的效果，能降低噪聲數(shù)據(jù)的干擾;同時(shí)GMTSM預(yù)測(cè)模型會(huì)對(duì)道路車流量進(jìn)行預(yù)測(cè)，能減少預(yù)測(cè)誤差、提高預(yù)測(cè)準(zhǔn)確度。

2）在相同軌跡數(shù)據(jù)量下，四種預(yù)測(cè)模型預(yù)測(cè)誤差密度都隨噪聲數(shù)據(jù)比的增大而增大。原因在于：GMTSM、GMM和VGMM需要對(duì)歷史軌跡點(diǎn)進(jìn)行聚類分析，若軌跡數(shù)據(jù)中噪聲數(shù)據(jù)比增加，則有些軌跡點(diǎn)被劃分到距離遠(yuǎn)的聚類中，出現(xiàn)較大的預(yù)測(cè)誤差;而VMM是通過可觀察的參數(shù)推算需要的隱含參數(shù)，當(dāng)噪聲數(shù)據(jù)比重增加時(shí)，對(duì)觀察參數(shù)產(chǎn)生影響，因此對(duì)模型的預(yù)測(cè)誤差密度產(chǎn)生了很大的影響。

[9]?BEST G， FITCH R. Bayesian intention inference for trajectory prediction with an unknown goal destination [C]// Proceedings of the 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway， NJ： IEEE， 2015： 5817-5823.

[10]?SU I， LEI P， SHEN T J， et al. Exploring spatial-temporal trajectory model for location prediction [C]// Proceedings of the 2011 IEEE International Conference on Mobile Data Management. Piscataway， NJ： IEEE， 2011：58-67.

[11]?GAO H J， TANG J L， LIU H. Mobile location prediction in spatio-temporal context [EB/OL]. [2018-05-12]. https：//www.researchgate.net/profile/Huan_Liu6/publication/265437484_Mobile_Location_Prediction_in_Spatio-Temporal_Context/links/551c9ba80cf20d5fbde557eb.pdf.

[12]?JEUNG H， SHEN H， LIU Q， et al. A hybrid prediction model for moving objects [C]// Proceedings of the IEEE 24th International Conference on Data Engineering. Piscataway， NJ： IEEE， 2008：70-79.

[13]?李昇智， 喬建忠， 林樹寬， 等. 基于GPS軌跡數(shù)據(jù)的混合多步Markov位置預(yù)測(cè)[J]. 東北大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017， 38（12）： 1686-1690. （LI S Z， QIAO J Z， LIN S K， et al. Hybrid multi-step Markov location prediction based on GPS trajectory data[J]. Journal of Northeastern University （Natural Science）， 2017， 38（12）： 1686-1690）

[14]?WIEST J， HFFKEN M， KREEL U， et al. Probabilistic trajectory prediction with Gaussian mixture models [C]// Proceedings of the 2012 IEEE Intelligent Vehicles Symposium. Piscataway， NJ： IEEE， 2012：141-146.

[15]?夏卓群， 胡珍珍， 羅君鵬， 等. 不確定環(huán)境下移動(dòng)對(duì)象自適應(yīng)軌跡預(yù)測(cè)方法[J]. 計(jì)算機(jī)研究與發(fā)展， 2017， 54（11）：2434-2444. （XIA Z Q， HU Z Z， LUO J P， et al. Adaptive trajectory prediction for moving objects in uncertain environment [J]. Journal of Computer Research and Development， 2017， 54（11）：2434-2444.）

[16]??BILJECKI F， LEDOUX H， van OOSTEROM P. Transportation? mode-based segmentation and classification of movement trajectories [J]. International Journal of Geographical Information Science， 2013， 27（2）： 385-407.

[17]?WEI Y， ZHENG Y， YANG Q. Transfer knowledge between cities [C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York，： ACM， 2016： 1905-1914.

[18]?ZHENG Y， CAPRA L， WOLFSON O， et al. Urban computing： concepts， methodologies， and applications [J]. ACM Transactions on Intelligent Systems and Technology — Special Section on Urban Computing， 2014， 5（3）： No.38.

[19]?MUSA J D. A theory of software reliability and its application[J]. IEEE Transactions on Software Engineering， 1975， 1（3）： 312-327.