章夢杰,邵培南,于銘華

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

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

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

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

1 基本概念及模型框架

本節(jié)首先對所使用的軌跡數(shù)據(jù)結(jié)構(gòu)進行簡要說明,然后介紹本文所提出模型的框架及工作原理.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 系統(tǒng)模型框架圖

歷史軌跡數(shù)據(jù)庫:過去采集到的歷史軌跡數(shù)據(jù)作為結(jié)構(gòu)化數(shù)據(jù)存放在Mysql數(shù)據(jù)庫.實時的新到移動對象軌跡數(shù)據(jù),經(jīng)過清洗后也將存入歷史軌跡數(shù)據(jù)庫中.

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

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

2 生成訓(xùn)練集

2.1 軌跡特征點選取

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

2.1.1 最小描述長度

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

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

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

圖3 經(jīng)過特征點提取之后的軌跡

2.2 軌跡聚類

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

算法的相關(guān)概念:本文中ε表示軌跡的密度半徑,Mintrs表示軌跡的密度閾值,即核心軌跡區(qū)域內(nèi)軌跡的最少條數(shù).定義如下所示.

定義1.如圖4所示,在移動對象時空軌跡的數(shù)據(jù)空間中,任意軌跡的領(lǐng)域是由與該軌跡的空間距離不超過ε的所有軌跡構(gòu)成的區(qū)域.

圖4 核心軌跡搜索區(qū)域

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

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

算法 1.聚類相關(guān)算法輸入:(1)經(jīng)過特征點提取后的軌跡數(shù)據(jù)(2)密度半徑參數(shù)ε和最小軌跡閾值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//如果該軌跡是核心軌跡,則標記該區(qū)域內(nèi) 所有軌跡j)ExpandCluster()//擴展該區(qū)域內(nèi)的其他軌跡,執(zhí)行同樣操作k)ClusterID ++l)ELSE m)tri put D0//如果軌跡既不是核心軌跡也未標記則單獨保存在D0簇中n)END IF o)END

3 頻繁模式搭建

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

3.1 加速度模式搭建

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

表1 加速度頻繁模式表

3.2 轉(zhuǎn)向角模式搭建

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

表2 轉(zhuǎn)向角頻繁模式表

圖5 轉(zhuǎn)向角預(yù)測

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

4 軌跡預(yù)測模型及算法實現(xiàn)

4.1 工作原理

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

4.2 算法實現(xiàn)

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

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

5 實驗與性能分析

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

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

內(nèi)存:4.00 GB

軟件環(huán)境:Eclipse+mysql.實驗中進行的參數(shù)設(shè)置如表3所示.

表3 參數(shù)設(shè)置

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

圖6 軌跡預(yù)測示例圖

6 結(jié)束語

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

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

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

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

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

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

6 馬國兵,張楠.一種基于神經(jīng)網(wǎng)絡(luò)的機動目標軌跡預(yù)測方法.青島理工大學(xué)學(xué)報,2006,27(5):108–111.

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

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

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

10 袁晶.大規(guī)模軌跡數(shù)據(jù)的檢索、挖掘和應(yīng)用[博士學(xué)位論文].合肥:中國科學(xué)技術(shù)大學(xué),2012.

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

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