基于改進ISODATA的無先驗擴展目標聚類分析算法

吳湘霖，楊士義

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

基于改進ISODATA的無先驗擴展目標聚類分析算法

吳湘霖1，2，楊士義3

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

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

擴展目標；聚類；彈載雷達；改進的ISODATA算法

0 引 言

隨著各種武器系統對作戰能力的要求不斷提高,高速、高機動目標精確碰撞、目標識別與抗干擾等都對彈載雷達的高分辨率參數估計提出了要求。高分辨率雷達使得原先以單一點跡形式出現的目標呈現擴展狀態,可能占據多個分辨單元,這種目標稱為擴展目標［1-3］。

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

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

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

1 現有聚類算法分析

1.1 聚類依據

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

式中：q＞0；p為空間維數。當q取為2時,該距離即轉化為歐幾里得距離：

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

在完成對樣本相似性的測量之后,聚類分析通過準則函數聚合同類樣本,同時將不同類的樣本分離。在這里準則函數被用于評價聚類質量,如果聚類質量滿足要求,則輸出聚類結果,否則重復執行聚類過程以優化聚類結果。

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

1.2 典型聚類算法

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

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

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

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

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

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

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

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

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

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

(4)一般只能發現球狀類。

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

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

2 改進的ISODATA算法

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

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

第零步,檢測譜初始化：

(1)二維譜量綱歸一化：根據目標可能的距離、速度分布信息,分別在二維譜距離、速度維乘以適當的尺度變換系數,使得目標散射點比較均勻地散布在新二維譜的指定半徑Q圓內。這一散布區間可同時為后續算法的初始化參數使用；

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

第一步,參數初始化：

(1)最大聚心數C：按照分析區域內最大可能出現的目標個數確定；

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

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

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

(5)分裂一個類的最小類內標準差門限Qs：可根據目標散射點分布的先驗信息,統計后使用；

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

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

第二步,聚心初始化：

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

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

第三步,開始迭代：

Counter計數若等于I,則跳出循環轉向第九步；否則進入第四步。

第四步,散射點聚類：

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

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

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

第五步,類內信息計算：

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

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

第六步,分裂處理：

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

(2)新類聚心可以設定為(mj1,mj2±DAvg/2)或(mj1±DAvg/2,mj2),根據新分類距離標準差選取。

第七步,合并處理：

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

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

第八步,迭代判斷：

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

第九步,迭代輸出：

根據聚類結果,估計Nc類,即Nc個目標的參數。

3 數字仿真

3.1 基本仿真環境

本文利用某高分辨PD雷達體目標模型,在Matlab中進行數字仿真。使用三個體目標,參數設置如下：

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

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

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

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

圖1 體目標二維速度-距離譜

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

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

3.2 算法仿真

3.2.1 仿真初始條件

ISODATA算法初始參數如下所示：

a.最大聚心數C=25

b.初始聚心數Nc=25或1

c.類內最少散射點個數Qn=10

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

e.分裂一個類的最小類內均方差Qs=3

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

g.迭代次數I=10

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

表1 聚心坐標定義

3.2.2 常規ISODATA算法聚類仿真

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

圖3 常規ISODATA算法聚類結果

3.2.3 聚類仿真1

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

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

圖4 改進ISODATA算法聚類初始狀態

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

圖5 改進ISODATA算法第1次迭代輸出

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

圖7 改進ISODATA算法聚類完成狀態

3.2.4 聚類仿真2

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

圖8 改進ISODATA算法聚類初始狀態

圖9 改進ISODATA算法聚類完成狀態

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

4 結 論

本文針對彈載雷達擴展目標檢測區分的需求,提出了一種有效的改進的ISODATA聚類分析算法,并給出算法流程。數字仿真結果顯示：新算法對目標數量、位置等彈載環境難以獲得的先驗信息無依賴,受分析區間內孤立噪聲點的影響小,能夠穩健區分二維譜上的多個臨近目標,與窄帶恒虛警檢測算法配合可以有效解決多個擴展目標的檢測與區分工作。

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

［2］孫以平,陸林根.距離擴展目標檢測的研究［J］.系統工程與電子技術,1994,16(8)：35-36.

［3］楊建宇,李俊生.高分辨率雷達目標的隨機參量脈沖串檢測方法［J］.電子學報,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-），男，浙江寧波人，高級工程師，研究方向是雷達導引頭總體設計、總體算法設計。