基于分級(jí)聚類和近鄰函數(shù)準(zhǔn)則的目標(biāo)分群算法＊

劉維國(guó) 莊錦成

（91550部隊(duì)91分隊(duì) 大連 116023）

1 引言

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

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

2 分級(jí)聚類方法

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

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

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

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

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

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

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

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

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

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

3.2 計(jì)算類間損失

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

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

總類間損失：

式中c為類數(shù)。

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

4 基于分級(jí)聚類算法和近鄰函數(shù)準(zhǔn)則算法的目標(biāo)編隊(duì)分群算法

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

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

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

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

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

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

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

5 目標(biāo)編隊(duì)分群算法實(shí)例

5.1 求距離最近兩目標(biāo)中心點(diǎn)的坐標(biāo)

經(jīng)過(guò)計(jì)算可知，目標(biāo)N1和N4之間的距離最近，即Δ（Γ1，Γ4）＝2000m。則目標(biāo) N1和 N4中心點(diǎn) N0的方位值和距離值為（0，15000）。

5.2 形成初始聚類

計(jì)算各目標(biāo)與中心點(diǎn)N0的距離值：N1N0＝1000，N2N0＝3100，N3N0＝2100，N4N0＝1000，N5N0＝2100，N6N0＝12369，N7N0＝13757。

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

圖1 非預(yù)定打擊編隊(duì)目標(biāo)與預(yù)定打擊編隊(duì)目標(biāo)位置示意圖

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

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

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

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

5.4 求出預(yù)定打擊編隊(duì)目標(biāo)

因Γ6和Γ7均不能并入Γ4，故Γ4類內(nèi)的所有目標(biāo)即為預(yù)定打擊目標(biāo)編隊(duì)，即預(yù)定打擊編隊(duì)目標(biāo)為N1、N2、N3、N4、N5。

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

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

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

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

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

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

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