改進cell密度聚類算法在空戰(zhàn)目標分群中的應用

閆孟達，楊任農(nóng)，王 新，左家亮，嵇慧明，尚金祥

(1. 空軍工程大學 空管領航學院， 陜西 西安 710051； 2. 中國人民解放軍94994部隊， 江蘇 南京 210019；3. 中國人民解放軍94701部隊， 安徽 安慶 246000； 4. 中國人民解放軍94347部隊， 遼寧 沈陽 110042)

空戰(zhàn)目標分群是態(tài)勢感知[1]階段的關鍵步驟，其目的在于根據(jù)當前空戰(zhàn)環(huán)境，綜合分析速度、航向和位置等態(tài)勢要素，將敵方參戰(zhàn)力量按一定的層次結(jié)構(gòu)劃分為不同的空間群和相互作用群[2]，幫助指揮員將紛繁復雜的目標信息規(guī)整為不同類型的目標群組，有助于減少冗余態(tài)勢信息，降低態(tài)勢評估難度，提高空戰(zhàn)決策準確度[3-4]。

目前，目標分群主要有兩大類方法。一類是基于相似性度量、優(yōu)化算法和神經(jīng)網(wǎng)絡的模型法。文獻[5-7]通過建立目標位置、航向等屬性的相似度函數(shù)，將相似度較大的目標劃分到同一群組。該方法雖然計算簡單，但需根據(jù)屬性的不同設置多種相似度調(diào)節(jié)系數(shù)和決斷閾值，實際應用效果不佳。文獻[8-10]分別利用蟻獅優(yōu)化算法[11]、自組織特征映射(Self-Organizing Feature Mapping, SOM)神經(jīng)網(wǎng)絡[12]、遺傳算法和支持向量機(Support Vector Machine, SVM)處理目標分群問題，這四種方法雖然實時性較好，但其穩(wěn)定性相對較差且SOM和SVM的訓練數(shù)據(jù)難以獲得。另一類是對目標屬性進行聚類分析的屬性聚類法。文獻[13]首開基于聚類算法處理目標分群問題的先河，此后研究主要集中于如何使聚類算法更好地適用于目標分群問題。文獻[14-15]運用改進的K-means和模糊C均值聚類算法解決目標分群問題，上述算法只適用于編隊數(shù)目已知的聚類問題，雖然可以通過算法改進推理出可能的編隊數(shù)目，但其準確度相對較差。文獻[16-17]基于Chameleon算法處理目標分群問題，雖然該算法可處理類數(shù)未知問題且準確度較高，但其實時性相對較差。文獻[18]通過改進迭代自組織數(shù)據(jù)分析技術算法(Iterative Self-Organizing Data Analysis Techniques Algorithm, ISODATA)的分裂標準提高了分群效率，但該方法以歐式距離衡量目標相似度，只對球形分布數(shù)據(jù)有良好的聚類效果[19]，而空中目標往往呈流形列隊，故該方法難以適用于目標分群。文獻[20-21]基于流形距離分別改進密度峰值算法和二階段聚類算法，使其能夠處理流形分布聚類問題，提高了目標分群的準確度，但流形距離計算復雜，容易造成實時性較差的問題。因此，發(fā)現(xiàn)一種能夠?qū)崿F(xiàn)流形聚類，且實時性和準確度相對較好的聚類算法，是處理目標分群問題的關鍵。

基于cell的密度聚類(Cell-based Density Spatial Clustering of Applications with Noise, CBSCAN)算法[22]可以在事先不知道簇類數(shù)目的情況下，在含有噪聲點的數(shù)據(jù)集合中發(fā)現(xiàn)任意形狀的簇，對流形分布數(shù)據(jù)有較好的聚類效果。本文通過改進CBSCAN算法的簇類擴展方式，在保證算法準確度的同時，提高目標分群的實時性。

1 目標分群模型

目標分群是空戰(zhàn)態(tài)勢評估的首要任務?，F(xiàn)代空戰(zhàn)中，敵方往往以多編隊協(xié)同空戰(zhàn)的方式向我方目標發(fā)起進攻，其主要編隊樣式為圖1所示的流形分布。若對敵方每架飛機逐一進行態(tài)勢評估，工作量很大且耗時較長。目標分群技術可以將編隊內(nèi)部戰(zhàn)機劃分為一個整體，用對整體的評估預測代表對內(nèi)部每架戰(zhàn)機的評估預測。

圖1 基本編隊隊形Fig.1 Basic formation style

1.1 分群類型

目標分群抽象層次如圖2所示，空戰(zhàn)目標分群是自底向上的分析推理過程，其主要分為：

1)空戰(zhàn)目標——參與空戰(zhàn)過程的作戰(zhàn)飛機(殲擊機、轟炸機等)及部分導彈。

2)空間群——空間位置相近且類型相同的空戰(zhàn)目標。

3)相互作用群——執(zhí)行相同任務的空間群。

4)中立、敵、我方目標群——根據(jù)敵我屬性進行劃分后的相互作用群。

圖2 目標分群抽象層次Fig.2 Target grouping abstraction level

1.2 分群模型

令空戰(zhàn)目標數(shù)據(jù)集合為D={d1,d2,…,dn}，其中di=(Fofi,Typei,xi,yi,θi,vi)(i=1,2,…,n)表示第i個空戰(zhàn)目標。目標各屬性參數(shù)如下所示。

Fof：空戰(zhàn)目標的敵我屬性。該參數(shù)可以由戰(zhàn)機上的敵我應答機自動判定，是進行目標分群的前提，只有當目標的Fof值一致時，才可將它們歸為一類。Fof=0表示目標為中立方目標；Fof=1表示目標為我方目標；Fof=2表示目標為敵方目標。

Type：作戰(zhàn)飛機類型，主要包括直升機、殲擊機、轟炸機等。不同類型的飛機一般執(zhí)行不同的任務，處于不同的空間群。

{x,y}：作戰(zhàn)飛機的橫縱坐標。一般情況下，根據(jù)目標在xy平面上的分布即可將它們劃分到不同的空間群中。為節(jié)省時間開支將忽略目標的飛行高度數(shù)據(jù)，只根據(jù)橫縱坐標進行空間群劃分。

{θ,v}：作戰(zhàn)飛機的航向和速度值。由于航向和速度可以體現(xiàn)戰(zhàn)機執(zhí)行任務的對象和任務類型，因此劃分空間群后，基于每個空間群的平均航向和速度，利用分群算法劃分相互作用群。

根據(jù)如圖3所示的模型框架，利用分群算法，最終可將探測到的空戰(zhàn)目標分為敵我識別群CC1、空間群CC2和相互作用群CC3。對于每種分群類型CCi，都包括多個群體Cj。例如CC3={C1,C2,…,Ck}表示將目標分成了k個不同的相互作用群。

在獲取空戰(zhàn)目標數(shù)據(jù)的基礎上，尋求一種可以快速準確得到空間群的方式。

圖3 目標分群模型框架Fig.3 Target grouping model framework

2 改進的CBSCAN算法

CBSCAN是一種基于密度聚類(Density-Based Spatial Clustering of Applications with Noise, DBSCAN)算法[23]進行劃分改進的聚類算法。進一步改進CBSCAN的簇類擴展方法，以提高CBSCAN算法的聚類實時性。

2.1 DBSCAN算法

DBSCAN算法是一種應用廣泛的聚類算法。該算法主要通過鄰域范圍半徑ε和最小鄰域點數(shù)目閾值MinPts將數(shù)據(jù)點劃分為核心點、邊界點和噪聲點，繼而通過數(shù)據(jù)點之間的密度關系進行簇的劃分。DBSCAN算法的基本概念及其流程如下所述。

2.1.1 點的劃分

DBSCAN算法根據(jù)數(shù)據(jù)點密度及其位置關系，將數(shù)據(jù)點分為核心點、邊界點和噪聲點。劃分方法如圖4所示。

鄰域Nε(p)：以數(shù)據(jù)點p為圓心，以鄰域范圍ε為半徑的圓形范圍內(nèi)的數(shù)據(jù)點。表示為Nε(p)={q∈D|dist(p,q)≤ε}，其中D為數(shù)據(jù)點集合，dist(p,q)為p,q兩點間的歐式距離。|Nε(p)|為p點ε鄰域內(nèi)的鄰居點個數(shù)，以此表示數(shù)據(jù)點p的密度。

核心點：如果點p的鄰居點個數(shù)滿足|Nε(p)|≥MinPts，則點p為核心點。

邊界點：如果點p的鄰居點個數(shù)滿足|Nε(p)|

噪聲點：如果點p既不是核心點，又不是邊界點，則該點為噪聲點。即鄰居點個數(shù)滿足|Nε(p)|

圖4 劃分流程Fig.4 Division process

2.1.2 密度關系

DBSCAN算法將同一簇中任意兩點間的密度關系分為直接密度可達、密度可達、和密度相連三種情況，進而由密度可達關系導出最大密度相連的樣本集合，以此為最終簇。

直接密度可達：如果位置點p滿足p∈Nε(q)，且q為核心點，則點p直接密度可達點q，即點p直接密度可達其ε鄰域內(nèi)的任一核心點。

密度可達：給定位置點p1,p2,…,pn，如果pi直接密度可達pi+1(i=1,2,…,n-1)，則p1密度可達pn。

密度相連：如果點p和點q都密度可達點l，則點p與點q密度相連。

密度簇：所有密度相連數(shù)據(jù)點構(gòu)成的數(shù)據(jù)集合。

2.1.3 算法流程

DBSCAN算法流程如圖5所示，DBSCAN算法從數(shù)據(jù)集合D中的任意一點p開始，檢索其ε鄰域中的數(shù)據(jù)點。如若|Nε(p)|≥MinPts，則將建立一個新的密度簇C，并對該簇進行擴展。由于DBSCAN算法需計算每個點的鄰域點數(shù)目，計算量較大，耗時較多。

圖5 DBSCAN 算法流程Fig.5 DBSCAN algorithm flow

2.2 CBSCAN算法

圖6 CBSCAN算法網(wǎng)格劃分Fig.6 Meshing of CBSCAN algorithm

1)包含網(wǎng)格：給定某單元格G(b1,b2)和密度簇C，對于?p(p∈G(b1,b2))，若滿足p∈C，則G(b1,b2)是C的包含網(wǎng)格。

2)XG1型排他網(wǎng)格：若式(1)成立，則G(b1,b2)中數(shù)據(jù)點都是核心點，此時定義G(b1,b2)是某密度簇的XG1型排他網(wǎng)格。

(1)

由于G(b1,b2)周圍8格中任一點與G(b1,b2)中任一點(核心點)的距離都小于等于ε，根據(jù)直接密度可達關系，可以將包括G(b1,b2)在內(nèi)的9格都劃為同一密度簇，此時G(b1,b2)周圍8格均為密度簇的包含網(wǎng)格。

3)XG2型排他網(wǎng)格：若式(1)不成立，則檢查G(b1,b2)周圍45格中數(shù)據(jù)點與G(b1,b2)中所有點間的距離關系。若?p(p∈G(b1,b2))，使得式(2)成立，則G(b1,b2)中存在核心點p，此時定義G(b1,b2)是簇的XG2型排他網(wǎng)格。由于G(b1,b2)周圍8格中的點與G(b1,b2)中核心點p的距離均小于等于ε，與XG1型排他網(wǎng)格相同，也可以將包括G(b1,b2)在內(nèi)的9格劃為同一密度簇。

∑qk≥MinPts

(2)

此后，檢查排他網(wǎng)格的鄰居網(wǎng)格和含有邊界點的網(wǎng)格是否為排他網(wǎng)格，以此進行密度簇的擴展。CBSCAN算法流程如圖7所示。

圖7 CBSCAN算法流程Fig.7 CBSCAN algorithm flow

分析圖7所示流程可知，CBSCAN算法運用網(wǎng)格劃分的方式將數(shù)據(jù)點劃分到網(wǎng)格中，把數(shù)據(jù)點的查詢歸類轉(zhuǎn)化為網(wǎng)格的查詢歸類，較大地減少了DBSCAN算法的時間開銷。但該算法僅通過1個排他網(wǎng)格附帶周圍8個包含網(wǎng)格的方式進行簇類擴展，在高密度區(qū)的擴展效率依然相對較低。

2.3 改進的CBSCAN算法

1)XG3高密型排他網(wǎng)格：對于單元格G(b1,b2)，若式(3)成立，則G(b1,b2)是XG3高密型排他網(wǎng)格。如圖8(b)所示，此時網(wǎng)格G(b1+i,b2+j),(i=-1,0,1;j=-1,0,1)均是XG1型排他網(wǎng)格，可向外擴展25個包含網(wǎng)格。

|G(b1,b2)|≥MinPts

(3)

(4)

(5)

(c) XG4中密型排他網(wǎng)格(c) XG4 exclusive grid (d) XG5次密型排他網(wǎng)格(d) XG5 exclusive grid圖8 排他網(wǎng)格示意圖Fig.8 Exclusive grid diagram

由上述定義分析可知，在CBSCAN算法中，當確定某網(wǎng)格G(b1,b2)為排他網(wǎng)格時，最多只能將9個包含網(wǎng)格擴展到密度簇中。通過提出高密、中密和次密型排他網(wǎng)格等概念，一次查詢最多可以擴展25個包含網(wǎng)格。

3 基于改進CBSCAN的目標分群模型

3.1 飛行態(tài)勢數(shù)據(jù)處理

1)剔除異常值?？諔?zhàn)態(tài)勢數(shù)據(jù)中難免會存在部分異常值，常見的異常值處理方法主要包括刪除元組、數(shù)據(jù)補齊、缺失值處理和不處理等，采用刪除元組的方式處理異常值。孤立森林算法是一種無監(jiān)督的異常檢測方法，它可以通過隨機分割數(shù)據(jù)集的方式，快速發(fā)現(xiàn)分布稀疏且離密度較高群體較遠的孤立點，能夠在低維數(shù)據(jù)集中取得良好的檢測效果。因此，采用孤立森林算法檢測并刪除飛行態(tài)勢數(shù)據(jù)中的異常值。

2)坐標系轉(zhuǎn)換。為了定量分析戰(zhàn)機間的相對態(tài)勢，將各型雷達獲取的目標數(shù)據(jù)統(tǒng)一到同一坐標系中。

3)歸一化處理。當態(tài)勢數(shù)據(jù)范圍不一致時，需要通過歸一化方法進行數(shù)據(jù)處理。

(6)

3.2 模型的算法處理

3.2.1 作戰(zhàn)空間網(wǎng)格劃分

分群模型在數(shù)據(jù)預處理的基礎之上，需要根據(jù)目標點di橫縱坐標的最大最小值和單元格邊長，由式(7)和式(8)確定網(wǎng)格的行數(shù)與列數(shù)。此后模型根據(jù)式(9)將所有坐標點分配到相應的單元格中，當坐標點處于網(wǎng)格邊線時，將該目標點歸屬到其右上方的網(wǎng)格中。

(7)

(8)

(9)

3.2.2 目標空間群擴展

基于改進CBSCAN算法進行空間群擴展的方式與圖7所示CBSCAN算法的執(zhí)行流程大致相同，其區(qū)別在于改進CBSCAN算法有更多的排他網(wǎng)格擴展選擇。圖9所示為基于改進CBSCAN算法的目標分群模型。

圖9 基于改進CBSCAN的目標分群模型Fig.9 Target grouping model based on improved CBSCAN

3.3 空間群拆分

同一空間群中的目標往往具有相同的敵我屬性和飛機類型。根據(jù)圖3目標分群模型框架，通過改進CBSCAN算法進行分群后，需根據(jù)敵我屬性和飛機類型的不同，對空間群進行拆分。

4 仿真實驗

仿真硬件環(huán)境為：Intel(R) Core(TM) i7-7700HQ 2.8GHz處理器，16 GB內(nèi)存，Win7 64位操作系統(tǒng)，軟件平臺為MATLAB 2014a。

4.1 作戰(zhàn)想定分析

多任務編隊協(xié)同空戰(zhàn)中的參戰(zhàn)飛機較多，涉及大量的飛行態(tài)勢數(shù)據(jù)。給出30組作戰(zhàn)場景想定，利用其中的飛行態(tài)勢數(shù)據(jù)檢驗改進CBSCAN算法處理空戰(zhàn)目標分群問題的適用性。每組想定中參戰(zhàn)飛機的數(shù)量不等，共有476個數(shù)據(jù)元組，每個元組都包括一架飛機的敵我屬性、飛機類型、坐標、飛行速度和航向等態(tài)勢數(shù)據(jù)。由于只針對敵方目標進行空間群分類實驗，所以設定所有數(shù)據(jù)元組中的Fof值為2。

圖10所示為其中一組典型空戰(zhàn)態(tài)勢，敵方共有15架飛機參與戰(zhàn)斗，他們欲通過偵察編隊、掩護編隊、轟炸編隊、伴隨干擾編隊和預警指揮編隊間的協(xié)同配合攻擊我方地面目標。

圖10 作戰(zhàn)想定Fig.10 Battle plan

表1數(shù)據(jù)為圖10作戰(zhàn)想定中的態(tài)勢數(shù)據(jù)。其中，類型 1為無人偵察機，類型2為殲擊轟炸機，類型3為電子干擾機，類型4為預警機，類型5為戰(zhàn)斗機。

表1 作戰(zhàn)想定飛行態(tài)勢數(shù)據(jù)

4.2 仿真結(jié)果

為驗證改進CBSCAN算法處理目標分群問題的有效性，分別利用K-means、最大期望(Expectation-Maximization, EM)算法、密度峰值、DBSCAN算法、CBSCAN算法和改進CBSCAN算法處理30組作戰(zhàn)想定中的飛行態(tài)勢數(shù)據(jù)。只分析算法處理空間群分類問題的有效性，故只對數(shù)據(jù)中的坐標位置進行聚類分析。

利用上述6種算法對圖10和表1所示飛行態(tài)勢數(shù)據(jù)進行10次目標分群實驗，將K-means和EM算法的聚類數(shù)目設置為6，實驗結(jié)果如圖11、圖12和圖13所示。

(a) K-means分群錯誤結(jié)果(a) Poor grouping results of K-means

(b) K-means分群正確結(jié)果(b) Good grouping results of K-means

(c) EM分群錯誤結(jié)果(c) Poor grouping results of EM

(d) EM分群正確結(jié)果(d) Good grouping results of EM圖11 K-means、EM目標分群結(jié)果Fig.11 K-means, EM target grouping results

(a) 決策圖(a) Decision diagram

(b) 聚類中心選擇(b) Cluster center selection

(c) 分群結(jié)果(c) Grouping results圖12 密度峰值算法分群結(jié)果Fig.12 Density peak algorithm target grouping results

(a) 目標分群結(jié)果(a) Target grouping results

(b) 平均運行時間(b) Average running time圖13 DBSCAN及其改進算法分群結(jié)果Fig.13 DBSCAN and its improved algorithm target grouping results

圖11為K-means算法和EM算法對作戰(zhàn)想定中15個空戰(zhàn)目標進行多次聚類后產(chǎn)生的部分不同結(jié)果。通過仿真實驗可以看出，在流形分布數(shù)據(jù)中，選擇不同的初始聚類中心會使K-means和EM產(chǎn)生不同聚類結(jié)果，這就使上述兩種算法的穩(wěn)定性較差，且正確率較低。圖12為密度峰值算法的分群結(jié)果。在10次聚類中，該算法均產(chǎn)生了相同的錯誤分群結(jié)果，說明其穩(wěn)定性較好，但正確率不高。圖11和圖12說明傳統(tǒng)聚類方法難以對流形分布的戰(zhàn)機編隊進行正確分群。圖13為DBSCAN、CBSCAN及改進CBSCAN算法的仿真結(jié)果。圖13(a)表明，DBSCAN及其改進算法對圖10所示作戰(zhàn)想定均得到了穩(wěn)定且正確的分群效果，圖13(b)說明改進CBSCAN算法可以在保證正確率的同時，提高算法的執(zhí)行效率。

為進一步說明改進算法的準確度和實時性，對30組作戰(zhàn)想定進行10次分群實驗，得到表2所示的仿真結(jié)果。

由表2結(jié)果可知：K-means算法執(zhí)行效率較高，但其正確率較低且穩(wěn)定性較差；EM算法執(zhí)行效率低、正確率差且穩(wěn)定性不好；此外，利用這兩種算法進行目標分群時，均需手動輸入類別數(shù)目，但目標分群屬于類數(shù)未知問題，故K-means和EM算法不適合處理空戰(zhàn)目標分群問題。密度峰值算法的時間復雜度較高，且由于該算法利用歐式距離作為相似性度量，無法準確對流形分布的空戰(zhàn)目標進行正確分類，導致其準確度與DBSCAN及其改進算法相比較差。DBSCAN、CBSCAN和改進CBSCAN三種算法的準確度較高，但改進CBSCAN算法的分群實時性在CBSCAN算法基礎上提高了約30%，達到了算法改進的目的。綜上，改進CBSCAN算法與其他算法相比，穩(wěn)定性較好、準確度和實時性較高，能夠較好地處理編隊協(xié)同空戰(zhàn)中的目標分群問題。

表2 分群算法結(jié)果對比

5 結(jié)論

1)K-means、EM和密度峰值算法難以對流形分布目標進行準確穩(wěn)定的分群操作。

2) DBSCAN、CBSCAN和改進CBSCAN算法都可以對流形分布目標進行準確分群。

3) 通過改進CBSCAN算法的簇類擴展方式，可以在保證原始算法準確度的同時，將分群實時性提高約30%。

4)改進后的CBSCAN算法能夠在多編隊協(xié)同空戰(zhàn)背景下，對空戰(zhàn)目標進行準確且更加快速的分群編組。