基于M-CFSFDP算法的戰(zhàn)場目標分群方法

李偉楠, 章衛(wèi)國, 史靜平, 吳云燕

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

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

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

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

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

1 問題描述

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

T={O1,O2,…,On}

(1)

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

Oi={xi1,xi2,…,xim}

(2)

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

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

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

(3)

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

2 基于流形距離的CFSFDP算法

2.1 CFSFDP算法

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

1) 局部密度

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

(4)

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

(1) 截斷核

(5)

(2) 高斯核

(6)

(3) 指數(shù)核

(7)

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

2) 高密度近鄰點距離

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

(8)

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

δi=maxi(dij)

(9)

3) 截斷距離的求取

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

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

(10)

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

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

(11)

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

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

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

2.2.1 CFSFDP算法的缺陷

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

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

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

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

2.2.2 M-CFSFDP

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

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

(12)

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

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

(13)

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

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

表1 流形距離

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

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

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

輸入:待聚類數(shù)據(jù)集

輸出:聚類結(jié)果

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

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

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

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

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

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

3 仿真實驗

3.1 人工數(shù)據(jù)集和UCI數(shù)據(jù)集聚類

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

表2 人工數(shù)據(jù)集和UCI數(shù)據(jù)集信息

圖2 threecircles數(shù)據(jù)集聚類結(jié)果 圖3 lineblobs數(shù)據(jù)集聚類結(jié)果

圖4 jain數(shù)據(jù)集聚類結(jié)果 圖5 spiral數(shù)據(jù)集聚類結(jié)果

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

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

圖6 wine數(shù)據(jù)集決策圖

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

表3 UCI數(shù)據(jù)集聚類正確率

3.2 戰(zhàn)場目標分群

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

我方目標任務(wù)執(zhí)行過程如圖7所示:

圖7 我方目標任務(wù)執(zhí)行過程航跡

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

2) 當(dāng)?shù)竭_t1時刻,目標3,5,6接到突發(fā)任務(wù)安排,目標3與目標1,2分裂并單獨成群,目標5,6與目標4,7分裂為2個空間群。其余目標仍執(zhí)行原任務(wù)。

3) 當(dāng)?shù)竭_t2時刻,目標3與目標5,6合并成一個群,并開始向遠處執(zhí)行攻擊任務(wù)。其余目標仍執(zhí)行原任務(wù)。

下面應(yīng)用本文提出的目標分群方法,來對上述任務(wù)執(zhí)行過程中的所有目標進行分群。

1) 某時刻目標靜態(tài)分群結(jié)果

t時刻目標狀態(tài)信息如表4所示:

表4 狀態(tài)信息表

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

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

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

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

表5 聚類結(jié)果表

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

圖11 t時刻目標航跡

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

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

任務(wù)執(zhí)行全時段目標分群結(jié)果如下所示:

圖12 全時段目標分群結(jié)果

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

圖13以全程航跡的形式表現(xiàn)了目標分群結(jié)果。上述分群結(jié)果與設(shè)計的任務(wù)執(zhí)行過程吻合,并且對于目標分裂、合并以及單獨成群等特殊情況都可以

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

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

4 結(jié) 論

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