劉維國 莊錦成

（91550部隊91分隊 大連 116023）

1 引言

由于飛行器開機錄取扇面內可能存在非預定打擊編隊目標以外的其它目標，因此必須進行目標編隊分群，剔除非預定打擊目標。根據編隊目標間的距離特征進行預定打擊目標編隊決策，這正符合聚類算法“凡是同一類的樣本其特征向量應該是互相靠近的，而不同類的樣本其特征向量之間的距離要大得多”的基本特征。

動態(tài)聚類方法是一種普遍采用的方法，它具有以下三個要點：1）選定某種距離度量作為樣本間的相似性度量；2）確定某個評價聚類結果質量的準則函數；3）給定某個初始分類，然后用迭代算法找出使準則函數取極值的最好聚類結果。本文主要結合分級聚類方法和近鄰函數準則算法來研究目標編隊分群問題。

2 分級聚類方法

任何兩個樣本yi和yj總會在某一水平被分為同一類，分級聚類就是這樣一種劃分序列。分級聚類算法的基礎是兩個聚類之間的相似性度量，最常用的相似性度量有最近距離、最遠距離和均值距離等。在確定了相似性度量之后，就有如下的分級聚類算法：

初始時設置Γj＝y(tǒng)j，?j∈I，I＝｛j｜j＝1，2，…，N｝，這里Γj是各個聚類集合，N是樣本數，即初始時設每一個樣本為一個類。

步驟1 在集合｛Γj｜j∈I｝中找到一對滿足條件Δ（Γi，Γk）的聚類集合Γi和Γk。其中Δ（Γi，Γj）是Γi和Γk之間的相似性度量。

步驟2 把Γi并入Γk，并去掉Γi。

步驟3 把i從指標集中除掉，若I的基數等于2時，則終止計算；否則轉向步驟1。

3 近鄰函數準則算法的原理

對于數據集中的任何兩個樣本yi，yj，若yi是yj的第I個近鄰，則稱yj對yi的近鄰系數為I。若yi是yj的第K個近鄰，則稱yi對yj的近鄰系數為K。這里定義yi和yj之間的近鄰函數值為（I＋K－2）。若用αij表示yi和yj之間的近鄰函數值，則有：

3.1 規(guī)定類內損失

若在聚類的過程中，yi和yj被分在同一類，那么yi和yj是相互連接的。對于每一個這樣的連接存在著一個相應的連接損失。本算法中，連接損失規(guī)定為這兩個樣本間的近鄰函數值αij。當規(guī)定了樣本間的“連接”損失后，就可以規(guī)定類內損失和類間損失。總類內損失規(guī)定為

對于同一類中的yi和yj，由于存在連接關系，所以αij不等于零。對于不同類的yi和yj，由于不存在連接關系，所以αij等于零。

3.2 計算類間損失

首先計算wi和wj兩類之間的最小近鄰函數值γij，并取其中的最小值。則：

設αimax是同一類wi中兩點間的最大類間損失，αkmax是同一類wk中兩點間的最大連接損失。則其它類對wi類的類間損失為：

總類間損失：

式中c為類數。

對于βi，當某一類wi中的一點與其它任何一類wk中的一點的最小近鄰函數值小于或等于相應的任一類內的最大“連接”損失時，就要付出一些“代價”。即βi為正值。如式（4）中的第二、三、四種情況，它意味著若當兩類之間的最小近鄰函數值小于或等于相應的任一類內的最大“連接”損失的話，則這兩類就應當被合并。對于第一種情況，若當不同類間的最小近鄰函數值大于相應的類內的最大“連接”損失的話，由于所付出的“代價”為負，則這兩類就自然地為兩個聚類。

4 基于分級聚類算法和近鄰函數準則算法的目標編隊分群算法

分級聚類算法是一種劃分序列方法，這種劃分序列具有如下性質：只要在K水平時樣本被歸入同一類后，在進行更高水平的劃分時，它們也永遠屬于同一類。而目標編隊分群僅需劃分出預定打擊編隊即可，并不需要經過多個水平的劃分把扇面內所有目標劃分為一類，因此這里僅利用其選定的相似性度量來確定初始聚類，然后利用近鄰函數準則算法中的類間損失來確定預定打擊目標編隊。其算法如下：

初始時設置錄取目標數據表中的N個有效目標為N個樣本，組成樣本集｛y1，y2，…，yN｝，設置Γj＝y(tǒng)j，?j∈I，I＝｛j｜j＝1，2，…，N｝，這里Γj是各個聚類集合，即初始時設每一個樣本為一個類。

步驟1 在集合｛Γj｜j∈I｝中找到一對滿足條件

的聚類集合Γi和Γk。其中Δ（Γi，Γk）是Γi和Γk之間的最近距離相似性度量。

步驟2 找出距離最近兩目標之間的中心點，計算Γj中的各個樣本距離該中心點的距離值，并將距離值小于2Δ（Γi，Γk）的聚類集合合并為一類，并入Γk，并從指標集I中除掉相應的樣本數。

步驟3 對于指標集I中余下的類，共同形成初始聚類。對于初始聚類中的每個類i計算γi，并與αimax和αkmax進行比較。若γi小于或等于αimax和αkmax中的任何一個，則合并類i和類k，即在兩類間建立“連接”。重復步驟3，直至無這樣的“連接”為止。

步驟4 對于步驟3重新聚合的各類，暫取樣本數最多的類即為所求的類，該類內的所有目標即為預定打擊編隊目標。

5 目標編隊分群算法實例

5.1 求距離最近兩目標中心點的坐標

經過計算可知，目標N1和N4之間的距離最近，即Δ（Γ1，Γ4）＝2000m。則目標 N1和 N4中心點 N0的方位值和距離值為（0，15000）。

5.2 形成初始聚類

計算各目標與中心點N0的距離值：N1N0＝1000，N2N0＝3100，N3N0＝2100，N4N0＝1000，N5N0＝2100，N6N0＝12369，N7N0＝13757。

因N1N0、N2N0、N3N0、N4N0、N5N0的 值 均 小 于4000m，則目標N1、N2、N3、N4、N5聚合為一類，并入Γ4，并從指標集I中除掉相應的樣本數，即Γj＝｛Nj｝，j∈I，I＝｛j｜j＝4，6，7｝，形成初始聚類。

圖1 非預定打擊編隊目標與預定打擊編隊目標位置示意圖

5.3 在初始聚類中的任意兩類間建立“連接”

對于Γ4＝｛N1、N2、N3、N4、N5｝，其類內的最大連接損失N1N5＝4200m。

因為類Γ6內僅有目標N6，其與類Γ4中的一點的最小近鄰函數值N6N5＝10678m，且大于Γ4類內的最大連接損失，故類Γ7不能并入Γ4。

同樣，類Γ7內僅有目標N7，其與類Γ4中的一點的最小近鄰函數值N7N3＝10208m，且大于Γ4類內的最大連接損失，故類Γ6不能并入Γ4。

5.4 求出預定打擊編隊目標

因Γ6和Γ7均不能并入Γ4，故Γ4類內的所有目標即為預定打擊目標編隊，即預定打擊編隊目標為N1、N2、N3、N4、N5。

［1］董肇軍.系統(tǒng)工程與運籌學［M］.北京：國防工業(yè)出版社，2003，1.

［2］張劍.軍事裝備系統(tǒng)的效能分析、優(yōu)化與仿真［M］.北京：國防工業(yè)出版社，2000，1.

［3］陳玉文.海面機動目標散布規(guī)律及反艦導彈搜索區(qū)的劃分［J］.飛航導彈，1999（7）.

［4］孫國禎.海軍艦艇電子對抗作戰(zhàn)使用.海軍大連艦艇學院，1998.

［5］徐敏，程鳳舟，陳士櫓.反艦導彈多目標識別技術探討［J］.戰(zhàn)術導彈技術，2000（2）：35－40.

［6］李啟元，段立，李亞楠.海戰(zhàn)場目標航跡間距離聚類方法［J］.計算機與數字工程，2010，38（5）.

［7］陳玉文.海面機動目標散布規(guī)律及反艦導彈搜索區(qū)的劃分［J］.飛航導彈，1999（7）：6－10.