?

一種新的k-means聚類雷達信號分選算法*1

張冉1，夏厚培2

(1.南京信息工程大學 電子與信息工程學院， 江蘇 南京210044；

2.中國船舶重工集團 第七二四研究所，江蘇 南京210003)

摘要：針對傳統(tǒng)k-means聚類算法在雷達信號分選中應(yīng)用存在的不足，提出了一種基于數(shù)據(jù)場和灰關(guān)聯(lián)分析的k-means聚類雷達信號分選算法。該算法首先根據(jù)數(shù)據(jù)場理論計算所有數(shù)據(jù)樣本的勢值，尋找局域勢值最大值，選取距最大值最近的樣本數(shù)據(jù)作為初始聚類中心，局域勢值最大值個數(shù)作為聚類數(shù)目；然后用灰關(guān)聯(lián)度代替歐式距離來判斷數(shù)據(jù)樣本間相似性。該算法能夠自動獲取初始聚類中心和聚類數(shù)目，對頻率捷變雷達具有較好的分選效果。仿真結(jié)果驗證了算法的可行性。

關(guān)鍵詞：雷達信號分選；k-means聚類；聚類中心和數(shù)目；數(shù)據(jù)場理論；灰關(guān)聯(lián)分析；頻率捷變

0引言

復雜電磁環(huán)境下雷達信號分選是雷達偵察系統(tǒng)的重要組成部分，只有在正確分選基礎(chǔ)上，才能對雷達信號進行參數(shù)估計和提取[1]。在現(xiàn)代化戰(zhàn)爭中，新體制雷達大量出現(xiàn)并列入裝備使用，信號形式復雜，脈沖密度越來越高，基于PRI單參數(shù)的傳統(tǒng)分選方法已不能適應(yīng)當前分選需要[2]。k-means聚類算法是一種無監(jiān)督實時分類方法，該算法收斂快、易于實現(xiàn)、思想簡單、不需要先驗信息[3]，但聚類數(shù)目需要人為預(yù)先確定，初始聚類中心隨機選取，數(shù)據(jù)樣本相似性用多個參數(shù)的歐式距離來判斷，但在空間距離上相近的數(shù)據(jù)并不一定具有高的相似性[4]，這些限制了k-means聚類算法在雷達信號分選中的應(yīng)用。

為了解決k-means聚類算法在雷達信號分選中應(yīng)用存在的問題，學者們提出來很多算法。文獻[5]通過相像系數(shù)來代替歐氏距離，用小波系數(shù)和傳統(tǒng)參數(shù)聯(lián)合分選，分選準確率可達到96.2%，但該方法不能自動獲取初始聚類中心和聚類數(shù)目。文獻[6]聯(lián)合蟻群算法和k-means聚類算法，用蟻群算法來確定聚類中心和聚類數(shù)目，得到了理想的分選效果，但數(shù)據(jù)樣本相似性仍然用歐式距離來衡量。針對上述問題，本文將數(shù)據(jù)場理論和灰關(guān)聯(lián)分析相結(jié)合應(yīng)用到雷達信號分選中來，提出了一種新的k-means聚類雷達信號分選算法。該算法根據(jù)數(shù)據(jù)勢場分布來得到初始聚類中心和聚類數(shù)目，用灰關(guān)聯(lián)度來代替歐式距離來判斷數(shù)據(jù)樣本相似性。該方法能自動獲取初始聚類中心，無需人為指定聚類數(shù)，不需要先驗信息，對頻率捷變雷達有較分選效果。

1k-means聚類原理

J.B.MacQueen提出的k-means算法是一種非監(jiān)督實時聚類算法，在準則函數(shù)收斂基礎(chǔ)上將數(shù)據(jù)樣本分成m類[7-9]。設(shè)有n個PDW(脈沖描述字)樣本集：

PDW=(PDW1,PDW2,…,PDWn)，

每一個PDW樣本包含以下5個參數(shù)：到達時間(TOA)、脈沖頻率(RF)、脈沖幅度(PA)、脈沖寬度(PW)、到達角(DOA),即PDWi=(TOAi,RFi,PAi,PWi,DOAi)，聚類數(shù)目m是預(yù)先確定的，隨機選取m個初始聚類中心，按照最小距離原則將各樣本歸類到m個類的某一類，然后不斷計算聚類中心和調(diào)整類，最后當各樣本到各中心的距離平方之和最小時，分類結(jié)束。其步驟為：

(3) 重新調(diào)整分類后的各聚類中心：

k-means算法是基于局部最優(yōu)的聚類分析算法，不同的初始聚類中心和聚類數(shù)目可能得到不同的分析結(jié)果，因此合適的選取初始聚類中心和聚類個數(shù)顯得尤為重要。

2新的k-means聚類雷達信號分選算法

2.1數(shù)據(jù)場

根據(jù)數(shù)據(jù)場理論，數(shù)據(jù)空間中的數(shù)據(jù)不是孤立的，而是通過數(shù)據(jù)場這個客觀存在的媒介與其他數(shù)據(jù)相互作用[10-11]。類比物理學中的電場和引力場，定義數(shù)據(jù)間相互作用的影響函數(shù)為場強函數(shù)：

(1)

式中：σ為輻射因子；ρ反應(yīng)數(shù)據(jù)點的數(shù)據(jù)量，一般取1；d(x,y)為歐式距離。

每一數(shù)據(jù)對數(shù)據(jù)場中其它任何數(shù)據(jù)都輻射能量，那么任一點的場強就是所有這些能量在此點的代數(shù)和，稱為此處數(shù)據(jù)場的勢，根據(jù)場強函數(shù)可以得到數(shù)據(jù)場的勢函數(shù)：

(2)

式中：n為數(shù)據(jù)的數(shù)量。

由式(2)可知，勢函數(shù)由位置和距離決定，勢值大小和兩者距離成反比。一般來說，勢值大的區(qū)域數(shù)據(jù)密集，勢值小的區(qū)域數(shù)據(jù)稀疏。

2.2初始聚類中心的確定

將數(shù)據(jù)場中勢值相等的點連起來形成的線稱為等勢線，等勢線圍繞形成的不同中心稱為勢心[12]。勢心是大量數(shù)據(jù)樣本在一個或者一個以上的屬性數(shù)據(jù)值中所體現(xiàn)出來的極值特征，單個數(shù)據(jù)的勢心就是數(shù)據(jù)本身所在的位置，從等勢線圖中可以發(fā)現(xiàn)勢心的位置，其數(shù)學語言描述為

Fmax≥Fy(i,j)，

(3)

式中：Fmax為勢心值；Fy(i,j)為勢心周圍的勢值；(i,j)為點的位置。

由式(3)可知，勢心就是在一定范圍內(nèi)勢值極大值點，通過勢心就能確定初始聚類中心和聚類數(shù)目，但勢值是疊加作用的結(jié)果，勢心不一定和空間數(shù)據(jù)樣本重合，應(yīng)該選擇距離勢心最近的數(shù)據(jù)樣本為初始聚類中心，數(shù)學表達式為

Dmin=d|Fmax,data(i,j)|，

(4)

Fcenter=data(i,j)，

(5)

式中：data(i,j)表示任意數(shù)據(jù)；d代表某種距離運算(這里采用歐式距離)；Fcenter為初始聚類中心。

2.3灰關(guān)聯(lián)分析

傳統(tǒng)的k-means聚類算法中，脈沖相似性常常用歐式距離來衡量，但在空間上相近的數(shù)據(jù)并不一定具有高的相似性，而灰關(guān)聯(lián)度根據(jù)整體相似性來衡量數(shù)據(jù)之間的距離，能克服這個問題[13-16]。計算數(shù)據(jù)樣本間灰關(guān)聯(lián)度有以下幾個步驟：

(1) 數(shù)據(jù)樣本標準化處理

在實際的雷達信號偵察中，偵收到的信號比較復雜，不同參數(shù)數(shù)據(jù)不在同一數(shù)量級上，為保證數(shù)據(jù)具有可比性，在灰關(guān)聯(lián)分析時，需要對數(shù)據(jù)集中所有參數(shù)維數(shù)進行歸一化處理[12]，根據(jù)如下公式進行標準化處理：

(6)

(2) 計算關(guān)聯(lián)系數(shù)

將式(5)得到的Fcenter作為參考序列，為表示方便，這里表示為X0(j)，偵察雷達偵收到的序列Xi(j)作為比較序列，則第i個比較序列的第j維的絕對差為

Δi(j)=|X0(j)-Xi(j)|，

(7)

則兩者關(guān)聯(lián)系數(shù)為

(8)

ξi={ξi(j),j=1,2,…,N}.

(9)

(3) 計算灰關(guān)聯(lián)度

將各維的關(guān)聯(lián)系數(shù)用一個值來表示，這個值就是灰關(guān)聯(lián)度。Xi(j)和X0(j)的關(guān)聯(lián)度為

(10)

灰關(guān)聯(lián)度越大，說明Xi(j)和X0(j)的相似性越大，反之越小。

2.4新的k-means聚類雷達信號分選算法

這里對傳統(tǒng)k-means聚類算法進行改進，并應(yīng)用到雷達信號分選中。首先通過數(shù)據(jù)場理論計算所有數(shù)據(jù)樣本的勢值，在一定范圍內(nèi)尋找勢值最大值來確定初始聚類中心，勢值最大值個數(shù)來確定聚類數(shù)目；再用灰關(guān)聯(lián)度來描述脈沖間相似性。在偵收到的雷達信號5個參數(shù)：TOA，DOA，RF，PW，PA中，根據(jù)TOA可以得到脈沖重復頻率(PRI)，PRI工作方式多、變化快，一般不作為分選的依據(jù)，PA隨著天線的掃描而變化，因此本文用DOA，RF，PW進行分選。新的算法步驟如下：

(1) 根據(jù)DOA，RF，PW3個參數(shù)按照式(6)進行標準化處理。

(2) 按照式(2)計算每個數(shù)據(jù)點的勢值，再根據(jù)式(4)，(5)找出距局域勢值最大值最近的樣本數(shù)據(jù)作為初始聚類中心，局域勢值個數(shù)作為聚類數(shù)目。

(3) 根據(jù)式(7)～(10)計算每個樣本數(shù)據(jù)和初始聚類中心的灰關(guān)聯(lián)度，將灰關(guān)聯(lián)度最大的劃分到該聚類中心所在的類。

(4) 對于每一類，重新計算聚類中心，

若2次計算出的聚類中心沒有變化，則聚類準則函數(shù)收斂，算法結(jié)束。否則轉(zhuǎn)到步驟(3)。

3仿真分析

為驗證本文方法的有效性，用Matlab進行仿真試驗。在實際工程中，雷達體制復雜，脈沖流在時間上交錯，并且脈沖部分參數(shù)交疊，例如2部頻率捷變雷達參數(shù)在頻域上交疊，因此這里選取4部頻率捷變進行試驗，在很短時間內(nèi)，DOA可以認為是不變的，但是RF，PW是變化的，不考慮脈沖丟失，每部雷達信號參數(shù)都加入了測量誤差，仿真參數(shù)如表1。

數(shù)據(jù)經(jīng)標準化處理后，根據(jù)數(shù)據(jù)場理論通過勢函數(shù)計算所有數(shù)據(jù)樣本勢值來描述雷達信號參數(shù)分布情況從而確定初始聚類中心和聚類數(shù)目，如圖1～3所示。從圖中可以比較直觀的看到雷達信號可分為4類，通過計算距勢值最大值點最近的樣本數(shù)據(jù)可得到初始聚類中心，如表2。然后按照本文算法步驟(3)，(4)對數(shù)據(jù)進行分選，最終的聚類中心如表3。比較表2和表3可知，初始聚類中心選取是合理的。

圖1　載頻和脈寬等勢線分布Fig.1　Equipotential line distribution of carrier　　　frequency and pulse width

圖2　到達角和載頻等勢線分布Fig.2　Equipotential line distribution of arrival　　　angle and carrier frequency

圖3　脈寬和到達角等勢線分布Fig.3　Equipotential line distribution of pulse　　　width and arrival angle

雷達輻射源序號DOA/(°)RF/MHzPRI/μsPW/μs脈沖數(shù)1353170～3426載頻捷變175～180重頻抖動8.36～12.68脈寬抖動2882372836～3462載頻捷變140～185重頻抖動10.75～16.24脈寬抖動3423393430～3867載頻捷變189～241重頻抖動16.63～20.42脈寬抖動2534412955～3142載頻捷變152～181重頻抖動19.30～23.66脈寬抖動279

表2　初始聚類中心

表3　最終聚類中心

為了比較本文算法和傳統(tǒng)k-means算法的分選效果，用k-means算法處理試驗數(shù)據(jù)，考慮到k-means算法隨機選取聚類中心和聚類數(shù)目，會得到不同的結(jié)果，故這里仿真100次，然后取統(tǒng)計平均。所得分選結(jié)果和本文算法分選結(jié)果比較如表4所示。

表4　k-means算法和本文算法效果比較

從表4可以看出，本文算法迭代次數(shù)減少，正確分選概率得到提高。

4結(jié)束語

本文對在雷達信號分選中得到廣泛應(yīng)用的k-means算法進行了改進，首先用數(shù)據(jù)場理論自動獲取初始聚類中心，確定聚類數(shù)目，然后用灰關(guān)聯(lián)分析代替歐式聚類來判斷脈沖相似性。本文算法能自動獲取初始聚類中心，確定聚類數(shù)目，不需任何先驗信息支撐，對單個參數(shù)不超過30%交疊或者2個參數(shù)不同時交疊的頻率捷變雷達有很好的分選效果。文中的仿真實例證明了該算法的有效性。但本文算法也有局限性，因為沒有考慮噪聲孤立點對聚類中心的影響，故本文算法只適用于接收信號信噪比很高情況，若信噪比較低，要先將噪聲孤立點去除，然后再用該算法。

參考文獻：

[1]國強.復雜環(huán)境下未知雷達輻射源信號分選的理論研究[D].哈爾濱：哈爾濱工程大學，2007.

GUO Qiang.Signal Sorting Methods for Unknown Radar Emitters in Complex Environments[D].Harbin:Harbin Engineering University,2007.

[2]梅桂圓.密集信號環(huán)境下雷達信號分選算法[D].哈爾濱：哈爾濱工程大學，2011.

MEI Gui-yuan.Radar Signal Sorting Algorithm on Intensive Signal Condition[D]. Harbin:Harbin Engineering University,2011.

[3]JOSHUA Z H,MICHAEL K N,RONG Hong-qiang.Automated Variable Weighting in k-means Type Clustering[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,2005,27(5):657-688.

[4]郭昆，張岐山.基于灰關(guān)聯(lián)分析的多數(shù)據(jù)流聚類[J].模式識別與人工智能，2011,24(6),769-774.

GUO Kun,ZHANG Qi-shan.Multiple Data Streams Clustering Based on Grey Relational Analysis[J].Pattern Recognition and Artificial Intelligence, 2011,24(6),769-774.

[5]馮明月，何明浩，王冰切.基于改進相似熵的參數(shù)交疊雷達信號分選[J]. 電子信息對抗技術(shù)，2013,28(4):1-4.

FENG Ming-yue,HE Ming-hao,WANG Bing-qie.Radar Signal Sorting of Parameters Overlapping Based on Improved Similitiude Entropy[J]. Technology of Electronic Information Confrontation, 2013,28(4):1-4.

[6]趙貴喜，駱魯秦，陳彬.基于蟻群算法的k-均值聚類雷達信號分選算法[J].雷達科學與技術(shù)，2009,7(2):142-145.

ZHAO Gui-xi,LUO Lu-qin,CHEN Bin.Radar Signal Sorting Based on Ant Colony and K-means Clustering[J].Science and Technology of Radar, 2009,7(2):142-145.

[7]GUO Qiang,ZHANG Xing-zhou,LI Zheng.SVC&K-Means and Type-Entropy Based Deinterleaving/Recognition System of Radar Pulse[J].Proceeding of IEEE International Conference on Information Acquisition,2006,20(1):742-747.

[8]孫鑫，侯慧群，楊承志.基于改進K-均值算法的未知雷達信號分選[J].現(xiàn)代電子技術(shù)，2010,17(3):91-93.

SUN Xin,HOU Hui-qun,YANG Cheng-zhi.Unknown Radar Signals Deinterleaving Based on Improved K-Means Algorithm[J]. Modern Electronic Technology, 2010,17(3):91-93.

[9]雍霄駒，張登福，王世強.一種新的雷達輻射源分選算法[J].現(xiàn)代防御技術(shù)，2011,39(3):148-151.

YONG Xiao-ju,ZHANG Deng-fu,WANG Shi-qiang.A New Method of Sorting Radar Emitter Signals[J]. Modern Defense Technology, 2011,39(3):148-151.

[10]吳鵬飛.數(shù)據(jù)場在聚類分析中的應(yīng)用研究[D].包頭：內(nèi)蒙古科技大學，2010.

WU Peng-fei.Research of Data Field in Clustering Analysis[D].Baotou:Inner Mongolia University of Sciecce and Technology,2010.

[11]簡艷，賈洪勇.一種基于數(shù)據(jù)場的k-均值算法[J].計算機應(yīng)用研究，2010,27(12):4498-4501.

JIAN Yan,JIA Hong-yong.k-Means Algorithm Based on Data Field[J].Computer Application Research,2010,27(12):4498-4501.

[12]張紅昌，阮懷林，龔亮亮.一種新的未知雷達輻射源聚類分選方法[J].計算工程與應(yīng)用，2008,44(27):200-202.

ZHANG Hong-chang,RUAN Huai-lin,GONG Liang-liang.New Clustering Approach for Sorting Unknown Radar Emitter Signal[J].Computer Engibeering and Application,2008,44(27):200-202.

[13]陳昊，侯慧群，楊承志，等.基于改進灰關(guān)聯(lián)的雷達輻射源識別方法研究[J].現(xiàn)代防御技術(shù)，2013,41(2):155-159.

CHEN Hao,HOU Hui-qun,YANG Cheng-zhi，et al.Radar Emitter Identification Based on Improved Grey Relation[J].Modern Defense Technology, 2013,41(2):155-159.

[14]關(guān)欣，孫祥威，曹昕瑩.改進的k-mean算法在特征關(guān)聯(lián)中的應(yīng)用[J].雷達科學與技術(shù)，2014,12(1):81-85.

GUAN Xin,SUN Xiang-wei,CAO Xin-ying.A Novel Algorithm for Feature Association Based on Gray Correlation Cluster[J]. Science and Technology of Radar,2014,12(1):81-85.

[15]陳韜偉，金煒東，陳振興.基于灰關(guān)聯(lián)分析的雷達輻射源信號盲分類[J].計算機工程與設(shè)計，2009,30(20):4686-4689.

CHEN Tao-wei,JIN Wei-dong,CHEN Zhen-xing.Blind Classification of Radar Emitter Signals Based on Grey Relation Analysis[J].Computer Engineering and Design, 2009,30(20):4686-4689.

[16]郭昆，張岐山.基于灰關(guān)聯(lián)分析的譜聚類[J].系統(tǒng)工程理論與實踐，2010,30(7):1260-1264.

GUO Kun,ZHANG Qi-shan.Spectral Clustering Based on Grey Relational Analysis[J].Systems Engineering-Theory & Practice, 2010,30(7):1260-1264.

Radar Signal Sorting Algorithm of a New k-means Clustering

ZHANG Ran1, XIA Hou-pei2

(1.Nanjing University of Information Science & Technology,College of Electrics and Information Engineering,Jiangsu Nanjing 210044,China; 2. No.724 Research Institute of CSIC,Jiangsu Nanjing 210003,China)

Abstract:For the defects in the application of radar signal sorting of the tradition k-means clustering algorithm, a radar signal sorting algorithm of k-means clustering is put forward based on data field and grey relational analysis. Firstly potential value of all the data samplesis calculated with the algorithm based on data field theory, to find local maximum potential value, select the maximum value from the recent sample data as the initial clustering center, the number of local maximum potential value as the number of clustering. Then grey relational degree is used to determine the similarity between data sample instead of Euclidean. The algorithm can automatically obtain the initial clustering center and clustering number, so it has a good sort effect of frequency agility radar. The simulation results verify the feasibility of this algorithm.

Key words:radar signal sorting; k-means clustering; cluster center and number; data field theory; grey relational analysis; frequency agility

中圖分類號：TN957.51；TP301.6

文獻標志碼：A

文章編號：1009-086X(2015)-06-0136-06

doi:10.3969/j.issn.1009-086x.2015.06.023

通信地址：210044江蘇省南京市江寧區(qū)水閣路長青街30號E-mail：1044713043@qq.com

作者簡介：張冉(1989-)，男，安徽安慶人。碩士生，主要研究方向為雷達信號處理。

*收稿日期：2014-11-06；修回日期：2015-02-06