基于高斯混合-時間序列模型的軌跡預測

高建 毛鶯池 李志濤

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

關鍵詞：智能交通;迭代網格劃分;軌跡預測;模型可靠性;軌跡相似性

中圖分類號：?TP391.4

文獻標志碼：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 引言

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

在時空軌跡數據挖掘中，對移動對象未來位置預測是當今熱點研究方向之一，有廣闊的應用場景，具體如下：

1）基于位置的推薦。當一名用戶通過社交網絡分享了自己當前的位置，如果軌跡預測模型能夠預測到該用戶將要到達的區域，那么我們可以向該用戶推薦必要信息，如餐飲信息、商場折扣信息等。

2）車輛之間未來軌跡共享，緩解交通堵塞。隨著智能城市的發展，很多城市安裝了監控系統，交通路況被實時記錄下來。軌跡預測模型可以實時預測車輛未來的運行軌跡，交通部門可以預知未來的交通狀況，同時，用戶可以根據其他車輛的預測路線調整自己的路線，起到緩解交通壓力的作用。

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

移動對象未來位置受個人和集體移動模式影響。例如，去上班的路徑選擇主要受個人移動模式影響;去陌生的地方時，采用地圖導航或詢問他人等方式選擇路徑，主要受集體移動模式影響?，F有位置預測方法只采用個人或集體的一種移動模式，具有局限性，沒有考慮到軌跡影響因子（如時間、天氣、季節等）。

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

現有移動對象軌跡預測方法包括貝葉斯推理、馬爾可夫鏈、隱馬爾可夫模型、神經網絡方法以及狀態預測方法。Killijian等[1]考慮到歷史狀態的影響，提出高階的馬爾可夫鏈模型，擴展了馬爾可夫鏈的流動性。李萬高等[2]提出了一種改進的貝葉斯推理算法（Modified Bayesian Inference， MBI），解決了有限的歷史軌跡數據問題，MBI建立的馬爾可夫模型量化了相關的相鄰的位置，劃分歷史軌跡能得到更多精確馬爾可夫模型。

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

本文通過對現有軌跡預測模型的分析，結合道路車流量分析，提出基于高斯混合 時間序列模型（Gauss Mixture Time Series Model， GMTSM）的軌跡預測方法。主要內容有：1）針對均勻網格劃分方法容易造成相關軌跡點分裂問題，提出迭代式網格劃分，實現軌跡點的數量均衡。2）訓練并結合了高斯混合模型（Gaussian Mixture Model， GMM）和時間序列分析中的差分自回歸滑動平均模型（Autoregressive Integrated Moving Average model， ARIMA）。3）為了避免GMTSM混合模型中子模型自身不穩定性對預測結果產生干擾，通過對子模型的預測誤差分析，動態計算子模型的權重。4）通過實驗驗證GMTSM的準確性和穩定性。

1 軌跡預測模型分析

移動對象的軌跡預測需要考慮自身因素、道路車流量因素、時間天氣因素等多種因素?，F有的軌跡預測模型主要分為以下三類：基于運動模型的軌跡預測、基于歷史數據挖掘的軌跡預測和基于混合方法的軌跡預測。

1.1 基于運動模型的軌跡預測

移動對象的運動信息包括運動速度、運動方向和運動時間等。很多模型通過構造線性運動函數預測移動對象的運動信息。線性模型雖然高效，但不符合現實生活中移動對象非線性運動情況，導致預測誤差大。若通過不斷更新移動對象運動信息的方法降低預測誤差，模型預測效率會下降。因此，線性模型軌跡預測不適合實際應用。

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

1.2 基于歷史數據挖掘的軌跡預測

基于運動模型的預測方法是建立線性或非線性函數進行預測，但預測誤差大、預測時間短，考慮到運動模型沒有充分用到移動對象的歷史數據，基于歷史軌跡數據的預測算法被提出。通過對歷史軌跡數據的學習，觀察移動對象頻繁活動區域，挖掘數據隱含的規律。

基于歷史數據的軌跡預測方法有貝葉斯網絡、隱馬爾可夫模型、神經網絡以及高斯混合模型等。喬少杰等[7]在多種運動形式下建立GMM來實現移動對象復雜運動形式下的概率分布進行軌跡預測;同時，喬少杰等[8]還提出了基于隱馬爾可夫模型的自適應軌跡預測模型，通過發現不連續的隱藏狀態進行長期的軌跡預測。

Best等[9]提出了貝葉斯預測模型實現對人體運動的預測，但不適合快速移動對象預測。Xue等[3]提出了變階的馬爾可夫模型（Variable-order Markov Model， VMM），利用車輛互聯的關系對車輛網絡數據進行分析，挖掘車輛之間的移動模式;但只是對交通狀況信息的獲取，不能針對車輛使用者作出軌跡預測。

移動軌跡數據包含空間信息和時間信息，Lei等[10]通過獲取移動對象在空間和時間上的運動行為建立時空軌跡模型，該模型建立軌跡后綴樹，樹上每個節點記錄了下一個位置的空間信息和時間信息，實現了空間位置的預測，同時預測預定時間到達的概率。Gao等[11]充分考慮時間信息對軌跡的影響，使用貝葉斯公式進行位置點預測，實驗結果顯示，時間信息的引入可以提高預測準確性。

1.3 基于混合方法的軌跡預測

不同移動對象表現的運動規律性不完全相同，隨著時間的變化，同一個移動對象在不同時間段內的運動模式也存在差別。同時，由于移動對象具有獨特的生活方式和訪問偏好，對歷史位置的訪問呈現冪律分布現象，只有少量位置被頻繁訪問，大多數位置訪問次數稀少。針對不同移動對象、不同時間段以及不同位置需要混合多種預測方法進行預測。

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

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

2 軌跡預測框架

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

高斯混合模型（GMM）是一種基于非參數的概率模型，對具有噪聲點的軌跡數據預測效果較好。概率模型進行軌跡預測的優勢是：避免了軌跡數據離散性質的弊端，可以依據概率模型的精確度評判模型的預測誤差。但是單獨使用高斯混合模型進行軌跡預測，解決不了不同時間點預測誤差差別較大的問題。

針對道路車流量數據變化大、隨機性強、非線性等特點， 采用時間序列分析中的差分自回歸滑動平均模型（ARIMA）對道路車流量進行預測。ARIMA模型優勢是對數據序列的形式沒有限制，訓練需要有限的樣本序列，車流量樣本序列具有時序性和自相關性，為數據建模提供了足夠信息，可以建立高精度的預測模型。ARIMA模型解決了交通流量預測存在的問題。

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

本文提出GMTSM軌跡預測模型框架如圖2所示。首先將數據通過兩個單模型訓練，分別是迭代網格劃分后的GMM和數據平穩化后的ARIMA模型;然后通過對單模型的誤差分析調整模型權重，對模型進行加權融合;最終使用融合后的模型進行軌跡預測。主要研究內容有：1）針對均勻網格劃分方法容易造成相關軌跡點分裂和劃分尺度不明確的問題，提出迭代式網格劃分，實現軌跡點初始聚類，并完成子模型訓練學習。2）為了避免GMTSM中子模型自身不穩定性對預測結果產生干擾，通過對子模型的預測誤差進行分析，計算子模型的可靠性，動態改變子模型的權重。

3 軌跡預測建模與實現

軌跡預測模型GMTSM首先對移動軌跡數據采用迭代網格劃分進行軌跡鏈序列化，以便于建模處理;其次進行兩個單模型的訓練，分別為GMM和ARIMA模型;然后對兩個模型進行誤差分析，計算模型的權重;最后依據權重融合單模型，構造預測模型。

3.1 迭代網格劃分

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

迭代網格劃分對高密度樣本區域進行層次劃分，劃分層次的不斷深入可以提高軌跡點覆蓋網格的精度。迭代式劃分對樣本分布進行高密度的細分，使網格單元格尺寸得到一個合適值，實現單元格數據量的均衡，并在劃分的網格上形成軌跡點初始聚類，排除了噪聲數據，避免了關聯數據的割裂問題。如圖4所示。

迭代網格劃分的優點是：

1）排除大量離群軌跡點，減少噪聲數據干擾。

2）高密度區域迭代劃分，減少網格數據量計算時間。

3）迭代劃分結果使單元格數據量達到均衡狀態，保證軌跡序列的有效性。

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

算法1?? DIGP算法。

輸入? 軌跡數據集合D;網格劃分初始參數s;單元格內軌跡點數量閾值num;

輸出? 迭代劃分的網格集合G。

程序前

BE GIN? //移動對象軌跡點被初始化為s×s長方形

Rects=initial_Partition（D）;

//每一個分割的長方形重復迭代分割{g0，i | 0≤i≤（s×s）}

for each gi in Rects：

N=count_Points（g0，i）;

//計算g0，i內軌跡點

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

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

//IGP迭代

G.push（TmpG）;

//在迭代網格分區集G中添加TmpG

el se

G.push（g0，i）;

//將gi存入G

END

程序后

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

算法2? IGP算法。

輸入? 劃分結果網格G;待劃分單元格gi;單元格內軌跡點數量閾值num;

輸出? 經過迭代劃分后的網格集合G。

程序前

BE GIN

for each gi， j in gi

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

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

N=count_Points（gi+1， j）;

//計算gi+1， j中軌跡點數

if? N≥num then

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

//遞歸對gi+1， j進行劃分

el se

G.push（gi+1， j）;

END

程序后

其中，參數gi， j表示一個網格，i表示劃分次數， j表示單元格的劃分排序。每次將待劃分的網格進行四等分劃分，劃分后的單元格被標識為gi+1， j（0≤j≤3）。

3.2 基于高斯混合模型的訓練

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

1）每個軌跡點隨機來自于歷史軌跡的迭代劃分區域。

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

為了準確地描述一條軌跡，將移動對象軌跡數據的空間信息按X、Y方向劃分，實現軌跡線性化。如圖5所示，通過對X、Y方向分別進行建模（螺旋狀線），最后得到軌跡鏈（直線）。

軌跡鏈 S i={（ x i， y i，ti） | 1≤i≤n}的概率由對X和Y方向特征矢量的高斯概率混合計算得到，如式（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符合高斯過程的概率函數;Y方向上同理。將軌跡鏈劃分到X、Y方向上的d維矢量表示為 X =（ x 1， x 2，…， x d）T和 Y =（ y 1， y 2，…， y d）T，d是軌跡鏈中軌跡點數量，概率函數定義如式（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分別表示橫坐標、縱坐標數據集合;? μ 、 Σ 表示樣本數據在X方向上經過高斯過程得到的均值和協方差矩陣，均值 μ =[E（ x 1）， E（ x 2）， …， E（ x d）]T，協方差矩陣 Σ =（Cij）d×d，Cij=Cov（ x i， y j）;Y方向上同理。

GMM的聚類問題較為復雜，本文采用最大期望（Expectation Maximization，EM）方法實現參數求解。EM方法中迭代周期分為兩個步驟，計算期望（E-step）和最大化（M-step），執行迭代直到收斂。對于軌跡 TR =（ x n， y n），在E-step中，迭代網格劃分得到GMM的初始聚類參數，第k個高斯模型在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計算出的樣本概率值，通過最大期望方法確定第k個高斯模型的參數，如式（6）所示，求出的參數值作為式（5）的參數，進行下個迭代周期的計算，重復迭代過程直到收斂。

ω′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是對每個高斯模型參數的估計;M-step的實現基于E-step估計的參數，M-step得到的值作為E-step中的參數參與計算，確定高斯模型參數，不斷迭代上述步驟，直到參數波動很小，近似達到極值。

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

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

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

（7）

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

GMM首先對訓練軌跡數據進行聚類分析;然后通過EM算法獲得模型參數，符合正態分布的條件，得到m個高斯分量回歸函數;最后通過式（7）得到軌跡概率模型。

3.3 基于時間序列模型的訓練

ARIMA模型是差分運算與自回歸移動平均模型（ARMA）模型的組合，ARMA（p，q）模型適用于平穩的時間序列，而在道路車流量預測應用中，軌跡數據的時間序列是非平穩的，需要通過差分運算將非平穩時間序列轉化為平穩時間序列。ARMA（p，q）模型與差分運算組合形成ARIMA（p，q，r）模型，AR是自回歸，p為自回歸項數;MA為移動平均，q為移動平均項數;r為時間序列成為平穩時所作的差分次數。模型結構如式（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）模型。其中，▽為差分算子，一階差分指序列中連續相鄰兩項之差，即xt=xt-xt-1; r階差分是對r-1階差分再進行差分運算，即rxt=r-1xt-r-1xt-1;B為延遲算子，Φ（B）=1-φ1B-φ2B2-…-φpBp表示p階自回歸系數多項式;Θ（B）=1-θ1B-θ2B2-…-θqBq表示q階移動平均系數多項式。

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

路段車流量的預測分為下面四個步驟：

1）從數據庫選取短時的動態車流量數據作為樣本序列。

2）通過相關圖和偏相關圖對車流量序列進行平穩性檢驗，對于非平穩性時間序列，則采用差分方法將原始序列進行平穩化處理，變為平穩序列。

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

4）為了實現對車流量的動態預測，需要采集實時的車流量數據并更新數據庫，最后重復步驟1）～3）。

ARIMA模型預測流程如圖6所示。

3.4 模型預測誤差分析

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

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

均方根誤差（Root Mean Squared Error， RMSE）用來衡量觀測值同真實值之間的偏差，與平均絕對誤差（Mean Absolute Deviation， MAE）相比，RMSE相當于L2范數，而MAE相當于L1范數，次數越高，計算結果對于較大值表現越突出，而忽略較小值。

因此，RMSE對異常值更敏感（即有一個預測值與真實值相差很大，那么RMSE就會很大），本文選擇RMSE作為模型的誤差計算。均方根誤差如式（9），（xi，yi）是真實軌跡點坐標，（x′i，y′i）是預測軌跡點坐標，N為預測的軌跡點數。

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

（9）

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

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

（10）

在給定時刻t，模型在某一個軌跡點的失效概率稱為失效分布函數F（t），該函數反映了預測誤差的趨勢，如式（11）：

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

（11）

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

3.5 模型權重計算

式（11）定義了模型的誤差分布函數F（t），它可以呈現模型的預測誤差分布，實現未來模型預測誤差的計算。式（12）引入了模型可靠性R（R表示模型準確預測的概率），在規定時間內，模型預測誤差越小可靠性越大。

R=1-F（t）

（12）

本文通過微軟亞洲研究院T-Driver項目[17-18]的數據得出GMM和ARIMA在正常情況和突發情況（節假日）下模型可靠性與TPED的關系，如表1。

從表1可以看出兩種模型的可靠性隨著預測誤差的增大而降低，模型可靠性與TPED呈負相關關系。在正常情況下，GMM的可靠性在0.80～0.95，準確性比較高;在突發情況下，GMM預測誤差變大，可靠性也大幅度減低，只有0.20～0.40，因此GMM在突發情況下可靠性比較差。ARIMA只是對車流量的預測，在兩種情況下，預測誤差變化比較小，可靠性比較穩定，保持在0.80～0.95，但時間序列模型不能實現對車輛軌跡的預測。為了在兩種情況下實現準確的軌跡預測，本文將兩種模型進行混合，并且通過可靠性動態分配它們的權重。

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

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

（13）

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

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

（14）

兩個模型結果之間的相互支持程度分別作為各模型的動態權重，可表示為：

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

（15）

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

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

3.6 預測模型實現

高斯混合 時間序列模型的軌跡概率公式定義式（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）相似度求得，因此子模型的權重之和不等于1。

GMTSM混合模型采用線性回歸的思想理論對時空軌跡數據進行處理，采用軌跡點迭代的方式進行長距離預測。首先，模型輸入當前時刻位置信息進行第1步的預測，表示為 S d+1 =f（ S d， S d-1，…， S d-k+1）;然后，將第1步預測軌跡點存入歷史軌跡數據集合，實現第2步軌跡預測;依此類推，第n步（d+n位置）預測軌跡鏈表示為 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）}為真實有序的歷史軌跡鏈，k為回歸預測過程輸入的歷史軌跡長度。軌跡位置預測需要將上一步預測值作為歷史軌跡點數據，迭代預測移動對象未來位置。GMTSM預測流程如圖8所示。

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

步驟1? 步驟在X和Y方向對移動對象分別進行預測建模，得到各自軌跡預測的回歸函數f，以X方向為例，表示為xd+1 =f（xd，xd-1，…，xd-k+1）。預測下一個位置點xd+1，其中，xd+1 =fx（x）+εx，d，通過Δx={Δx2，Δx3，…，Δxd}求出下一個位置增量Δxd+1=xd-xd-1，ε為軌跡噪聲，ε～N（0，σ2），計算公式如式（17）：

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

（17）

步驟2? 利用真實數據值x=[x1，x2，…，xd-1]，Δx=[Δx2，Δx3，…，Δxd]，預測xd+1=xd+Δxd+1的值，得到d+1位置點在X方向的坐標為：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時刻X和Y方向上的預測增量Δxd+1 、Δyd+1 ，得到位置點的預測值式（19）：

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

（19）

步驟4

通過步驟3得到的第i個聚類中的 S d+1 的值記為 S d+1 i，利用式（20）比較不同聚類形成的多條預測軌跡鏈，選擇概率最大的記為最終軌跡鏈 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）

本文提出的基于高斯混合 時間序列模型的軌跡預測算法如算法3所示。

算法3? GMTSM算法。

輸入? 訓練歷史軌跡數據集D;

輸出? 模型預測軌跡鏈 S 。

程序前

Be gin

data=ReadFile（filename）;

//獲得歷史軌跡序列

CM=DIGP（D）;

//迭代網格劃分，獲得聚類

set_parameter（ω， μ ， Σ ）;

//混合模型參數初始化

wh ile（True）：

E_step（CM，ω， μ ， Σ ）;

//EM算法參數預計過程

M_step（CM， ω， μ ， Σ ）;

// EM算法最大化過程

flg=Judge（ω， μ ， Σ ）;

//判斷參數是否達到規定閾值

if （flg）

BREAK;

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

//獲得高斯混合模型G

rolmean=Rollmean（N）;

//獲得車流量平均數

rolstd=Rollstd（N）;

dftest=Adfuller（N， rolstd， rolmean）;

//用adf檢驗平穩性

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

ts_log=Log（N）

moving_avg=Rollmean（ts_log）;

decomposition=Decompose（N， moving_avg）;

P=ARIMA（N）;

//獲得時間序列模型P

fo r i in K

//K為預測的時刻數量

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

//子模型的權重訓練x

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

//預測軌跡鏈

END

程序后

4 實驗驗證和分析

4.1 實驗環境

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

為了對本文提出的GMTSM進行性能上的檢驗，從三個條件選擇對比算法：

1）概率模型。概率模型在軌跡預測上具有一定優勢，GMTSM是一種概率模型，通過概率模型之間的對比分析，可以展示GMTSM的混合優勢。

2）混合模型?；旌夏Ｐ蛯壽E預測達到優勢互補的效果，GMTSM是一種混合模型，通過混合模型之間預測效果的對比，可以分析GMTSM將車流量預測考慮到軌跡預測中產生的效果。

3）非概率、非混合模型。選擇一種與GMTSM不同類型的軌跡預測模型，可以檢測GMTSM子模型選擇的可行性，同時分析GMTSM預測效果的穩定性。

實驗部分選取了高斯混合 時間序列模型（GMTSM）、高斯混合模型（GMM）、貝葉斯網絡-高斯混合模型（VGMM）和變階隱馬爾可夫模型（VMM）四種模型進行對比分析，分別從預測誤差密度、預測時間、抗干擾性分析以及不同時長的預測四個方面作對比分析。

4.2 預測誤差密度分析

本節實驗實現了四種模型在工作日數據組（D1、D2、D3）和非工作日數據組（D4、D5、D6）下對軌跡預測誤差密度的對比分析，每組數據包含100～1000條測試數據。實驗對軌跡預測誤差密度進行比較，比較結果如圖9所示。

從圖9得出以下結論：

1）在工作日數據組（D1、D2、D3）下，四種模型的預測誤差密度均在25～50m/s，預測效果都比較穩定。

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

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

4.3 預測時間比較分析

在車輛軌跡預測應用系統中，軌跡預測模型輸出時間十分重要，為了計算軌跡預測模型的時間代價，本節實驗比較了四種模型在工作日和非工作日不同數據組下的時間消耗。在實驗過程中，模型建立時間和預測時間單獨計算，模型建立時間是對子模型的構建和混合模型的初始化時間，不包括軌跡迭代網格劃分的時間;模型預測時間包括子模型可靠性分析和混合模型預測值的輸出時間。實驗結果如圖11所示。

從圖11可以得出以下結論：

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

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

4.4 抗干擾性分析

GPS采集的數據存在噪聲，會對軌跡預測模型產生干擾。本文選取工作日的軌跡數據進行抗干擾性分析，結果如圖12所示。

因為除GMTSM外的三種模型在非工作日數據組下誤差比較高，進行抗干擾性分析意義不大，所以只選取工作日數據進行實驗。

1）在相同的參數設置下，GMTSM的預測誤差密度比其他三種模型都要低，原因在于：GMTSM對軌跡點初始化聚類使用了迭代網格劃分，達到了數據量均衡的效果，能降低噪聲數據的干擾;同時GMTSM預測模型會對道路車流量進行預測，能減少預測誤差、提高預測準確度。

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

[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軌跡數據的混合多步Markov位置預測[J]. 東北大學學報（自然科學版）， 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]?夏卓群， 胡珍珍， 羅君鵬， 等. 不確定環境下移動對象自適應軌跡預測方法[J]. 計算機研究與發展， 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.