多維空間中基于模式的移動對象軌跡預測①

章夢杰,邵培南,于銘華

(中國電子科技集團公司第三十二研究所,上海 201800)

近些年來,隨著機器學習等相關技術的廣泛使用,人們對不確定性事件的預測也變得更加精確.現代戰爭中,能否準確地預測敵方目標的活動從而快速定位敵方目標是取得戰爭勝利的關鍵.

在對移動對象軌跡的研究中,移動對象大致可以分為兩種類型:運動道路非受限的移動對象(如飛機、艦船)和運動道路受限的移動對象(如城市道路中的車輛或人)[1-3].一般來說,對移動對象的軌跡進行預測主要包括三個方面:重現歷史軌跡、實時軌跡和未來軌跡的預測,其中移動對象未來軌跡預測方法主要分為基于歐式空間的軌跡預測和基于路網受限的軌跡預測.目前,對移動目標軌跡預測的研究方法主要有以下幾種:文獻[4]提出了基于曲線擬合技術對目標軌跡預測,此方法首先由人工圈出要跟蹤的移動目標,然后利用其歷史軌跡點數據對其以后目標位置進行預測,該方法每進行一個目標位置的預測就要進行曲線擬合,運算量很大,而且擬合函數的多項式次數難以確定;文獻[5]提出了利用卡爾曼濾波預測船舶航行軌跡,卡爾曼濾波是以最小均方誤差估計的最佳準則,來尋求一套遞推估計的算法,但該方法只考慮到當前目標位置對預測目標位置的影響,所以得到的預測位置不夠精確;文獻[6]提出了基于神經網絡的預測方法,該方法利用遺傳算法對BP神經網絡的參數進行優化,在此基礎上進行的目標軌跡預測,該算法同樣存在網絡訓練頻繁和運算時間長等問題.基于此,本文提出了一種新的軌跡預測方法來對道路非受限的移動對象軌跡進行預測.

現如今,研究人員主要通過挖掘移動對象軌跡的頻繁模式,然后通過各頻繁模式組合來進行移動對象軌跡的預測[7-9].然而現有的相關研究大都是基于路網受限的軌跡預測[10],而對非受限空間的軌跡預測的相關研究還比較少.本文所采用的方法就是對非受限空間中移動對象軌跡的預測,通過對軌跡的相關屬性預測來實現對軌跡的預測.具體來說,主要對以下三個方面進行研究分析:首先對移動對象歷史軌跡進行聚類分析[11],分類出不同的軌跡訓練集;然后根據聚類后的軌跡訓練集采用多核并行技術建立移動對象加速度和軌跡偏轉角的頻繁模式;最后通過對移動對象加速度和軌跡偏轉角的預測來實現移動對象軌跡的預測.

1 基本概念及模型框架

本節首先對所使用的軌跡數據結構進行簡要說明,然后介紹本文所提出模型的框架及工作原理.

描述移動對象時空軌跡的數據庫D,該數據庫中存放著移動對象不同時間序列的位置信息,其中位置點信息由來表示,位置點在一定時間的有序集合構成了一條完整的目標軌跡,由來表示.

下面對本研究中所使用的移動對象的軌跡數據集作如下說明.

說明2.軌跡數據集.在多維空間進行建模,軌跡數據集表示為:其中tr1代表其中一條軌跡.

說明3.加速度計算.本文中由于移動對象軌跡上的位置點的時間間隔較小,高速巡航的移動目標的速度基本保持不變,為了方便計算,我們假設相鄰位置點之間移動對象的運動為勻加速運動.由于位置點信息中已經包括了移動對象的當前速度,所以計算兩點之間的加速度可以用相鄰位置點之間的速度差和時間差的比值表示.加速度A的計算公式如下所示:

說明4.偏轉角計算.偏轉角表示移動對象在當前位置點向下一位置點運動的方向角.

如圖1所示,已知點p1,p2,p3表示移動對象的三個連續的位置點,直線p1p2與直線p2p3所構成的夾角稱為開放角,它的補角稱為偏轉角,即為位置點p2的偏轉角.可以利用三個連續位置點來計算出相應子軌跡的偏轉角α.求取偏轉角α的公式如下所示:

圖1 軌跡的偏向角和開放角

說明5.特征點提取.如果移動對象在某一位置點的偏轉角大于一定閾值則該位置點就是軌跡的特征點.移動對象軌跡數據是通過相隔固定時間采集得到的時間序列位置點,所以一條軌跡是由大量的時間序列的位置信息點.其中有很多冗余的位置點,例如一條直線子軌跡上的多個點都是冗余的.所以在訓練模式之前需要對特征點進行提取.

說明6.軌跡聚類.聚類是數據挖掘過程中最常用和最重要的技術手段之一,該技術能從海量的軌跡數據中挖掘出精簡而有用的信息.本文中的原始數據的軌跡形狀多種多樣,例如圓形軌跡,拋物線軌跡,直線軌跡等等,聚類的任務就是根據數據之間的相似性將相似數據組合在一起.其中相似的對象構成的組被稱為簇(Cluster),同一個簇中的對象彼此相似,不同的簇中的對象彼此相異.軌跡聚類可以去除噪聲數據,提高算法的準確性,提高算法的時間性能.本研究在度量軌跡相似性時只考慮軌跡的空間屬性.

本文所提出模型的具體流程如圖2所示,其工作原理如下.

利用轉向角篩選算法和最小描述長度算法對軌跡集進行特征點篩選.

利用軌跡聚類算法對軌跡集進行軌跡聚類,分類出若干個軌跡訓練集.

采用多核并行技術根據得出的軌跡訓練集進行加速度和偏向角的模型訓練,分別建立基于軌跡的加速度和轉向角的頻繁模式的預測模型.

利用相似度比較,結合歷史軌跡以及移動對象加速度和軌跡偏轉角的預測模型進行目標移動對象軌跡預測.

圖2 系統模型框架圖

歷史軌跡數據庫:過去采集到的歷史軌跡數據作為結構化數據存放在Mysql數據庫.實時的新到移動對象軌跡數據,經過清洗后也將存入歷史軌跡數據庫中.

軌跡預測模型訓練服務器:該節點會從歷史軌跡數據庫中獲取軌跡數據,對不同運動模式軌跡數據進行初步聚類分析.在此基礎上,采用多核并行迭代訓練生成加速度和偏轉角的頻繁模式的預測模型.

軌跡預測及web服務器:新的軌跡數據進來(仍然是通過結構化數據接口),經過清洗后流入該節點的軌跡預測模塊,它使用訓練好的預測模型,預測未來連續一段時間的軌跡點,并計算每步的預測誤差.同時該節點還提供web服務功能,使得用戶可以通過互聯網在瀏覽器端進行多活動目標的軌跡管理與軌跡監察.

2 生成訓練集

2.1 軌跡特征點選取

在采集目標軌跡的過程中,有許多冗余的位置點,在對軌跡進行聚類之前需要對軌跡進行軌跡特征點的選取.我們需要在進行軌跡特征點選取的過程中同時考慮軌跡的精確性和簡潔性.本文采用文獻[12]提供的特征點選取算法進行特征點選取,其中軌跡特征點選取分為兩個過程,第一步:計算每個軌跡位置點上的偏轉角,計算方法見公式(2)所示,并設置轉向角閾值,其中大于閾值的位置點將成為候選特征點,小于閾值的位置點將直接被刪除;第二步:采用最小描述長度算法對軌跡做進一步處理,篩選出來的軌跡點即為軌跡特征點.

2.1.1 最小描述長度

顯然僅僅通過偏轉角篩選得到的特征點集還不夠簡潔,還需要進一步處理.為了在軌跡劃分中得到精確性和簡潔性之間的最優的解,本研究采用信息論中的最小描述長度(Minimum Description Length,MDL)理論對候選集進一步篩選.MDL的基本原理是對于一組給定的實例數據D,如果要對其進行保存,為了節省存儲空間,一般采用某種模型對其進行編碼壓縮,然后再保存壓縮后的數據.同時也要保存所用模型來進行數據的恢復.所以需要保存的數據有兩部分構成,我們將總的數據長度成為總描述長度.最小描述長度原理就是使得總描述長度最小的模型.

本文中的實例數據為位置點信息,我們可以通過面積來壓縮位置點信息.則總描述長度由兩部分組成:L(H)和L(D|H).D是要描述的數據,H是面積信息.L(H)是面積信息的開銷,L(D|H)是在H這種假設下描述數據D的開銷.最終采用局部最優替代全局最優的軌跡劃分方法來尋找一個最好的H來描述D使得L(H)和L(D|H)總開銷最小.假設原始軌跡如圖3所示,首先通過偏轉角篩選,

得到的特征點為p1,p3,p4,p5,p6,p7,p8,p10,p12.然后通過MDL方法進一步篩選得到最終的軌跡特征點集p1,p4,p6,p9,p12.

圖3 經過特征點提取之后的軌跡

2.2 軌跡聚類

采集的大量軌跡經過特征點提取之后,還需要對軌跡數據進行適當的聚類分析,分類出若干個訓練集.對目標軌跡進行聚類就是將大量的軌跡數據進行分類處理,從而形成一個相對簡單可用的知識,繼而對目標軌跡進行準確地軌跡分類、預測.軌跡聚類一般分為軌跡的相似性度量和相似性度量基礎上的軌跡聚類.本研究在度量軌跡相似性時只考慮軌跡的空間屬性.通過軌跡之間的空間相似度來進行軌跡聚類以獲得可靠的模型參數.通過對軌跡進行聚類來分類出若干的訓練集.下面我們首先介紹算法的相關概念,然后介紹算法的主要思想.

算法的相關概念:本文中ε表示軌跡的密度半徑,Mintrs表示軌跡的密度閾值,即核心軌跡區域內軌跡的最少條數.定義如下所示.

定義1.如圖4所示,在移動對象時空軌跡的數據空間中,任意軌跡的領域是由與該軌跡的空間距離不超過ε的所有軌跡構成的區域.

圖4 核心軌跡搜索區域

定義2.在移動對象時空軌跡的數據空間中,任意軌跡的領域中軌跡的個數大于等于Mintrs,則軌跡稱為核心軌跡.

算法的主要思想如下:首先將所有的軌跡標記為未聚類,然后順序讀取未聚類的軌跡,通過參數ε和MinTrs判斷該軌跡是否是核心軌跡.如果該軌跡是核心軌跡,則該核心軌跡的ε鄰域的所有軌跡形成一個新簇并用該核心軌跡標記.如果不是核心軌跡則進行下一條軌跡的操作.然后這個簇通過ε鄰域內的核心軌跡不斷向外擴展,直到簇不再增長為止,最后所有未標記的軌跡作為一個新的簇存在.以上過程迭代執行直到所有的軌跡都被標記到簇中為止.

算法 1.聚類相關算法輸入:(1)經過特征點提取后的軌跡數據(2)密度半徑參數ε和最小軌跡閾值Mintrs輸出:若干軌跡簇步驟:Input trajectory List:D=;a)For tri in D b)lable tri as uncluster//首先將所有軌跡標記的未標記c)END FOR d)ClusterID = 0 e)For tri in D f)IF tri is unclustered THEN g)Compute t = N(tri)h)IF t ＞= Mintrs i)assign ClusterID to all trj//如果該軌跡是核心軌跡,則標記該區域內 所有軌跡j)ExpandCluster()//擴展該區域內的其他軌跡,執行同樣操作k)ClusterID ++l)ELSE m)tri put D0//如果軌跡既不是核心軌跡也未標記則單獨保存在D0簇中n)END IF o)END

3 頻繁模式搭建

在搭建模型的過程中,模式的選取是搭建模型的關鍵.本文采用區間的形式來進行模式的表示.加速度我們選擇[0～2]為單位1,轉向角我們將方向角劃分為九等份,即[0～40]為單位 1.

3.1 加速度模式搭建

本文規定軌跡當前點和軌跡預測點的時間差為1秒鐘,短時間內高速巡航的移動目標加速度保持不變或者變化較小,所以可以假定兩點之間目標的運動狀態是勻速或者勻加速運動,則軌跡中兩個連續位置點之間速度差和時間差的比值就是兩點間的加速度.經過反復試驗,加速度模式選擇三階的加速度模式能得到很好的效果,model=[A1-A2-A3],其中model是加速度模型中的一個模式,A1,A2,A3是三個連續子軌跡上的加速度.對加速度模式的劃分如表1所示.

表1 加速度頻繁模式表

3.2 轉向角模式搭建

對移動目標軌跡的預測不僅要考慮目標的速度,同時還需要對目標進行轉彎預測.通過轉向角的篩選之后,每一個位置點都會有一定的轉向角,如圖5所示.同樣,偏轉角模式選擇三階的偏轉角模式能得到很好的效果,model = [α1-α2-α3],其中 model是偏轉角模型中的一個模式,α1,α2,α3是三個連續位置點上的偏轉角.偏轉角的計算公式見第2節公式(2).本文通過預測轉向角的大小來進行轉彎預測,對轉向角模式的劃分如表2.

表2 轉向角頻繁模式表

圖5 轉向角預測

算法3.模型訓練相關算法輸入:根據目標內碼得到的單個目標的所有軌跡D=輸出:關于加速度的模式angleModel步驟:Input trajectory List:D=;a)For tri in D b)getAngleModel(tri);c)End for;d)/*************************/e)getAccModel(tri);f);//輸入一條軌跡序列g)Key1=getKey();//五個點確定一個長度為3的Key h)Model=putIntoModel(key);//將模式寫出模型i)重復f、g;j)end

4 軌跡預測模型及算法實現

4.1 工作原理

在上節中,我們通過訓練分別得到了加速度和轉向角的模型.根據目標移動對象已經產生的實時軌跡,基于各訓練集聚類對目標移動對象的軌跡數據進行軌跡相似度并行計算,找出最大相似度的軌跡數據并記錄該軌跡所在的子訓練集.基于此,我們就可以利用該子訓練集訓練的加速度和偏轉角模型結合傳來的目標移動對象軌跡分別預測出目標移動對象的加速度和轉向角.然后結合最大相似度的歷史軌跡以及移動對象加速度和軌跡偏轉角的預測模型得出目標移動對象的加速度和轉向角.最后通過加速度和偏轉角求出目標移動對象預測點的位置信息.

4.2 算法實現

算法4.軌跡預測算法輸入:訓練軌跡數據集D1=測試軌跡數據集D2=輸出:未來軌跡的位置點信息1.for tri in D1 2.trj=angleTurning(tri,angle)//經過偏轉角算法進行特征點提取3.trk=DML(tri);//經過MDL算法進一步篩選4.D.add(trk)5.end for 6.set = Julei(D);//聚類分析產生若干的訓練集7.Model=train(set);//模型訓練,分別得到相應模型8.For i=0 to k 9.Point=Predict(model);//連續預測K步10.e[i]=mis(point,point0);//誤差分析11.end

由于在本方法中兩預測點的時間間隔很短,所以可以假定目標到下一個軌跡點是以一定的加速度a勻加速運動,這樣可以通過加速度a求出目標移動對象在下一軌跡點的速度v,然后根據求出的轉向角ɑ,求出速度在各個方向上的分矢量vx,vy,vz.最后根據如下公式求出下一時刻軌跡點坐標:

5 實驗與性能分析

為了測試本文所提出的算法效果和性能,我們通過模擬移動對象軌跡數據進行了實驗,來驗證算法對軌跡的聚類效果和算法對軌跡的預測效果.同時采用普遍應用的回歸算——卡爾曼濾波的預測算法,來進行實驗.其中硬件的實驗環境如下所示:

處理器:Intel(R)Core(TM)i5-4570 CPU@3.20GHz

內存:4.00 GB

軟件環境:Eclipse+mysql.實驗中進行的參數設置如表3所示.

表3 參數設置

本方法中實驗參數的選取非常重要,直接影響到本方法的聚類和預測效果.本節我們設置了不同的實驗參數,經過多次實驗之后發現當ε=30和最小軌跡數MinTrs=15時,我們提出的方法聚類效果比較理想.算法對經過篩選的歷史軌跡數據進行計算,最終檢測出了8個簇,也就是8個子訓練集.從實驗得出的結果可知,隨著移動對象測試軌跡數量的增加,本文算法的預測誤差比較小,一直保持在 1 km以內,如果已知的目標軌跡相對較長,則算法預測精度相對較高并且比較穩定.通過分析實驗結果可知:卡爾曼濾波預測算法的誤差比本文提出的方法明顯高出近20%以上,而且本文方法的精確度比卡爾曼濾波預測算法更為精確.原因是因為本文提出的預測算法對于處理較為復雜運動模式軌跡預測的精度較好,而實驗中我們所模擬的目標軌跡數據大都是軌跡模式較為復雜且種類繁多,基于卡爾曼濾波的軌跡預測僅僅對軌跡進行線性回歸預測,沒有對不同的軌跡模式進行聚類分析,因此其預測誤差很大 .軌跡預測結果如圖6所示,通過實驗結果可以看出,誤差在500 m范圍內最終的預測命中率能達到90%以上,誤差在1KM范圍內的最終預測命中率能達到98%以上.通過進一步合理設計加速度和偏轉角的模式還能進一步提高預測命中率.

圖6 軌跡預測示例圖

6 結束語

通過實驗對模擬數據進行分析發現,實驗結果表明:該方法能夠達到比較理想的預測效果.同時,該方法能夠實現增量挖掘,預測精度和可靠性有了進一步提高,具有較高的實用.本文在已有算法基礎上提出了一種新的軌跡預測方法,即基于模式的移動目標軌跡預測.經過對測試軌跡集進行實驗的結果表明,誤差在500 m范圍內本預測方法最終的預測命中率能達到90%以上,而且預測時間相對較短.為了進一步提高軌跡預測的實時性要求,下一步工作我們將把該系統移植到Spark平臺上.

1 章逸豐.快速飛行物體的狀態估計和軌跡預測[博士學位論文].杭州:浙江大學,2015.

2 徐慶飛,張新,李衛民.二維空間中目標軌跡預測算法研究與分析.航空電子技術,2012,43(1):10–14.

3 徐肖豪,楊國慶,劉建國.空管中飛行軌跡預測算法的比較研究.中國民航學院學報(綜合版),2001,19(6):1–6.

4 魏賽.基于曲線擬合的目標跟蹤算法研究[碩士學位論文].合肥:安徽大學,2014.

5 何靜.利用卡爾曼濾波預測船舶航行軌跡異常行為.艦船科學技術,2017,39(1A):16–18.

6 馬國兵,張楠.一種基于神經網絡的機動目標軌跡預測方法.青島理工大學學報,2006,27(5):108–111.

7 趙越,劉衍珩,余雪崗,等.基于模式挖掘與匹配的移動軌跡預測方法.吉林大學學報(工學版),2008,38(5):1125–1130.

8 喬少杰,沈志強.PathExplorer:基于頻繁模式的不確定性軌跡預測系統.中國計算機學會.第29屆中國數據庫學術會議論文集(B輯)(NDBC2012).合肥,中國.2012.5.

9 陳傳運.云計算環境下時空軌跡頻繁模式挖掘研究[碩士學位論文].南京:南京師范大學,2015.

10 袁晶.大規模軌跡數據的檢索、挖掘和應用[博士學位論文].合肥:中國科學技術大學,2012.

11 喬少杰,金琨,韓楠,等.一種基于高斯混合模型的軌跡預測算法.軟件學報,2015,26(5):1048–1063.[doi:10.13328/j.cnki.jos.004796]

12 何苗.移動對象的時空軌跡聚類算法研究[碩士學術論文].蘭州:蘭州大學,2013.