一種基于數據降維的移動目標軌跡分析方法*

吳 聰 崔 雋 施衛峰

(中國電子科技集團公司第二十八研究所 南京 210007)

?

一種基于數據降維的移動目標軌跡分析方法*

吳 聰 崔 雋 施衛峰

(中國電子科技集團公司第二十八研究所 南京 210007)

大數據是信息技術領域又一次顛覆性的技術革命,已在軍用領域凸顯潛在的應用價值。由于各類傳感器廣泛應用,軍事系統采集到了大量移動目標的軌跡數據,但數據體量大、復雜多樣且變化速度快,傳統的數據分析和挖掘方法很多已不適用,難以發揮數據的效用。根據實際應用需求,論文借助大數據表示和感知的相關算法,提出了大量移動目標頻繁訪問的熱門區域提取和軌跡相似性計算的方法,提高了計算效率,實用性較強。

軌跡分析; 大數據表示; 壓縮感知; 熱門區域; 軌跡相似性

Class Number TP311

1 引言

隨著物聯網、云計算、無線通信等技術的飛速發展以及多種傳感器的廣泛應用,數據種類和規模正以前所未有的速度積累,在社會、經濟、國防和科技發展的方方面面起到了前所未有的重要作用,如何更好利用大數據已經成為普遍關注的話題[1]。美國政府在2012年宣布“大數據研究和發展倡議”[2],大力推動大數據的獲取、存儲、管理、分析和共享等技術研究,提高美國的科研、教育與國家安全能力。美軍開展了包括DARPA的多尺度異常檢測(ADAMS)、網絡內部威脅(CINDER)、Insight、面向任務的彈性云、加密數據編程計算(PROCEED)等大數據發展戰略及研究項目[3],通過海量數據感知、理解和決策支持的結合,提升戰場態勢感知、情報分析、智能決策以及安全防護能力,化數據優勢為戰爭優勢[4～5]。

在信息化作戰中,軍事系統中電、磁、聲、光等形形色色的傳感器不斷發展與廣泛應用,使得各種移動目標(如飛機、船舶等)都得到較為準確的定位和有效的追蹤,采集到了大量移動目標的軌跡數據。但獲取的軌跡數據體量大、復雜多樣且變化速度快[6],其采集、存儲、傳輸只解決了數據存在的問題[7],要發揮數據的效用,挖掘其中蘊含的豐富信息,必須對大數據進行分析處理[8],這直接關系到指揮者能否快速有效地分析敵方的行動企圖并及時準確地做出決策。因此,提高移動目標軌跡的分析處理能力具有重要的研究價值和實戰意義。

移動目標的軌跡是移動對象在某一時間段內所經過的路線,它可以表示為二維、三維甚至更高維的時間序列,移動目標軌跡具有復雜性、海量性和實時性等特點,傳統的分析處理技術較難有效地發揮作用[9]。目前國內外已經開展了相關的研究工作,如軌跡聚類[10～11]、熱門路徑分析[12]、軌跡相似性度量[13]等,但大多集中于車輛的軌跡數據分析研究,受限于平面網絡空間,如道路交通網絡,通過提取一些停留點或者標志性的參考點來進行數據降維,并不適用于飛機或者船舶的軌跡數據分析。其中,有些研究考慮了移動目標的熱門區域的挖掘方法,通過已有的復雜聚類算法發現所需的區域[14～15],但很少考慮大量軌跡數據分析時的計算效率,較難在實際中得以應用。

根據實際應用需求,借助大數據表示和感知的相關算法,本文從熱門區域提取和軌跡相似性分析兩個部分對移動目標軌跡數據進行分析,流程如圖1所示。

圖1 移動目標軌跡數據處理流程圖

首先,針對大量移動目標的歷史軌跡數據,挖掘移動目標頻繁訪問的熱門區域,反映了移動目標的個體或群體運動模式,可輔助敵方意圖判斷和決策分析等。

為提高計算效率和實用性,本文將運動空間分割為不重疊的單元格,移動對象的軌跡轉變為其經過的單元格,根據被訪問的頻率找出符合熱門區域定義的若干相鄰單元格的集合。計算開銷只與單元格數目有關,計算量大大減少,并且針對實時數據具有較好的適用性,只需根據實時的子軌跡更新相應單元格的被訪問頻率。

其次,衡量移動目標軌跡之間的相似性對于提取移動對象的運動特征和分析敵方行為模式等起著重要的作用。由于大數據的高維非線性,本文通過流行的數據降維和特征提取方法,將高維原始數據映射到低維空間,保留重要信息,去除冗余信息,降低了計算復雜度,再利用基于差異和特征點集的相似性度量函數分析軌跡間的相似程度。

2 數據的表示和感知

隨著大數據時代的到來,人們已經能夠在不分時間和地域的情況下,方便地獲取各種數據和信息。高維數據提供了有關客觀現象的更加豐富和詳細的信息描述,但給后續的數據分析和處理帶來了前所未有的困難和挑戰,可能導致計算效率低下、維度災難、較難準確地從高維數據中找出本質的或者用戶感興趣的信息等問題。大數據的分析處理中,大數據的表示和感知是關鍵性環節:通過表示,大數據中高維蘊涵的有用信息得以凸現出來;通過感知,大數據中包含的重要信息得以定位和利用。

2.1 數據的表示

研究表明,高維數據中包含大量冗余信息和噪聲,而其本質維度很低,需要對高維數據進行降維,即維數約簡,即獲取原始高維數據在低維空間中的表示,從而揭示蘊含在高維數據中的本質特性[16]。

傳統的線性降維技術,如主成分分析(Principal Component Analysis,PCA)、線性判別分析(Linear Discriminant Analysis,LDA)等,對具有線性結構分布的數據集進行一定的維數約簡,計算簡單,易于理解,但現實世界中所獲得的真實數據集更多呈現出結構非線性或屬性強相關性,線性方法較難適用。

基于流形學習的降維方法是近年發展起來的非線性降維方法[17],假設高維觀測數據采樣于一個潛在的低維流形上,通過某種顯示或隱式的映射關系學習出此假設存在的流形,并將原始數據從周圍觀測空間投影到一個低維嵌入空間,反映了數據的本質特征。假設給定數據集X={x1,x2,…,xn}?RD,其中X中的樣本是由低維空間的數據集Y={y1,y2,…,yn}?Rd通過某個位置的非線性映射f所生成,即

xi=f(yi)+εi

(1)

式(1)中,εi表示噪聲,d?D,f:Rd→RD是嵌入映射,那么,流形學習的任務是基于給定的觀測數據集X:

1) 獲取低維表達Y={yi,i=1,2,…,n};

2) 構造從高維空間到低維空間的非線性映射f-1:RD→Rd。

數據降維不僅可以將高維數據壓縮到低維空間,而且能夠提取反映原始數據集的本征特征,為聚類、分類、可視化等后續分析工作提供更有價值的信息。

2.2 數據的感知

在大數據環境下,由于高維空間存在著稀疏性、空空間現象等特性,經典的聚類算法在高維數據空間上進行聚類分析時效果很差。大數據的量大且價值密度低的先天特性呼喚著有效感知數據核心規律的計算體系。壓縮感知作為近年來興起的信號處理手段,強調在大量數據中選擇出“核心價值”,為簡約數據規模、感知數據機理、揭示數據結構提供了必要的理論保障。

壓縮感知(Compressed Sensing,CS)理論與傳統奈奎斯特采樣定理不同[17],它認為,如果信號在某一變換域上是稀疏的,就可以用一個與變換基不相關的觀測矩陣將變換所得高維信號投影到一個低維空間上,然后通過求解優化問題就可以用此信號在某投影域上的觀測向量來近似無損地重構原信號。

在壓縮感知理論中,對于稀疏結構的探求可以描述為下列優化問題:

xl0=argmin‖x‖l0s.t.φx=y

(2)

式(2)中,‖ ‖l0表示l0范數,即零范數,表示矩陣中非零元素的個數,φ是一組觀測矩陣,而y為現實世界中觀測到的信號。然而,對于上述問題l0的優化求解是NP難問題,可以通過相應方法近似求解,獲得高維數據的低維特征,大大提高了后續分析的計算效率。

3 移動目標軌跡分析

3.1 熱門區域提取

熱門區域通常是指移動對象頻繁經過的區域,一定程度上反映著移動目標的個體或群體運動模式,可輔助敵方意圖判斷和決策分析等。本文針對大量移動目標的高維軌跡數據,將移動對象的運動空間分割為許多不重疊的二維或三維的單元格[11],移動對象的連續軌跡轉變為其可能經過的單元格,通過統計單元格被訪問次數和不同軌跡相交的單元格的頻次[12],找出符合熱門區域定義的若干相鄰單元格的集合。其優勢在于計算量大大減小,提高熱門區域發現的效率,計算的開銷只與單元格的數目有關[14],只要這些單元格足夠小,該方法就可以提供較好的近似結果。

1) 軌跡網格化

由于軌跡數據是離散采樣的,假設在二維坐標中給定兩個連續的軌跡點Pm(xm,ym)和Pm+1(xm+1,ym+1)(對應時間點為tm和tm+1),可以根據移動目標的當時速度找出在Δt時間內移動目標可能的覆蓋區域。由于車輛行駛軌跡靈活多變,已有橢圓、最小邊界矩形、對稱六邊形等幾種覆蓋區域計算方法[14],然而飛機、船舶等敵方目標軌跡數據采樣間隔相對較小,可以在Δt時間內的移動近似視為直線運動,即將兩軌跡點連線經過的單元格視為其經過區域,相應簡化的計算步驟如下。

首先將子軌跡PmPm+1等分為一系列子軌跡點Pk,則點Pk所在的單元格

(3)

其中l為單元格的長度,fix函數為取整函數,k=1,2,…,10,k值范圍可根據單元格長度和軌跡點之間的距離調整。

相應地,子軌跡PmPm+1所經過的單元格的計算簡化為每個子軌跡點所在單元格的并集,如下式所示。

Tri(PmPm+1)= {Grid(x1,y1)}∪{Grid(x2,y2)}

∪…∪{Grid(xm+1,ym+1)}

(4)

對每一段子軌跡做同樣操作,可獲得每條軌跡在單元格上的投影,最終將移動目標經過的一系列時空點轉化為經過的一系列單元格{{Tri(PmPm+1)}}。

2) 頻繁訪問的單元格提取

在給定時間間隔Δt和相應的所有移動目標的歷史軌跡{Tr1,Tr2,…,Trn}中,某個單元格Grid(a,b)的被訪問的頻率(Frequency)可表示為

Frequency(Grid(a,b))=N(a,b)/Δt

(5)

其中,N(a,b)是在時間段Δt內所有移動目標穿過單元格Grid(a,b)的次數。根據上述計算,由每條軌跡Tri經過的單元格{{Tri(PmPm+1)}}來構建單元格被訪問的頻次的矩陣Mi,其中

Mi(a,b)=

(6)

其中,Num(Grid(a,b))表示在時間段Δt內軌跡{{Tri(PmPm+1)}}穿過單元格Grid(a,b)的次數,最小值為1。

那么時間間隔Δt所有歷史軌跡經過單元格Grid(a,b)的次數N(a,b)可表示為

N(a,b)=∑iMi(a,b)

(7)

將式(6)和式(7)帶入到計算即可獲得單元格Grid(a,b)在一定時間段內被所有移動目標穿過的頻率。

將頻繁訪問的單元格定義為:若某個單元格被訪問的頻率大于等于設置的頻率閾值δ1,則稱該單元格為核心單元格;若某個單元格被訪問的頻率大于等于設置的頻率閾值δ2,則稱該單元格為重要單元格。閾值參數與移動目標的數目等數據相關聯,可根據實際應用需求進行更改,其值越大,符合要求的區域也就越少。

(8)

經過上述步驟,根據某時間段內所有移動目標的歷史軌跡將空間分為頻繁訪問的核心單元格、重要單元格和一般單元格。

3) 熱門區域的發現

在實際過程中,某個區域可能由幾個單元格組成,而單元格本身只是由劃分獲得一些不重疊的子區域,需要對單元格進行分類,進而組合成需要關注的熱門區域。本文根據以下三個步驟來發現熱門區域:

Step 1 若Grid(a,b)和Grid(c,d)是核心單元格且相鄰,那么該熱門區域為包含這兩個核心單元格的最小外接矩形;

Step 2 若Grid(m,n)為重要單元格,且鄰域中存在不相鄰的若干個核心單元格或熱門區域,那么更新后的熱門區域應為包含上述區域的最小外接矩形;

Step 3 若兩個熱門區域存在相交區域,更新后的熱門區域為包含上述區域的最小外接矩形。

每個步驟重復執行,直到沒有更新再執行下一步驟。通過最小外接矩形框定熱門區域符合使用習慣,也可以通過最小區域或其他圖形來框定。

上述方法針對實時數據具有較好的適用性,只需要根據軌跡數據更新的子軌跡更新單元格的訪問頻率,不需要重新計算。上述過程使用二維平面位置數據舉例分析,三維數據也可以采用上述過程進行分析。

3.2 軌跡相似性分析

移動目標的軌跡相似性分析是移動目標軌跡分析的典型應用之一,其目標就是從歷史軌跡中找到相似的運動軌跡,提取移動對象的運動特征模式,便于敵方行為模式和意圖分析等。軌跡相似性分析通過對軌跡數據降維和特征信息提取,確定軌跡間的相似程度,然后將相似程度較高的軌跡歸為一類[19]。由于每個軌跡數據Tri由一系列的離散點組成,表示每條軌跡的維度較高,對于計算兩條軌跡的相似性,傳統的方法考慮計算所有的數據,計算量較大且效率較低。

1) 數據降維

本文采用流形學習中的局部線性嵌入法(Locally Linear Embedding,LLE)[20]進行數據降維。給定軌跡數據集Tr,其中Tri∈RD,i=1,…,N,其中N為樣本總數,D為原始空間維數,在每個樣本點尋找它的鄰域{Tri(1),…,Tri(k)},Tri(k)∈Tr,然后通過求解如下一個約束最小二乘優化問題來計算最小重構權值。

(9)

將其轉化成求解一個可能奇異的線性方程組,并通過引入一個小的正則因子來保證線性方程組系數矩陣的非奇異性。求出重構權值后,利用這些重構權值可以構造一個稀疏矩陣。

M=(I-W)T(I-W)

(10)

通過求解這個稀疏矩陣的幾個最小特征值對應的特征向量來獲得數據的低維嵌入{LTri},其中LTri∈Rd,d?D。

2) 特征提取

基于壓縮感知的特征提取來降低分析數據的維度也是一種可行的方法。基于上述原始高維數據的稀疏表示,采用稀疏子空間聚類(Sparse Subspace Clustering,SSC)方法,假設數據間的仿射矩陣是稀疏的,l0最小化問題的求解可以通過其凸包絡[21],即l1來求解。因此,優化下列目標取而代之。

xl1=argmin‖x‖l1s.t.φx=y

(11)

式中,l1范數表示了信號中所有元素絕對值之和,上述優化目標可以通過凸優化的方式得以求解。基于l1范數的凸優化算法有基追蹤算法(Basis Pursuit,BP)、梯度投影法、內點迭代法等,可將約束條件轉換為懲罰項,構造非約束優化問題,如式(12)所示,控制參數可視為求解約束優化問題的Lagrange乘數,具體的計算步驟見文獻[22]。

(12)

其中,原始數據為軌跡數據集Tr,Tri∈RD,通過求解獲得特征數據FTr其中FTri∈Rm,m?D,即軌跡上運動或狀態發生明顯變化的點,降低數據維度,去除冗余信息,找到蘊含其中的本質特性,便于后續的分析工作。

對軌跡數據采用數據降維或特征提取主要根據分析實際數據的效果進行選擇,也可以結合考慮,目前上述兩種方法都應用較廣。

3) 相似性度量

如何衡量每對軌跡段之間的相似程度,是需要解決最重要的問題之一。為了簡化計算,很多研究采用Hausdorff距離公式來衡量軌跡片段之間的差異[13],如式(13)和式(14)所示。

Diff(LTri,LTrj)= max(h(LTri,LTrj),

h(LTrj,LTri))

(13)

(14)

其中,h(LTri,LTrj)為直接Hausdorff距離,即LTri中的點到最近LTrj中的點的最大距離,dist(P,Q)表示兩個軌跡點之間的歐式距離。

但由于軌跡數據中可能包含一些噪聲點和異常點,對計算的結果影響較大,所以對于異步的軌跡數據,本文采用式(15)來衡量兩個軌跡之間的差異。

(15)

其中,h(LTri,LTrj)為LTri中的點到最近LTrj中的點的平均距離。通過計算兩條軌跡之間的差異就可以獲得兩條軌跡之間的相似性,如式(16)所示。

(16)

由上述公式可以看出,通過數據降維可以有效地降低相似性度量的計算量。

對于通過稀疏學習提取或自定義的特征點FTri,可以通過軌跡之間特征點集的關系計算兩條軌跡之間的相似性,如式(17)所示,num表示集合中元素的個數。

(17)

4 結語

本文借助于大數據表示和感知的相關算法,針對蘊含重要信息的大量移動目標的軌跡數據,從實際應用角度出發,提出了大量移動目標頻繁訪問的熱門區域提取和軌跡相似性計算的方法,降低了數據維度,提高了計算效率,實用性較強。可通過更先進的大數據技術,進一步對移動目標軌跡進行聚類、分類、預測等分析處理,挖掘出更多隱含的有用信息。

大數據技術在情報信息提取及處理、信息網絡防御、網絡安全及監控、作戰指揮等方面開始發揮著越來越重要的作用,重點是研究海量數據分析、大數據處理、數據可視化等一些關鍵方法和技術,與國外相比還存在較大的差距。本文通過對移動目標軌跡大數據的分析處理,為大數據技術盡早在國防軍事系統中廣泛應用拋磚引玉。

[1] Mayer-Sch?nberger Viktor.大數據時代[M].周濤,譯.杭州:浙江人民出版社,2012.

[2] Big Data Across the Federal Government[EB/OL]. http://www.whitehouse.gov/sites/default/files/microsites/ostp/big_data_fact_sheet_final_1.pdf,2012-10-02.

[3] 莊林,沈彬.美國國防部大數據項目研發與應用[J].國防科技,2013,34(3):58-61.

[4] 蔣盤林.大數據通用處理平臺及其在ISR領域的潛在軍事應用[J].通信對抗,2013,32(3):1-5.

[5] 李紀舟.美軍大數據發展戰略及對我啟示[J].外軍網絡空間戰,2012(4).

[6] 孟小峰,慈祥.大數據管理:概念、技術與挑戰[J].計算機研究與發展,2013,50(1):146-169.

[7] 王珊,王會舉,覃雄派,等.架構大數據:挑戰、現狀與展望[J].計算機學報,2011,34(10):1741-1752.

[8] 何清,李寧,羅文娟,等.大數據下的機器學習算法綜述[J].模式識別與人工智能,2014,27(4):327-336.

[9] Zheng Y, Zhou X F. Computing with spatial trajectories[M]. New York: Springer-Verlag,2011:143-177.

[10] Kharrat A, Popa I S, ZeitouniKarine, et al. Clustering algorithm for network constraint trajectories[C]//Proceedings of 13th International Symposium on Spatial Data Handling, Montpellier, France: Springer,2008:631-647.

[11] Mamoulis N, Cao H P, Kollios G, et al. Mining, indexing, and querying historical spatiotemporal data[C]//Won K, Ron K, Johannes G, William D, eds. Proc. of the 10th ACM SIGKDD Int’l Conf. on KnowledgeDiscovery and Data Mining(KDD 2004). New York: ACM Press,2004:236-245.

[12] Verhein F, Chawla S. Mining spatio-temporal association rules, sources, sinks, stationary regions and thoroughfares in objectmobility databases[C]//Lee M, Tan KL, Wuwongse V, eds. Proc. of the 11th Int’l Conf. on Database Systems for Advanced Applications. Berlin, Heidelberg: Springer-Verlag,2006:187-201.

[13] Vlachos M, Gunopulos D, Kollios G. Robust similarity measures for mobile object trajectories[C]//Proceedings of the 13th International Workshop on Database and Expert Systems Applications. IEEE Computer Society,2002:721-728.

[14] 劉奎恩,肖俊超,丁治明,等.軌跡數據庫中熱門區域的發現[J].軟件學報,2013,24(8):1816-1835.

[15] Giannotti F, Nanni M, Pedreschi D, et al. Trajectory pattern mining[C]//Berkhin P, Caruana R, Wu XD, eds. Proc. of the 13thACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining(KDD 2007). New York: ACM Press,2007:330-339.

[16] 趙連偉,羅四維,趙艷敞,等.高維數據流形的低維嵌入及嵌入維數研究[J].軟件學報,2005,16(8):1423-1430.

[17] 王自強,錢旭,孔敏.流形學習算法綜述[J].計算機工程與應用,2008,44(8):9-12.

[18] Donoho D L. Compressed sensing[J]. IEEE Transactions onInformation Theory,2006,52(4):1289-1306.

[19] Gariel M, Srivastava A N, Feron E. Trajectory clustering and an application to airspace monitoring[J]. IEEE Transaction on Intelligent Transportation Systems,2011,12(4):1511-1524.

[20] Chang H, Yeung D Y. Robust locally linear embedding[J]. Pattern Recognition,2006,39(6):1053-1065.

[21] E. Elhamifar, R. Vidal. Sparse subspace clustering[C]//IEEE Conference on Computer Vision and Pattern Recognition,2009:2790-2797.

[22] Cong Wu, Bo Li, Shu Shen, et al. Vehicle classification in pan-tilt-zoom videos via sparse learning[J]. Journal of Electronic Imaging,2013,22(4):041102-1-12.

An Analysis Method of Moving Object Trajectories Based on Data Dimensionality Reduction

WU Cong CUI Jun SHI Weifeng

(The 28th Research Institute of CETC, Nanjing 210007)

Big data is another technological revolution in information technology domain, has highlighted the potential applications in the military field. Due to the wide application of various types of sensors, a large number of moving object trajectories has been collected. But the data is volume, complicated and fast changing, traditional data analysis and mining is no longer applicable in many ways. According to the actual application requirements, with big data representation and sensing algorithms, a method of hot region extraction and similarity measures for trajectory databases is proposed, which improves the computational efficiency and practicability.

trajectory analysis, big data representation, compressed sensing, hot region, trajectory similarity

2015年3月11日,

2015年4月26日

吳聰,男,博士,工程師,研究方向:數據分析和輔助決策。崔雋,男,博士,工程師,研究方向:數據建模和數據分析。施衛峰,男,碩士,高級工程師,研究方向:防空作戰指揮。

TP311

10.3969/j.issn.1672-9730.2015.09.010