多模式移動對象不確定性軌跡預測模型

喬少杰 韓楠 丁治明 金澈清 孫未未 舒紅平

隨著無線通信和定位技術的高速發展,人們對持續移動物體所處的空間位置的跟蹤能力不斷加強,推動相關應用領域的研究不斷深入,如智能交通控制、智能導航和軍事指揮等.此類應用系統往往基于移動對象數據庫構建,其中存儲了大量關于移動對象時空位置及運動狀態的信息.這些數據通常以軌跡的形式存儲,隱藏著關于移動對象大量的行為特征及運動規律.然而,移動對象所處的運動環境往往是動態變化的,不能單純依賴靜態交通網絡環境預測其運動行為,需要綜合考慮移動速度和方向的動態變化對對象運動行為的影響.如何綜合考慮主客觀因素,高效準確地查詢和預測移動對象不確定性位置成為當前移動數據管理領域的研究熱點[1].尤其值得注意的是,在包含較為復雜的軌跡模式場景下，典型運動模式不止一個,一條軌跡可能隸屬于多個軌跡模式,稱之為多模式.不同類型移動對象運動行為各有差異,相同類型的移動對象由于主客觀因素影響,運動模式也不盡相同,因此挖掘多模式移動對象運動行為特征更具實際意義.

多模式移動對象位置預測是一項非常困難和富有挑戰意義的課題.1)由于移動對象運動模式復雜多變,且通過定位系統獲得的數據流信息量大,具有不確定性,需要更加穩定和具有可伸縮性的挖掘方法進行處理;2)位置預測需要盡可能快地對可能運動軌跡進行評價,延時或滯后將產生無意義的預測結果;3)基于模擬技術的預測方法依賴于大量輸入參數,這些參數的設置極大地影響模型的準確性,對于不確定性的軌跡數據進行預測,需要考慮諸多客觀因素和領域專家知識;4)如果算法設計不合理,隨著移動對象數目的增加,模型的計算代價可能呈指數級增長.下面以移動對象軌跡預測為主要背景,以智能交通系統為例說明問題意義和概貌.

智能交通旨在建立一種在較大范圍內,全方位發揮作用的實時、準確和高效的綜合運輸和管理系統.系統將采集到的各種道路交通及服務信息處理后,傳輸到運輸系統的各種用戶(例如駕駛員、居民、警察),出行者可實時選擇交通方式和交通路線,交通管理部門可進行自動和合理的交通疏導、控制及事故處理.決策者可知每天哪一時段,具體在哪一區域是機動車出行的高峰期,應該采用何種手段可以使路網上的交通流量處于最佳狀態,改善交通擁擠和阻塞狀況,最大限度地提高交通的通行能力,提高整個公路運輸系統的機動性、安全性和運輸效率.可以形式化描述為在一組約束下,確定一組閾值ε和σ,使得

上式(?)意義為求取當各種車輛總和∑Ti＜ε,且保證不同時段j內交通事故發生率Pj＜σ時,各種車輛的數量Num(Ti),并且在測試數據集上支持度超過Supp,置信度超過Conf.其中,ε表示交通運輸能力,σ表示事故發生率門限值.

本文結構如下:第1節對國內外在移動對象不確定性軌跡預測領域的成果進行綜述;第2節針對單一運動模式軌跡,挖掘軌跡熱點區域并利用頻繁模式樹準確高效預測移動對象連續位置信息;第3節介紹一個面向復雜運動場景的基于高斯混合回歸的多模式軌跡預測模型;第4節驗證本文提出的兩種針對不同運動模式的軌跡預測算法的性能;第5章總結全文工作并對未來工作進行展望.

1 國內外研究現狀

針對移動對象的連續位置預測主要包括過去軌跡的重現及當前和未來軌跡的預測,主要研究集中于軌跡頻繁模式挖掘,通過挖掘頻繁模式找出典型運動路徑.Hu等[2]將連續軌跡視為離散狀態點之間轉變的過渡,對軌跡離散狀態分析的不足之處在于對大量時空數據進行離散化處理代價極高,而且需要計算離散數據點之間的相關性.Parker等[3]設計了移動對象運動目標概率函數可以滿足的若干axiom,這些axiom用于精確度量預測軌跡與真實軌跡之間的差異.Song等[4]在Science上發表了預測人類移動性的研究成果,通過測量個體軌跡的信息熵,定量地給出了人類動態運動軌跡具有93%的可預測性,并證明了人類有規律的運動路線與距離無關.Centola[5]在Science上的工作是在原始GPS數據中使用層次型馬爾科夫模型抽取重要地點,進而檢測用戶的行為模式.針對已有軌跡預測算法僅能預測短期內運動路徑的不足,Jeung等[6]提出了一種基于路網的移動預測模型,用于準確計算移動對象在交叉路口運動變換模式和在不同路段上的速度信息,但該方法局限于路網中應用.Zhou等[7]利用動態選取的參考軌跡構建預測模型,模型建立之前目標軌跡是已知的,具備先驗知識,可以基于少量的歷史軌跡構建精準的預測模型.

隨著越來越多不同種類移動對象軌跡數據被收集,近期多模式軌跡預測的工作得到學者的廣泛關注,Pan等[8]提出了基于多變元正態分布的線性預測器,應用這一方法預測會產生延遲,不能應用于交通流的實時監控環境中.Qiao等[9]借助隱馬爾科夫模型(Hidden Markov model,HMM),設計實現了一種可以自適應調整軌跡預測參數的動態預測算法,根據不同類型軌跡數據預測最佳路線,但是這一模型沒有考慮大數據環境下算法的運行時間性能問題.此外,喬少杰等[10]提出了基于隱馬爾科夫模型的自適應軌跡預測模型,該算法通過對大數據環境下移動對象海量軌跡利用基于密度的聚類方法進行位置密度分區和高效分段處理,根據輸入軌跡自動選取參數組合,避免隱馬爾科夫模型中隱狀態不連續、狀態停留等問題.Ding等[11]近期提出了一種路網匹配的基于軌跡數據庫的交通流分析方法,用于預測移動對象位置信息.Xu等[12]提出了用于避免大圖上過度二次計算的有效策略,更好地支持動態路網中路徑動態規劃.為了支持軌跡大數據中個性化多模式運動路徑預測,Dai等[13]利用高斯混合模型,描述行駛偏好矢量中隨機變量的概率分布，構建帶權重的軌跡圖，權重反映對象候選路徑的可能性，并結合最短路徑算法推薦個性化運動軌跡.Tripathy等[14]根據不同對象的歷史軌跡特征,構建線性函數,預測移動對象將來可能運動位置,所提方法可以保證較小的預測偏差.Xu等[15]提出一種通用位置表達模型,定義不同對象可能的位置,實現復雜場景不同運動模式下軌跡預測.黃玉龍等[16]提出了一種改進的高斯近似濾波方法,用于再入飛行器的目標跟蹤.陳成等[17]提出了一種基于四階貝塞爾曲線的無人車可行軌跡規劃算法,用于在實際道路中行駛的車輛.考慮到高緯度和不確定性對軌跡預測準確性的影響,Monfort等[18]提出了一種逆最優控制方法,用于計算人類活動軌跡出現的概率.

通過對上述移動對象軌跡預測工作進行分析,可以得到如下結論:1)如果針對海量軌跡數據挖掘移動對象頻繁軌跡模式,已有算法需要多次掃描數據庫,代價很高,需要設計新型頻繁模式挖掘算法,提高挖掘的效率和準確性.2)現有軌跡預測算法對具有單一簡單模式的移動對象的位置跟蹤預測效果較好,對于復雜場景下多模式軌跡預測的研究內容相對較少.

2 基于頻繁軌跡模式樹的軌跡預測算法

移動對象的運動模式通常比較單一,例如在城市交通道路上勻速運動.針對單一運動模式,本節提出一種基于頻繁模式挖掘的軌跡預測算法[19].

2.1 軌跡熱點區域挖掘算法

在預測前改進DBSCAN算法對海量GPS軌跡點進行聚類挖掘軌跡熱點區域,可以將軌跡點與由信號不穩定等原因產生的噪點區分.軌跡熱點區域挖掘算法RoIDiscovery采用密度聚類思想,通過遍歷每個軌跡點的鄰域生成簇.如果軌跡點p的鄰域內包含多于θ個軌跡點,則創建一個新的簇,將p作為該簇的核心對象.然后,遞歸地遍歷核心對象直接密度可達的對象,這個過程中包含簇的合并操作.當沒有新的點可以被添加到任何簇時,過程結束.基于密度的軌跡熱點區域挖掘算法如算法1所示[19].

算法1.基于密度的軌跡聚類算法

輸入.軌跡數據集Tr,聚簇半徑ε,最少軌跡點數θ.

輸出.聚類后簇集合R={R1,R2,···,Rn}.

1.n=0;

2.foreachp∈Trdo

3.markpas visited;

4.N=getNeighbours(p,ε);

5.ifsize(N)＜ θthen

6.markpas noise;

7.else

8.create a new clusterRk;

9.ExpandCluster(p,N,Rk,ε,θ).

算法1的基本思想為:遍歷Tr中所有軌跡點,初始化簇個數(第1行);將軌跡點p標記為已訪問(第3行);第4～9行利用getNeighbours(·)函數計算軌跡點p與其他軌跡點的距離,將距離小于ε的軌跡點存入集合N中,如果size(N)＜θ,則標記p為噪聲點,否則以p為核心建立新簇,并調用ExpandCluster(·)函數遞歸訪問N中軌跡點.ExpandCluster(·)基本思想是對N鄰域內的所有點進行半徑檢查,如果大于θ,擴展N的數目,將新節點加入擴展后的簇.當沒有新節點可以被添加到任何簇,該過程結束.

2.2 頻繁軌跡模式挖掘算法

本節介紹基于頻繁軌跡模式樹的軌跡預測算法FTP-mining[19],首先給出頻繁軌跡模式樹定義.

定義 1(頻繁軌跡模式樹—FTP-tree)[19].FTP-tree由一個標記為空的根節點及一系列由原子路段組成的前綴子樹構成,且包含一個頭節點表Header table.FTP-tree的數據結構與FP-tree類似,前綴子樹上的每一個節點具有三個屬性:id,count和pointer,其中id表示原子路段的標識,count表示從根節點到達某一節點的路徑被訪問次數,pointer表示指向FTP-tree中具有相同id的下一個節點指針.Header table中每一行記錄包含兩個屬性:節點id和頭指針(指向FTP-tree中具有某id的第一個節點).基于頻繁軌跡模式樹的軌跡預測算法FTP-mining如算法2所示[19].

算法2.FTP-mining( FFF, α)

輸入.具有根節點t的FTP-treeF,與t對應的軌跡熱點路段L,空集合α.

輸出.頻繁軌跡模式集合R={f1,f2,···,fn}.

1.構建一個空的頻繁軌跡模式集合R;

2.if有一條從t出發的路徑Qthen

3.構建一條模式q=Q∪α;

4.support_count=min{counti};//counti表示Q中第i個節點被訪問的次數;

5.Q.add(q);

6.else

7.for each候選項li∈Ldo

8.構建模式p=li∪α;

9.suppor_tcount=min{counti};

10.構建與p對應的conditional pattern base和conditional FTP-treeF0;

11.ifF0nullthen

12.FTP-mining(F0,p);

13.ifR不變化then

14.R.add(p);

15.輸出R中頻繁軌跡模式.

算法2的基本思想為:首先生成長度為1的頻繁序列集;然后根據長度為1的頻繁序列集生成長度為2的頻繁序列集;依此類推,產生所有頻繁序列模式,與FP-tree[20]類似.FTP-mining與FTP-tree的不同之處在于:1)FTP-tree中的項集表示被移動對象訪問的路段,從根節點到葉節點的一條完整的路徑表示一條頻繁軌跡模式;2)每一條前綴樹帶有時間戳信息,時間戳表示訪問一條路段的時間間隔.基于FTP-tree的軌跡預測算法包含FTP-tree構建和FTP-mining兩個步驟,FTP-tree的構建過程與FP-tree的構建相同,不再贅述.FTP-mining算法挖掘頻繁軌跡模式的過程不同于FP-tree,其主要目標是找到大于給定門限值的最長的頻繁路徑,算法2第4～12行計算生成的最長頻繁序列模式沒有考慮路段模式組合的情況,第10行中conditional pattern base是具有相同前綴模式的頻繁路段項子集合.

在上述兩項技術基礎上,給出基于FTP-tree的移動對象軌跡預測算法PathPrediction,如算法3所示[19].

算法3.基于FTP-tree的移動對象軌跡預測算法PathPrediction

輸入.移動對象數據庫D,路網中路段集合S.

輸出.預測軌跡集合Tr.

1.R=RoIDiscovery(D,S);

2.foreach RoIrinRdo

3.Tr=FTPTreeGeneration(r);

4.FTP-mining(Tr,α);

5.輸出最可能運動軌跡集合Tr.

算法3首先利用RoIDiscovery算法從移動對象數據庫D找出熱點區域集合R(第1行).然后,對R中的每個軌跡熱點區域構建FTP-tree(第2行和第3行),并利用FTP-mining計算出頻繁軌跡模式(第4行).最后,輸出所有頻繁軌跡模式(第5行).

3 基于GPR的復雜多模式軌跡預測模型

本節主要解決復雜場景中包含多種運動模式且很難用單一一種運動模式刻畫的復雜運動模式預測問題,首先介紹利用高斯過程回歸模型實現單一運動模式預測,進而引出基于高斯混合回歸的復雜運動模式預測模型.

3.1 高斯過程回歸

一種典型運動模式路徑可以由一個高斯過程表示,利用高斯過程回歸(Gaussian process regression,GPR)[21]進行預測.下面介紹針對簡單運動模式的高斯過程回歸模型的理論基礎.

對于輸入訓練數據集其中xi∈Rd為d維輸入矢量,yi∈R 為相應輸出.對于給定輸入數據集合X,可構成一個隨機變量集合{f(x1),f(x2),···,f(xN)},且具有聯合高斯分布,則該高斯過程(Gaussian process,GP)的全部統計數字特征可由均值函數m(x)和協方差函數k(x,x′) 確定,即

其中,m(x)=E[f(x)],k(x,x′)=E[(f(x)?m(x))×(f(x′)?m(x′))],本文所用核函數為標準指數協方差函數,表示為

其中,θ0為指數權重參數,θ1表示長度規模參數,δij是狄拉克函數,當i=j時,函數δij=1,否則為0.

應用高斯過程回歸的目的是在訓練集輸入數據X和輸出數據Y之間建立映射關系f(·):Rd→R,繼而預測出與新測試輸入數據x?對應最可能的觀測輸出值f(x?),求取回歸估計函數過程如下.

求解過程:由于輸入輸出的觀測和測量數據經常伴隨噪聲數據干擾,因此將噪聲數據考慮進觀測目標值y,建立高斯過程回歸一般模型:y=f(x)+ε.其中,ε為獨立的高斯白噪聲,符合高斯分布,均值為0,方差為σ2,可記為ε～N(0,σ2).由于噪聲ε獨立于f(x),所以當f(x)服從高斯分布時,有限觀測值聯合分布的集合y同樣可形成一個高斯過程,即

其中,協方差函數以矩陣方式表達,即

式中,I表示N×N的單位矩陣,C(X,X)表示N×N協方差矩陣,K(X,X)表示N×N的核函數矩陣,元素Kij=k(xi,xj),K(X,X)表示如下:

K(X?,X)=[k(x?,x1),k(x?,x2),...,k(x?,xn)]表示K(X,X)中某一行,且K(X?,X?)=k(x?,x?).

由于整個高斯過程模型利用多元高斯分布表達數據,根據貝葉斯原理可知,GP在給定訓練集數據Dtrain集合上建立先驗函數,然后在測試數據集下轉變為后驗分布,則訓練數據輸入數據X的輸出向量y和測試數據X?的輸出向量y?之間的聯合高斯密度分布為

為了求取輸出向量y?,需要借助聯合高斯密度回歸定理.

由此可知,當(y,y?)T服從聯合高斯分布時,條件概率p(y?|y)是高斯分布,所以得到y?關于y回歸方程及相應方差如下:根據定理1,可以得到關于預測輸出數據的條件概率P(y?|y)和GP回歸方程,即

其中,K?=K(X?,X),K??=K(X?,X?),于是y?關于y的最佳回歸估計方程,即y?的預測值為

而關于y?的預測不確定性區間用方差表示為

3.2 基于高斯混合回歸的軌跡預測模型

在軌跡包含較為復雜運動模式場景下,需要采用多個高斯過程,利用高斯混合回歸模型(Gaussian mixture regression,GMR)[22]進行軌跡預測分析.

3.2.1 訓練模型

在具有多種軌跡模式的場景中,一條軌跡可能隸屬于多個軌跡模式,準確地刻畫一條軌跡需要采用混合模型.例如,對于軌跡S=〈(x1,y1),(x2,y2),···,(xn,yn)〉,本文將其轉化為X和Y方向上的n維矢量X=(x1,x2,···,xn)T和Y=(y1,y2,···,yn)T,n表示軌跡的觀測點個數,X和Y方向上矢量在所有M個軌跡模式中出現的總概率是由不同運動模式的高斯概率混合而成,表示為

其中,M表示混合軌跡模式的狀態數量,wi表示第i個軌跡模式的權重,且和Σx,i分別表示第i個軌跡模式狀在X方向上的均值和協方差,參數λ={wi,μi,Σi},i=1,2,···,M.GP(Xn|μx,i,Σx,i)表示軌跡矢量Xn相對第i個運動模式狀態的高斯概率函數,定義如下:

其中,μ和Σ表示軌跡高斯過程的典型運動模式在X方向上的均值和協方差矩陣,μ=[E(x1),E(x2),···,E(xd)]T,Σ =(Cij)d×d,Cij=Cov(xi,xj).

于是,對于軌跡訓練集S={X,Y},整個軌跡訓練集高斯混合模型似然函數為

模型中如何計算復雜運動模式中的參數λ是一個關鍵步驟,本文通過使軌跡訓練模型(即式(14)和式(15))概率達到最大,從已知的訓練軌跡矢量集S={X,Y}中學習訓練出最佳參數λ,利用概率最大的方式,使用最大似然法估計(Expectationmaximization,EM),選出構成運動模型的概率密度最大的那一組參數,為軌跡回歸分析預測時所用.

EM 算法在迭代中改善模型參數估計,在每次迭代中不斷地增加模型估計參數λ與觀測訓練軌跡X方向矢量xi(由若干軌跡點構成)的匹配概率,這里討論X軸方向,Y軸方向情況類似,即每次迭代使式(14)滿足p(X|λk+1)＞p(X|λk),其中k表示迭代的次數.通過不斷地學習,獲得最佳匹配訓練軌跡矢量集X={x1,x2,···,xn}.迭代訓練的目的即為找到一組λ,使得p(X|λ)最大,即

由于篇幅限制,求解使p(X|λ)達到最大的參數λ值的過程參見文獻[23].

3.2.2 預測模型

在上一節的基礎上,本節給出基于GMR的軌跡預測模型.已知訓練數據集為S=(x,y),其中輸入數據為x,輸出數據為y.測試數據集S?=(x?,y?), 輸入測試數據為x?, 預測輸出y?, 那么[y,y?]T的聯合概率密度函數遵從如下的GMR模型.

其中并且滿足每個高斯成分GP(·|μi,Σi) 可由式(9)計算出,聯合概率密度函數表示為

其中,除此之外,邊緣密度py和條件密度py?|y可由式(17)和式(18)求得,y的邊緣密度函數為

條件密度函數為

其中混合權重

因此,y?關于y的回歸函數(y?預測值)為

對應的方差為

式(22)稱作高斯混合回歸模型,基于GMR的軌跡預測算法思路即利用式(20)對預測數據概率密度函數建模,應用EM算法估計相應參數,依據正態分布數據的條件分布(參見定理1)得到m個高斯分量回歸函數,利用式(22)將總體回歸函數加權混合實現對整體數據的回歸預測分析.

4 實驗及算法性能分析

4.1 基于FTP-tree的軌跡預測算法性能分析

為了驗證基于FTP-tree的軌跡預測算法預測準確性和時間性能,對Naive算法(沒有采用軌跡熱點區域挖掘RoIDiscovery算法,僅應用FTP-mining算法),PutMode算法[24](基于時間連續貝葉斯網絡的軌跡預測算法)和PathPrediction算法(集成軌跡熱點區域挖掘和FTP-mining算法)進行對比實驗.實驗數據集使用New York,Kansas和Chengdu真實矢量地圖.New York,Kansas和Chengdu地圖分別由435186×563287,348693×437998和23514×25672個像素構成,合成的軌跡數據通過修改Brinkhoff軌跡生成器[25]生成.為了進一步證明算法的真實有效性,實驗使用微軟亞洲研究院GeoLife數據集[26],由182個用戶5年間1129天GPS軌跡數據組成,包含17621條軌跡.

4.1.1 軌跡預測準確性對比

實驗利用預測命中率評價算法的有效性[19].

定義2(預測命中).已知一條軌跡序列S={s1,s2,···,sk},根據S得到的預測軌跡序列為Tp={p1,p2,···,pk},dist(p,q) 表示時空點p和q之間的歐氏距離,θ是一個給定的距離門限值,dist(si,pi)≤θ表明一次軌跡預測命中,預測命中定義為

定義3(預測命中率).已知一條軌跡序列S和預測得到的軌跡序列Tp,預測命中率定義為

其中,|Tp|表示組成Tp軌跡點的數量.

圖1和圖2給出了不同算法隨軌跡數量增加的軌跡預測準確率.其中,橫軸表示軌跡數量,縱軸表示預測準確率.實驗結果表明,融合軌跡熱點區域挖掘和基于FTP-tree的頻繁軌跡模式挖掘方法PathPrediction的預測精度在Chengdu數據集上平均高出PutMode算法8.0個百分點,高出Naive預測算法29.2個百分點,在GeoLife真實數據集上平均高出PutMode算法5.5個百分點,高出Naive預測算法28.9個百分點.原因在于PathPrediction算法對經過聚類后的軌跡熱點區域進行頻繁軌跡模式的挖掘,軌跡熱點區域是由經過噪聲處理后的軌跡點組成的,因此預測的準確性更高.此外,構建的頻繁軌跡模式樹FTP-tree綜合考慮了真實路網中的軌跡運動規則,因此預測的結果與移動對象真實運動情況更加吻合,而PutMode算法融合了軌跡聚類和時間連續貝葉斯網絡,相比于沒有進行軌跡熱點挖掘的Naive算法準確性要高.

圖1 Chengdu數據集下不同算法預測準確率比較Fig.1 Prediction accuracy comparison of different algorithms under Chengdu datasets

圖2 GeoLife數據集下不同算法預測準確率比較Fig.2 Prediction accuracy comparison of different algorithms under GeoLife datasets

4.1.2 軌跡預測時間性能對比

為了驗證本文提出的基于FTP-tree的軌跡預測算法的時間性能,本節實驗在不同的電子地圖(New York,Kansas和Chengdu)上生成軌跡數據集,觀察PathPrediction算法的預測時間,結果如圖3所示.可以發現,不同電子地圖上,隨著生成軌跡數量的增加,PathPrediction算法的運行時間均近似呈線性增長,證明了算法的可伸縮性.

圖3 PathPrediction算法在不同數據集下預測時間比較Fig.3 Prediction time of PathPrediction algorithm under different datasets

為了進一步驗證PathPrediction的時間性能,隨著移動對象數量增加,觀察算法1～3的運行時間,實驗數據集為Chengdu地圖生成的軌跡數據集和GeoLife真實軌跡數據集,結果如圖4和圖5所示.

圖4 Chengdu數據集下不同算法預測時間比較Fig.4 Prediction time comparison of different algorithms under Chengdu datasets

通過圖4和圖5可以發現,PathPrediction算法在所有情況下預測時間均小于PutMode算法,略高于Naive算法.原因在于Naive算法沒有應用軌跡熱點區域挖掘算法,因此預測時間要小于PathPrediction算法.而PutMode算法需要訓練時間連續貝葉斯網絡并構建轉換強度矩陣,該過程非常耗時,時間遠遠高于本文提出的頻繁軌跡模式挖掘算法FTP-mining.此外,可以發現Naive和PathPrediction算法運行時間接近,說明本文提出的軌跡熱點區域挖掘算法時間隨著軌跡數量的增加不會發生巨大變化.

圖5 GeoLife數據集下不同算法預測時間比較Fig.5 Prediction time comparison of different algorithms under GeoLife datasets

4.2 基于高斯混合回歸的軌跡預測算法性能分析

為了驗證本文提出的面向多模式移動對象軌跡預測算法的性能,設計實現了基于高斯混合回歸的軌跡預測算法GMRTP,基于卡爾曼濾波的預測算法Kalman,基于隱馬爾科夫模型(Hidden Markov model,HMM)的軌跡預測算法HMTP[9].其中,Kalman filter[27]是一種應用普遍的回歸預測方法,與本文提出的預測算法的可比性較高.HMTP算法基于HMM模型提取隱狀態和觀察狀態,預測效果較好,通過與其比較,可以充分證明本文算法的性能優勢.

本節比較上述三種算法的準確性和時間性能.實驗數據來源于MIT停車場行駛車輛數據1http://www.ee.cuhk.edu.hk/xgwang/MITtrajsingle.html,收集了40453條真實軌跡.

4.2.1 高斯過程分量的選取

GMRTP算法中高斯過程分量個數M的選取很重要,如果選擇的過程分量過少,算法不能充分地對數據建模,進而對測試軌跡進行準確的預測;選擇的過程分量太多,則會增加軌跡預測時間代價.本節實驗觀察在不同高斯過程分量個數下,不同軌跡輸入長度(即已知軌跡點個數)對預測誤差的影響.

定義4(預測誤差).軌跡預測是將測試軌跡數據集輸入預測模型得到預測輸出軌跡,其中輸入測試軌跡為部分軌跡點的集合,采用均方根誤差(Root mean squared error,RMSE)計算預測軌跡點與實際軌跡點的誤差.

其中,(xi,yi)表示真實位置,表示預測位置,k為預測軌跡點的數量.

實驗中每條觀測軌跡由60個軌跡點構成,已知輸入軌跡點長度分別取10,30,50,對應預測的未來軌跡點數目分別是50,30,10,實驗結果如圖6所示.

圖6 不同高斯過程分量下軌跡預測誤差比較Fig.6 Prediction error comparison with distinct Gaussian regression components

從圖6可以看出:1)在不同高斯過程分量下,當觀測的歷史軌跡輸入點個數越多時(例如observable length=50),算法預測誤差越低.因為預測模型有了更多的歷史軌跡數據點信息,包含更多的運動模式,預測誤差降低.2)GP混合分量個數從1增加到5時,其預測誤差變化較大.當高斯過程分量達到5時,預測誤差收斂.值得注意的是,不同軌跡數據集其運動模式個數不同,因此需要通過實驗探尋最佳的高斯過程分量個數.本節后面實驗內容中GMRTP中高斯過程分量個數均設置為5.

4.2.2 預測準確性分析

本節觀察三種預測算法在訓練軌跡數量為39000條、不同測試集數據規模為100～1000條軌跡下的預測準確性.用預測命中率評價算法的準確性,用預測誤差(RMSE)評價算法的預測精度,實驗結果取每種測試集下所有軌跡預測結果的平均值,如圖7和圖8所示.

從圖7可以看出,相比于其他兩種算法,隨著測試軌跡數量的增加,GMRTP預測誤差最小,一直保持在40m上下波動,相對較長的真實軌跡,預測精度較高且比較穩定.分析實驗結果發現,HMTP預測的平均誤差比GMRTP平均高出5.5m,GMRTP相比Kalman算法,預測誤差平均減少18.6m.原因在于HMTP和Kalman軌跡預測算法對于處理較為簡單運動模式的軌跡預測精度較好,而實驗中采用的數據集中軌跡模式較為復雜且種類繁多,因此預測誤差最大.而基于GMR的模型通用性較好,可以針對不同的多模式軌跡利用高斯過程回歸預測.

圖7 不同算法預測誤差比較Fig.7 Prediction bias comparison of different algorithms

圖8 不同算法預測準確率比較Fig.8 Prediction accuracy comparison of different algorithms

從圖8可以看出,相比HMTP和Kalman算法,GMRTP算法的預測準確率平均提高9.9%和21.2%,且GMRTP比較穩定,準確率維持在90%上下波動.

4.2.3 預測時間性能分析

本節實驗觀察上述三種算法隨著移動對象數量增加的預測時間代價,結果如圖9所示.

從圖9可以看出,GMRTP的預測時間最少,相比HMTP和Kalman算法,平均減少49.3%和11.3%.原因在于Kalman算法對每條軌跡中下一個位置預測都要將前一個位置信息代入回歸分析,當預測的軌跡數量增加時,預測時間近似呈線性增長.而GMRTP預測時利用高斯過程刻畫的軌跡僅需一次性預測即可,因此當預測軌跡數量增加時,只要沒有增加較多的軌跡運動模式,預測時間并不會產生較大的增加和波動.而HMTP算法預測最為耗時,因為其在訓練模型時需對軌跡進行分段處理,并利用HMM模型提取隱狀態和觀察狀態,代價較高.

圖9 不同算法預測時間性能比較Fig.9 Prediction time comparison among different algorithms

4.2.4 單一運動模式軌跡預測準確性對比

為了進一步證明基于高斯過程回歸的軌跡預測算法GMRTP的通用性,本節比較在單一運動模式下,GMRTP和PathPrediction的預測準確性,實驗采用GeoLife數據集,結果如圖10所示.其中,橫軸表示軌跡的數量,縱軸表示預測準確性.

圖10 單一運動模式軌跡預測準確率比較Fig.10 Prediction accuracy comparison beyond single-motion-pattern trajectories

從圖10可以看出,GMRTP算法對具有單一運動模式的軌跡進行預測時仍然具有很高的準確性,當移動對象數量大于2000時,預測準確率在90%以上;且隨著移動對象數量增加,GMRTP均優于本文提出的基于頻繁模式樹的單一模式軌跡預測算法PathPrediction.原因在于GMRTP對軌跡數據利用概率密度函數建模,依據符合正態分布數據的條件分布得到回歸函數完成回歸預測,能夠準確地反應移動對象真實運動行為.

5 總結與展望

多模式移動對象不確定性軌跡預測是移動對象數據庫領域新提出的充滿挑戰性的研究課題,針對當前部分軌跡預測算法精度不高,復雜多模式軌跡預測準確性不高、預測實時性不能保證、預測軌跡長度較短的不足,本文提出一種基于軌跡頻繁模式樹的軌跡預測方法,充分考慮真實路網中的軌跡運動規則,預測結果準確性較高.為了對復雜多模式移動對象位置進行預測,提出了基于高斯過程回歸的多模式軌跡預測模型,算法運行過程中無需設置大量參數,可以通過數據自身利用概率統計分布獲得各種運動模式下的位置信息.

未來工作包括:1)對頻繁模式樹FTP-tree挖掘頻繁項集進一步優化,提高算法的挖掘效率;2)與國內交通部門合作將所提模型應用于卡口攝像頭采集到的交通數據,輔助跟蹤和定位機動車輛和行人(主要針對未裝備GPS定位系統的交通工具);3)為了保證預測的準確性,充分考慮影響對象運動行為的主客觀因素.

References

1 Meng X F,Ding Z M,Xu J J.Moving Objects Management:Models,Techniques and Applications.Berlin:Springer-Verlag,2014.117?131

2 Hu W M,Xiao X J,Fu Z Y,Xie D,Tan T N,Maybank S.A system for learning statistical motion patterns.IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(9):1450?1464

3 Parker A,Subrahmanian V S,Grant J.Fast and accurate prediction of the destination of moving objects.In:Proceedings of the 3rd International Conference on Scalable Uncertainty Management.Berlin,Germany:Springer,2009.180?192

4 Song C M,Qu Z H,Blumm N,Barabási A L.Limits of predictability in human mobility.Science,2010,327(5968):1018?1021

5 Centola D.The spread of behavior in an online social network experiment.Science,2010,329(5996):1194?1197

6 Jeung H,Yiu M L,Zhou X F,Jensen C S.Path prediction and predictive range querying in road network databases.The VLDB Journal,2010,19(4):585?602

7 Zhou J B,Tung A K H,Wu W,Ng W S.A “semi-lazy”approach to probabilistic path prediction in dynamic environments.In:Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2013.748?756

8 Pan T L,Sumalee A,Zhong R X,Indra-payoong N.Shortterm traffic state prediction based on temporal-spatial correlation.IEEE Transactions on Intelligent Transportation Systems,2013,14(3):1242?1254

9 Qiao S J,Shen D Y,Wang X T,Han N,Zhu W.A selfadaptive parameter selection trajectory prediction approach via hidden Markov models.IEEE Transactions on Intelligent Transportation Systems,2015,16(1):284?296

10 Qiao Shao-Jie,Li Tian-Rui,Han Nan,Gao Yun-Jun,Yuan Chang-An,Wang Xiao-Teng,Tang Chang-Jie.Self-adaptive trajectory prediction model for moving objects in big data environment.Journal of Software,2015,26(11):2869?2883(喬少杰,李天瑞,韓楠,高云君,元昌安,王曉騰,唐常杰.大數據環境下移動對象自適應軌跡預測模型.軟件學報,2015,26(11):2869?2883)

11 Ding Z M,Yang B,Güting R H,Li Y G.Network-matched trajectory-based moving-object database:models and applications.IEEE Transactions on Intelligent Transportation Systems,2015,16(4):1918?1928

12 Xu J J,Gao Y J,Liu C F,Zhao L,Ding Z M.Efficient route search on hierarchical dynamic road networks.Distributed and Parallel Databases,2015,33(2):227?252

13 Dai J,Yang B,Guo C J,Ding Z M.Personalized route recommendation using big trajectory data.In:Proceedings of the 31st IEEE International Conference on Data Engineering.Seoul,South Korea:IEEE Computer Society,2015.543?554

14 Tripathy S,Howard C J.Multiple trajectory tracking.Scholarpedia,2012,7(4):Article No.11287

15 Xu J Q,Güting R H.A generic data model for moving objects.Geoinformatica,2013,17(1):125?172

16 Huang Yu-Long,Zhang Yong-Gang,Li Ning,Zhao Lin.An improved Gaussian approximate filtering method.Acta Automatica Sinica,2016,42(3):385?401(黃玉龍,張勇剛,李寧,趙琳.一種改進的高斯近似濾波方法.自動化學報,2016,42(3):385?401)

17 Chen Cheng,He Yu-Qing,Bu Chun-Guang,Han Jian-Da.Feasible trajectory generation for autonomous vehicles based on quartic Bézier curve.Acta Automatica Sinica,2015,41(3):486?496(陳成,何玉慶,卜春光,韓建達.基于四階貝塞爾曲線的無人車可行軌跡規劃.自動化學報,2015,41(3):486?496)

18 Monfort M,Liu A Q,Ziebart B D.Intent prediction and trajectory forecasting via predictive inverse linear-quadratic regulation.In:Proceedings of the 29th AAAI Conference on Arti ficial Intelligence.Austin,Texas,USA:AAAI,2015.3672?3678

19 Qiao S J,Han N,Zhu W,Gutierrez L A.TraPlan:an effective three-in-one trajectory-prediction model in transportation networks.IEEE Transactions on Intelligent Transportation Systems,2015,16(3):1188?1198

20 Han J W,Pei J,Yin Y W,Mao R Y.Mining frequent patterns without candidate generation:a frequent-pattern tree approach.Data Mining and Knowledge Discovery,2004,8(1):53?87

21 Rasmussen C E,Williams C K I.Gaussian Processes for Machine Learning(Adaptive Computation and Machine Learning).Cambridge,USA:The MIT Press,2005.12?22

22 Yu Jian-Bo,Lu Xiao-Lei,Zong Wei-Zhou.Wafer defect detection and recognition based on local and nonlocal linear discriminant analysis and dynamic ensemble of Gaussian mixture models.Acta Automatica Sinica,2016,42(1):47?59(余建波,盧笑蕾,宗衛周.基于局部與非局部線性判別分析和高斯混合模型動態集成的晶圓表面缺陷探測與識別.自動化學報,2016,42(1):47?59)

23 Dellaert F.The Expectation Maximization Algorithm,Technical Report GIT-GVU-02-20,Colleage of Computing,Georgia Institute of Technology,USA,2002.

24 Qiao S J,Tang C J,Jin H D,Long T,Dai S C,Ku Y C,Chau M.PutMode:prediction of uncertain trajectories in moving objects databases.Applied Intelligence,2010,33(3):370?386

25 BrinkhoffT.A framework for generating network-based moving objects.GeoInformatica,2002,6(2):153?180

26 Zheng Y,Xie X,Ma W Y.Geolife:a collaborative social networking service among user,location and trajectory.IEEE Data(base)Engineering Bulletin,2010,33(2):32?40

27 Deng Hu-Bin,Zhang Lei,Wu Ying,Zhou Jie,Liu Feng.Research on track estimation based on Kalman filtering algorithm.Transducer and Microsystem Technologies,2012,31(5):4?7(鄧胡濱,張磊,吳穎,周潔,劉楓.基于卡爾曼濾波算法的軌跡估計研究.傳感器與微系統,2012,31(5):4?7)