一種新的基于網(wǎng)格聚類的雷達信號預分選算法*

邱磊，楊承志，何佃偉

(空軍航空大學，吉林長春 130022)

0 引言

雷達信號分選是電子對抗情報偵察系統(tǒng)的重要組成部分，在當今戰(zhàn)場中起著重要作用。近幾年，隨著雷達信號環(huán)境日益復雜，許多學者將數(shù)據(jù)挖掘技術(shù)中的聚類分析方法引入到雷達信號分選領(lǐng)域［1-4］。聚類分選算法可以分為基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法、基于網(wǎng)格的聚類以及基于模型的算法等［5-6］?；诰W(wǎng)格的聚類算法具有處理速度快、對輸入數(shù)據(jù)順序不敏感，可以發(fā)現(xiàn)任意形狀類的優(yōu)點［7］，是一種有效的信號預分選算法。

現(xiàn)有的基于網(wǎng)格聚類的預分選算法存在的主要問題有:①網(wǎng)格劃分數(shù)和密度閾值需要人為設(shè)定，②聚類邊界被當作噪聲點丟棄導致聚類精度不高。針對這2個問題，很多學者對算法進行了改進。其中文獻［8］提出了先移除孤立點和噪聲再進行聚類的方法，但它要計算所有脈沖之間的距離，算法復雜度高，難以滿足實時性要求;文獻［9］提出了一種動態(tài)網(wǎng)格聚類預分選算法，算法復雜度較低，但邊界處理效果較差。本文提出了一種新的基于網(wǎng)格聚類的預分選算法。提出了網(wǎng)格數(shù)據(jù)壓縮率概念，首先根據(jù)雷達脈沖數(shù)和網(wǎng)格數(shù)據(jù)壓縮率，自適應(yīng)確定網(wǎng)格劃分和密度閾值，減少了人為因素的影響;其次利用密度閾值去除孤立點和噪聲，對低密度網(wǎng)格進行邊界提取，提高聚類精度。

1 一種新的網(wǎng)格聚類預分選算法

1.1 網(wǎng)格聚類概念

給定d維空間D中的一個點，其屬性(D1，D2，…，Dd)都是有界的，設(shè)第 i維的值在區(qū)間［li，hi］中，其中 i=1，2，…，d。則 D=［l1，h1］×［l2，h2］× … ×［ld，hd］。將D的每一維平均分成K個長度相等的區(qū)間段。這樣將空間D劃分為Kd個子空間。若2個網(wǎng)格單元有相鄰的邊界或頂點，則稱這2個網(wǎng)格相交。相交的2個網(wǎng)格互稱為鄰居。網(wǎng)格單元所包含的數(shù)據(jù)點的個數(shù)稱為該網(wǎng)格單元的網(wǎng)格密度。一個網(wǎng)格單元的網(wǎng)格密度大于或等于給定密度閾值MinPts時，稱該單元為高密度網(wǎng)格，否則稱為低密網(wǎng)格。如果一個低密度網(wǎng)格單元的所有鄰居都是低密度單元，那么該單元中的點為噪聲。一個聚類是相鄰的高密度網(wǎng)格單元的集合。

1.2 算法基本步驟

輸入:3維數(shù)據(jù)集D，數(shù)據(jù)個數(shù)N.

輸出:帶標號的聚類，噪聲點。

(1)讀入數(shù)據(jù)并歸一化，歸一化公式為x～=(x-xmin)/(xmax-xmin)。xmin表示參數(shù)集的最小值，xmax表示參數(shù)集的最大值。

(2)自適應(yīng)計算網(wǎng)格劃分數(shù)K和網(wǎng)格邊長。

(3)將數(shù)據(jù)映射到的網(wǎng)格，計算網(wǎng)格密度和密度閾值MinPts。

(4)根據(jù)MinPts，找出高密度網(wǎng)格和低密度網(wǎng)格，去除空網(wǎng)格;

(5)把每個低密度網(wǎng)格劃分成3d個子網(wǎng)格，把有高密度鄰居子網(wǎng)格的數(shù)據(jù)點歸為對應(yīng)的高密度單元，無高密度鄰居子網(wǎng)格的數(shù)據(jù)點作為噪聲舍去。

(6)任取一個高密度網(wǎng)格，按照廣度優(yōu)先原則將與之相鄰的高密度網(wǎng)格進行合并，重復這個過程直到所有的高密度網(wǎng)格單元處理完畢。

(7)輸出聚類結(jié)果。

算法流程圖如圖1所示。

圖1 網(wǎng)格聚類算法流程圖Fig.1 Flow chart of grid clustering algorithm

1.3 確定網(wǎng)格劃分數(shù)K

網(wǎng)格劃分決定了網(wǎng)格尺寸，對聚類結(jié)果有著重要影響。如果網(wǎng)格的尺寸太大，算法會將本屬于不同聚類中的點劃分到同一個聚類中;如果網(wǎng)格的尺寸太小，網(wǎng)格單元數(shù)就多，計算復雜度提高。采用網(wǎng)格劃分的方式處理數(shù)據(jù)本質(zhì)上是數(shù)據(jù)壓縮，每一維劃分數(shù)K就代表了數(shù)據(jù)壓縮的程度，本文通過網(wǎng)格數(shù)據(jù)壓縮率來設(shè)置參數(shù)K，網(wǎng)格數(shù)據(jù)壓縮率α定義為

式中:N為輸入數(shù)據(jù)個數(shù);K為網(wǎng)格劃分數(shù);d為數(shù)據(jù)維數(shù)。

由式(1)得到網(wǎng)格劃分:

設(shè)雷達信號預分選時1 000個脈沖為一幀，α取70%，則

1.4 確定密度閾值MinPts

雷達信號預分選中，密度閾值的作用是濾除混雜在雷達脈沖信號中的噪聲脈沖，它的取值與偵察環(huán)境中噪聲脈沖的數(shù)量有關(guān)。現(xiàn)有的網(wǎng)格聚類算法要求用戶輸入密度閾值MinPts來判定網(wǎng)格是否為高密度單元，輸入?yún)?shù)的不同可能會導致差別很大的聚類結(jié)果［10］。本文根據(jù)輸入數(shù)據(jù)和網(wǎng)格劃分自動確定密度閾值。依次掃描每個網(wǎng)格單元，得到非空網(wǎng)格的數(shù)GridNum，網(wǎng)格的最大密度Max_Grid。N是輸入數(shù)據(jù)個數(shù)，則網(wǎng)格密度閾值定義為

1.5 邊界優(yōu)化

網(wǎng)格聚類預分選中，低密度網(wǎng)格內(nèi)可能是噪聲點或邊界點?，F(xiàn)有的網(wǎng)格聚類算法直接移除低密度網(wǎng)格，這樣低密度網(wǎng)格內(nèi)的有用信息會被當作噪聲點移除，聚類的邊界將受到影響。如果把低密度網(wǎng)格中的數(shù)據(jù)全部歸到相鄰的高密度網(wǎng)格單元，則又引入了大量的噪聲脈沖，還有可能把多部雷達歸為一類［11］。本文對低密度網(wǎng)格進行邊界提取。首先將低密度網(wǎng)格每一維再等分為3個區(qū)間，形成3d子網(wǎng)格單元。把與高密度網(wǎng)格相鄰的子網(wǎng)格合并到高密度網(wǎng)格，否則子網(wǎng)格作為孤立點舍去。下面以二維空間為例進行說明。

圖2中，數(shù)據(jù)映射到網(wǎng)格1到網(wǎng)格9。密度閾值MinPts為7，網(wǎng)格4，6，7是高密度網(wǎng)格，其余是低密度網(wǎng)格?？梢灾庇^地看出圖中存在2部輻射源。記左側(cè)數(shù)據(jù)點屬于輻射源A，右側(cè)數(shù)據(jù)點屬于輻射源B。網(wǎng)格5中包含2部輻射源的邊界和噪聲脈沖。邊界優(yōu)化時，將網(wǎng)格5每一維三等分，與高密度網(wǎng)格有公共界面的單元歸于高密度網(wǎng)格，點a和點b歸為網(wǎng)格4，屬于輻射源A;點d和點e歸為網(wǎng)格6，屬于輻射源B;點c是噪聲點被移除。可以看出，邊界優(yōu)化處理在正確處理邊界點的同時，去除了噪聲脈沖，提高了聚類精度。

圖2 邊界優(yōu)化示例圖Fig.2 Edges optimization

2 實驗結(jié)果及分析

2.1 聚類結(jié)果的對比

為了驗證本文提出的網(wǎng)格聚類算法用于雷達信號預分選的性能，構(gòu)造表1的全脈沖數(shù)據(jù)為進行仿真實驗。仿真實驗環(huán)境為:Windows XP SP3，Intel CPU Q8200@2.33 GHz，3.73 GB內(nèi)存，編程工具為Matlab R2008a。

表1中的7部雷達按照到達時間順序混疊在一起，考慮到實際信號產(chǎn)生時的參數(shù)與預設(shè)總有一定誤差，以及傳輸信道影響和接收機的測量誤差，對每個參數(shù)都加上了一個隨抖動，其中到達方向(direction of arrival，DOA)的偏差是 2°，載頻(radio frequency，RF)和脈寬(pulse width，PW)的偏差都在1%以內(nèi)。同時加入了10%的環(huán)境噪聲［12］。從圖3可以看出，噪聲與7部雷達信號在到時域空域和載頻域都是嚴重交疊的。基本滿足復雜電磁環(huán)境的要求。

輸入脈沖總數(shù)為 870個，α =0.7，K=7，MinPts=3。仿真結(jié)果的二維分布如圖4所示。由圖4可以看出，網(wǎng)格聚類算法將含有噪聲的全脈沖數(shù)據(jù)正確聚為7類，且較好地去除了散落在真實脈沖參數(shù)值范圍之外的脈沖，即去除了大部分噪聲脈沖，實驗結(jié)果驗證了網(wǎng)格聚類算法的有效性。表2給出了分選結(jié)果統(tǒng)計。

表1 雷達參數(shù)仿真數(shù)據(jù)Table 1 Simulation data of radar parameters

表2 分選結(jié)果信息表Table 2 Information of sorting result

誤分選是把本不屬于此雷達的脈沖歸到該雷達中，漏分選是指本屬于該雷達的脈沖沒有被劃分到該類中。對于雷達信號預分選而言，漏分選比誤分選嚴重得多。

表2中參與分選的全脈沖總數(shù)為870個，其中包括噪聲脈沖85個，真實脈沖785個。從表2得到，網(wǎng)格聚類分選得到脈沖796個，其中準確分選775個，漏分選10個，誤分選21個。

表3給出了相同實驗條件下，α取不同值時的仿真結(jié)果，其中α＇是實際的壓縮率。

表3 不同網(wǎng)格數(shù)據(jù)壓縮率下的分選結(jié)果信息表Table 3 Information of sorting result with different grid data compression ratios

網(wǎng)格數(shù)據(jù)壓縮率決定了網(wǎng)格劃分，α=0.3即壓縮率是30%時，由于網(wǎng)格劃分只能取整數(shù)，K=9，總的網(wǎng)格數(shù)為729。平均每個網(wǎng)格內(nèi)有870/729=1.193 4個數(shù)據(jù)點，因此實際的壓縮率只有16.21%。

從表3可以看出，壓縮率為70%時，噪聲條件下分選結(jié)果和運行時間明顯優(yōu)于其他2個壓縮率條件下的結(jié)果。這是由于隨著α的增大，網(wǎng)格劃分數(shù)減少，運行時間減少，每個網(wǎng)格內(nèi)包含的數(shù)據(jù)點增多，同一部輻射源信號容易落入同一個網(wǎng)格，使得大部分信號都包含在網(wǎng)格中。同時算法對網(wǎng)格邊界進行優(yōu)化處理，減少了漏脈沖數(shù)。在某些網(wǎng)格劃分下，同一個聚類中的數(shù)據(jù)可能分散到多個相鄰的網(wǎng)格中，而這些網(wǎng)格不一定都是高密度網(wǎng)格，邊界優(yōu)化使得一部分有效數(shù)據(jù)被舍棄。這也是α=0.5時的分選結(jié)果差于α=0.3時的原因。因此，在本實驗條件下，α=0.7時，算法運行時間短，分選準確率高，網(wǎng)格聚類的優(yōu)勢得以體現(xiàn)。而當α取值較小時，劃分的網(wǎng)格數(shù)與輸入數(shù)據(jù)點數(shù)相當，體現(xiàn)不出網(wǎng)格聚類的優(yōu)勢。

將本文提出的方法與文獻［8］的網(wǎng)格密度聚類和文獻［9］的移動網(wǎng)格聚類進行對比，α=0.7。相同實驗條件下，算法的分選結(jié)果如表4所示。

表4 3種聚類方法預分選結(jié)果比較Table 4 Comparison of pre-sorting results by three clustering algorithms

從表4的分選結(jié)果可看出，在相同數(shù)據(jù)源和仿真條件下，采用本文得到的漏脈沖數(shù)目明顯小于另外2種方法。這是由于本文對邊界進行了處理，誤分選脈沖數(shù)和另外2種方法相似，略優(yōu)于文獻［9］中的方法。在噪聲脈沖較多時，誤分選數(shù)增大，但是漏分選數(shù)較小。實驗結(jié)果說明，本文的網(wǎng)格聚類算法比現(xiàn)有的聚類算法有較高的性能，對噪聲脈沖有良好的識別能力。

2.2 算法復雜度分析

網(wǎng)格聚類算法的計算復雜度為O(N+Kd+3d)［11］，其中，d為數(shù)據(jù)空間的維數(shù)，N為雷達脈沖總數(shù)，Kd為劃分的網(wǎng)格數(shù)。對于雷達信號預分選，采用了RF，PW，DOA 3位參數(shù)，因此 d=3，且 Kd＜N。由此可知，網(wǎng)格聚類算法在處理三維數(shù)據(jù)時，算法的計算復雜度在數(shù)據(jù)對象總數(shù)較大的情況下趨近于O(n)。因此，網(wǎng)格聚類算法能夠較好地滿足雷達信號預分選實時性的需要。

3 結(jié)束語

本文提出了一種新的網(wǎng)格聚類算法，并將該算法應(yīng)用于雷達信號預分選領(lǐng)域。算法復雜度低，可擴展性好，可以發(fā)現(xiàn)任意形狀的聚類，適合大規(guī)模的偵察數(shù)據(jù)集，對噪聲脈沖也有很好的識別能力，較好地滿足雷達信號預分選的要求。

［1］ 葉菲，羅景青.基于BFSN聚類的雷達信號分選與特征提取算法［J］.艦船電子對抗，2005，28(3):29-34 YE Fei，LUO Jing-qing.Radar Signal Sorting and Feature Extraction Algorithm Based on BFSN Clustering［J］.Shipboard Electronic Countermeasure，2005，28(3):29-34.

［2］ 郭杰，陳軍文.一種處理未知雷達信號的聚類分選方法［J］. 系統(tǒng)工程與電子技術(shù)，2006，28(6):853-856.GUO Jie，CHEN Jun-wen.Clustering Approach for Deinterleaving Unknown Radar Signals［J］.Systems Engineering and Electronics，2006，28(6):853-856.

［3］ 張紅昌，阮懷林，龔亮亮，等.一種新的未知雷達輻射源聚類分選方法［J］.計算機工程與應(yīng)用，2008，44(27):200-202.ZHANG Hong-chang，RUAN Huai-lin，GONG Liang-liang，et al.New Clustering Approach for Sorting Unknown Radar Emitter Signal［J］.Computer Engineering and Applicaitons，2008，44(27):200-202.

［4］ 岳宏偉，羅景青，呂久明，等.雷達信號非均勻粒度聚類分選方法［J］.火力與指揮控制，2008，33(8):23-26.YUE Hong-wei，LUO Jing-qing，Lü Jiu-ming，et al.Research on Radar Signal Sorting Method Based on Uneven Granules Clustering［J］.Fire Control and Command Control，2008，33(8):23-26.

［5］ 趙慧，劉希玉，崔海青.網(wǎng)格聚類算法［J］.計算機技術(shù)與發(fā)展，2010，20(9):83-85.ZHAO Hui，LIU Xi-yu，CUI Hai-qing.Grid-Based Clustering Algorithm［J］.Computer Technology and Development，2010，20(9):83-85.

［6］ 程偉想.網(wǎng)格聚類算法的研究［D］.保定:華北電力大學，2008:9-11.CHENG Wei-xiang.Research of Grid-Based Clustering Algorithm［D］.Baoding:North China Elertic Power U-niversity，2008:9-11.

［7］ 邱保志，鄭智杰.基于局部密度和動態(tài)生成網(wǎng)格的聚類算法［J］.計算機工程與設(shè)計，2010，31(2):385-387.QIU Bao-zhi，ZHENG Zhi-jie.Grid Clustering Algorithm Based on Local Density and Dynamic Creating Grids［J］.Computer Engineering and Design，2010，31(2):385-387.

［8］ 向嫻，湯建龍.一種基于網(wǎng)格密度聚類的雷達信號分選［J］.火控雷達技術(shù)，2010，39(4):67-72.XIANG Xian，TANG Jian-long.A Method of Radar Signal Sorting Based on Grid Density Clustering［J］.Frie Control Radar Technology，2010，39(4):67-72.

［9］ 何佃偉，楊承志，張榮，等.一種基于改進網(wǎng)格聚類的雷達信號分選算法［J］.雷達與對抗，2011，31(2):43-49.HE Dian-wei，YANG Cheng-zhi，ZHANG Rong，et al.A Radar Signal Sorting Algorithm Based on Improved Grid Clustering［J］.Radar ＆ ECM，2011，31(2):43-49.

［10］ 邱保志，劉洋，陳本華.基于網(wǎng)格熵的邊界點檢測算法［J］. 計算機應(yīng)用，2008，28(3):21-24.QIU Bao-zhi，LIU Yang，CHEN Ben-hua.Grid-Entropy Based Boundary Points Detecting Algorithm ［J］.Computer Applications，2008，28(3):21-24.

［11］ 邱保志，沈鈞毅.基于網(wǎng)格技術(shù)的高精度聚類算法［J］.計算機工程，2006，32(3):12-13.QIU Bao-zhi，SHEN Jun-yi.A Grid-Based Improving Clustering Quality Algorithm［J］.Computer Engineering，2006，32(3):12-13.

［12］ 孫連寶，劉治國.雷達偵察信號環(huán)境描述與建模［J］.艦船電子工程，2009，29(11):93-95.SUN Lian-bao，LIU Zhi-guo.Description and Modeling of the Radar Reconnaissance Signals Environment［J］.Ship Electronic Engineering，2009，29(11):93-95.