基于半監(jiān)督譜聚類的通信網臺識別方法*

丁天一，張 旻，方勝良

（國防科技大學電子對抗學院，合肥 230037）

0 引言

在未來信息化戰(zhàn)爭中，敵方通信網臺的識別將是戰(zhàn)場態(tài)勢分析的重要研究內容。隨著偵察手段的提高，數據庫中積累了大量雜亂無章的通信偵察數據，如何有效地從參數級數據中挖掘出有用知識，得到通信網臺間的通聯(lián)關系，完成通信網臺識別，成為了一個亟待解決的問題[1-2]。

文獻[3]提出了一種基于粗糙集理論進行偵察數據融合處理的方法，利用中心頻率、調制樣式和電臺位置作為關鍵屬性進行同一電臺的通信記錄合并，但由于偵察數據存在誤差，滿足條件的可能是一個通信網內的其他電臺。同時，該方法通過某一時刻電臺的平臺經度、平臺緯度和平臺高度定義的等價關系來對電臺庫的記錄進行分類，如果電臺存在航跡交叉勢必會造成誤判；文獻[4]提出了使用統(tǒng)計距離及DBSCAN算法用于通信電臺關聯(lián)，但該算法僅對電臺的位置信息進行聚類，沒有考慮其他屬性的影響，電臺間位置分布相近時很難做出正確判斷，存在較大誤差；文獻[5-7]提出了一種基于灰關聯(lián)分析和粗糙集的通信電臺識別方法，利用粗糙集理論進行等價類劃分得到電臺航跡后，把電臺航跡與雷達航跡進行關聯(lián)，判斷電臺與裝載平臺的關系，但該算法不能判斷哪些電臺在一個通信網內進行通信。

本文首先介紹了譜聚類算法和成對約束信息的相關概念，然后分析利用譜聚類算法進行通信網臺識別的合理有效性，并充分利用知識庫中已有的約束條件，提出了一種基于半監(jiān)督譜聚類的通信網臺識別方法。首先，通過密度峰值的方法確定通信網數目；然后通過半監(jiān)督譜聚類的方法完成通信網臺識別。實驗結果表明，本文提出的方法可以有效地完成通信網臺識別。

1 相關概念

1.1 譜聚類算法

譜聚類算法來源于譜圖的劃分理論，核心思想是將數據的聚類問題轉化為一個無向圖的多路劃分問題。譜聚類將數據集中的每個樣本點看作圖中的頂點V，頂點之間用邊E連接，其權重為樣本點間的相似度W，由此構造出了一個基于樣本相似度的無向加權圖G（V，E），聚類問題就轉化為圖G的最優(yōu)劃分問題，劃分準則就是使劃分成的子圖內部相似度最大，子圖之間的相似度最小。

譜聚類算法的實現方式有很多，但都可以歸納為以下3個步驟：1）根據相似度函數構造相似度矩陣，并計算得到Laplacian矩陣；2）計算Laplacian矩陣的前k個特征向量，構建特征向量空間；3）采用k-means等聚類算法對特征向量空間進行聚類。

相比于傳統(tǒng)的聚類算法，譜聚類算法能夠識別非凸分布聚類，收斂于全局最優(yōu)解，適用于許多實際問題[8]。

1.2 成對約束信息

聚類是一種典型的無監(jiān)督學習方法，然而在現實的聚類任務中往往能獲得少部分數據的先驗知識。因此，可以通過半監(jiān)督聚類的方法利用這些具有先驗知識的數據來輔助聚類，獲得更好的聚類效果。對于用戶來說，要確定樣本類屬會比較困難，而獲得一些關于樣本點是否可以或不能位于同一類的約束信息將會比較容易[9]。

若兩個數據點為must-link，則這兩個數據點必須在同一聚類中；若兩個數據點為cannot-link，則這兩個數據點必須分配在不同類中。must-link和cannot-link這兩類成對約束作為樣本的先驗信息在實際聚類中是非常容易得到的，但是一般數量有限，因此，需要對這些成對約束進行擴展。Klein等人提出must-link和cannot-link在樣本上具備一組二值傳遞關系：

式中，M和C分別表示must-link和cannot-link的約束集[10]。

利用上述傳遞關系，通過數據集中的成對約束信息，可以得到數據集的閉包關系。屬于同類閉包的數據點互為must-link，屬于異類閉包的數據點互為cannot-link。通過現有的成對約束求同類閉包和異類閉包，可以擴展must-link和cannot-link這兩類成對約束的數量，從而最大化地利用成對約束信息。

2 通信網臺識別

通信偵察的主要目的是通過對敵方通信信號的搜索、截獲、記錄、測向定位、技術參數測量，解調和監(jiān)聽通信信息等作業(yè)，獲取敵方通信信號內涵信息及技術參數，查明敵方通信電臺分布、活動規(guī)律及隸屬關系，提供戰(zhàn)略與戰(zhàn)術決策情報。通信偵察數據信息表如下頁表1所示[3]。

2.1 基于聚類分析的通信網臺識別

通信網臺識別面臨的主要問題有：數據的迅速更新使得數據庫中積累了大量雜亂無章的偵察數據難于分析；知識庫中不具備足夠的完整數據用于一般有監(jiān)督學習算法的學習過程。

聚類算法能夠通過無標記的樣本來揭示數據的內在性質及規(guī)律，將聚類算法用于通信網臺的識別和分析，能夠在已有知識匱乏的情況下，發(fā)現隱藏在其中的內在聯(lián)系，有效判斷通信網臺間的通聯(lián)關系。

2.2 半監(jiān)督譜聚類

傳統(tǒng)的聚類算法，如 k-means、k-medoids、模糊c均值等算法的聚類結果依賴于數據的分布，對于趨于球形分布的數據集能夠取得一個較好的聚類結果，但是對于不規(guī)則形狀數據集，聚類結果較差[11-12]。由于電臺目標分布的復雜性，傳統(tǒng)聚類算法的這一特點可能會帶來結果上的較大偏差。例如，電臺目標在地理位置上的分布會依據任務部署呈現出不規(guī)則分布，尤其在目標的轉移過程中可能會形成彎曲的帶狀分布。此時，傳統(tǒng)的聚類算法不再適用。因此，本文選取具有識別非凸分布聚類能力的譜聚類算法，聚類結果能夠收斂于全局最優(yōu)解。

表1 通信偵察數據信息表

譜聚類是一種基于配對的聚類算法，使得在算法中利用成對約束信息變得非常容易。通過偵察方已有的少量先驗知識，可以得到部分通信電臺間的通聯(lián)關系，以此作為must-link和cannot-link約束。將通信偵察數據投影到二維平面，并添加成對約束信息，如圖1所示。

圖1 添加成對約束信息

由圖1可以看出，通信網1和通信網2的部分通信偵察數據樣本相似度很高，難以區(qū)分；通信網2中的部分通信偵察數據樣本與同類別中的其他樣本相似度較小。在這種情況下，如果僅憑借無監(jiān)督的聚類分析方法進行通信網臺識別，結果經常會造成誤判。如果能夠根據偵察方已有的先驗知識，添加少量的成對約束信息輔助聚類，以半監(jiān)督聚類的方法來判別通信偵察數據樣本的類屬，就能夠有效地將不同通信網的通信電臺區(qū)分開，從而提高通信網臺識別準確率。

3 基于半監(jiān)督譜聚類的通信網臺識別方法

3.1 基于密度峰值的通信網數目確定

在通信網臺識別之前，首先需要判斷通信網的數目。密度峰值的方法可以自動發(fā)現數據集樣本的類簇中心，從而得到類別數目，其基本原理是理想的類簇中心應具備兩個基本特征：1）其局部密度大于圍繞它鄰居的局部密度；2）不同類簇中心之間的距離相對較遠[13]。

定義1（局部密度ρi）局部密度ρi采用高斯核的方法進行計算，計算結果滿足與xi的距離小于dc的數據點越多，ρi的值越大，如式（2）所示：

其中，dij為樣本xi與xj間的歐氏距離，dc為截斷距離。

定義2（相鄰密度點距離δi）在所有局部密度大于xi的數據點中，找到與xi距離最小的數據點，其與xi之間的距離即為相鄰密度點距離δi，如式（3）所示：

對于局部密度ρi最大的樣本xi，其。

由樣本xi的相鄰密度點距離δi的定義可見，若樣本xi的密度是最大局部密度或最大全局密度，則樣本xi的距離δi遠大于其最近鄰樣本的相鄰密度點距離。因此，類簇中心往往是δ異常大的樣本點，這些樣本點的局部密度ρ也相對較高。通過構造獲勝神經元相鄰密度點距離δ相對于局部密度ρ的決策圖，選擇ρ、δ都較大的點作為類簇中心，類簇中心的數目就是樣本的類別數。具體步驟如下：

Step 1：計算所有樣本間的距離dij。

Step 2：確定截斷距離dc。將上一步計算的n個樣本的距離dij進行升序排列，假設得到的升序序列為，則截斷距離dc為：

其中，t是每個樣本點的鄰居樣本點的平均個數占數據集樣本點總數的百分比，round（nt）表示對nt四舍五入后得到的整數。

Step 3：根據式（2）計算每一個樣本的局部密度ρi，將樣本按照局部密度由高到低進行排序。

Step 5：根據ρi和δi構成的關系決策圖，中點的分布位置，以“最上最右”的點為起點，按照“向下向左”的原則，找到與剩余點差異最大的一組點，這組點的ρ和δ都較大，并且明顯偏離剩余點所構成的密集分布區(qū)域，這組點的數目即為類別數k。

文獻[13]中給出dc的選擇策略是使每個樣本點的鄰居樣本點的平均個數是數據集樣本點總數的 1%到 2%，即 t∈[0.01，0.02]，本文將參數 t設置為0.02。

3.2 譜聚類相似度矩陣構造

為了能夠更好地適應樣本數據可能出現的不均勻分布，本文采用了文獻[12]提出的相似度矩陣構造方法：

3.3 基于成對約束的半監(jiān)督譜聚類

在某些特殊情況下，偵察方對通信偵察數據的情報分析過程中，可能具備一定量的先驗知識，這些先驗知識可能來自于對個別偵察目標的細致分析、對敵方通信裝備的掌控、長久以來偵察方知識庫積累的知識，以及情報分析人員對戰(zhàn)場環(huán)境和偵察數據的分析判斷等諸多方面。先驗知識作為判別通信電臺間通聯(lián)關系的重要約束條件，可以用來指導通信偵察數據的情報分析過程。

戰(zhàn)場區(qū)域內，同一個通信網內的所有通信電臺在進行通信的過程中一定會滿足以下基本條件：通信電臺的工作頻率屬于同一個頻段；通信信號的調制樣式和通信體制等技術參數相同；通信電臺在通信時間上存在交叉。如果在某一相同工作時間段內，某些通信電臺不在同一頻段工作、調制樣式不同或通信體制不同，那么這些通信電臺一定不在一個通信網內。

同時，通過知識庫中已有的先驗知識以及通信輻射源個體識別等方法，可以得到部分電臺間的通聯(lián)關系，以此作為must-link和cannot-link約束。

在獲得樣本間的成對約束后，通過修改相似度矩陣的方法來施加成對約束信息，按照式（6）的方法更新約束點間的相似度：

得到更新后的相似度矩陣之后，繼續(xù)執(zhí)行譜聚類的算法步驟，完成對通信偵察數據樣本的聚類。

3.4 算法步驟

輸出：通信偵察數據X的聚類結果。

Step 1：符號型屬性數值化，并采用式（7）的最小-最大規(guī)范化的方式進行數據預處理。

Step 2：通過密度峰值方法構造決策圖，找到明顯偏離剩余點所構成的密集分布區(qū)域的一組點，點的數目即為通信網數目k。

Step 3：根據式（1）的傳遞關系，通過初始成對約束集合M，C擴展成對約束關系。

Step 4：根據式（5）建立相似度矩陣W。

Step 5：按照式（6）的方法根據成對約束信息更新約束點間的相似度。

Step 6：計算規(guī)范化Laplacian矩陣L：

其中，D為W的度矩陣，對角線上的元素為W每行元素的和，表達式為。

Step 7：求解規(guī)范化Laplacian矩陣L的前k個最大特征值所對應的k個特征向量，建立矩陣，其中vi為列向量。

Step 8：對V的行向量規(guī)范化處理，得到單位長度向量組成的新矩陣Y，其中，。

Step 9：將Y的每一行看成是Rk空間內的一點，使用k-means算法把n行數據劃分為k類。

Step 10：當矩陣Y的第i行在類Aj中時，劃分原樣本空間中的樣本到Bj類中。

4 實驗結果與分析

仿真實驗以現有的外軍戰(zhàn)術電臺的技術參數為依據，按照表1通信偵察數據信息表的構成方式，模擬生成通信偵察數據進行實驗。通信偵察系統(tǒng)一般是由分布在偵察區(qū)域內的多個地面、升空等偵察設備組成，因此，在某一偵察時間段內，對于每一個通信電臺可能有多條通信偵察數據的記錄。在對通信偵察數據的聚類分析過程中，由于通信信號參數的復雜性，可能會造成一個通信電臺的多條偵察數據被劃分到不同的類別中。為此，在通信偵察數據的聚類分析實驗中，本文采取擇多法的判別方式來確定通信電臺的類屬，即如果某通信電臺的大多數通信偵察數據被劃分到某一類中，那么就將此通信電臺的類屬確定為該類。

仿真的場景為在一個短時間段內，偵察區(qū)域內有4個通信網內的共50個超短波電臺正在進行通信，通信電臺的地理位置相對固定，通信電臺的類型為美軍的SINCGARS電臺。仿真截獲了400條通信偵察數據，偵察記錄內容如表2所示。

表2 通信偵察數據信息表

依據通信偵察數據的經度與緯度參數可以得到通信電臺的地理位置分布，如圖2所示。

圖2 通信電臺地理位置分布

從圖2（a）可以看出，通信電臺的地理位置分布較為復雜，僅憑借地理位置分布很難區(qū)分屬于不同通信網的通信電臺。從圖2（b）可以看出，不同通信網的通信電臺在地理位置上分布相近，通信網3和通信網4的部分通信電臺在地理位置上存在交叉，同時通信網3的通信電臺形成了非凸的帶狀分布。

為了驗證基于半監(jiān)督譜聚類的通信網臺識別方法的有效性，本節(jié)設計了兩個實驗。實驗1在不具備約束條件的情況下分別采用k-means算法和譜聚類算法對通信偵察數據進行聚類分析，通過比較無約束條件下兩種算法的聚類結果，驗證選取譜聚類算法作為半監(jiān)督聚類中使用的聚類算法的合理性。實驗2在具備一定量約束條件的情況下，采用半監(jiān)督譜聚類算法對通信偵察數據進行聚類分析，實驗中增加不同數量的成對約束，通過比較不同數量成對約束下聚類結果的正確率驗證本文方法的有效性。

實驗1：無約束條件的聚類分析

實驗1在偵察方不具備先驗知識的情況下對通信偵察數據進行聚類分析。首先，采用k-means算法對通信偵察數據進行聚類實驗，得到的3次聚類結果如下頁圖3所示。

由圖3可以看出，由于k-means算法初始聚類中心的不確定性，即便在指定聚類數目的情況下，也會造成重復實驗過程中聚類結果的多樣性，不同聚類結果差別較大，使得通信網臺識別率較低。

圖3 k-means算法聚類結果

下一步，采用本文方法對通信偵察數據進行聚類實驗。在對通信偵察數據進行數據預處理后，通過密度峰值方法得到的決策圖如圖4所示。

圖4 決策圖

密度峰值方法得到的決策圖中有4個點明顯偏離于剩余點所構成的密集分布區(qū)域，因此，指定通信網的數目k=4。在不添加任何成對約束信息的情況下，采用譜聚類算法對通信偵察數據進行聚類實驗，得到的聚類結果如圖5所示。

圖5 譜聚類算法聚類結果

由圖5可以看出，譜聚類算法對通信偵察數據進行聚類后，得到的聚類結果的正確率要高于k-means算法的3次聚類結果，50個通信電臺中有43個通信電臺得到了正確的聚類結果，聚類正確率為86%。

實驗2：有約束條件的聚類分析

實驗2在具備一定量先驗知識的情況下對通信偵察數據進行聚類分析。假設根據偵察方所具備的先驗知識，可以得到通信電臺間成對約束的數目分別為25、50和75時對通信偵察數據進行聚類分析。由于所選的通信電臺以及通信電臺間約束的不同對聚類算法的性能有很大影響，所以對于每一個給定的成對約束數目產生50組不同的成對約束，以此重復進行50次實驗，輸出聚類結果的平均正確率，實驗結果如圖6所示。

由圖6可以看出，在增加了成對約束之后，通信偵察數據聚類結果的正確率有了提高，并且隨著約束對數目的增加，聚類結果的正確率呈上升趨勢。實驗結果表明，本文算法可以充分利用先驗知識，有效提高通信偵察數據聚類分析的正確率。

5 結論

通信偵察積累了大量的通信偵察數據，如何從海量偵察數據中挖掘出有用價值的信息，從而判別電臺間的通聯(lián)關系，是戰(zhàn)場態(tài)勢分析的重點。本文提出了一種基于半監(jiān)督譜聚類的通信網臺識別方法，通過密度峰值的方法判別通信網的數目，然后借助于已有的先驗知識，通過半監(jiān)督譜聚類方法對通信偵察數據進行聚類，得到最終的聚類結果。實驗結果表明，本文算法可以充分利用具備的先驗知識，有效地完成通信網臺識別。