基于改進ISODATA的無先驗擴展目標(biāo)聚類分析算法

吳湘霖，楊士義

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

基于改進ISODATA的無先驗擴展目標(biāo)聚類分析算法

吳湘霖1，2，楊士義3

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

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

擴展目標(biāo)；聚類；彈載雷達；改進的ISODATA算法

0 引 言

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

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

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

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

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

1.1 聚類依據(jù)

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

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

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

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

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

1.2 典型聚類算法

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

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

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

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

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

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

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

(1)需要聚類個數(shù)的先驗信息；

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

(3)對噪聲點和孤立點敏感；

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

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

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

2 改進的ISODATA算法

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

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

第零步,檢測譜初始化：

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

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

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

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

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

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

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

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

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

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

第二步,聚心初始化：

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

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

第三步,開始迭代：

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

第四步,散射點聚類：

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

(2)針對每個類,利用其中的散射點重新計算聚心,公式如下：

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

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

(1)計算每個類中各個散射點到聚心的平均距離DAvg；

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

第六步,分裂處理：

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

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

第七步,合并處理：

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

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

第八步,迭代判斷：

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

第九步,迭代輸出：

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

3 數(shù)字仿真

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

本文利用某高分辨PD雷達體目標(biāo)模型,在Matlab中進行數(shù)字仿真。使用三個體目標(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)二維速度-距離譜

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

圖2 距離-速度譜檢測點陣圖

3.2 算法仿真

3.2.1 仿真初始條件

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

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

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

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

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

e.分裂一個類的最小類內(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點初始聚心,使用常規(guī)ISODATA算法進行仿真,由于常規(guī)算法未考慮量綱歸一化以及孤立點的影響,聚類過程始終無法收斂。經(jīng)過10次迭代后,輸出的聚類結(jié)果如圖3所示,顯然無法正確分類三個體目標(biāo)的散射點。

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

3.2.3 聚類仿真1

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

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

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

圖5～7中,在初始化處理的基礎(chǔ)上,改進的ISODATA算法僅經(jīng)歷3次迭代后給出最終的聚類分析結(jié)果。迭代過程及最終結(jié)果顯示,算法“分裂”與“合并”操作正常起作用,使得三個目標(biāo)在3次迭代后正確聚類(事實上兩次迭代即完成分類,第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 改進ISODATA算法第1次迭代輸出

圖6 改進ISODATA算法第2次迭代輸出

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

3.2.4 聚類仿真2

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

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

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

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

4 結(jié) 論

本文針對彈載雷達擴展目標(biāo)檢測區(qū)分的需求,提出了一種有效的改進的ISODATA聚類分析算法,并給出算法流程。數(shù)字仿真結(jié)果顯示：新算法對目標(biāo)數(shù)量、位置等彈載環(huán)境難以獲得的先驗信息無依賴,受分析區(qū)間內(nèi)孤立噪聲點的影響小,能夠穩(wěn)健區(qū)分二維譜上的多個臨近目標(biāo),與窄帶恒虛警檢測算法配合可以有效解決多個擴展目標(biāo)的檢測與區(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］孫以平,陸林根.距離擴展目標(biāo)檢測的研究［J］.系統(tǒng)工程與電子技術(shù),1994,16(8)：35-36.

［3］楊建宇,李俊生.高分辨率雷達目標(biāo)的隨機參量脈沖串檢測方法［J］.電子學(xué)報,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-均值聚類的測量圖像增強算法［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-），男，浙江寧波人，高級工程師，研究方向是雷達導(dǎo)引頭總體設(shè)計、總體算法設(shè)計。