基于M-CFSFDP算法的戰場目標分群方法

李偉楠, 章衛國, 史靜平, 吳云燕

(1.西北工業大學 自動化學院, 陜西 西安 710072; 2.航空工業自控所, 陜西 西安 710065)

態勢估計通過感知戰場環境和敵我目標信息,推理敵方意圖,預測敵方行動,從而輔助指揮人員做出正確決策,奠定戰場勝局[1]。然而,現代戰爭中存在數量眾多、種類繁雜、屬性多樣的敵我戰場目標,這些都導致了信息量激增,從而對態勢估計提出了挑戰。而目標分群能夠根據目標自身屬性、目標間的空間關系,將目標分類合并為互不相交的空間群體,大大減少冗余信息,從而降低態勢估計難度,提高決策效率。

戰場目標分群問題具備以下特點:①空間群數量未知。由于戰場敵方目標部署情況未知,而我方目標部署又可能針對敵方發生改變,因而敵我雙方目標分群的空間群數量是未知的。②目標屬性多樣。目標具備多種屬性,如位置、速度、航向等,使得目標分群面對的數據往往是高維的。③目標分群動態性。戰場戰況瞬息萬變,目標的狀態也在時刻改變,從而導致目標所屬空間群的改變。目標分群問題不單是對應某一時刻的靜態分群,還是對應一段時間甚至整場戰爭的動態分群。

針對戰場目標分群問題,文獻[2-3]對目標屬性如位置、速度等建立相似度函數,然后構建空間相似度矩陣來進行目標分群。然而,多個相似度函數中引入了相似度計算閾值,空間相似度矩陣中又引入了相似度判定閾值。過多的閾值,會因為某些閾值取值不當而影響算法效果。文獻[4-6]將目標分群看作聚類問題,分別利用k-means算法和chameleon算法進行求解。然而,文獻[4]在確定空間群個數時,需要人為指定合理分群數的上限。但是在一些復雜戰況下,指揮人員可能無法指定該上限;文獻[5-6]則是在合并相鄰群時,必須人為指定相對互連性和相對近似性所需要滿足的閾值,但文中并未給出指定的依據或方法。最后,上述文獻都只是對某時刻戰場目標進行靜態分群,并未進行動態分群仿真。

本文結合目標分群問題的特點,提出了一種基于M-CFSFDP算法的目標分群方法來將戰場目標劃分為空間群。首先,建立戰場目標分群問題模型,并將其轉化為數據集聚類問題。其次,目標分群的特點要求聚類算法能夠在類別數量未知的前提下,解決高維數據的動態聚類問題。CFSFDP算法[7]能夠自動搜索與發現聚類中心,且可以對高維數據進行聚類,并且已經被用于目標分群問題中[8],故選擇CFSFDP算法來實現聚類。再次,針對CFSFDP算法中的歐氏距離無法正確衡量目標之間相似性的問題,提出引入流形距離將CFSFDP改進為M-CFSFDP。最后,應用M-CFSFDP算法對人工數據集和UCI數據集進行聚類仿真實驗,并對戰場目標進行靜態與動態目標分群仿真實驗,仿真結果證明了M-CFSFDP算法的正確性與可行性。

1 問題描述

目標分群的輸入為戰場中的各目標的狀態信息,如位置、速度、航向等。某時刻戰場目標集合可表示為:

T={O1,O2,…,On}

(1)

式中,Oi表示一個目標,n為目標的數量。對于一個目標Oi,其狀態屬性可表示為一個多元組:

Oi={xi1,xi2,…,xim}

(2)

式中,xij表示第i個目標的第j個屬性值,m為屬性的數量,即一個目標對應m維空間的一個點,T對應m維空間一個具有n個點的點集。

本文所需解決的問題,就是根據戰場中所有目標的自身屬性值,以及目標之間的時空關系,將它們分解到多個互不相交的空間群中,即

?i≠j,ψi∩ψj=?

(3)

式中,ψi表示一個空間群,N為空間群的數量。每個空間群由至少一個目標組成。

2 基于流形距離的CFSFDP算法

2.1 CFSFDP算法

CFSFDP算法針對聚類中心提出了2點假設:①聚類中心的局部密度大于其近鄰點;②聚類中心距高于其局部密度的點較遠。這2點假設實際上描述了聚類中心所具備的2條特性:自身局部密度大,以及聚類中心之間的距離遠。而非聚類中心的樣本點則只具備其中一個特性,或者都不具備。

1) 局部密度

對于數據集X=[x1,x2,…xn]中的一個點xi,其局部密度定義如(4)式所示:

(4)

式中，dij為數據點xi與xj之間的歐氏距離,dc為截斷距離,χ(·)為核函數。核函數可選擇3種形態[9]:

(1) 截斷核

(5)

(2) 高斯核

(6)

(3) 指數核

(7)

由此可見,以數據點xi為中心,以截斷距離dc為半徑所劃出的一個區域,該區域在二維或三維空間對應一個圓形或球體,在高維空間對應一個超球體。核函數則決定了xi以外的點處于該區域內的概率。局部密度實際上是概率的和,表示了點xi周圍近鄰點的密集程度。

2) 高密度近鄰點距離

高密度近鄰點距離定義如下:

(8)

對于點xi,xj是所有局部密度大于該點且與該點距離最近的點。xi與xj之間的歐氏距離即為高密度近鄰點距離。如果xi是局部密度最大的點,其高密度近鄰點距離為:

δi=maxi(dij)

(9)

3) 截斷距離的求取

在求取局部密度時,關鍵問題就是截斷距離dc的取值。文獻[7]僅給出dc的經驗性取值范圍。然而該范圍過大,需要人工篩選,不利于算法的自動化;與此同時,對于某些數據集,合適的dc甚至不在該范圍內。文獻[10-11]中介紹了數據場的概念并應用在數據聚類中,文獻[12]則在數據場的基礎上利用信息熵給出了自動求取dc的方法。

該方法將數據集等價為一個數據場,將數據點的局部密度ρi等價為該點在數據場中的勢能函數φi,其定義如下

(10)

式中,影響因子σ即為截斷距離dc。

然后,利用信息熵H來度量整個數據集的不確定性,其定義如(11)式所示

(11)

信息熵與數據集的分布相對應,熵值越小,不確定性越小,數據集越符合其真實的分布方式。當σ從0到+∞增加時,H先從Hmax=log(n)減小,在某個σ處達到最小值,然后又增大到Hmax。在H達到最小值時對應的σ,即為最優dc。

綜上所述,CFSFDP首先計算各個數據點的局部密度ρi以及高密度近鄰點距離δi,然后構建ρ-δ決策圖來快速尋找和發現聚類中心,最后指定剩余點的類別,其類別與高于該點局部密度且距該點最近的點相同[13]。

2.2 基于流形距離的CFSFDP算法改進

2.2.1 CFSFDP算法的缺陷

CFSFDP算法搜尋聚類中心時主要依靠ρi和δi,而δi的求取則依賴于ρi。因此,ρi的正確求解直接決定了CFSFDP算法聚類結果的正確性。在求取ρi時,其核心為首先利用數據點xi與xj間的歐氏距離來衡量xi與xj的相似性,然后通過核函數將相似性轉化為ρi。因此,數據點間的歐氏距離越小,相似性越大,ρi越接近1;反之,歐氏距離越大,相似性越小,ρi越接近0。然而,對于很多數據集,尤其是高維數據,歐氏距離卻無法正確衡量數據點之間的相似性。某數據集一部分數據空間分布如圖1所示:

圖1 歐氏距離和流形距離的相似性度量對比圖

由圖1可知,a與c屬于同一類,而b屬于另一類。然而,a與b之間的歐氏距離dab為0.209,a與c之間的歐氏距離dac為0.458,且dab

究其根本原因,是由于數據集的樣本點在空間內不再是簡單且彼此隔離的球狀簇集,而是形成一個個彼此相連的復雜結構,統稱為流形[14]。針對流形結構明顯的數據,數據點之間的最短距離并非歐氏距離,而是測地距離,即流形距離。此時,只有采用流形距離才能正確衡量數據點之間的相似性。

2.2.2 M-CFSFDP

空間上xi與xj之間的流形上的線段長度定義如下[15]:

L(xi,xj)=ρdl(xi,xj)-1

(12)

式中,dl(xi,xj)為xi與xj之間的歐氏距離,ρ>1為伸縮因子,此處可取e3。

將數據點xi與xj看作是圖G=(V,E)的頂點,令p={p1,p2,…pl}∈V表示圖上一條連接點p1與pl的路徑,其中邊(pk,pk+1)∈E,1≤k≤l-1。令Pij表示連接數據xi與xj的所有路徑集合,則xi與xj之間的流形距離定義如下[15]

(13)

式中,L(a,b)表示兩點間流形上的線段長度。

由流形距離的定義可以看出,它不像歐氏距離直接計算兩點間的空間距離,而是首先將數據點作為圖的頂點,將近鄰點連線作為圖的邊,然后從起點開始搜索最短邊來尋找下一個最近鄰點直至終點為止,最后計算所有最短邊流形上的線段長度并加和便得到流形距離。收縮因子使得流形距離相比歐氏距離,放大了位于不同流形的點間距離,縮小了相同流形內的點間距離,如圖1所示。

表1 流形距離

a與b之間的流形距離D(a,b)為0.872 4,a與c之間的流形距離D(a,c)為a至c共16個最短邊的集合(最短邊流形距離見表1),其大小為0.106 1。此時,流形距離可以正確衡量數據點間相似性。

綜上所述,M-CFSFDP算法首先計算數據點之間的流形距離,然后在流形距離的基礎上計算所有數據點的ρi和δi,再然后建立ρ-δ決策圖來搜索聚類中心,最后指定剩余數據點類別,獲得聚類結果。

下面給出M-CFSFDP的算法流程:

輸入:待聚類數據集

輸出:聚類結果

1) 數據標準化。采用min-max標準化將各維數據映射到[0,1]之間。

2) 計算流形距離。首先計算數據點之間的歐式距離;然后指定近鄰點個數n,一般可取3～5;再然后將每個數據點與其近鄰點連接生成圖;最后依據(12)～(13)式計算各數據點之間的流形距離。

3) 求取截斷距離。依據(11)式計算信息熵H,取H最小時對應的影響因子σ為截斷距離dc。

4) 計算局部密度ρi和高密度近鄰點距離δi。計算方法依據公式(7)～(9)。

5) 尋找聚類中心。構建ρ-δ決策圖來尋找聚類中心。

6) 非中心數據點歸類。歸類原則為:對于數據點xi,尋找高于該點局部密度的所有點,選擇其中距該點最近的點xj,則xi與xj的類別一致。

3 仿真實驗

3.1 人工數據集和UCI數據集聚類

本文同時利用CFSFDP算法和M-CFSFDP算法,來對人工數據集和UCI標準數據庫中的數據集進行聚類實驗,以期驗證M-CFSFDP算法的正確有效,且聚類結果優于CFSFDP算法。實驗數據基本信息如表2所示。圖2～5是人工數據集的仿真結果。

表2 人工數據集和UCI數據集信息

圖2 threecircles數據集聚類結果 圖3 lineblobs數據集聚類結果

圖4 jain數據集聚類結果 圖5 spiral數據集聚類結果

圖2～4表示4種人工數據集聚類結果,其中a)、b)分別表示CFSFDP算法和M-CFSFDP算法的ρ-δ決策圖,用于確定聚類中心;c)、d)分別表示2種算法的聚類結果。對于圖2數據集,圖2a)顯示CFSFDP算法只能尋找到一個正確的聚類中心,無法準確尋找到其余2個聚類中心,從而導致圖2c)聚類結果完全錯誤;而圖2b)顯示M-CFSFDP算法可以準確搜尋3個聚類中心,圖2d)聚類結果也將所有數據正確分為3類。對于圖3、4數據集,雖然CFSFDP算法可以找到聚類中心,然而由于歐氏距離無法正確衡量數據點間的相似性,使得數據點的ρi和δi計算結果出現偏差,從而導致部分數據點的聚類錯誤,圖3c)和圖4c)都顯示有數據點被錯分。而流形距離可以正確衡量數據點間的相似性,故圖3d)和圖4d)中M-CFSFDP算法聚類結果未出現錯分數據點。對于圖5數據集,決策圖與聚類結果表明,CFSFDP能夠正確聚類時,M-CFSFDP也能夠正確聚類。此外,對比上述所有數據集的決策圖,發現M-CFSFDP能夠更加明確地反映出聚類中心。正是由于流形距離的作用,使得M-CFSFDP搜索聚類中心的能力以及聚類效果都優于CFSFDP。

對于高維數據,本文以UCI數據庫中的wine數據集為例,對比2種的聚類結果,如圖6所示:

圖6 wine數據集決策圖

由圖6a)可知,CFSFDP算法只能找到2個聚類中心,而圖6b)中M-CFSFDP算法能夠正確搜索3個聚類中心。而圖中ρi很小而δi很大的點為單獨孤立點,故不算作聚類中心。由于UCI數據集都為高維數據,聚類結果不便以圖形表示,故表3給出聚類結果對比。由表3可知,對于iris數據集,M-CFSFDP能夠顯著提高聚類正確率;對于wine數據集,原方法甚至無法準確搜索聚類中心,確定聚類類別數。M-CFSFDP不但能準確搜索聚類中心,而且能夠得到較為理想的聚類結果。對于seeds數據集,M-CFSFDP算法的聚類正確率僅是略微提高,這是由于數據集自身特性導致,說明該數據集僅通過CFSFDP算法就可以獲得較高的聚類正確率。盡管聚類正確率提高有限,M-CFSFDP依然得到了較高的正確率,且優于CFSFDP算法。通過對人工數據集與UCI數據集的聚類仿真結果,可以充分證明M-CFSFDP算法的正確有效,且優于CFSFDP算法。

表3 UCI數據集聚類正確率

3.2 戰場目標分群

在實際戰場中,目標不斷運動,其狀態不斷變化,從而導致目標之間所形成的空間群也會有所改變。一般來說,戰場目標群體會存在諸如分裂、合并、單獨成群等情況,這對于目標分群方法提出了更高的要求。下面通過一組戰場我方目標的任務執行過程,來驗證本文目標分群方法的正確性、有效性與可行性。

我方目標任務執行過程如圖7所示:

圖7 我方目標任務執行過程航跡

1) 起始時刻,目標1～3向北偏東30°方向飛行,執行偵查任務;目標4～7向北偏東60°方向飛行,執行偵查任務;目標8～10由北向西逆時針執行巡邏任務。

2) 當到達t1時刻,目標3,5,6接到突發任務安排,目標3與目標1,2分裂并單獨成群,目標5,6與目標4,7分裂為2個空間群。其余目標仍執行原任務。

3) 當到達t2時刻,目標3與目標5,6合并成一個群,并開始向遠處執行攻擊任務。其余目標仍執行原任務。

下面應用本文提出的目標分群方法,來對上述任務執行過程中的所有目標進行分群。

1) 某時刻目標靜態分群結果

t時刻目標狀態信息如表4所示:

表4 狀態信息表

其中,x,y,z表示目標的位置信息;φ表示目標的航跡方位角;V表示目標的速度。

t時刻目標分群結果如圖8～10所示:

圖8 t時刻目標分群結果(x-y視圖) 圖9 t時刻目標分群結果(x-z視圖)圖10 t時刻目標分群結果(三維視圖)

由圖8～10可知,t時刻目標被分為5個空間群,如表5:

表5 聚類結果表

由圖8～10可知,如果僅僅參考目標之間的位置,可以明顯得出目標1,2,目標4,7以及目標8,9,10各自成為一個空間群。然而,本文目標分群方法將目標3,5,6分為2個空間群,則證明了該方法在分群時能夠結合目標各屬性,切合實際地正確分群。圖11表示各目標由起始時刻到達該時刻的航跡,航跡末端為該時刻目標所處位置。

圖11 t時刻目標航跡

結合圖11可知:目標1,2維持原航線,為空間群1;而目標3已經分裂出去并單獨成群,為空間群4;目標4～7此時也已分裂為2個群體,目標5,6為空間群2,目標5,7為空間群4;目標8～10為空間群3。

(2)全時段目標分群結果

任務執行全時段目標分群結果如下所示:

圖12 全時段目標分群結果

由圖12可知,在起始時刻,目標1～3屬于空間群1,目標4～7屬于空間群2,目標8～10屬于空間群3;經過一段時間后,目標3與目標1,2分裂并單獨成群,為空間群4。目標4,7與目標5,6分裂,為空間群5;最后,目標3與目標4,7又合并成空間群4。

圖13以全程航跡的形式表現了目標分群結果。上述分群結果與設計的任務執行過程吻合,并且對于目標分裂、合并以及單獨成群等特殊情況都可以

正確分群,充分說明了本文目標分群方法對于動態分群的正確性與可行性。

圖13 全時段目標分群航跡圖

4 結 論

本文針對戰場目標分群問題,提出了一種基于M-CFSFDP算法的目標分群方法。該方法利用流形距離替代歐氏距離以期正確衡量目標之間的相似度,并在此基礎上對CFSFDP算法進行改進。通過對人工數據集和UCI數據集進行仿真,驗證了M-CFSFDP算法搜索聚類中心與聚類效果均優于CFSFDP算法;同時應用該方法對戰場目標進行靜態與動態分群,仿真結果表明該方法能夠在起始空間群數量未知的前提下,對具有高維屬性的戰場目標既可以進行某時刻的靜態空間分群,又可以獲得整個任務執行過程的正確分群結果。