劉志鵬，　田楨熔，　毛　重

(1.空軍航空大學(xué) 信息對抗系， 吉林 長春　130022；

2.空軍航空大學(xué) 飛行訓(xùn)練基地， 吉林 長春　130022；

3.空軍航空大學(xué) 信息管理中心， 吉林 長春　130022)

?

基于核仿射傳播聚類雷達(dá)信號分選

劉志鵬1，田楨熔2，毛重3

(1.空軍航空大學(xué) 信息對抗系， 吉林 長春130022；

2.空軍航空大學(xué) 飛行訓(xùn)練基地， 吉林 長春130022；

3.空軍航空大學(xué) 信息管理中心， 吉林 長春130022)

摘要：將一種新的仿射傳播聚類算法引入雷達(dá)信號分選，對仿射傳播聚類算法的相似度計算和評價指標(biāo)進(jìn)行改進(jìn)和簡化，提高了分選性能。實驗結(jié)果證明，本方法在不同的測試環(huán)境下均可以取得較好的分選效果。

關(guān)鍵詞：信號分選； 聚類算法； 核方法； 評價指標(biāo)

0引言

由于缺少先驗信息，對未知雷達(dá)信號的分選需利用參數(shù)自身的分布特點和規(guī)律進(jìn)行去交錯處理。聚類方法是一種無監(jiān)督的學(xué)習(xí)方法[1]，在缺少先驗信息的情況下，利用數(shù)據(jù)本身的相似度和一定的評價準(zhǔn)則來完成分類，從而發(fā)現(xiàn)數(shù)據(jù)集的內(nèi)在組織結(jié)構(gòu)，其優(yōu)良的特性非常適合對未知雷達(dá)信號的分選。

近年來，國內(nèi)外學(xué)者討論較多的聚類方法如k-means聚類[2]、網(wǎng)格密度聚類[3]、C-均值模糊聚類[4]等，存在著諸如對初始條件敏感、對類邊緣數(shù)據(jù)及高維數(shù)據(jù)處理不佳、需反復(fù)迭代等問題，因而并未在雷達(dá)信號分選中得到廣泛應(yīng)用。

仿射傳播聚類是Frey B J[5]等在Science上提出的一種新型聚類算法，不同程度上克服了上述聚類算法的不足，具有處理速度快，聚類準(zhǔn)確性高，可以自適應(yīng)給出聚類數(shù)目等優(yōu)點，文中即利用仿射傳播聚類算法對雷達(dá)信號進(jìn)行分選。但由于復(fù)雜體制雷達(dá)信號參數(shù)的分布和變化特征都極其復(fù)雜，而核方法通過將信號參數(shù)映射到高維空間中，把復(fù)雜的非線性分類問題轉(zhuǎn)化為高維特征空間中的線性分類或近似線性分類問題，文中為了提高仿射傳播聚類算法的性能，將核方法引入到分選過程中，提出核仿射傳播聚類算法。

1仿射傳播聚類算法原理

仿射傳播聚類(AP)算法的本質(zhì)是將各數(shù)據(jù)點視為網(wǎng)絡(luò)中的節(jié)點，通過各節(jié)點間信息的不斷交換，選出代表節(jié)點，從而完成聚類。算法首先構(gòu)造相似度矩陣，在此基礎(chǔ)上，計算數(shù)據(jù)點間的吸引度(responsibility)和歸屬度(availability)用以表示數(shù)據(jù)點間信息的傳遞和競爭，經(jīng)過有限次迭代后，得出最優(yōu)聚類結(jié)果。

1.1相似度矩陣及偏置

在初始狀態(tài)時，將每個數(shù)據(jù)點都視為潛在的代表點(聚類中心)，并計算相似度矩陣s，原始的AP算法的相似度采用歐式距離平方的負(fù)值，即s(i,k)=-‖xi-xk‖2，其中i≠k，即xi,xk為兩個不同的數(shù)據(jù)點。s(k,k)為偏置值，需預(yù)先設(shè)定，利用s(k,k)值可以控制聚類數(shù)目的大小，一般將s(k,k)設(shè)為總相似度的平均值，文獻(xiàn)[6]證明AP算法對初值不敏感，因此初始參數(shù)的選擇較為寬泛。

1.2吸引度和歸屬度的計算

定義r(i,k)和a(i,k)：r(i,k)為數(shù)據(jù)點xi向數(shù)據(jù)點xk發(fā)送的吸引度信息，r(i,k)表示xk作為xi的代表點的合適程度；a(i,k)為xk向xi發(fā)送的歸屬度信息，a(i,k)搜集其他數(shù)據(jù)點支持xk作為代表點的證據(jù)信息，反映xk作為xi代表點的可信度；二者之和作為xk是否為代表點的證據(jù)。數(shù)據(jù)點間信息傳遞原理如圖1所示。

圖1數(shù)據(jù)點信息傳遞示意

二者的計算方法為：

(1)

(2)

1.3迭代更新及聚類生成

由式(1)計算出所有數(shù)據(jù)點的吸引度r(i,k)后，即可根據(jù)r(i,k)通過式(2)計算每個數(shù)據(jù)點的歸屬度a(i,k)，再利用a(i,k)的新值依據(jù)式(1)計算r(i,k)，以此進(jìn)行循環(huán)迭代，從而完成數(shù)據(jù)點間的信息交換。為了防止迭代過程發(fā)生大幅度震蕩，采用衰減因子λ控制更新速率，不妨設(shè)當(dāng)前過程為第j個循環(huán)階段(j≥2)，更新規(guī)則如下：

(3)

(4)

式(3)、式(4)中右側(cè)的rj，aj為當(dāng)前吸引度和歸屬度依據(jù)式(1)、式(2)的計算值，式(3)、式(4)左側(cè)rj，aj為當(dāng)前循環(huán)確定的吸引度和歸屬度的最終值，rj-1和aj-1為上一個循環(huán)階段吸引度和歸屬度的最終值。對于點xi，在循環(huán)過程的任一階段，搜索到r(i,k)+a(i,k)的最大值，可以做出如下判斷：

1)若k≠i，則xk為xi的代表點；

2)若 k=i，則xi本身為一個代表點。

在第j個循環(huán)找到所有點xi(i=1,2,…,N)的代表點xk(k=1,2,…,m)，把代表點看成聚類中心，其所代表的數(shù)據(jù)點即為該聚類的成員，于是就得出了該階段的聚類結(jié)果。迭代的終止條件為是否滿足聚類評價指標(biāo)或達(dá)到最大迭代次數(shù)。聚類評價指標(biāo)一般采用Silhouette指標(biāo)[7]：假設(shè)n個數(shù)據(jù)點被劃分成m個類，其中某個類為Ci(i=1,2,…，m),p為Ci中的一個樣本，I(p)為聚類中樣本p與Ci中其他樣本的平均距離；Ci(i′≠i)為有別于Ci的另一個類，設(shè)d(p,Ci′)為樣本p到Ci′中所有樣本的平均距離，Dp=min{d(p,Ci′)}，其中i′=1，2，…，m且i′≠i；于是可得樣本p的Silhouette指標(biāo)為

(5)

由式(5)可計算出聚類Ci中每個樣本的Sil值，進(jìn)而求出所有類的平均值Sav(C)，通過觀察式(5)不難發(fā)現(xiàn)，Sav(C)通過類內(nèi)數(shù)據(jù)的平均距離反映類內(nèi)的離散程度，通過最小類間距離反映不同類的可分性，Silhouette指標(biāo)正是綜合以上兩個因素估計聚類質(zhì)量的優(yōu)劣，其值越大，代表聚類質(zhì)量越好。

仿射傳播聚類算法已在人臉識別、尋找基因外顯子、航線規(guī)劃等領(lǐng)域得到成功實踐，已證實其具備聚類速度快、聚類結(jié)果可靠、適合處理大類別、特征分布不規(guī)則的數(shù)據(jù)等優(yōu)點。然而，該算法的數(shù)據(jù)間相似度是利用歐式距離的負(fù)值來表征的，文獻(xiàn)[8]已證明，采用歐氏距離作為相似性測度的聚類方法，在處理非線性分類問題時，分類性能會嚴(yán)重下降?，F(xiàn)代體制雷達(dá)信號參數(shù)變化復(fù)雜，具有非線性分布的性質(zhì)，因此，若直接利用該算法進(jìn)行雷達(dá)信號分選，則無法更好地提高分選的準(zhǔn)確率。為此，文中引入核方法來改進(jìn)相似度計算，并簡化聚類指標(biāo)計算，提出核仿射傳播聚類算法(KernelizedAffinityPropagationClustering，KAPC)。

2核方法原理

核方法是機(jī)器學(xué)習(xí)中為處理非線性分類問題而發(fā)展起來的一種技巧，顧名思義，核方法通常采用核函數(shù)替代數(shù)據(jù)間的內(nèi)積運(yùn)算，將數(shù)據(jù)特征向量映射到高維的特征空間，從而使得在低維狀態(tài)下不易發(fā)掘的特征在高維度的特征空間得到凸顯，進(jìn)而使復(fù)雜的非線性分類問題轉(zhuǎn)化為較為簡單的線性分類問題[9]。核方法高效巧妙處理非線性問題的能力使其在模式識別、預(yù)測、綜合評價等問題中得到廣泛應(yīng)用。核方法將非線性分類問題轉(zhuǎn)化為線性分類的思想如圖2所示。

圖2核方法思想示意圖

但是，我們通常不能確知非線性映射Φ(·)的具體形式，然而通過選擇滿足Mercer半正定的核函數(shù)κ(xi,xj)，可以建立高維空間的內(nèi)積運(yùn)算即〈Φ(xi),Φ(xj)〉與低維空間原數(shù)據(jù)點間的關(guān)系：

(6)

常用的核函數(shù)有：

1)多項式核

(7)

式中:d----多項式階數(shù)。

2)高斯核

(8)

式中：β----高斯核寬度。

此外，由于升維映射是通過核函數(shù)隱式定義的非線性映射實現(xiàn)的，因此其內(nèi)積運(yùn)算就是利用原數(shù)據(jù)空間樣本間的運(yùn)算進(jìn)行的，計算量并未因為維數(shù)的增多而增多。文中在仿射傳播聚類的基礎(chǔ)上，引入核方法來構(gòu)建雷達(dá)信號分選模型，即是考慮到了其處理特征分布復(fù)雜、分類邊界非線性的數(shù)據(jù)所具有的優(yōu)勢。

3基于KAPC算法的雷達(dá)信號分選

3.1核方法下的相似度

引入非線性映射Φ:x→Φ(x)∈H，從而原數(shù)據(jù)空間的數(shù)據(jù)點被映射到高維核空間H中，則平方歐式距離可表述為：

(9)

式中i≠j，采用式(9)來代替原算法定義的歐式距離平方負(fù)值，作為新的相似性測度。同時，構(gòu)造核矩陣Κ

(10)

矩陣中每個元素為兩個樣本在高維空間內(nèi)積的結(jié)果，其大小表征了樣本間的相似性，其值越大，樣本屬于同類的概率就越大；反之，元素的值越小，對應(yīng)樣本的相似度越低，于是，利用核矩陣Κ代替原算法的相似矩陣S。此時，預(yù)設(shè)偏置為Κ(i,i)，吸引度的計算方法變形為下式

(11)

而歸屬度的計算基于式(2)且形式不變。

3.2核方法下簡化的聚類指標(biāo)

(12)

首先定義中心判別矩陣和聚類指標(biāo)矩陣。

1)中心判別矩陣。

將每個樣本點的吸引度和歸屬度之和作為元素構(gòu)成中心判別矩陣Z，則有

(13)

注意，此時r(i,k)與a(i,k)已進(jìn)行核化處理，搜索矩陣Z中每一行的最大值元素，設(shè)Z=(z1,z2,…,zn)T，Z(i,k')=max(zi)，則數(shù)據(jù)點k′是數(shù)據(jù)點i所在類的聚類中心。

2)聚類指標(biāo)矩陣。

將中心判別矩陣Z中的行最大值元素置1，其余元素置0，并由此構(gòu)成中心指標(biāo)矩陣W，設(shè)W=(w1,w2,…,wn)，其中wj(j=1,2,…,n)為構(gòu)成W的列向量，則元素不全為0的列向量wj′即為所形成的子類，wj′中非零元素的行坐標(biāo)對應(yīng)類j′所包含的樣本點，sum(wj′)為類j′成員的個數(shù)。

3)反聚類指標(biāo)矩陣。

于是，若假設(shè)樣本點p屬于類j′，則p與同類樣本點的平均相似度Ip可由下式獲得

(14)

式中：kp----矩陣K中第p行構(gòu)成的行向量；

wj′----類j′所對應(yīng)的指標(biāo)矩陣的列向量。

樣本點p與其他類樣本平均相異度為

(15)

進(jìn)而得出

(16)

(17)

3.3 基于核仿射傳播聚類算法的雷達(dá)信號分選流程

由于實際信號環(huán)境中存在著干擾脈沖，這些干擾脈沖有可能形成小樣本數(shù)的類，從而造成誤分選，因此，設(shè)定閾值Thsmall，當(dāng)某類別的脈沖個數(shù)小于Thsmall時，將其判定為小樣本數(shù)的類，這些小樣本數(shù)的類可能屬于某部雷達(dá)，也可能是干擾噪聲，因此需對這些小樣本數(shù)的脈沖組進(jìn)行后續(xù)判斷。

綜上，通過核方法改進(jìn)相似度計算及簡化聚類評價指標(biāo)后，基于KAPC算法的雷達(dá)信號分選流程總結(jié)如下：

1)對分選特征進(jìn)行歸一化處理；

2)初始化聚類參數(shù)，包括偏置值K(i,i)、衰減因子λ以及最大迭代次數(shù)；

3)設(shè)定核參數(shù)并計算核相似度矩陣K；

4)計算樣本間的吸引度和歸屬度，并進(jìn)行迭代更新；

5)生成聚類中心和各子類成員，并判斷是否收斂，若收斂，或達(dá)到最大迭代次數(shù)，則轉(zhuǎn)到步驟6),否則返回步驟4)；

6)根據(jù)聚類指標(biāo)矩陣和反聚類指標(biāo)矩陣計算每個聚類結(jié)果對應(yīng)的修改Silhouette指標(biāo)，判斷最優(yōu)的聚類結(jié)果，并識別出小樣本數(shù)的類別，流程如圖3所示。

圖3KAPC流程示意圖

4 仿真實驗

仿真環(huán)境：Windows 7,AMD CPU A6,4 GB 內(nèi)存，編程工具為MATLAB 7.10.1。分別利用生成的仿真信號和實際的偵察數(shù)據(jù)對算法進(jìn)行驗證。

4.1 仿真信號

實驗數(shù)據(jù)為模擬的典型雷達(dá)全脈沖數(shù)據(jù)，按脈沖到達(dá)時間順序生成方向相近的交疊脈沖串，考慮到實際偵察中存在的脈沖丟失及干擾脈沖會影響分選結(jié)果，因此向脈沖串引入一定量的丟失和干擾脈沖，脈沖參數(shù)及脈內(nèi)調(diào)制特征見表1。

表1　仿真數(shù)據(jù)典型脈沖參數(shù)

初始化KAPC算法參數(shù)，選擇高斯核作為核函數(shù)，文獻(xiàn)[10]通過大量雷達(dá)數(shù)據(jù)試驗驗證高斯核的分類能力，證實當(dāng)核寬度β≥0.5時，分類準(zhǔn)確率最高，文中取β=0.707；偏置值陣K(i,i)設(shè)為核矩陣陣K元素的平均值、衰減因子λ=0.5，最大迭代次數(shù)設(shè)為40次。

當(dāng)脈沖個數(shù)達(dá)到2 000時，分別測試KAPC算法在脈沖丟失及加入干擾脈沖情況下的分選正確率，并與原始AP算法，模糊C-均值算法及修正PRI算法進(jìn)行對比。分選正確率定義為：

模糊C-均值算法及修正PRI算法的參數(shù)設(shè)置分別同文獻(xiàn)[1]和文獻(xiàn)[11]，脈沖丟失率和干擾脈沖量從0變化到40%時，不同算法的分選正確率曲線對比如圖4所示。

(a) 脈沖丟失下的正確率

(b) 加干擾脈沖的正確率

從圖4可以看出，在沒有脈沖丟失和脈沖干擾的理想情況下，KAPC算法的分選正確率幾乎為100%，高于其他幾種常見的分選算法；隨著脈沖丟失和干擾脈沖的增多，分選正確率有所下降，但仍能接近90%，高于其他算法，且可以看出，雖然修正PRI變換算法的性能在理想情況下接近KAPC算法，但是一旦分選數(shù)據(jù)質(zhì)量下降，分選的準(zhǔn)確性迅速下降。

為驗證KAPC算法的處理速度，采用表1數(shù)據(jù)進(jìn)行測試，并與原始AP算法、修正PRI算法及模糊C-均值算法進(jìn)行比較。參數(shù)設(shè)置同上，不斷增加每部雷達(dá)的脈沖數(shù)，1 000次蒙特卡洛實驗后，得到脈沖數(shù)與處理時間的關(guān)系如圖5所示。

圖5　處理速度對比

從圖5可知，AP算法處理速度明顯優(yōu)于其他算法，而改進(jìn)后的KAPC算法在實時性上與原始AP算法相比又有了進(jìn)一步的提高。

4.2實際信號

為驗證KAPC在實際分選中的性能，選擇實際偵察數(shù)據(jù)作為實驗數(shù)據(jù)，利用不同方法得出分選結(jié)果，并將分選結(jié)果與人工分析后的結(jié)果比對，得到的分選正確率記錄見表2(KAPC算法及其它各算法的參數(shù)設(shè)置同上節(jié))。

從表2可以看出，KAPC在實際數(shù)據(jù)測試中仍能保持90%以上的分選正確率，其它的分選方法均低于90%，證實了KAPC算法良好的分選性能。

表2　實際數(shù)據(jù)測試結(jié)果　　　　　　　　　　　　　　　　　%

5 結(jié)語

研究了對未知雷達(dá)信號的分選方法，針對目前幾種聚類方法存在的不足，提出了核仿射傳播聚類算法，即利用核內(nèi)積運(yùn)算代替原仿射傳播聚類的相似度計算，在此基礎(chǔ)上利用指標(biāo)矩陣簡化了聚類評價指標(biāo)的計算，并對小樣本數(shù)據(jù)進(jìn)行噪聲識別。仿真實驗表明,該算法性能優(yōu)于其他算法，在不同信噪比的環(huán)境下均具有良好的分選性能，且運(yùn)算速度快，適合處理大規(guī)模脈沖數(shù)據(jù)集。

參考文獻(xiàn)：

[1]尹亮,潘繼飛,姜秋喜.基于模糊聚類的雷達(dá)信號分選[J].火力與指揮控制,2014,39(2):52-57.

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

[3]向嫻,湯建龍.一種基于網(wǎng)格密度聚類的雷達(dá)信號分選[J].火控雷達(dá)技術(shù),2010,39(4):67-72.

[4]楊多.復(fù)雜環(huán)境下多參數(shù)雷達(dá)信號分選算法研究[D].哈爾濱:哈爾濱工程大學(xué),2012:56-60.

[5]FreyBJ,DueckD.Clusteringbypassingmessagesbetweendatapoints[J].Science,2007,316(5814)：972-976.

[6]MichaelJ.Brusc，Hans-FriedrichKohn.Commenton“Clusteringbypassingmessagesbetweendatapoint”[J].Science,2008,319:726.

[7]JoshuaZH,MichaelKN,RongHongqiang,etal.Automatedvariableweightingink-meanstypeclustering[J].IEEETransactiononPatternAnalysisandMachineIntelligence,2005,27(5):657-668.

[8]王開軍,張軍英,李丹，等.自適應(yīng)仿射傳播聚類[J].自動化學(xué)報,2007,33(12):1242-1246.

[9]紀(jì)秋穎,林健.基于核方法的聚類算法及其應(yīng)用[J].北京航空航天大學(xué)學(xué)報,2006,32(6):747-750.

[10]普運(yùn)偉.復(fù)雜體制雷達(dá)輻射源信號分選模型與算法研究[D].成都:西南交通大學(xué),2007:69-70.

[11]羅長勝,吳華,程嗣怡.一種對重頻調(diào)制與抖動信號的PRI變換分選新方法[J].電訊技術(shù),2012,52(9):1491-1496.

A radar signal de-interleaving method based on kernelized affinity propagation clustering

LIU Zhipeng,TIAN Zhenrong,MAO Zhong*

(1.Information Countermeasure Department， Aviation University of Air Force, Changchun 130022， China；2.Flight Training Base， Aviation University of Air Force, Changchun 130022， China；3.Information Management Center， Aviation University of Air Force, Changchun 130022， China)

Abstract：A new affinity propagation clustering algorithm is applied to radar signal sorting for improving and simplifying the similarity calculation and evaluation indexes, so the sorting performance is optimized. Experiments verify that the good sorting features can be get with the method.

Key words：signal de-interleaving; clustering method; kernel trick; cluster validity index.

中圖分類號：TN 971

文獻(xiàn)標(biāo)志碼：A

文章編號：1674-1374(2016)01-0056-07

DOI:10.15923/j.cnki.cn22-1382/t.2016.1.12

作者簡介：劉志鵬(1990-)，男，漢族，吉林長春人，空軍航空大學(xué)碩士研究生，主要從事雷達(dá)信號分選與主識別方向研究,E-mail:tianrunlan@126.com.

收稿日期：2015-11-16