基于改進網(wǎng)格聚類的動態(tài)雷達信號分選算法

陳維高，張國毅

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

0 引言

雷達信號分選是指從偵察接收機輸出的隨機交疊脈沖流中分離出各部雷達信號的過程，也就是脈沖信號去交錯的過程。它是現(xiàn)代電子偵察系統(tǒng)的關鍵技術，同時也是電子情報偵察系統(tǒng)(ELINT）和電子支援系統(tǒng)(ESM）的重要組成部分。然而，隨著雷達數(shù)目的急劇增加和信號形式的日趨復雜，使得現(xiàn)代雷達信號分選任務面臨巨大的挑戰(zhàn)。目前，應用到雷達信號分選的主要方法有模板匹配法［1］、直方圖分選法(CDIF、SDIF）［2-3］和平面變換技術［4］等。在現(xiàn)代高密度復雜信號環(huán)境下，這些算法存在著運算量巨大、無法滿足實時性需要的問題。因此，亟需一種運算量小、實時性好的分選算法來稀釋高密度脈沖流，完成對偵察信號的初步分類，減少后續(xù)分選任務的負擔。

近年來聚類分析技術廣泛應用于雷達信號分選中，并取得了較好的效果。其中，由于網(wǎng)格聚類算法［5］實時性好，可以在無先驗知識的條件下充分利用數(shù)據(jù)集自身的密度連通性完成聚類，且該算法的處理時間獨立于數(shù)據(jù)對象的數(shù)目，因此非常適合處理數(shù)據(jù)量巨大且對實時性要求高的雷達信號分選任務。然而，傳統(tǒng)網(wǎng)格聚類算法存在密度閾值設置不夠合理、對邊緣數(shù)據(jù)處理不完善、聚類精度較低的問題［6］。針對以上問題，本文提出了一種基于改進網(wǎng)格聚類的動態(tài)雷達信號分選算法。該方法首先將CluStream 聚類算法中的雙層框架引入雷達信號分選系統(tǒng)，增強了分選系統(tǒng)的實時性，然后通過雙密度閾值策略和邊緣稀疏網(wǎng)格優(yōu)化處理，改進了傳統(tǒng)網(wǎng)格聚類算法。仿真結果表明，該方法具備較高的抗干擾能力和聚類精度，取得了較好的分選效果。

1 動態(tài)信號分選框架

數(shù)據(jù)流聚類是針對連續(xù)數(shù)據(jù)流的聚類分析方法，如果把接收機不斷輸出的雷達偵察數(shù)據(jù)看作數(shù)據(jù)流，則雷達信號分選就可以轉化為數(shù)據(jù)流聚類的問題。本文將經(jīng)典數(shù)據(jù)流聚類算法CluStream［7］的雙層框架引入雷達信號分選，并結合文獻［8］提出的動態(tài)信號分選框架來設計信號分選系統(tǒng)。如圖1所示，動態(tài)信號分選框架主要分為兩個部分:一是在線層不斷將偵察數(shù)據(jù)轉化為概要數(shù)據(jù)結構信息，并定時存儲;二是離線層直接訪問暫存數(shù)據(jù)庫，利用概要信息完成信號分選。

圖1 動態(tài)信號分選框架圖

1.1 在線層

偵察接收機偵收到的數(shù)據(jù)不斷涌入，形成偵察數(shù)據(jù)流，此時數(shù)據(jù)流中包含大量的數(shù)據(jù)信息，需要對其進行數(shù)據(jù)轉換以獲得離線部分所需的概要數(shù)據(jù)結構信息。在滿足一定的存儲時間條件下，將數(shù)據(jù)轉換后形成的概要數(shù)據(jù)結構信息存儲到暫存數(shù)據(jù)庫中，以供離線層調(diào)用。

1.2 離線層

根據(jù)具體的分選需求從暫存數(shù)據(jù)庫中調(diào)取相應的概要數(shù)據(jù)信息，然后利用改進網(wǎng)格聚類算法完成信號的分選任務，并顯示出聚類結果。

將分選系統(tǒng)設置成雙層框架結構，可以在接收機輸出偵察數(shù)據(jù)的同時將數(shù)據(jù)轉化為概要數(shù)據(jù)結構信息，不用直接處理接收機輸出的海量數(shù)據(jù)，相比傳統(tǒng)的靜態(tài)分選方法，節(jié)省了整個分選過程所用的時間，增加了分選系統(tǒng)的實時性［9］。

2 網(wǎng)格聚類算法

2.1 網(wǎng)格單元

將參數(shù)空間D=(D1，D2，…，Dd）的每一維劃分為K個區(qū)間。這些區(qū)間按照該維參數(shù)值的大小順序排列，則整個參數(shù)空間被分成有限個不相交的矩形(或超矩形）單元。這種劃分后的單元稱為網(wǎng)格單元，使得數(shù)據(jù)集中所有數(shù)據(jù)信息都能投影于這些網(wǎng)格單元中去。

2.2 相鄰網(wǎng)格單元

當d 維參數(shù)空間中的兩個網(wǎng)格單元U1、U2存在公共頂點或者公共邊界時，稱這兩個網(wǎng)格單元為相鄰網(wǎng)格單元。

2.3 網(wǎng)格密度

通過網(wǎng)格劃分將參數(shù)空間劃分為體積相等的各個網(wǎng)格單元，將每一個網(wǎng)格單元中包含的數(shù)據(jù)個數(shù)作為該網(wǎng)格單元的密度ρ。

2.4 數(shù)據(jù)壓縮比

每一維劃分的網(wǎng)格單元個數(shù)K 就代表著數(shù)據(jù)壓縮的程度，本文通過定義數(shù)據(jù)壓縮比η來設置參數(shù)K:

式中，n為待分選脈沖個數(shù)，d為特征參數(shù)的維數(shù)。

K 值越大，對應的數(shù)據(jù)壓縮比越小，劃分的網(wǎng)格數(shù)越接近數(shù)據(jù)個數(shù)，此時會產(chǎn)生許多空網(wǎng)格耗費存儲空間，并且計算代價也將增大;當K 值過小時，會將大量噪聲和不同類數(shù)據(jù)劃分到同一網(wǎng)格中去，給聚類精度帶來很大的影響。綜合兩方面的因素，經(jīng)過大量仿真驗證，當數(shù)據(jù)壓縮比取70%時，既可保證分選實時性又能獲取較高的聚類精度。

2.5 傳統(tǒng)網(wǎng)格聚類算法局限性分析

傳統(tǒng)網(wǎng)格聚類中只設定一個密度閾值ε'，當網(wǎng)格密度ρ ＞ε'時，該網(wǎng)格為密集網(wǎng)格，然后將相鄰密集網(wǎng)格聯(lián)通的最大集合作為一類數(shù)據(jù);若ρ＜ε'時，該網(wǎng)格判為非密集網(wǎng)格，予以舍棄。這種密度閾值的設置是不合理的，會使密度沒有達到該閾值的一些真實數(shù)據(jù)被當作噪聲舍棄。通過圖2 可以更加清楚地說明這個問題。

圖2 網(wǎng)格聚類密度示意圖

圖2中c～d 段代表某一類真實數(shù)據(jù)網(wǎng)格，e～f 段代表噪聲分布較密集的網(wǎng)格。假設一個較大的密度閾值ε，則只有a～b 段的網(wǎng)格可以被聚類，而c～a、b～d段以及兩段邊緣的密度小于ε的網(wǎng)格將被舍棄，這將使一部分數(shù)據(jù)丟失從而降低聚類精度;假設一個較小的密度閾值δ/2，則某些噪聲較為密集的網(wǎng)格(如e～f段）也會被認為是某一類而聚類，產(chǎn)生“增批”現(xiàn)象，并且對于c～d 段兩側邊緣的網(wǎng)格依然不能被聚類。針對以上問題，本文設計了雙密度閾值策略和邊緣稀疏網(wǎng)格優(yōu)化方法。

3 改進網(wǎng)格聚類算法

3.1 雙密度閾值策略

如圖2所示，ε 是第一層密度閾值，設置為空間中網(wǎng)格單元的平均密度加上標準差的一半;δ/2 是第二層密度閾值，設置為統(tǒng)計學中判斷離散度的標準差的一半。計算過程如下:

式中，ρi為第i個網(wǎng)格單元的密度，K為每一維劃分的區(qū)間個數(shù)，d 代表參數(shù)空間的維數(shù)，G為參數(shù)空間中非空網(wǎng)格的個數(shù)，σ為方差代表數(shù)據(jù)離散程度。

根據(jù)雙密度將網(wǎng)格劃分為3 種狀態(tài):當ρi≥ε時，該網(wǎng)格為密集網(wǎng)格，如圖2中a～b 段的網(wǎng)格;當ε ＞ρi≥δ/2時，該網(wǎng)格為過渡網(wǎng)格，如圖2中c～a、b～d、e～f 段的網(wǎng)格;當ρi＜δ/2時，該網(wǎng)格為稀疏網(wǎng)格，如圖2中除去e～f、c～d 段之外的網(wǎng)格。

在每一次進行聚類時，首先選取未被聚類且密度最大的網(wǎng)格U0，判斷該網(wǎng)格是否為密集網(wǎng)格，只有當網(wǎng)格U0是密集網(wǎng)格時，才以網(wǎng)格U0為聚類起始點開始聚類。依據(jù)廣度優(yōu)先搜索原則［10］依次訪問網(wǎng)格U0的相鄰網(wǎng)格單元，并將其中未被聚類的過渡網(wǎng)格和密集網(wǎng)格Ui(i=1，2，3，…，i）都歸屬到該類，然后再順序訪問所有與網(wǎng)格Ui(i=1，2，3，…，i）相鄰的未聚類網(wǎng)格單元，重復上述過程并進行歸類，直到所有未聚類的相鄰網(wǎng)格單元都是稀疏網(wǎng)格，此時對不為空的邊緣稀疏網(wǎng)格進行優(yōu)化處理。優(yōu)化處理后，對剩余數(shù)據(jù)按照上述方法進行下一次聚類，直到選取的U0不是密集網(wǎng)格時該批數(shù)據(jù)完成聚類。

將聚類起始網(wǎng)格規(guī)定為密集網(wǎng)格，可以避免一些噪聲分布較為密集的網(wǎng)格被聚類，如圖2所示。只能選擇a～b 段的密度最大的網(wǎng)格作為聚類起始網(wǎng)格，而不會選擇e～f 段的網(wǎng)格作為起始網(wǎng)格，從而避免將一些噪聲網(wǎng)格聚類造成“增批”現(xiàn)象，提高了算法的抗干擾能力。

3.2 邊緣稀疏網(wǎng)格優(yōu)化方法

在對某一類數(shù)據(jù)進行聚類的過程中，當所有未聚類的相鄰網(wǎng)格單元都是稀疏網(wǎng)格時，對不為空的邊緣稀疏網(wǎng)格進行優(yōu)化處理。如圖3所示，c2、c4 網(wǎng)格為密集網(wǎng)格，c1為過渡網(wǎng)格，其他都為稀疏網(wǎng)格。以稀疏網(wǎng)格b3中的數(shù)據(jù)點p 進行優(yōu)化處理舉例:首先，計算與網(wǎng)格b3 相鄰的非空網(wǎng)格中數(shù)據(jù)點到點p的歐氏距離;其次，記錄每個相鄰網(wǎng)格中歐氏距離di≤r(i=1，2，3，…，i，r為歸屬度門限值，選取為網(wǎng)格邊長的最大值）的個數(shù)，將該個數(shù)作為數(shù)據(jù)點p 對應該網(wǎng)格的歸屬度，記為Sn(n=1，2，3，…，n，n為相鄰網(wǎng)格標號），圖中點p對于鄰近非空網(wǎng)格b2，c2，c3，c4，b4，a4，a3的歸屬度依次為1，1，2，5，1，0，1;最后，比較點p的歸屬度，選取歸屬度最大的網(wǎng)格將數(shù)據(jù)點p 歸屬到該網(wǎng)格所屬的類中去，圖中點p 將歸屬到網(wǎng)格c4所屬的類1中去。需要指出的是:當數(shù)據(jù)點對幾個網(wǎng)格的歸屬度相等時，將同一類的網(wǎng)格歸屬度累加，計算數(shù)據(jù)點對類的歸屬度，然后再比較數(shù)據(jù)點對不同類的歸屬度，從而判斷該點的歸屬問題。

圖3 邊緣優(yōu)化示意圖

如果應用傳統(tǒng)網(wǎng)格聚類算法，只將密集網(wǎng)格c2、c4聚類，將會丟失大量有用數(shù)據(jù)，嚴重影響聚類精度。然而，本文提出的邊緣優(yōu)化方法在雙閾值策略的基礎上對邊緣稀疏網(wǎng)格里的數(shù)據(jù)點依據(jù)“類內(nèi)聚集度”(對比數(shù)據(jù)點到各個類別的歸屬度）進行判別歸屬，可以很好地解決分布在網(wǎng)格邊緣數(shù)據(jù)的歸屬問題，從而提高聚類精度。

3.3 算法流程

下面結合圖4 介紹改進網(wǎng)格密度聚類算法的具體步驟:

(1）對待分選數(shù)據(jù)集中存儲的參數(shù)數(shù)據(jù)進行歸一化處理;

(2）依據(jù)設定的數(shù)據(jù)壓縮比η來確定K 值的大小，對整個空間進行劃分，并將歸一化后的數(shù)據(jù)投影到網(wǎng)格空間中。計算每個網(wǎng)格的密度，對所有非空網(wǎng)格設置狀態(tài)標簽label。在聚類過程中該標簽隨對應網(wǎng)格狀態(tài)的變化而變化，label=0 表示該網(wǎng)格未聚類，label=1 表示該網(wǎng)格已聚類;

(3）由每個網(wǎng)格的密度及非空網(wǎng)格的個數(shù)依據(jù)式(2）、(3）、(4）來計算兩個密度閾值;

(4）選取網(wǎng)格中密度最大的網(wǎng)格作為聚類起始點，依據(jù)3.1 小節(jié)提出的自適應雙密度閾值策略進行聚類;

(5）對邊緣稀疏網(wǎng)格依據(jù)3.2 小節(jié)提出的邊緣優(yōu)化方法進行優(yōu)化處理，優(yōu)化處理后，標志該類數(shù)據(jù)聚類完成;

(6）選取剩余未聚類網(wǎng)格中密度最大的，如果該網(wǎng)格是密集網(wǎng)格，則跳至步驟(3），表示還有新的類別;如果不是密集網(wǎng)格，表示該批數(shù)據(jù)全部完成聚類。

圖4 改進網(wǎng)格密度聚類算法流程圖

4 仿真實現(xiàn)及結果分析

實驗采用的仿真平臺為Intel CPU Q8200，3GB 內(nèi)存，操作系統(tǒng)為Windows XP，仿真軟件為Matlab R2010a。利用計算機形成脈沖描述字序列(PDW）來模擬接收機輸出的偵察數(shù)據(jù)流，針對PDW中各個參數(shù)的特點和分選要求，實驗選擇其中最穩(wěn)定的3個參數(shù)PW、RF、DOA 作為特征參數(shù)進行聚類。

為了驗證改進網(wǎng)格聚類算法應用于雷達信號分選的有效性和對噪聲脈沖的識別能力，在脈沖數(shù)據(jù)中加入了15%的噪聲脈沖。實驗選用的雷達類型、數(shù)目、脈沖個數(shù)以及特征參數(shù)信息如表1所示，原始信號參數(shù)的歸一化二維分布如圖5所示。

表1 偵察數(shù)據(jù)信息表

圖5 原始信號參數(shù)歸一化分布圖

分別利用傳統(tǒng)網(wǎng)格聚類算法和改進網(wǎng)格聚類算法對原始數(shù)據(jù)進行處理，數(shù)據(jù)壓縮比η=70%，仿真結果如圖6所示。

圖6 分選結果對比圖

由圖6(a）可以看出，傳統(tǒng)網(wǎng)格聚類算法由于閾值設置為空間中網(wǎng)格單元的平均密度，一些密度累積較大的噪聲脈沖將會被當作真實類別而聚類。所以，傳統(tǒng)算法受噪聲脈沖影響巨大，不僅在真實聚類結果中存在大量的噪聲脈沖，而且將噪聲脈沖當作真實類別進行聚類，出現(xiàn)了嚴重的“增批”現(xiàn)象(如圖中的符號*代表噪聲被算法聚成許多的類）。而圖6(b）中改進網(wǎng)格聚類算法使用了雙閾值策略，將初始聚類網(wǎng)格的閾值依據(jù)數(shù)據(jù)的離散度進行提高，防止一些密度較大的噪聲脈沖被當作真實脈沖而聚類。同時，由于真實類別的網(wǎng)格密度(數(shù)據(jù)最密集處）要遠大于改進后的第一層密度閾值(只要大于第一層密度閾值就可以進行聚類），所以避免了目標丟失的現(xiàn)象。由圖可以看出，改進后的算法能夠正確地將數(shù)據(jù)聚成4類，并且受噪聲影響較小，去除了大量散落在真實脈沖參數(shù)值之外的噪聲脈沖，取得了良好的分選效果。具體分選結果如表2、表3所示，其中分選準確率為準確分選的脈沖總數(shù)與實際脈沖總數(shù)之比。

從表2、表3的統(tǒng)計結果可以看出，傳統(tǒng)網(wǎng)格聚類算法雖然用時較少，但誤分選和漏分選脈沖數(shù)目較多，并且聚類結果中存在9個由噪聲組成的類，即出現(xiàn)“增批”現(xiàn)象，對分選結果產(chǎn)生巨大影響。而改進網(wǎng)格聚類算法雖然運算總時間略大于傳統(tǒng)算法，但其受噪聲脈沖影響較小，不產(chǎn)生“增批”現(xiàn)象，并且聚類精度較傳統(tǒng)算法有較大提高。整體而言，改進網(wǎng)格聚類算法對先驗知識要求較低，受噪聲脈沖的影響較小，分選準確率高，并且具備較高的運算速率，能夠有效地完成雷達信號的分選任務。

表2 傳統(tǒng)網(wǎng)格聚類算法分選結果

表3 改進網(wǎng)格聚類算法分選結果

5 結束語

本文提出了一種基于改進網(wǎng)格聚類的動態(tài)雷達信號動態(tài)分選算法，算法將CluStream 數(shù)據(jù)流聚類經(jīng)典雙層框架引入雷達信號分選中，增加了整個分選系統(tǒng)的實時性。改進了傳統(tǒng)網(wǎng)格聚類算法，通過雙密度閾值策略使聚類密度閾值更加合理化，增強了抗干擾能力，并且利用邊緣稀疏網(wǎng)格優(yōu)化方法進一步提高了聚類精度。通過仿真驗證，證實了該算法較傳統(tǒng)算法具備較高的聚類精度和抗干擾能力，適用于現(xiàn)代雷達信號分選系統(tǒng)。

文中提出的方法雖然提高了聚類精度和抗干擾能力，但在噪聲信號密集情況下有時仍會出現(xiàn)“增批”現(xiàn)象，如何避免“增批”現(xiàn)象并且進一步提高算法的效率還需要更加深入研究。

［1］Davies C L，Holland P.Automatic Processing for ESM［J］.IEE Proc F Commun Radar ＆ Signal Process，1982，4(8）:52-56.

［2］Mardia H K.Adaptive Clustering for ESM［J］.IEE Colloquium on Signal Processing for ESM systems，1988，62(5）:149-154.

［3］Milojevic D J，Popovic B M.Improved Algorithm for the Deinterleaving Radar Pulses［J］.IEE Proceedings，Part F:Radar and Signal Processing，1992，139(1）:98-104.

［4］胡來招.平面變換用于復雜環(huán)境的信號處理［M］.電子工業(yè)部29 研究所科技成果匯編，1995.

［5］Anant Ram，Ashish Sharma，Anand S Jalall.An Enhanced Density Based Spatial Clustering of Applications with Noise［J］.IEEE International Ad-vance Computing Conference，2009 (3 ）:1475-1478.

［6］Shan Shimin.Research on data stream clustering based on grid and density［D］.Dalian University of Technology，2006.

［7］Aggarwal C C，Han J，Wang J，et al.A Framework Clustering Evolving Data Streams［C］// Proc.of the 29th VLDB Conference，2003:81-92.

［8］張國毅，王曉峰，張旭洲.基于數(shù)據(jù)流聚類的動態(tài)信號分選框架［J］.電訊技術，2011，51(9）:65-68.

［9］AGGARWAL C C，HAN J，WANG J，et al.A frame work for projected clustering of high dimensional data streams［C］//Proc.of the 30th VLDB Conf，2004:852-863.

［10］張忠平，王愛杰，陳麗萍.一種基于廣度優(yōu)先搜索的K-Means 初始化算法［J］.計算機工程與應用，2008，44(27）:159-161.