邱磊，楊承志，何佃偉

(空軍航空大學(xué)，吉林長(zhǎng)春 130022)

0 引言

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

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

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

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

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

1.2 算法基本步驟

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

輸出:帶標(biāo)號(hào)的聚類，噪聲點(diǎn)。

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

(2)自適應(yīng)計(jì)算網(wǎng)格劃分?jǐn)?shù)K和網(wǎng)格邊長(zhǎng)。

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

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

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

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

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

算法流程圖如圖1所示。

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

1.3 確定網(wǎng)格劃分?jǐn)?shù)K

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

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

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

設(shè)雷達(dá)信號(hào)預(yù)分選時(shí)1 000個(gè)脈沖為一幀，α取70%，則

1.4 確定密度閾值MinPts

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

1.5 邊界優(yōu)化

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

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

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

2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

誤分選是把本不屬于此雷達(dá)的脈沖歸到該雷達(dá)中，漏分選是指本屬于該雷達(dá)的脈沖沒(méi)有被劃分到該類中。對(duì)于雷達(dá)信號(hào)預(yù)分選而言，漏分選比誤分選嚴(yán)重得多。

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

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

表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%時(shí)，由于網(wǎng)格劃分只能取整數(shù)，K=9，總的網(wǎng)格數(shù)為729。平均每個(gè)網(wǎng)格內(nèi)有870/729=1.193 4個(gè)數(shù)據(jù)點(diǎn)，因此實(shí)際的壓縮率只有16.21%。

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

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

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

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

2.2 算法復(fù)雜度分析

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

3 結(jié)束語(yǔ)

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

［1］ 葉菲，羅景青.基于BFSN聚類的雷達(dá)信號(hào)分選與特征提取算法［J］.艦船電子對(duì)抗，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］ 郭杰，陳軍文.一種處理未知雷達(dá)信號(hào)的聚類分選方法［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］ 張紅昌，阮懷林，龔亮亮，等.一種新的未知雷達(dá)輻射源聚類分選方法［J］.計(jì)算機(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］ 岳宏偉，羅景青，呂久明，等.雷達(dá)信號(hào)非均勻粒度聚類分選方法［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］.計(jì)算機(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］.保定:華北電力大學(xué)，2008:9-11.CHENG Wei-xiang.Research of Grid-Based Clustering Algorithm［D］.Baoding:North China Elertic Power U-niversity，2008:9-11.

［7］ 邱保志，鄭智杰.基于局部密度和動(dòng)態(tài)生成網(wǎng)格的聚類算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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)格密度聚類的雷達(dá)信號(hào)分選［J］.火控雷達(dá)技術(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］ 何佃偉，楊承志，張榮，等.一種基于改進(jìn)網(wǎng)格聚類的雷達(dá)信號(hào)分選算法［J］.雷達(dá)與對(duì)抗，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)格熵的邊界點(diǎn)檢測(cè)算法［J］. 計(jì)算機(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］.計(jì)算機(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］ 孫連寶，劉治國(guó).雷達(dá)偵察信號(hào)環(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.