基于改進網格聚類的動態雷達信號分選算法

陳維高，張國毅

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

0 引言

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

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

1 動態信號分選框架

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

圖1 動態信號分選框架圖

1.1 在線層

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

1.2 離線層

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

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

2 網格聚類算法

2.1 網格單元

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

2.2 相鄰網格單元

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

2.3 網格密度

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

2.4 數據壓縮比

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

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

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

2.5 傳統網格聚類算法局限性分析

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

圖2 網格聚類密度示意圖

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

3 改進網格聚類算法

3.1 雙密度閾值策略

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

式中，ρi為第i個網格單元的密度，K為每一維劃分的區間個數，d 代表參數空間的維數，G為參數空間中非空網格的個數，σ為方差代表數據離散程度。

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

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

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

3.2 邊緣稀疏網格優化方法

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

圖3 邊緣優化示意圖

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

3.3 算法流程

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

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

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

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

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

(5）對邊緣稀疏網格依據3.2 小節提出的邊緣優化方法進行優化處理，優化處理后，標志該類數據聚類完成;

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

圖4 改進網格密度聚類算法流程圖

4 仿真實現及結果分析

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

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

表1 偵察數據信息表

圖5 原始信號參數歸一化分布圖

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

圖6 分選結果對比圖

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

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

表2 傳統網格聚類算法分選結果

表3 改進網格聚類算法分選結果

5 結束語

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

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

［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］胡來招.平面變換用于復雜環境的信號處理［M］.電子工業部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］張國毅，王曉峰，張旭洲.基于數據流聚類的動態信號分選框架［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］張忠平，王愛杰，陳麗萍.一種基于廣度優先搜索的K-Means 初始化算法［J］.計算機工程與應用，2008，44(27）:159-161.