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

王美玲，張復(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)督聚類是解決這類問(wèn)題的有效方法。DBSCAN聚類算法［1］是目前機(jī)器學(xué)習(xí)領(lǐng)域的熱點(diǎn)。但是，DBSCAN在處理分布復(fù)雜、樣本不均勻分布時(shí)的識(shí)別率較低。其主要原因是該算法在聚類時(shí)采用了全局變量，影響了聚類質(zhì)量。針對(duì)DBSCAN算法在處理不均勻樣本時(shí)識(shí)別率較低的缺陷，本文引入親和傳遞（AP）算法［2－4］，并將該算法與 DBSCAN 算法結(jié)合，以期達(dá)到提高識(shí)別率的目的。實(shí)驗(yàn)表明，新的算法能有效處理不均勻樣本，獲得較高的正確識(shí)別率。

1 DBSCAN算法分析

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

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

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

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

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

定義5：如果存在一個(gè)對(duì)象鏈p1，p2，…，p n，其中p1＝p，p n＝q，且滿足p i從p i＋1直接密度可達(dá)，則稱對(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 聚類過(guò)程

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

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

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

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

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

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

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

2 AP聚類算法分析

2.1 算法思想

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

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

圖2 AP算法主要思想

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

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

AP算法任意2個(gè)數(shù)據(jù)點(diǎn)之間傳遞著2種類型的消息，分別為責(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的類代表點(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作為類代表點(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)作為聚類中心的可能性就越大。AP算法的核心步驟為2個(gè)信息量的迭代更新過(guò)程。下面是責(zé)任度R與可用度A的計(jì)算公式［6］：

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

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

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

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

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

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

3.1 基于AP密度聚類算法流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了驗(yàn)證基于AP密度聚類算法對(duì)未知雷達(dá)輻射源信號(hào)識(shí)別的有效性，本節(jié)利用生成的PDW信號(hào)進(jìn)行基于AP密度聚類算法的仿真實(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é)合前線真實(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)行正確分選；基于密度的聚類算法由于采用全局性參數(shù)，對(duì)第2部雷達(dá)進(jìn)行識(shí)別時(shí)出現(xiàn)了漏選情況。

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

圖5 DBSCAN聚類結(jié)果

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

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

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

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

［1］陳峰.基于聚類的增量數(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)督聚類［J］.軟件學(xué)報(bào)，2007，19（11）：197－199.

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

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