吳湘霖，楊士義

(1.中國空空導(dǎo)彈研究院，河南洛陽 471009；2.航空制導(dǎo)武器航空科技重點(diǎn)實(shí)驗(yàn)室，河南洛陽 471009；3.駐中國空空導(dǎo)彈研究院軍事代表室，河南洛陽 471009）

基于改進(jìn)ISODATA的無先驗(yàn)擴(kuò)展目標(biāo)聚類分析算法

吳湘霖1，2，楊士義3

(1.中國空空導(dǎo)彈研究院，河南洛陽 471009；2.航空制導(dǎo)武器航空科技重點(diǎn)實(shí)驗(yàn)室，河南洛陽 471009；3.駐中國空空導(dǎo)彈研究院軍事代表室，河南洛陽 471009）

基于彈載雷達(dá)多擴(kuò)展目標(biāo)檢測(cè)的應(yīng)用需求，在CFAR檢測(cè)輸出的基礎(chǔ)上，對(duì)檢測(cè)結(jié)果的聚類分析方法進(jìn)行了論證分析，提出了改進(jìn)的ISODATA算法。該算法擺脫了常用聚類分析算法對(duì)目標(biāo)個(gè)數(shù)、聚類初值等先驗(yàn)信息的要求以及孤立點(diǎn)的影響。數(shù)字仿真實(shí)驗(yàn)驗(yàn)證了新算法的有效性。

擴(kuò)展目標(biāo)；聚類；彈載雷達(dá)；改進(jìn)的ISODATA算法

0 引 言

隨著各種武器系統(tǒng)對(duì)作戰(zhàn)能力的要求不斷提高,高速、高機(jī)動(dòng)目標(biāo)精確碰撞、目標(biāo)識(shí)別與抗干擾等都對(duì)彈載雷達(dá)的高分辨率參數(shù)估計(jì)提出了要求。高分辨率雷達(dá)使得原先以單一點(diǎn)跡形式出現(xiàn)的目標(biāo)呈現(xiàn)擴(kuò)展?fàn)顟B(tài),可能占據(jù)多個(gè)分辨單元,這種目標(biāo)稱為擴(kuò)展目標(biāo)［1-3］。

研究表明,使用高分辨率PD雷達(dá)對(duì)擴(kuò)展目標(biāo)進(jìn)行積累檢測(cè),將在距離-多普勒域上占據(jù)一個(gè)區(qū)間,并在此區(qū)間具有尖峰群特征［4］。因此在對(duì)積累譜進(jìn)行CFAR檢測(cè)后需要對(duì)目標(biāo)區(qū)分,將應(yīng)該屬于同一個(gè)目標(biāo)的各個(gè)單元判為同一目標(biāo),而將相鄰的不同目標(biāo)過門限點(diǎn)區(qū)分開來,分別形成不同的目標(biāo)集群,得到目標(biāo)數(shù)量的估計(jì)并分別計(jì)算其待估計(jì)參數(shù)信息。

距離-多普勒空間上的多目標(biāo)識(shí)別判斷可采用多種方法,諸如聚類分析［5-9］方法以及基于概率統(tǒng)計(jì)的似然估計(jì)方法等。其中似然估計(jì)的方法雖具有很高的性能以及穩(wěn)健性,但沉重的計(jì)算量負(fù)擔(dān)限制了其在彈載環(huán)境的應(yīng)用；聚類分析方法在實(shí)際應(yīng)用中較為常用,其性能并非最佳,但實(shí)現(xiàn)性較好。根據(jù)彈載雷達(dá)工作環(huán)境(機(jī)載、地面雷達(dá))相對(duì)干凈、可用資源比較有限等特點(diǎn),聚類分析成為主要應(yīng)用方向。

聚類分析應(yīng)用于彈載雷達(dá)擴(kuò)展目標(biāo)區(qū)分,還存在一些問題。首先,彈載雷達(dá)雖然能夠獲得目標(biāo)的一些指示信息,但對(duì)于指示區(qū)域內(nèi)的集群目標(biāo)、以及存在欺騙式干擾時(shí),現(xiàn)有的很多聚類分析方法仍需要獲得分析區(qū)域內(nèi)目標(biāo)數(shù)量等難以獲得的先驗(yàn)信息；其次,為提高彈載雷達(dá)對(duì)擴(kuò)展目標(biāo)的識(shí)別性能,其CFAR檢測(cè)的虛警概率往往設(shè)置較高,分析區(qū)域內(nèi)的大量虛警孤立點(diǎn)也會(huì)造成常用聚類分析方法失效。針對(duì)這些問題,提出一種改進(jìn)的ISODATA的無先驗(yàn)擴(kuò)展目標(biāo)聚類分析算法。

1 現(xiàn)有聚類算法分析

1.1 聚類依據(jù)

聚類分析的基礎(chǔ)是對(duì)象的相似性(或相異性),評(píng)價(jià)相似性最常用的方法是基于距離計(jì)算,距離越短相似性越大。明氏距離定義如下：

式中：q＞0；p為空間維數(shù)。當(dāng)q取為2時(shí),該距離即轉(zhuǎn)化為歐幾里得距離：

歐幾里得距離也是聚類分析中最常用的距離計(jì)算方法。

在完成對(duì)樣本相似性的測(cè)量之后,聚類分析通過準(zhǔn)則函數(shù)聚合同類樣本,同時(shí)將不同類的樣本分離。在這里準(zhǔn)則函數(shù)被用于評(píng)價(jià)聚類質(zhì)量,如果聚類質(zhì)量滿足要求,則輸出聚類結(jié)果,否則重復(fù)執(zhí)行聚類過程以優(yōu)化聚類結(jié)果。

最常用的聚類準(zhǔn)則函數(shù)是誤差平方和準(zhǔn)則函數(shù)Jc。對(duì)于樣本集X=﹛x1,...,xn﹜,在完成相似性測(cè)量后聚類為C個(gè)分離子集﹛X1,…,XC﹜(分別包含n1,…,nC個(gè)樣本),為衡量聚類質(zhì)量,可采用如下誤差平方和準(zhǔn)則函數(shù)：

1.2 典型聚類算法

基于距離的聚類算法認(rèn)為,兩個(gè)樣本之間的距離越接近,則相似性就越大,由距離接近的多個(gè)樣本組成的子集可以被認(rèn)為是同類,這一類方法中比較經(jīng)典的一種就是K-means算法［8］。K-means算法應(yīng)用的數(shù)學(xué)工具不多,但卻是一種有效的聚類方法,其基本流程如下：

(1)隨機(jī)選取初始聚類中心；

(2)計(jì)算樣本到各個(gè)聚類中心的距離；

(3)按距離將樣本歸到最近聚類中心所在類；

(4)重新計(jì)算調(diào)整后的聚類中心；

(5)重復(fù)步驟(2)～(4),直至聚類中心不再變化。

K-means算法流程實(shí)現(xiàn)簡(jiǎn)單,物理概念清晰,時(shí)間復(fù)雜性接近線性,適用于大量數(shù)據(jù)的聚類分析處理,但也存在如下缺點(diǎn)：

(1)需要聚類個(gè)數(shù)的先驗(yàn)信息；

(2)初始值的選取對(duì)聚類結(jié)果影響很大,選取不當(dāng)可能導(dǎo)致陷入局部極小解,準(zhǔn)確的聚類需要一定的先驗(yàn)信息；

(3)對(duì)噪聲點(diǎn)和孤立點(diǎn)敏感；

(4)一般只能發(fā)現(xiàn)球狀類。

在彈載雷達(dá)應(yīng)用環(huán)境中,由于目標(biāo)的個(gè)數(shù)、初始位置及擴(kuò)展目標(biāo)類型等先驗(yàn)信息難以獲得,噪聲/雜波環(huán)境下的虛警往往以孤立點(diǎn)形式頻繁出現(xiàn),且距離-速度譜檢測(cè)一般也不具備圓形特征,所以經(jīng)典的K-means算法難以直接應(yīng)用于工程實(shí)踐。自組織迭代數(shù)據(jù)(Iterative Self-Organizing Data)分析方法［9］是一種可滿足上述要求的聚類分析方法。

ISODATA算法也是聚類分析中的一種常用方法,是對(duì)K-means算法的改進(jìn),屬于無監(jiān)督分類算法的一種。ISODATA算法通過迭代的方式進(jìn)行聚類分析,動(dòng)態(tài)、自適應(yīng)地進(jìn)行類的“合并”和“分裂”,不斷更新數(shù)量、中心等聚類信息,逐步逼近聚類的最優(yōu)結(jié)果。在迭代運(yùn)算中,ISODATA算法能夠汲取過程經(jīng)驗(yàn)并使用,體現(xiàn)了ISODATA算法的自組織性和人機(jī)交互性,同時(shí)也反映了人們對(duì)自然事物認(rèn)知的客觀過程。

2 改進(jìn)的ISODATA算法

如前所述,ISODATA算法能夠在沒有準(zhǔn)確的目標(biāo)數(shù)量信息條件下,自組織地通過分裂與合并操作完成聚類,且對(duì)初始值的選取依賴性小；而且算法正常運(yùn)作所需類內(nèi)最少樣本Qn、偏移量標(biāo)準(zhǔn)差門限Qs等先驗(yàn)信息,對(duì)于目標(biāo)類型基本可控的彈載雷達(dá)也易于提供。因此ISODATA算法與彈載雷達(dá)應(yīng)用需求十分吻合。

需要注意的是,常規(guī)的ISODATA算法同樣存在與K-mean算法相似的對(duì)噪聲點(diǎn)和孤立點(diǎn)敏感問題,并且未考慮距離-速度譜二維檢測(cè)的不同量綱以及分布散布問題,針對(duì)這一情況提出如下改進(jìn)算法：

第零步,檢測(cè)譜初始化：

(1)二維譜量綱歸一化：根據(jù)目標(biāo)可能的距離、速度分布信息,分別在二維譜距離、速度維乘以適當(dāng)?shù)某叨茸儞Q系數(shù),使得目標(biāo)散射點(diǎn)比較均勻地散布在新二維譜的指定半徑Q圓內(nèi)。這一散布區(qū)間可同時(shí)為后續(xù)算法的初始化參數(shù)使用；

(2)對(duì)檢測(cè)譜內(nèi)所有散射點(diǎn)進(jìn)行遍歷分析,凡周圍指定范圍內(nèi)(此處取為1.5Q)其他散射點(diǎn)數(shù)量少于目標(biāo)最少散射點(diǎn)個(gè)數(shù)一半的,認(rèn)為是孤立點(diǎn)并予以剔除。

第一步,參數(shù)初始化：

(1)最大聚心數(shù)C：按照分析區(qū)域內(nèi)最大可能出現(xiàn)的目標(biāo)個(gè)數(shù)確定；

(2)初始聚心數(shù)Nc：如有先驗(yàn)信息則依此設(shè)定,否則可將二維譜劃分為若干均勻區(qū)間并按區(qū)間數(shù)設(shè)定；

(3)判定為目標(biāo)所需最少散射點(diǎn)個(gè)數(shù)Qn：可按裝訂目標(biāo)類型先驗(yàn)信息設(shè)定。當(dāng)信噪比較低時(shí),對(duì)同樣目標(biāo)恒虛警檢測(cè)輸出散射點(diǎn)減少,所以Qn的設(shè)定必須參考最低可檢測(cè)信噪比；

(4)合并兩個(gè)類的最大聚心距離Qd：一般取為目標(biāo)圓半徑Q左右即可；

(5)分裂一個(gè)類的最小類內(nèi)標(biāo)準(zhǔn)差門限Qs：可根據(jù)目標(biāo)散射點(diǎn)分布的先驗(yàn)信息,統(tǒng)計(jì)后使用；

(6)聚心距離誤差和L：根據(jù)所需精度確定；

(7)迭代次數(shù)I和迭代次數(shù)計(jì)數(shù)器Counter：根據(jù)所需精度確定。

第二步,聚心初始化：

(1)若有先驗(yàn)信息則依此設(shè)定；

(2)若無先驗(yàn)信息則可將二維譜劃分為若干均勻區(qū)間,將每個(gè)區(qū)間中心設(shè)為初始聚心。

第三步,開始迭代：

Counter計(jì)數(shù)若等于I,則跳出循環(huán)轉(zhuǎn)向第九步；否則進(jìn)入第四步。

第四步,散射點(diǎn)聚類：

(1)計(jì)算各個(gè)散射點(diǎn)與各聚心之間的距離,按照最近鄰原則將ScatNum個(gè)散射點(diǎn)分別歸入Nc個(gè)類中,距離計(jì)算公式參考前文歐式距離公式；

(2)針對(duì)每個(gè)類,利用其中的散射點(diǎn)重新計(jì)算聚心,公式如下：

(3)如果一個(gè)類中散射點(diǎn)數(shù)量少于最小散射點(diǎn)個(gè)數(shù)Qn,則取消該類,類內(nèi)各散射點(diǎn)就近分配至其他類,并更新聚心。

第五步,類內(nèi)信息計(jì)算：

(1)計(jì)算每個(gè)類中各個(gè)散射點(diǎn)到聚心的平均距離DAvg；

(2)計(jì)算每個(gè)類中各個(gè)散射點(diǎn)到聚心的距離標(biāo)準(zhǔn)差Qstd。

第六步,分裂處理：

(1)對(duì)于某個(gè)類,如果該類內(nèi)的距離標(biāo)準(zhǔn)差Qstd大于標(biāo)準(zhǔn)差門限Qs,且類內(nèi)散射點(diǎn)個(gè)數(shù)不小于Qn的2倍,則將該類分為兩類,同時(shí)修改Nc；

(2)新類聚心可以設(shè)定為(mj1,mj2±DAvg/2)或(mj1±DAvg/2,mj2),根據(jù)新分類距離標(biāo)準(zhǔn)差選取。

第七步,合并處理：

(1)計(jì)算兩兩聚心之間的距離,如果距離小于Qd,則合并這兩類；

(2)更新合并后類的聚心,更新Nc。

第八步,迭代判斷：

若類數(shù)Nc無變化,且聚心與上次迭代之間的距離差小于L,則停止迭代,轉(zhuǎn)入第九步；否則跳轉(zhuǎn)回第三步。

第九步,迭代輸出：

根據(jù)聚類結(jié)果,估計(jì)Nc類,即Nc個(gè)目標(biāo)的參數(shù)。

3 數(shù)字仿真

3.1 基本仿真環(huán)境

本文利用某高分辨PD雷達(dá)體目標(biāo)模型,在Matlab中進(jìn)行數(shù)字仿真。使用三個(gè)體目標(biāo),參數(shù)設(shè)置如下：

目標(biāo)1：模糊距離R=100 m,模糊速度υ=50 m/s,SNR=20 dB；

目標(biāo)2：模糊距離R=110 m,模糊速度υ=48 m/s,SNR=15 dB；

目標(biāo)3：模糊距離R=160 m,模糊速度υ=30m/s,SNR=20 dB。

原始二維距離-速度相參積累譜如圖1所示。

圖1 體目標(biāo)二維速度-距離譜

聚類分析所用檢測(cè)輸出點(diǎn)陣圖基于OSCFAR算法一維距離像檢測(cè)形成,檢測(cè)輸出如圖2所示,檢測(cè)結(jié)果以離散點(diǎn)形式出現(xiàn)。

圖2 距離-速度譜檢測(cè)點(diǎn)陣圖

3.2 算法仿真

3.2.1 仿真初始條件

ISODATA算法初始參數(shù)如下所示：

a.最大聚心數(shù)C=25

b.初始聚心數(shù)Nc=25或1

c.類內(nèi)最少散射點(diǎn)個(gè)數(shù)Qn=10

d.合并兩個(gè)類的最大聚心距離Qd=8

e.分裂一個(gè)類的最小類內(nèi)均方差Qs=3

f.聚心距離誤差和L=2

g.迭代次數(shù)I=10

其中初始聚心的定義中將目標(biāo)附近劃分為5×5區(qū)間,并定義區(qū)間中心為所需聚心。聚心坐標(biāo)定義如表1所示。

表1 聚心坐標(biāo)定義

3.2.2 常規(guī)ISODATA算法聚類仿真

依據(jù)前述仿真條件及初始參數(shù),選擇25點(diǎn)初始聚心,使用常規(guī)ISODATA算法進(jìn)行仿真,由于常規(guī)算法未考慮量綱歸一化以及孤立點(diǎn)的影響,聚類過程始終無法收斂。經(jīng)過10次迭代后,輸出的聚類結(jié)果如圖3所示,顯然無法正確分類三個(gè)體目標(biāo)的散射點(diǎn)。

圖3 常規(guī)ISODATA算法聚類結(jié)果

3.2.3 聚類仿真1

仍使用前述仿真條件及初始參數(shù)、如上25點(diǎn)初始聚心進(jìn)行仿真。初始狀態(tài)及聚類結(jié)果分別如圖4～7所示。

圖4中,在初始狀態(tài)下,改進(jìn)ISODATA算法對(duì)孤立點(diǎn)的剔除顯然十分有效,三個(gè)體目標(biāo)的散射點(diǎn)全部保留,孤立點(diǎn)順利標(biāo)志出來并剔除,并未對(duì)后續(xù)聚類處理造成不利影響。另外,由于初始聚類中心分布較密,所有三個(gè)體目標(biāo)內(nèi)的散射點(diǎn)均被分割到了四個(gè)不同的初始類中。

圖4 改進(jìn)ISODATA算法聚類初始狀態(tài)

圖5～7中,在初始化處理的基礎(chǔ)上,改進(jìn)的ISODATA算法僅經(jīng)歷3次迭代后給出最終的聚類分析結(jié)果。迭代過程及最終結(jié)果顯示,算法“分裂”與“合并”操作正常起作用,使得三個(gè)目標(biāo)在3次迭代后正確聚類(事實(shí)上兩次迭代即完成分類,第3次確認(rèn)),完成目標(biāo)輸出。輸出目標(biāo)聚類中心分別為(113.9 m,48.1 m/s),(102.8 m,50.3 m/s), (165.4 m,30.1 m/s),與預(yù)設(shè)目標(biāo)基本一致。

圖5 改進(jìn)ISODATA算法第1次迭代輸出

圖6 改進(jìn)ISODATA算法第2次迭代輸出

圖7 改進(jìn)ISODATA算法聚類完成狀態(tài)

3.2.4 聚類仿真2

針對(duì)單一初始聚心(150 m,41.85 m/s)設(shè)置,采用同樣的輸入圖譜和初始參數(shù)進(jìn)行仿真,仿真結(jié)果如圖8～9所示。

圖8 改進(jìn)ISODATA算法聚類初始狀態(tài)

圖9 改進(jìn)ISODATA算法聚類完成狀態(tài)

此次仿真經(jīng)歷4次迭代達(dá)到收斂,輸出聚類的數(shù)量與中心正確,同樣顯示了算法的有效性。即使在沒有任何先驗(yàn)?zāi)繕?biāo)數(shù)量和位置信息的條件下,改進(jìn)ISODATA算法仍然可以通過自適應(yīng)的“分裂”與“合并”操作完成目標(biāo)的正確聚類,顯示了算法的穩(wěn)健性。

4 結(jié) 論

本文針對(duì)彈載雷達(dá)擴(kuò)展目標(biāo)檢測(cè)區(qū)分的需求,提出了一種有效的改進(jìn)的ISODATA聚類分析算法,并給出算法流程。數(shù)字仿真結(jié)果顯示：新算法對(duì)目標(biāo)數(shù)量、位置等彈載環(huán)境難以獲得的先驗(yàn)信息無依賴,受分析區(qū)間內(nèi)孤立噪聲點(diǎn)的影響小,能夠穩(wěn)健區(qū)分二維譜上的多個(gè)臨近目標(biāo),與窄帶恒虛警檢測(cè)算法配合可以有效解決多個(gè)擴(kuò)展目標(biāo)的檢測(cè)與區(qū)分工作。

［1］Gerlach K,Steiner M J.Adaptive Detection of Range Distributed Targets［J］.IEEE Transaction on Signal Processig,1999,8(27)：1844-1851.

［2］孫以平,陸林根.距離擴(kuò)展目標(biāo)檢測(cè)的研究［J］.系統(tǒng)工程與電子技術(shù),1994,16(8)：35-36.

［3］楊建宇,李俊生.高分辨率雷達(dá)目標(biāo)的隨機(jī)參量脈沖串檢測(cè)方法［J］.電子學(xué)報(bào),2004,32(6)：1044-1046.

［4］Liu Yongtan.Target Detection and TracKing with a High Frequency Ground Wave Over-the-Horizon Radar［C］// 1996 CIE International Conference of Radar Proceedings, Beijing,1996：29-33.

［5］Han Jiawei,Kambr M.Data Mining：Concepts and Techniques［M］.San Francisco：Morgan Kaufrnann Publishers,2001.

［6］李曉冰,馬海潮,高冰.一種基于C-均值聚類的測(cè)量圖像增強(qiáng)算法［J］.航空兵器,2008(4)：32-38.

［7］Ester M,Kriegel H P,Sander J,et al.A Density-Based Algorithm for Discovering Clusters in Large Spatial Databaseswith Noise［C］//Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96),Proland,Oregon,1996.

［8］Macqueen J.Some Methods for Classification and Analysis of Multivatiate Observations［C］//Proceedings of 5th BerKeley Symposium on Mathematical Statistics and Probability,1967：281-297.

［9］Memarsadeghi N,Mount D M,Netanyahu S.A Fast Implementation of the ISODATA Clustering Algorithm［J］. International Journal of Computational Geometry&Applications,2007,17(1)：71-103.

Clustering Analysis Algorithm of Extended Targetswithout Prior Information Based on Improved ISODATA

Wu Xianglin1,2,Yang Shiyi3
(1.China Airborne Missile Academy,Luoyang 471009,China；2.Aviation Key Laboratory of Science and Technology on Airborne Guided Weapons,Luoyang 471009,China；3.PLA's Military Representative Office in China Airborne Missile Academy,Luoyang 471009,China)

Based on CFAR detection output,an improved iterative self-organizing data analysis (ISODATA)algorithm is presented formulti-extended targets detection requirements ofmissile-borne radar.This algorithm can get rid of the influence of common clustering analysis algorithm on the prior information requirements,such as target number,clustering initial value,which can eliminate the effect on isolated points.Simulation results verify the algorithm effectiveness.

extended target；clustering；missile-borne radar；improved ISODATA algorithm

TJ765.3+31

A

1673-5048(2015)03-0033-05

2014-12-25

吳湘霖（1977-），男，浙江寧波人，高級(jí)工程師，研究方向是雷達(dá)導(dǎo)引頭總體設(shè)計(jì)、總體算法設(shè)計(jì)。