基于改進(jìn)CFSFDP的雷達(dá)信號(hào)預(yù)分選方法

韓佳寶, 崔天舒, 李志豪, 黃永輝, 安軍社

(1.中國(guó)科學(xué)院國(guó)家空間科學(xué)中心復(fù)雜航天系統(tǒng)電子信息技術(shù)重點(diǎn)實(shí)驗(yàn)室,北京 100000;2.中國(guó)科學(xué)院大學(xué),北京 100000; 3.清華大學(xué)北京信息科學(xué)與技術(shù)國(guó)家研究中心,北京 100000)

0 引言

雷達(dá)信號(hào)分選技術(shù)是電子偵察的重要環(huán)節(jié),隨著現(xiàn)代戰(zhàn)場(chǎng)電磁環(huán)境的日益復(fù)雜,雷達(dá)信號(hào)脈沖密度達(dá)到數(shù)十萬甚至數(shù)百萬每秒[1],傳統(tǒng)的一步式分選方法難以處理如此密集的信號(hào),現(xiàn)代雷達(dá)信號(hào)分選主要分為預(yù)分選與主分選兩步,其中,預(yù)分選主要利用雷達(dá)信號(hào)的載頻(CF)、脈沖寬度(PW)、到達(dá)角(DOA)等特征參數(shù)對(duì)信號(hào)進(jìn)行聚類,以降低信號(hào)脈沖的密度,實(shí)現(xiàn)初步分選,便于后續(xù)主分選等環(huán)節(jié)的進(jìn)行。因此,良好的聚類預(yù)分選是實(shí)現(xiàn)雷達(dá)信號(hào)準(zhǔn)確分選的必要前提。在過去幾十年里,關(guān)于聚類問題,學(xué)者們提出許多經(jīng)典思路,比如基于密度、基于模型、基于網(wǎng)格、基于層次及基于劃分等方法[2]。

K-means[3]是一種經(jīng)典的基于劃分的方法,數(shù)據(jù)被劃分為K個(gè)簇并迭代優(yōu)化,最終形成穩(wěn)定聚類結(jié)果,局限性在于只適用于球形簇,且難以發(fā)現(xiàn)信號(hào)中的異常值。同時(shí),該方法的準(zhǔn)確性受限于簇類別數(shù)及初始聚類中心的選取。DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一種基于密度連通區(qū)域的聚類方法[4],相比于基于距離的方法可以發(fā)現(xiàn)任意形狀的簇,但需要人為設(shè)置簇內(nèi)鄰域半徑(Eps)和簇內(nèi)最小樣本數(shù)目(MinPts),限制了該方法處理未知雷達(dá)數(shù)據(jù)的性能。近鄰傳播(Affinity Propagation,AP)[5]聚類是一種基于信息傳遞的方法,通過節(jié)點(diǎn)之間迭代的吸引度與歸屬度兩種消息的傳遞,判決出各信號(hào)樣本的聚類中心,其優(yōu)勢(shì)在于不需要預(yù)先人為設(shè)定聚類數(shù)目,對(duì)信號(hào)之間的相似度矩陣的對(duì)稱性沒有要求,因此,針對(duì)不同雷達(dá)信號(hào)數(shù)據(jù)具有較強(qiáng)的靈活性,但最終聚類效果受限于其中偏向參數(shù)的設(shè)置,同時(shí)難以適應(yīng)大規(guī)模雷達(dá)信號(hào)數(shù)據(jù)的處理。

以上典型方法存在各自相應(yīng)的局限性,不能很好地適應(yīng)聚類預(yù)分選的需求。近年來,關(guān)于聚類預(yù)分選,不少研究團(tuán)隊(duì)在上述方法基礎(chǔ)上做出了改進(jìn),文獻(xiàn)[6]在傳統(tǒng)K-means方法基礎(chǔ)上聯(lián)合數(shù)據(jù)場(chǎng)理論,提出了一種融合算法,首先通過數(shù)據(jù)場(chǎng)聚類方法得出初始聚類數(shù)目和聚類中心,再以此為基礎(chǔ)進(jìn)行K-means聚類,解決了對(duì)聚類數(shù)目設(shè)置的依賴以及對(duì)初始聚類中心選取敏感的問題,但該方法相較于K-means計(jì)算復(fù)雜度大大增加。文獻(xiàn)[7]針對(duì)DBSCAN方法不能很好處理密度分布不均勻雷達(dá)信號(hào)的局限性,借助OPTICS方法[8]和網(wǎng)格劃分方法提出了一種兩級(jí)聚類預(yù)分選措施,依次處理高密度信號(hào)與低密度信號(hào),該方法效果依賴于距離半徑、簇內(nèi)最小樣本數(shù)目等先驗(yàn)參數(shù)的設(shè)置。

2014年,RODRIGUEZ等[9]提出一種基于密度和距離的新聚類方法CFSFDP(Clustering by Fast Search and Find of Density Peaks),其具有聚類速度快、適應(yīng)任意形狀分布、經(jīng)驗(yàn)參數(shù)設(shè)置少的優(yōu)點(diǎn)。通過計(jì)算每個(gè)樣本點(diǎn)的局部密度和可達(dá)距離,根據(jù)兩個(gè)參數(shù)形成的聯(lián)合信息,判決聚類中心點(diǎn),并將剩余未判決點(diǎn)按照密度優(yōu)先原則,以就近原則依次將點(diǎn)分配到高密度點(diǎn)所屬簇中。

本文在此方法的基礎(chǔ)上,結(jié)合現(xiàn)代雷達(dá)信號(hào)參數(shù)的分布特點(diǎn),做出以下改進(jìn):一是利用直方圖均衡化思想緩解算法性能對(duì)截?cái)嗑嚯xdc設(shè)置敏感的問題;二是改進(jìn)可達(dá)距離計(jì)算方法和數(shù)據(jù)所屬簇分配規(guī)則,以適應(yīng)數(shù)據(jù)密度分布不均衡的情景。

1 CFSFDP方法原理

該方法基于兩個(gè)假設(shè):1) 簇的中心被擁有更低密度的鄰居點(diǎn)包圍;2) 每個(gè)聚類中心到其他中心的距離較遠(yuǎn)。在此基礎(chǔ)上,該方法關(guān)注數(shù)據(jù)點(diǎn)的兩個(gè)特征參數(shù):局部密度ρi和當(dāng)前點(diǎn)與最近的更高密度點(diǎn)的可達(dá)距離δi。假設(shè)數(shù)據(jù)點(diǎn)樣本集合為X={x1,x2,x3,…,xn},數(shù)據(jù)點(diǎn)i與j之間的距離dij為兩個(gè)點(diǎn)之間的歐氏距離,方法具體步驟如下。

1) 計(jì)算局部密度。

截?cái)嗪吮硎緸?/p>

(1)

式中,

(2)

為階躍函數(shù)。

高斯核表示為

(3)

式中,dc為截?cái)嗑嚯x,根據(jù)啟發(fā)式方法進(jìn)行設(shè)置,需要人為設(shè)置,一般范圍為1%～2%[9]。

2) 計(jì)算可達(dá)距離。

δi表示數(shù)據(jù)點(diǎn)i和最近的高密度點(diǎn)之間的距離,表示為

(4)

3) 聚類中心的確定。

根據(jù)計(jì)算得到的局部密度ρi和可達(dá)距離δi形成決策圖,人工從其中找到兩者都較大的點(diǎn)作為聚類中心。

4) 分配非聚類中心點(diǎn)。

對(duì)未分配的點(diǎn)按照局部密度從大到小的順序,依次將其分配到距離最近的高密度點(diǎn)所屬簇中。

2 改進(jìn)的CFSFDP方法

通過上述對(duì)CFSFDP方法的原理說明可以看出,該方法的有效性取決于dc的設(shè)置,其直接關(guān)系到每個(gè)樣本點(diǎn)局部密度的計(jì)算,最終聚類結(jié)果對(duì)dc設(shè)置較敏感。在原始算法中,dc的選取是基于啟發(fā)式的,即dc應(yīng)確保平均每個(gè)點(diǎn)的鄰居點(diǎn)的數(shù)量占到整個(gè)數(shù)據(jù)集樣本量的一定比例,這個(gè)值一般被設(shè)置為1%～2%。針對(duì)雷達(dá)信號(hào)分選所面臨的信號(hào)參數(shù)密度分布不均衡的特點(diǎn),這種啟發(fā)式方法顯然不是一種科學(xué)合理的選擇。同時(shí),其中提到的可達(dá)距離計(jì)算方法、信號(hào)類別的分配規(guī)則也需要改進(jìn),以更好地適應(yīng)復(fù)雜雷達(dá)數(shù)據(jù)的聚類場(chǎng)景,下面將對(duì)改進(jìn)方法展開具體分析與論述。

2.1 直方圖均衡化理論

首先,對(duì)數(shù)據(jù)各維度特征進(jìn)行歸一化,計(jì)算各數(shù)據(jù)點(diǎn)之間的距離形成距離矩陣

(5)

根據(jù)計(jì)算局部密度的方法可以看出,各數(shù)據(jù)點(diǎn)的相對(duì)密度大小只決定于相互之間的距離大小,不受dc的影響,因此可以完成直方圖的均衡化[12],即

(6)

式中:k=1,2,…,L-1,L為離散化的灰度級(jí)數(shù);ni為灰度為i級(jí)的樣本點(diǎn)數(shù);n為總樣本點(diǎn)數(shù)。直方圖均衡化后的密度矩陣為Rhisteq。

2.2 改進(jìn)的可達(dá)距離

原始CFSFDP方法僅依靠點(diǎn)與點(diǎn)之間的最近距離信息當(dāng)作可達(dá)距離,忽視了與周圍其他點(diǎn)之間的關(guān)系,這使得原始方法雖然可以在簡(jiǎn)單的數(shù)據(jù)集上獲得不錯(cuò)的效果,但不能很好地反映點(diǎn)與點(diǎn)之間的復(fù)雜結(jié)構(gòu)關(guān)系,因此在處理密度差異較大、參數(shù)相互交疊的數(shù)據(jù)時(shí),性能下降顯著。比如,按照原始方法在全局范圍內(nèi)尋找與當(dāng)前點(diǎn)最近的高密度點(diǎn),當(dāng)不同簇的數(shù)據(jù)密度差異較大時(shí),很有可能面臨離真正隸屬的簇較遠(yuǎn),被劃分到其他簇的可能。因此,綜合考慮距離與數(shù)據(jù)結(jié)構(gòu)信息尤為必要。對(duì)于數(shù)據(jù)集X中任意一點(diǎn)i,尋找密度大于i的點(diǎn)j,然后最小化兩點(diǎn)之間的距離與到它們各自k最近鄰點(diǎn)距離和的乘積作為點(diǎn)的可達(dá)距離δi。定義i,j兩點(diǎn)到各自k近鄰點(diǎn)的距離之和θ(i,j)為

(7)

式中:dij為i,j兩點(diǎn)之間的距離;Γ(i)是點(diǎn)i的k最近鄰點(diǎn)所構(gòu)成的集合;p為集合Γ(i)中的點(diǎn);q為集合Γ(j)中的點(diǎn)。

可達(dá)距離δi為

(8)

對(duì)于最高密度點(diǎn),其可達(dá)距離為

(9)

當(dāng)k增加時(shí),點(diǎn)i和j之間的最近鄰點(diǎn)數(shù)量會(huì)增加,點(diǎn)i和j到各自鄰居點(diǎn)的距離之和也會(huì)增加,即導(dǎo)致θ(i,j)的增加,但影響程度因數(shù)據(jù)簇密度不同而有差異,對(duì)于低密度簇,增加較為明顯,而對(duì)于高密度簇,增加較少。

假設(shè)dij是常數(shù)固定值,當(dāng)點(diǎn)i,j到各自的鄰居點(diǎn)距離較遠(yuǎn)時(shí),會(huì)使得δi較大,即在隨后的決策圖中低密度簇的聚類中心更容易被發(fā)現(xiàn)。

假設(shè)θ(i,j)是常數(shù)固定值,如果點(diǎn)i與j之間的距離較大,那么也會(huì)導(dǎo)致δi較大,這滿足了原始CFSFDP方法中對(duì)于兩個(gè)聚類中心之間相距較遠(yuǎn)的假設(shè)。反言之,當(dāng)兩個(gè)點(diǎn)之間歐氏距離較小時(shí),很難同時(shí)成為聚類中心。

通過以上分析可以看出,此處定義的δi不僅考慮到了點(diǎn)之間的距離因素,而且考慮到了點(diǎn)周圍鄰居點(diǎn)的信息,這對(duì)于提高同時(shí)含有高低密度簇的數(shù)據(jù)集中低密度簇的聚類性能有實(shí)際意義。因?yàn)閷?duì)于低密度中心點(diǎn)而言,在決策圖中雖然密度不占優(yōu)勢(shì),但可達(dá)距離較大;反之,高密度點(diǎn)的密度雖然較高,但可達(dá)距離較小;如此相互平衡,可以較好地解決原始CFSFDP方法中難以無遺漏發(fā)現(xiàn)密度差異較大數(shù)據(jù)集聚類中心的問題。

在閾值設(shè)置過程中,切比雪夫不等式僅基于數(shù)據(jù)的均值與方差進(jìn)行計(jì)算,適用于任意分布數(shù)據(jù),在確定界限時(shí)不需要考慮數(shù)據(jù)的分布情況。通過前面分析可知,相比于非聚類中心,聚類中心的局部密度和可達(dá)距離應(yīng)該明顯較大,因此文獻(xiàn)[13]提到可以將歸一化后密度的上限ρ*設(shè)置為

ρ*≥μ(X)+τσ(X)

(10)

式中:μ表示期望;σ表示標(biāo)準(zhǔn)差;τ經(jīng)過驗(yàn)證選取為2較合適。

(11)

在分別得出局部密度和可達(dá)距離的閾值后,應(yīng)該考慮如何設(shè)置最終閾值判決函數(shù),將兩個(gè)參數(shù)信息綜合考慮,準(zhǔn)確識(shí)別出聚類中心所在。如果只是將兩個(gè)參數(shù)進(jìn)行線性組合構(gòu)成最終門限函數(shù),那么當(dāng)某些中心點(diǎn)的其中一個(gè)參數(shù)超過閾值,另一個(gè)沒超過閾值;或者兩個(gè)參數(shù)都在閾值附近,但明顯大于一般點(diǎn)的參數(shù)值。在這些情況下,兩個(gè)參數(shù)線性組合構(gòu)成的門限函數(shù)不能很好判決聚類中心。

(12)

根據(jù)判決門限函數(shù),對(duì)數(shù)據(jù)集中的所有數(shù)據(jù)點(diǎn)進(jìn)行判斷,滿足條件的被識(shí)別為聚類中心,實(shí)現(xiàn)了聚類中心的自動(dòng)判決,無需人為手動(dòng)識(shí)別。

2.3 改進(jìn)的分配準(zhǔn)則

原始CFSFDP方法直接根據(jù)局部密度降序的順序,將非聚類中心點(diǎn)分配到最近的高密度點(diǎn)所屬簇中,這種方法沒有考慮到點(diǎn)自身所處的周圍鄰居點(diǎn)信息,很容易錯(cuò)誤地將低密度點(diǎn)劃分到不正確的高密度簇中,因?yàn)榫嚯x最近的點(diǎn)不一定同屬一類。同時(shí),這種按照密度降序分配的規(guī)則,一旦中間出現(xiàn)錯(cuò)誤,很容易造成后續(xù)點(diǎn)分配的鏈?zhǔn)藉e(cuò)誤。因此,為了更好地結(jié)合點(diǎn)自身所具備的密度信息和所處的周圍數(shù)據(jù)結(jié)構(gòu)鄰居點(diǎn)信息,文獻(xiàn)[15]提出對(duì)當(dāng)前未被分配的點(diǎn)求出其最近的M個(gè)高密度點(diǎn),評(píng)價(jià)當(dāng)前點(diǎn)與這M個(gè)點(diǎn)的相似性,相似性評(píng)價(jià)方法是當(dāng)前點(diǎn)的k鄰居點(diǎn)集合與高密度點(diǎn)的k鄰居點(diǎn)集合交集的大小,交集越大,說明兩者相似性越高,與該高密度點(diǎn)同屬一簇的概率也越大。本文認(rèn)為,這里對(duì)于雷達(dá)數(shù)據(jù)密度差異可能較大的情況,會(huì)出現(xiàn)當(dāng)前點(diǎn)與不同簇的高密度點(diǎn)都有交集的情況,此時(shí)難以判斷最終所屬類別。同時(shí),交集大小也是對(duì)于兩者距離相近程度的一種度量,沒有很好地反映周圍數(shù)據(jù)結(jié)構(gòu)信息。因此提出,對(duì)于一部分高密度點(diǎn),按照就近原則進(jìn)行分配,對(duì)于其余所有點(diǎn),找到當(dāng)前點(diǎn)的M個(gè)高密度近鄰點(diǎn),對(duì)其所屬類別進(jìn)行投票,按照少數(shù)服從多數(shù)原則,進(jìn)行所屬類別的判決。這里既考慮到了距離因素,即相似性程度,又考慮到了周圍數(shù)據(jù)結(jié)構(gòu)信息,對(duì)復(fù)雜數(shù)據(jù)分布適應(yīng)性更好,因此將當(dāng)前點(diǎn)i所屬簇判決為

(13)

式中:φi為i點(diǎn)所屬簇;k為近鄰點(diǎn)數(shù);nclus為識(shí)別出的聚類中心數(shù);mod(·)為查找眾數(shù)函數(shù),ν(i)為i點(diǎn)的M個(gè)近鄰高密度點(diǎn)集合。

2.4 改進(jìn)CFSFDP方法流程

輸入:包含特征參數(shù)的雷達(dá)脈沖序列數(shù)據(jù)集。

1) 對(duì)數(shù)據(jù)進(jìn)行歸一化預(yù)處理;

2) 計(jì)算樣本數(shù)據(jù)集中各點(diǎn)之間的距離,形成式(5)距離矩陣;

3) 設(shè)置初始截?cái)嗑嚯x,根據(jù)式(3)計(jì)算局部密度,并根據(jù)式(6)對(duì)密度值進(jìn)行直方圖均衡化;

4) 按照局部密度降序排列,根據(jù)式(8)、式(9)計(jì)算改進(jìn)的可達(dá)距離;

5) 對(duì)參數(shù)值局部密度、可達(dá)距離進(jìn)行歸一化,并根據(jù)式(12)自動(dòng)判決可能存在的聚類中心;

6) 根據(jù)改進(jìn)的分配準(zhǔn)則式(13)對(duì)非聚類中心點(diǎn)進(jìn)行分配。

輸出:數(shù)據(jù)集中各點(diǎn)所屬簇信息。

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

為驗(yàn)證本文所提方法的有效性,通過仿真數(shù)據(jù)集及UCI標(biāo)準(zhǔn)數(shù)據(jù)集(Aggregation[16],Jain[17],R15[18])進(jìn)行實(shí)驗(yàn),驗(yàn)證方法在不同參數(shù)分布特點(diǎn)下的性能,并與原始CFSFDP方法及典型的聚類方法(如DBSCAN,K-means,AP,OPTICS)進(jìn)行比較。

實(shí)驗(yàn)1 仿真數(shù)據(jù)集實(shí)驗(yàn),仿真參數(shù)如表1所示。

表1 仿真數(shù)據(jù)參數(shù)

表1中,12部雷達(dá)輻射源數(shù)據(jù)參數(shù)之間存在交疊,以模擬真實(shí)雷達(dá)信號(hào)分選過程中面臨的實(shí)際情況。按照方法流程,對(duì)數(shù)據(jù)歸一化后,據(jù)式(3)、式(6)計(jì)算出數(shù)據(jù)集直方圖均衡化后的局部密度Rhiseq,據(jù)式(8)、式(9)計(jì)算改進(jìn)的可達(dá)距離δi,二者分別歸一化后根據(jù)式(12)計(jì)算得到門限決策值γ,如圖 1所示。

從圖1中可以準(zhǔn)確識(shí)別出12個(gè)聚類中心點(diǎn),最后根據(jù)改進(jìn)的分配準(zhǔn)則式(13)對(duì)所有點(diǎn)進(jìn)行所屬類別的分配,形成如圖2(a)所示的聚類結(jié)果,原始CFSFDP方法聚類結(jié)果如圖2(b)所示。

圖1 仿真數(shù)據(jù)γ值

圖2 改進(jìn)前后聚類結(jié)果

從圖2結(jié)果可以看出,得益于均衡化及改進(jìn)的分配規(guī)則,改進(jìn)CFSFDP方法對(duì)于信號(hào)參數(shù)距離較近情況下的聚類性能得到了提升。

采用調(diào)整蘭德系數(shù)(ARI)、調(diào)整互信息(AMI)和F1-measure值評(píng)價(jià)算法對(duì)仿真數(shù)據(jù)集的聚類結(jié)果進(jìn)行評(píng)價(jià),指標(biāo)對(duì)比如表2所示。其中:ARI及AMI用來衡量真實(shí)值與聚類結(jié)果之間分布的吻合程度;F1-measure綜合考慮召回率與精確率兩個(gè)指標(biāo),更完整地評(píng)價(jià)算法性能。

表2 仿真數(shù)據(jù)集聚類結(jié)果

通過表2中不同方法對(duì)仿真數(shù)據(jù)集的聚類結(jié)果性能指標(biāo)對(duì)比可以看出,本文方法在參數(shù)交疊、不同簇相距較近的情況下有較好的性能提升。

實(shí)驗(yàn)2 UCI標(biāo)準(zhǔn)數(shù)據(jù)集實(shí)驗(yàn)。

圖3展示了6種方法(DBSCAN,K-means,AP,OPTICS,CFSFDP,本文方法)在UCI的3個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)際聚類效果,最終性能評(píng)價(jià)指標(biāo)對(duì)比如表3所示。

圖3 6種方法在3個(gè)數(shù)據(jù)集上的聚類結(jié)果

表3 3個(gè)數(shù)據(jù)集聚類指標(biāo)對(duì)比

通過實(shí)驗(yàn)結(jié)果可以得出:本文方法與K-means方法在R15數(shù)據(jù)集上性能相當(dāng),但對(duì)于聚類數(shù)目的先驗(yàn)信息錯(cuò)誤時(shí)K-means性能下降明顯;DBSCAN方法在3個(gè)數(shù)據(jù)集上適應(yīng)性較好,而本文方法性能總體優(yōu)于DBSCAN方法;本文方法與原始CFSFDP方法在Aggregation及R15類球形分布且點(diǎn)密度均勻數(shù)據(jù)集上都可以取得較好結(jié)果,但在Jain密度不均勻數(shù)據(jù)集上本文方法性能明顯優(yōu)于原始CFSFDP方法及其他聚類方法。綜上可以看出,本文方法相比于原始CFSFDP方法及經(jīng)典聚類方法有更好的適應(yīng)性,在參數(shù)交疊、密度分布不均勻、任意形狀數(shù)據(jù)集上的聚類性能也得到了提升。

4 結(jié)束語

本文重點(diǎn)對(duì)應(yīng)用CFSFDP方法進(jìn)行雷達(dá)信號(hào)聚類分選任務(wù)面臨的問題進(jìn)行了研究并提出改進(jìn)方法,針對(duì)聚類結(jié)果對(duì)dc設(shè)置敏感的問題采用均衡化思想對(duì)局部密度進(jìn)行處理,可適應(yīng)不同分布數(shù)據(jù)聚類需求;針對(duì)信號(hào)參數(shù)交疊、參數(shù)密度分布不均衡的復(fù)雜場(chǎng)景,提出改進(jìn)的可達(dá)距離計(jì)算方式,在考慮密度信息的同時(shí)添加數(shù)據(jù)結(jié)構(gòu)信息,同時(shí)改進(jìn)對(duì)非聚類中心點(diǎn)的分配規(guī)則,提升應(yīng)對(duì)復(fù)雜數(shù)據(jù)集的分選性能。最后,通過不同分布特點(diǎn)的數(shù)據(jù)集驗(yàn)證了所提方法的有效性。實(shí)驗(yàn)表明,本文的方法可以較好地實(shí)現(xiàn)對(duì)不同分布特點(diǎn)下數(shù)據(jù)的自動(dòng)聚類分選,同時(shí),與原始CFSFDP方法及經(jīng)典聚類方法對(duì)比顯示本文所提改進(jìn)方法具有良好的聚類性能。今后將考慮提取挖掘雷達(dá)信號(hào)新特征,應(yīng)用到聚類預(yù)分選環(huán)節(jié),提升算法性能,為信號(hào)主分選及目標(biāo)識(shí)別等任務(wù)奠定基礎(chǔ)。