多維空間中基于模式的移動(dòng)對(duì)象軌跡預(yù)測(cè)①

章夢(mèng)杰,邵培南,于銘華

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

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

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

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

1 基本概念及模型框架

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

描述移動(dòng)對(duì)象時(shí)空軌跡的數(shù)據(jù)庫(kù)D,該數(shù)據(jù)庫(kù)中存放著移動(dòng)對(duì)象不同時(shí)間序列的位置信息,其中位置點(diǎn)信息由來(lái)表示,位置點(diǎn)在一定時(shí)間的有序集合構(gòu)成了一條完整的目標(biāo)軌跡,由來(lái)表示.

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

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

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

說(shuō)明4.偏轉(zhuǎn)角計(jì)算.偏轉(zhuǎn)角表示移動(dòng)對(duì)象在當(dāng)前位置點(diǎn)向下一位置點(diǎn)運(yùn)動(dòng)的方向角.

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

圖1 軌跡的偏向角和開(kāi)放角

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

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

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

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

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

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

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

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

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

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

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

2 生成訓(xùn)練集

2.1 軌跡特征點(diǎn)選取

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

2.1.1 最小描述長(zhǎng)度

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

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

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

圖3 經(jīng)過(guò)特征點(diǎn)提取之后的軌跡

2.2 軌跡聚類

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

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

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

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

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

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

算法 1.聚類相關(guān)算法輸入:(1)經(jīng)過(guò)特征點(diǎn)提取后的軌跡數(shù)據(jù)(2)密度半徑參數(shù)ε和最小軌跡閾值Mintrs輸出:若干軌跡簇步驟:Input trajectory List:D=;a)For tri in D b)lable tri as uncluster//首先將所有軌跡標(biāo)記的未標(biāo)記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//如果該軌跡是核心軌跡,則標(biāo)記該區(qū)域內(nèi) 所有軌跡j)ExpandCluster()//擴(kuò)展該區(qū)域內(nèi)的其他軌跡,執(zhí)行同樣操作k)ClusterID ++l)ELSE m)tri put D0//如果軌跡既不是核心軌跡也未標(biāo)記則單獨(dú)保存在D0簇中n)END IF o)END

3 頻繁模式搭建

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

3.1 加速度模式搭建

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

表1 加速度頻繁模式表

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

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

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

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

算法3.模型訓(xùn)練相關(guān)算法輸入:根據(jù)目標(biāo)內(nèi)碼得到的單個(gè)目標(biāo)的所有軌跡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();//五個(gè)點(diǎn)確定一個(gè)長(zhǎng)度為3的Key h)Model=putIntoModel(key);//將模式寫(xiě)出模型i)重復(fù)f、g;j)end

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

4.1 工作原理

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

4.2 算法實(shí)現(xiàn)

算法4.軌跡預(yù)測(cè)算法輸入:訓(xùn)練軌跡數(shù)據(jù)集D1=測(cè)試軌跡數(shù)據(jù)集D2=輸出:未來(lái)軌跡的位置點(diǎn)信息1.for tri in D1 2.trj=angleTurning(tri,angle)//經(jīng)過(guò)偏轉(zhuǎn)角算法進(jìn)行特征點(diǎn)提取3.trk=DML(tri);//經(jīng)過(guò)MDL算法進(jìn)一步篩選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ù)測(cè)K步10.e[i]=mis(point,point0);//誤差分析11.end

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

5 實(shí)驗(yàn)與性能分析

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

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

內(nèi)存:4.00 GB

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

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

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

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

6 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

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