劉維國 莊錦成

（91550部隊91分隊 大連 116023）

1 引言

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

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

2 分級聚類方法

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

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

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

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

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

3 近鄰函數(shù)準則算法的原理

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

3.1 規(guī)定類內(nèi)損失

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

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

3.2 計算類間損失

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

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

總類間損失：

式中c為類數(shù)。

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

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

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

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

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

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

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

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

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

5 目標編隊分群算法實例

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

經(jīng)過計算可知，目標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中除掉相應的樣本數(shù)，即Γj＝｛Nj｝，j∈I，I＝｛j｜j＝4，6，7｝，形成初始聚類。

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

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

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

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

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

5.4 求出預定打擊編隊目標

因Γ6和Γ7均不能并入Γ4，故Γ4類內(nèi)的所有目標即為預定打擊目標編隊，即預定打擊編隊目標為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］徐敏，程鳳舟，陳士櫓.反艦導彈多目標識別技術(shù)探討［J］.戰(zhàn)術(shù)導彈技術(shù)，2000（2）：35－40.

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

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