王美玲，張復(fù)春，楊承志

（空軍航空大學(xué)，長(zhǎng)春 130022）

0 引 言

雷達(dá)輻射源識(shí)別是雷達(dá)偵察設(shè)備的一項(xiàng)基本功能，無(wú)論是對(duì)戰(zhàn)時(shí)的敵我識(shí)別還是和平時(shí)期的電子偵察都起著重要作用，也是實(shí)施雷達(dá)干擾的基礎(chǔ)和前提。隨著雷達(dá)技術(shù)的迅猛發(fā)展以及新體制雷達(dá)的應(yīng)用，雷達(dá)信號(hào)的密度、復(fù)雜程度都大幅度提高，傳統(tǒng)的識(shí)別方法如模式匹配法等對(duì)先驗(yàn)知識(shí)未知的雷達(dá)輻射源無(wú)法進(jìn)行識(shí)別，不能適應(yīng)日益復(fù)雜的電磁信號(hào)。雷達(dá)輻射源信號(hào)通常是未知的，而無(wú)監(jiān)督聚類(lèi)是解決這類(lèi)問(wèn)題的有效方法。DBSCAN聚類(lèi)算法［1］是目前機(jī)器學(xué)習(xí)領(lǐng)域的熱點(diǎn)。但是，DBSCAN在處理分布復(fù)雜、樣本不均勻分布時(shí)的識(shí)別率較低。其主要原因是該算法在聚類(lèi)時(shí)采用了全局變量，影響了聚類(lèi)質(zhì)量。針對(duì)DBSCAN算法在處理不均勻樣本時(shí)識(shí)別率較低的缺陷，本文引入親和傳遞（AP）算法［2－4］，并將該算法與 DBSCAN 算法結(jié)合，以期達(dá)到提高識(shí)別率的目的。實(shí)驗(yàn)表明，新的算法能有效處理不均勻樣本，獲得較高的正確識(shí)別率。

1 DBSCAN算法分析

DBSCAN算法是由Ester Martin等人提出的一種基于密度的空間聚類(lèi)算法。該算法利用基于密度的聚類(lèi)概念，即要求聚類(lèi)空間中一定區(qū)域內(nèi)包含對(duì)象（點(diǎn)或其他空間對(duì)象）的數(shù)目不小于某一給定的閾值。DBSCAN算法具有聚類(lèi)速度快、有效處理噪聲點(diǎn)和發(fā)現(xiàn)任意形狀空間聚類(lèi)的優(yōu)點(diǎn)。

DBSCAN算法的中心思想是：對(duì)于某一聚類(lèi)中的每個(gè)對(duì)象，在給定半徑（文中用Eps表示）的鄰域內(nèi)數(shù)據(jù)對(duì)象個(gè)數(shù)必須大于某個(gè)給定值，也就是說(shuō)，鄰域密度必須超過(guò)某一閾值（文中用Minpts表示）。DBSCAN算法的聚類(lèi)過(guò)程基于如下事實(shí)：任意兩核心點(diǎn)，如它們之間的距離在Eps內(nèi)，則將它們放入一類(lèi)中；類(lèi)似地，與核心點(diǎn)的距離足夠近的邊界點(diǎn)也放入核心點(diǎn)相同的類(lèi)中，丟棄噪音點(diǎn)。

1.1 相關(guān)概念

DBSCAN相關(guān)的一些定義：

定義1：x是給定數(shù)據(jù)集D中的一個(gè)對(duì)象，x的Eps鄰域定義為：NEps＝ ｛y∈D｜d（x，y）≤Eps｝。

定義2：如果一個(gè)對(duì)象的鄰域中至少包含Minpts個(gè)對(duì)象，就稱(chēng)這個(gè)對(duì)象為核心對(duì)象。

定義3：對(duì)于一個(gè)給定對(duì)象，如果它屬于某個(gè)核心點(diǎn)的近鄰而自己本身不是核心點(diǎn)，那么稱(chēng)它為邊界點(diǎn)，如圖1所示。

圖1 核心點(diǎn)和邊界點(diǎn)

定義4：如果p是一個(gè)核心對(duì)象，p在q的鄰域Eps中，稱(chēng)p是從直接密度可達(dá)的。

定義5：如果存在一個(gè)對(duì)象鏈p1，p2，…，p n，其中p1＝p，p n＝q，且滿(mǎn)足p i從p i＋1直接密度可達(dá)，則稱(chēng)對(duì)象p是從對(duì)象q關(guān)于Eps和Minpts密度可達(dá)。

定義6：如果對(duì)象集合D中存在一個(gè)對(duì)象o，使得對(duì)象p和q是從關(guān)于Eps和Minpts密度可達(dá)的，那么對(duì)象p和q是關(guān)于Eps和Minpts密度相連的。

1.2 聚類(lèi)過(guò)程

DBSCAN算法的詳細(xì)步驟：

（1）將所有點(diǎn)分類(lèi)，分別標(biāo)記為核心點(diǎn)、邊界點(diǎn)或噪音點(diǎn)；

（2）刪除噪音點(diǎn)；

（3）連接距離在Eps內(nèi)的所有核心點(diǎn)；

（4）將之間存在的連接的核心點(diǎn)放入同一類(lèi)中；

（5）將邊界點(diǎn)分入與之相應(yīng)的核心點(diǎn)所在類(lèi)中。

雖然DBSCAN算法有聚類(lèi)速度快、能夠有效處理噪聲點(diǎn)和發(fā)現(xiàn)任意形狀的空間聚類(lèi)的優(yōu)點(diǎn)，但是該算法無(wú)法同時(shí)聚類(lèi)不同密度的簇，這是因?yàn)樗鼘?duì)于一個(gè)數(shù)據(jù)集只選取統(tǒng)一的Eps和Minpts。在實(shí)際情況下，簇的密度雖然不同，但具有一定的相同意義，這種情況在輻射源識(shí)別問(wèn)題中很容易造成增批現(xiàn)象。

2 AP聚類(lèi)算法分析

2.1 算法思想

親和傳遞（AP）聚類(lèi)是由Frey等人于2007年在Science上提出的一種新的無(wú)監(jiān)督聚類(lèi)算法。親和傳遞聚類(lèi)算法的快速、有效性體現(xiàn)在處理大數(shù)據(jù)集的聚類(lèi)問(wèn)題上，例如對(duì)數(shù)千個(gè)手寫(xiě)郵政編碼的圖片，該算法只花費(fèi)了5 min就可以找出能準(zhǔn)確解釋各種筆跡類(lèi)型的少量圖片，而K均值算法在同樣的時(shí)間內(nèi)達(dá)到的精度卻很低。

AP算法將所有的數(shù)據(jù)點(diǎn)看成潛在的聚類(lèi)中心點(diǎn)，這樣就避免了聚類(lèi)結(jié)果受限于初始類(lèi)代表點(diǎn)的選擇。在AP聚類(lèi)中，假設(shè)把每個(gè)數(shù)據(jù)點(diǎn)都看作是有向圖中的一個(gè)節(jié)點(diǎn)，任意節(jié)點(diǎn)之間傳遞責(zé)任度和可用度2種信息，在該圖的有向途徑上不斷遞歸地傳送這2種信息并修改它們的值，直到一個(gè)適合的類(lèi)代表點(diǎn)和相應(yīng)的聚類(lèi)出現(xiàn)，如圖2所示。

2.2 AP算法的過(guò)程

AP算法首先建立一個(gè)N×N相似度關(guān)系矩陣S作為工作基礎(chǔ)，此相似度矩陣是由N個(gè)數(shù)據(jù)點(diǎn)之間的相似度組成的。本文使用負(fù)的歐氏距離平方來(lái)計(jì)算任意兩點(diǎn)之間的相似度，如S（i，j）＝－｜｜x iy j｜｜2，其范圍在（－∞，0］。相似度矩陣S就是由這些相似度組成的N×N階矩陣。在循環(huán)迭代過(guò)程中，各樣本點(diǎn)競(jìng)爭(zhēng)最終的聚類(lèi)中心。

圖2 AP算法主要思想

在循環(huán)迭代中，若一個(gè)數(shù)據(jù)點(diǎn)x k處于其相鄰數(shù)據(jù)點(diǎn)的中心位置上，則該點(diǎn)與其它數(shù)據(jù)點(diǎn)的相似度之和較大，即s（i，k）之和較大，將它作為類(lèi)代表點(diǎn)的可能性也就較大。反之，處于聚類(lèi)邊緣的數(shù)據(jù)點(diǎn)與其它數(shù)據(jù)點(diǎn)的相似度之和）較小，成為聚類(lèi)中心的可能性也越小。聚類(lèi)之前，AP算法中需預(yù)先設(shè)定的偏向參數(shù)p（k）作為樣本點(diǎn)k被選作聚類(lèi)中心的傾向性。

通常在沒(méi)有先驗(yàn)知識(shí)的情況下，筆者認(rèn)為每個(gè)數(shù)據(jù)點(diǎn)的偏向參數(shù)都應(yīng)取相同的值，一般取相似度矩陣S的中值作為偏向參數(shù)p的初始值，即設(shè)定所有偏向參數(shù)p（k）為相同值p。同樣，p值的大小也影響到最終得到聚類(lèi)的類(lèi)的個(gè)數(shù)。AP算法可以通過(guò)改變p值來(lái)尋找合適的類(lèi)的數(shù)目，一般情況下，減小p值可以減少類(lèi)的個(gè)數(shù)，增大p值可以增加類(lèi)的個(gè)數(shù)，p是AP算法的一個(gè)重要參數(shù)。

AP算法任意2個(gè)數(shù)據(jù)點(diǎn)之間傳遞著2種類(lèi)型的消息，分別為責(zé)任度矩陣R＝［r（i，k）］n×n和可用度矩陣A＝［a（i，k）］n×n。這2個(gè)信息量代表了不同的競(jìng)爭(zhēng)目的，r（i，k）是從點(diǎn)x i指向點(diǎn)x k，它代表點(diǎn)x k積累的能量，用來(lái)表示數(shù)據(jù)點(diǎn)x k適合作為數(shù)據(jù)點(diǎn)x i的類(lèi)代表點(diǎn)的代表程度。

a（i，k）是從點(diǎn)x k指向點(diǎn)x i，它代表點(diǎn)x i積累的能量，用來(lái)表示數(shù)據(jù)點(diǎn)x i選擇數(shù)據(jù)點(diǎn)x k作為類(lèi)代表點(diǎn)的合適程度。對(duì)于任何數(shù)據(jù)點(diǎn)x i，計(jì)算所有數(shù)據(jù)點(diǎn)的代表程度r（i，k）和a（i，k）之和。r（i，k）與a（i，k）的和越大，則k點(diǎn)作為聚類(lèi)中心的可能性就越大。AP算法的核心步驟為2個(gè)信息量的迭代更新過(guò)程。下面是責(zé)任度R與可用度A的計(jì)算公式［6］：

AP算法在信息更新這一步驟引入了另外一個(gè)重要的參數(shù)λ，即阻尼因子。它作為平衡因子，對(duì)上一次迭代和本次迭代的責(zé)任度和可用度進(jìn)行加權(quán)計(jì)算，得到本次迭代最終的相似度和可用度。平衡因子主要有2個(gè)作用：影響AP聚類(lèi)迭代的平穩(wěn)性；當(dāng)?shù)拇螖?shù)一定時(shí)，迭代循環(huán)發(fā)生振蕩不能收斂，可以增大阻尼因子使算法收斂。另外，當(dāng)算法產(chǎn)生的類(lèi)數(shù)過(guò)多時(shí)，也可以增大阻尼因子。設(shè)當(dāng)前迭代次數(shù)為i，加權(quán)公式為：

其中λ∈［0，1）阻尼因子的作用是避免AP算法發(fā)生振蕩，增大阻尼因子可以消除振蕩。在本文的實(shí)驗(yàn)中，為了避免振蕩的發(fā)生，設(shè)置阻尼因子為0.9。

AP聚類(lèi)相對(duì)K－Means聚類(lèi)的改進(jìn)之處在于：AP聚類(lèi)克服了K－Means聚類(lèi)方法的一些缺點(diǎn)：對(duì)初始聚類(lèi)中心的選擇極為敏感且容易陷入局部極值。在其迭代過(guò)程中不斷地搜索適合的聚類(lèi)中心，使得聚類(lèi)目標(biāo)函數(shù)最大化。

經(jīng)過(guò)聚類(lèi)后的數(shù)據(jù)變成了小樣本，減少了計(jì)算量，保證了系統(tǒng)實(shí)驗(yàn)具有可行性。所以該算法可以不必事先指定聚類(lèi)的數(shù)據(jù)，有助于解決未知雷達(dá)輻射源信號(hào)的識(shí)別處理問(wèn)題。

但是由于AP算法也是基于中心的聚類(lèi)算法，因此它也像其它中心算法一樣，不適應(yīng)非凸形分布的數(shù)據(jù)聚類(lèi)，且由于它的聚類(lèi)中心是實(shí)際數(shù)據(jù)，并非可移動(dòng)的虛擬中心，因此只能實(shí)現(xiàn)小范圍聚類(lèi)。實(shí)驗(yàn)證明，將AP聚類(lèi)算法用于信號(hào)識(shí)別會(huì)產(chǎn)生較嚴(yán)重的增批現(xiàn)象，因此需要對(duì)AP算法聚類(lèi)結(jié)果再進(jìn)行聚類(lèi)處理，以達(dá)到更理想的效果。

3 基于AP密度聚類(lèi)的雷達(dá)輻射源信號(hào)識(shí)別算法

3.1 基于AP密度聚類(lèi)算法流程

本文將AP聚類(lèi)與改進(jìn)后的DBSCAN算法結(jié)合，設(shè)計(jì)了適合未知雷達(dá)輻射源信號(hào)的識(shí)別算法，即基于AP密度算法。具體實(shí)現(xiàn)流程如圖3所示。

圖3 基于AP密度算法流程圖

3.2 基于AP密度聚類(lèi)分選實(shí)現(xiàn)步驟

基于AP密度聚類(lèi)分選的輸入是歸一化之后的脈沖描述字（PDW）特征參數(shù)，對(duì)PDW的信號(hào)分選處理過(guò)程如下：

（1）設(shè)置初始聚類(lèi)參數(shù)。初始聚類(lèi)參數(shù)有迭代數(shù)目、代表矩陣、適應(yīng)矩陣、阻尼因子和噪聲閾值。

（2）設(shè)輸入的歸一化［7］PDW 特征參數(shù)矩陣含有n條待聚類(lèi)的PDW特征參數(shù)（稱(chēng)為樣本），即：

式中：P為待分選的雷達(dá)信號(hào)特征參數(shù)矩陣；p i為一條PDW數(shù)據(jù)；θAOAi為第i個(gè)脈沖的到達(dá)角；τPWi為第i個(gè)脈沖的脈寬；fRFi為第i個(gè)脈沖的載頻。

（3）求解距離矩陣，得出相似矩陣，設(shè)置相似度矩陣對(duì)角線(xiàn)元素s（k，k）為矩陣的中值。

（4）進(jìn)行信息更新，找到每個(gè)數(shù)據(jù)點(diǎn)的類(lèi)中心點(diǎn)，若滿(mǎn)足以下迭代條件中任意一個(gè)，迭代過(guò)程則結(jié)束：

（a）滿(mǎn)足迭代次數(shù)；

（b）信息改變量低于閾值；

（c）選擇的類(lèi)中心值在連續(xù)幾次迭代中保持穩(wěn)定。

（5）生成局部聚類(lèi)結(jié)果，獲得聚類(lèi)與類(lèi)代表點(diǎn)。（6）設(shè)置局部密度聚類(lèi)閾值、鄰域半徑。

（7）運(yùn)用DBSCAN算法對(duì)AP聚類(lèi)結(jié)果進(jìn)行再次聚類(lèi)。

（8）輸出最終聚類(lèi)結(jié)果。

3.3 識(shí)別算法仿真實(shí)驗(yàn)及性能分析

為了驗(yàn)證基于AP密度聚類(lèi)算法對(duì)未知雷達(dá)輻射源信號(hào)識(shí)別的有效性，本節(jié)利用生成的PDW信號(hào)進(jìn)行基于AP密度聚類(lèi)算法的仿真實(shí)驗(yàn)。

為了驗(yàn)證本文算法的準(zhǔn)確性，對(duì)算法進(jìn)行了仿真試驗(yàn)，并將本算法與文獻(xiàn)［8］中提出的基于KMeans的改進(jìn)算法及DBSCAN算法進(jìn)行了比較。

為了體現(xiàn)雷達(dá)信號(hào)環(huán)境的復(fù)雜性、交錯(cuò)性與數(shù)據(jù)真實(shí)性，本實(shí)驗(yàn)查閱了機(jī)載和艦船雷達(dá)手冊(cè)，并結(jié)合前線(xiàn)真實(shí)數(shù)據(jù)，模擬了6部雷達(dá)信號(hào)數(shù)據(jù)，并設(shè)置了貼近實(shí)際的信號(hào)參數(shù)。雷達(dá)信號(hào)的頻域、時(shí)域、空域參數(shù)的變化形式是影響信號(hào)分選算法的主要因素，依據(jù)雷達(dá)手冊(cè)對(duì)相應(yīng)雷達(dá)輻射源的PDW參數(shù)變化形式進(jìn)行典型設(shè)置，如表1所示。

表1 仿真雷達(dá)輻射源參數(shù)信息表

從圖4～圖6和表2中可以看出，本文提出的基于AP密度算法成功將所有雷達(dá)信號(hào)識(shí)別出來(lái)，體現(xiàn)了較高的準(zhǔn)確性。

改進(jìn)的K－Means方法對(duì)第1部雷達(dá)進(jìn)行識(shí)別時(shí)產(chǎn)生了增批現(xiàn)象，這說(shuō)明雖然對(duì)原算法進(jìn)行了改進(jìn)，但是由于算法本身的限制，對(duì)于非凸形的信號(hào)分布仍然不能很好地進(jìn)行正確分選；基于密度的聚類(lèi)算法由于采用全局性參數(shù)，對(duì)第2部雷達(dá)進(jìn)行識(shí)別時(shí)出現(xiàn)了漏選情況。

圖4 改進(jìn)K－Means聚類(lèi)結(jié)果

圖5 DBSCAN聚類(lèi)結(jié)果

圖6 基于AP密度聚類(lèi)結(jié)果

表2 算法結(jié)果比較

4 結(jié)束語(yǔ)

本文在分析了AP聚類(lèi)及DBSCAN聚類(lèi)的基礎(chǔ)上，提出了一種基于基于AP密度聚類(lèi)的未知雷達(dá)輻射源信號(hào)識(shí)別算法。該方法在一定程度上克服了AP聚類(lèi)及DBSCAN聚類(lèi)的局限，提高了算法的識(shí)別率，具有一定的推廣價(jià)值。

［1］陳峰.基于聚類(lèi)的增量數(shù)據(jù)挖掘研究［D］.大連：大連海事大學(xué)，2007：27－34.

［2］Frey B J，Delbert Dueck.Clustering by passing messages between data points［J］.Science，2007（315）：972－976.

［3］Givoni I E，F(xiàn)rey B J.A binary variable model for affinity propagation［J］.Neural Computation，2009，21（6）：1589－1600.

［4］Dueck D，F(xiàn)rey B J，Jojic N.Constructing treatment portfolios using affinity propagation［A］.Proceeding of 12th Annual International Conference，RECOMB 2008［C］.Singapore，2008：360－371.

［5］肖宇，于劍.基于近鄰傳播算法的半監(jiān)督聚類(lèi)［J］.軟件學(xué)報(bào)，2007，19（11）：197－199.

［6］王慧，申石磊.一種改進(jìn)的特征加權(quán)K－means聚類(lèi)算法［J］.微電子學(xué)與計(jì)算機(jī)，2010，27（7）：161－163.

［7］孫鑫，侯慧群，楊承志.基于改進(jìn)K－均值分類(lèi)的未知信號(hào)分選方法［J］.現(xiàn)代電子技術(shù)，2010，17（2）：91－93.