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

邱磊，楊承志，何佃偉

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

0 引言

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

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

1 一種新的網格聚類預分選算法

1.1 網格聚類概念

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

1.2 算法基本步驟

輸入:3維數據集D，數據個數N.

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

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

(2)自適應計算網格劃分數K和網格邊長。

(3)將數據映射到的網格，計算網格密度和密度閾值MinPts。

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

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

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

(7)輸出聚類結果。

算法流程圖如圖1所示。

圖1 網格聚類算法流程圖Fig.1 Flow chart of grid clustering algorithm

1.3 確定網格劃分數K

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

式中:N為輸入數據個數;K為網格劃分數;d為數據維數。

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

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

1.4 確定密度閾值MinPts

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

1.5 邊界優化

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

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

圖2 邊界優化示例圖Fig.2 Edges optimization

2 實驗結果及分析

2.1 聚類結果的對比

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

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

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

表1 雷達參數仿真數據Table 1 Simulation data of radar parameters

表2 分選結果信息表Table 2 Information of sorting result

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

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

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

表3 不同網格數據壓縮率下的分選結果信息表Table 3 Information of sorting result with different grid data compression ratios

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

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

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

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

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

2.2 算法復雜度分析

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

3 結束語

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

［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］. 系統工程與電子技術，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］.計算機工程與應用，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］ 趙慧，劉希玉，崔海青.網格聚類算法［J］.計算機技術與發展，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］ 程偉想.網格聚類算法的研究［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］ 邱保志，鄭智杰.基于局部密度和動態生成網格的聚類算法［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］ 向嫻，湯建龍.一種基于網格密度聚類的雷達信號分選［J］.火控雷達技術，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］.雷達與對抗，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］ 邱保志，劉洋，陳本華.基于網格熵的邊界點檢測算法［J］. 計算機應用，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］ 邱保志，沈鈞毅.基于網格技術的高精度聚類算法［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］ 孫連寶，劉治國.雷達偵察信號環境描述與建模［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.