陳維高，張國毅

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

0 引言

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

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

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

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

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

1.1 在線層

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

1.2 離線層

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

將分選系統(tǒng)設(shè)置成雙層框架結(jié)構(gòu)，可以在接收機(jī)輸出偵察數(shù)據(jù)的同時(shí)將數(shù)據(jù)轉(zhuǎn)化為概要數(shù)據(jù)結(jié)構(gòu)信息，不用直接處理接收機(jī)輸出的海量數(shù)據(jù)，相比傳統(tǒng)的靜態(tài)分選方法，節(jié)省了整個分選過程所用的時(shí)間，增加了分選系統(tǒng)的實(shí)時(shí)性［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āng)d 維參數(shù)空間中的兩個網(wǎng)格單元U1、U2存在公共頂點(diǎn)或者公共邊界時(shí)，稱這兩個網(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è)置參數(shù)K:

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

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

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

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

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

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

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

3.1 雙密度閾值策略

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

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

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

在每一次進(jìn)行聚類時(shí)，首先選取未被聚類且密度最大的網(wǎng)格U0，判斷該網(wǎng)格是否為密集網(wǎng)格，只有當(dāng)網(wǎng)格U0是密集網(wǎng)格時(shí)，才以網(wǎng)格U0為聚類起始點(diǎn)開始聚類。依據(jù)廣度優(yōu)先搜索原則［10］依次訪問網(wǎng)格U0的相鄰網(wǎng)格單元，并將其中未被聚類的過渡網(wǎng)格和密集網(wǎng)格Ui(i=1，2，3，…，i）都?xì)w屬到該類，然后再順序訪問所有與網(wǎng)格Ui(i=1，2，3，…，i）相鄰的未聚類網(wǎng)格單元，重復(fù)上述過程并進(jìn)行歸類，直到所有未聚類的相鄰網(wǎng)格單元都是稀疏網(wǎng)格，此時(shí)對不為空的邊緣稀疏網(wǎng)格進(jìn)行優(yōu)化處理。優(yōu)化處理后，對剩余數(shù)據(jù)按照上述方法進(jìn)行下一次聚類，直到選取的U0不是密集網(wǎng)格時(shí)該批數(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ù)進(jìn)行聚類的過程中，當(dāng)所有未聚類的相鄰網(wǎng)格單元都是稀疏網(wǎng)格時(shí)，對不為空的邊緣稀疏網(wǎng)格進(jìn)行優(yōu)化處理。如圖3所示，c2、c4 網(wǎng)格為密集網(wǎng)格，c1為過渡網(wǎng)格，其他都為稀疏網(wǎng)格。以稀疏網(wǎng)格b3中的數(shù)據(jù)點(diǎn)p 進(jìn)行優(yōu)化處理舉例:首先，計(jì)算與網(wǎng)格b3 相鄰的非空網(wǎng)格中數(shù)據(jù)點(diǎn)到點(diǎn)p的歐氏距離;其次，記錄每個相鄰網(wǎng)格中歐氏距離di≤r(i=1，2，3，…，i，r為歸屬度門限值，選取為網(wǎng)格邊長的最大值）的個數(shù)，將該個數(shù)作為數(shù)據(jù)點(diǎn)p 對應(yīng)該網(wǎng)格的歸屬度，記為Sn(n=1，2，3，…，n，n為相鄰網(wǎng)格標(biāo)號），圖中點(diǎn)p對于鄰近非空網(wǎng)格b2，c2，c3，c4，b4，a4，a3的歸屬度依次為1，1，2，5，1，0，1;最后，比較點(diǎn)p的歸屬度，選取歸屬度最大的網(wǎng)格將數(shù)據(jù)點(diǎn)p 歸屬到該網(wǎng)格所屬的類中去，圖中點(diǎn)p 將歸屬到網(wǎng)格c4所屬的類1中去。需要指出的是:當(dāng)數(shù)據(jù)點(diǎn)對幾個網(wǎng)格的歸屬度相等時(shí)，將同一類的網(wǎng)格歸屬度累加，計(jì)算數(shù)據(jù)點(diǎn)對類的歸屬度，然后再比較數(shù)據(jù)點(diǎn)對不同類的歸屬度，從而判斷該點(diǎn)的歸屬問題。

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

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

3.3 算法流程

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

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

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

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

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

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

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

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

4 仿真實(shí)現(xiàn)及結(jié)果分析

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

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

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

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

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

圖6 分選結(jié)果對比圖

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

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

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

表3 改進(jìn)網(wǎng)格聚類算法分選結(jié)果

5 結(jié)束語

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

文中提出的方法雖然提高了聚類精度和抗干擾能力，但在噪聲信號密集情況下有時(shí)仍會出現(xiàn)“增批”現(xiàn)象，如何避免“增批”現(xiàn)象并且進(jì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］胡來招.平面變換用于復(fù)雜環(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］.電訊技術(shù)，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］.計(jì)算機(jī)工程與應(yīng)用，2008，44(27）:159-161.