DSets-DBSCAN無參數聚類的雷達信號分選算法

劉魯濤，王璐璐，李 品，陳 濤

(1. 哈爾濱工程大學 信息與通信工程學院， 黑龍江 哈爾濱 150001； 2. 南京電子技術研究所， 江蘇 南京 210000)

雷達信號分選是雷達信號處理中的重要一環，只有從多部隨機交錯的脈沖信號流中正確地分離出各單部雷達輻射源脈沖，才能對雷達數據進行準確分析，因此雷達信號分選的準確性直接影響了雷達的性能[1]。雷達信號分選主要由信號預分選和主分選兩部分組成，信號預分選作為雷達信號分選的一部分，主要是利用到達角(direction of arrival, DOA)、載頻(carrier frequency, CF)和脈寬(pulse width, PW)等參數進行聚類，對密集脈沖流進行稀釋處理，初步實現信號去交錯，便于主分選進行處理[2]，所以能正確聚類是得到準確分選結果的前提。

現有預分選算法主要是在K均值(K-means)聚類算法[3-4]、模糊C均值聚類(fuzzyC-means, FCM)算法[5]、密度聚類[6-7](density-based spatial clustering of applications with noise, DBSCAN)等幾個主流算法上進行改進，文獻[8]將數據場與K-means相結合，解決了傳統K-means聚類算法對初始聚類中心敏感問題；文獻[9]采用可變FCM(alternative fuzzyC-means, AFCM)算法對對稱聚類的參考點進行初始化，以改善噪聲和錯誤排序的影響；文獻[10]在DBSCAN基礎上進行了改進，解決了DBSCAN算法不能分選密度分布不均雷達信號的缺陷。

盡管上述算法及其改進算法在很大程度上完成了對復雜環境下雷達脈沖信號的聚類，但是這些算法得到的聚類效果都依賴于參數或閾值的選取[9，11]。針對上述問題，本文將無參數DSets-DBSCAN聚類算法應用于雷達信號處理中，給出了一種無參數的雷達信號脈沖聚類算法，該算法無須依賴于任何參數的設置就能自動聚類。

DSets-DBSCAN結合了主導集(dominant sets, DSets)聚類算法[12]和DBSCAN兩種算法。首先將雷達脈沖描述字(pulse descriptive word, PDW)參數形成的相似性矩陣經過圖像增強技術(直方圖均衡化)處理后輸入DSets算法中，該過程不涉及任何參數，并且能夠得到僅球形的脈沖超小簇。然后使用DBSCAN算法擴展剛生成的脈沖超小簇，盡管DBSCAN需要輸入參數鄰域半徑Eps和鄰域中的最小點數MinPts，但是能夠根據DSets生成的超小簇自適應確定，且是以區域增長的方式生成任意形狀的簇。通過這種方式，可以克服DSets的過度分割趨勢，并生成任意形狀的簇。由于DSets算法僅使用成對相似性矩陣作為輸入，且DBSCAN的輸入參數由DSets提取的脈沖集群確定，因此本文使用的DSets-DBSCAN算法不涉及任何參數。除此之外，這兩種算法的結合可以有效地抑制噪聲對脈沖聚類結果的影響。

1 算法流程

與DSets和DBSCAN一樣，DSets-DBSCAN算法在聚類過程中按順序提取脈沖集群。首先，輸入由DOA、PW和CF形成的三維PDW數據，并進行相似性矩陣的生成；其次，將連續的空間進行離散化，得到的結果進行直方圖均衡化，以此來消除參數σ對算法的影響；再次，處理后的相似性矩陣利用復制動力學因子求解一個聚類結果DSet；最后，利用DBSCAN算法擴展集群，輸入參數由DSet確定，得到一個最終聚類結果，同時去除已聚類脈沖在相似性矩陣中對應的行和列，重新進行下一次聚類結果的提取。算法流程如圖1所示。

圖1 算法流程Fig.1 Algorithm flow chart

2 數據預處理

2.1 相似性矩陣生成

假設接收到的脈沖數目為M，脈沖向量為(p1,p2,…,pM)；pm=[cfm;pwm;doam],m=1,2,…,M，則各脈沖參數間的相似性度量構成的相似性矩陣如式(1)所示。

(1)

2.2 直方圖均衡化

不同σ得到的相似性矩陣之間的差異主要在于相似性對比，這些差異與不同灰度對比度的圖像之間的差異非常相似[9]。所以可以利用直方圖均衡化使不同的σ生成相同的相似性矩陣，從而得到相同的聚類結果，消除算法對參數σ的依賴。

首先將一個連續空間變換成一個離散空間，將相似性矩陣離散化為N個灰度等級。離散化后的相似性矩陣記為A1=[s1(pi,pj)]M×M(i=1,2,…,M；j=1,2,…,M)。

由于s1(pi,pj)的相對大小只取決于元素之間的距離，與σ無關，且值均在[0,1]之間，所以可以直接通過式(2)完成直方圖均衡化[13]:

(2)

其中：k=1,2,…,L-1，L是灰度級數；nj是灰度級j的像素數；n是所有像素數，直方圖均衡化后的相似性矩陣記為Ahisteq。

但是，當一個灰度等級中包含一個以上元素時，相似度范圍的離散化使得變換后的相似性矩陣略有不同，這就是直方圖均衡化后的相似性矩陣仍然存在略微差異的原因。為了便于表達，本文在下面使用DSets-histeq表示直方圖均衡化后的DSets聚類算法。

3 DSets-DBSCAN無參數聚類

3.1 DSets算法

DSets算法得到的每個主導集嚴格滿足簇的高度內部相似性，一旦集合內部包含任何來自外部的數據，內部相似性將被破壞，這個條件使DSet成為數據的最大一致性子集。將直方圖均衡化后的相似性矩陣Ahisteq輸入DSets中，集群內部相干性的自然表示方法是f(x)=xTAhisteqx，其中xT表示的是x的轉置，將聚類問題公式化為尋找使f最大化的向量x的問題[14]：

maxf(x) s.t.x∈Δ

(3)

其中，Δ={x∈Rn:∑ixi=1,xi≥0}為Rn的標準單純形。 通過DSets的加權特征向量，證明了式(3)的嚴格局部解與DSet一一對應。

利用進化博弈論中發展起來的復制因子動力學求解式(3)并提取DSet，如式(4)所示：

(4)

3.2 DSets-DBSCAN算法

從主導集的定義[12]可知，主導集對主導集內的所有數據強加了全局密度約束。為了滿足此條件，主導集中的每個脈沖數據必須與主導集中的所有其他脈沖成員非常相似。這種嚴格的條件會產生兩個后果：①很難將同一部雷達的所有脈沖數據收集到同一個集合中，導致DSets聚類結果過小，出現將同一部雷達聚類為多部雷達的過度分割現象；②聚類僅形成球形的聚類結果，不能將任意形狀的脈沖進行聚類。顯然這兩種后果都會損害雷達信號的聚類質量。

為了解決上述問題，給出了DSets-DBSCAN算法進行雷達信號脈沖聚類，該算法通過將DSets和DBSCAN這兩個算法的互補性差異結合起來，得到分選性能更好的聚類算法。在使用DSets算法聚類之前，將直方圖均衡化變換應用于相似性矩陣，所以DSets聚類步驟沒有參數輸入；然后使用DBSCAN[15]擴展主導集時，根據主導集確定DBSCAN所需的參數。這樣確保在整個脈沖聚類過程中，不需要用戶指定任何參數。此外，由于使用DBSCAN將主導集擴展為聚類，可以很好地解決過度分割問題，并可以獲得任意形狀的聚類結果。

與DBSCAN相比，DSets-DBSCAN受MinPts的影響較小，這將在仿真結果中顯示。下面就是自適應地確定Eps參數，如式(5)所示：

(5)

其中，S是主導集，pMinPts是距離脈沖p最近的第MinPts個脈沖元素，p和pMinPts都在集合S中。對于每個脈沖集群，算法會根據相應的主導集為每個脈沖集群自適應地生成Eps，與原始DBSCAN中使用的全局參數不同。

MinPts和Eps兩個參數確定完畢后使用DBSCAN算法擴展主導集：從主導集中的任意脈沖開始檢索所有密度可達到的脈沖數據點，并獲得一個聚類。從脈沖數據集中刪除聚類的脈沖數據，重復進行主導集提取和擴展的過程，完成剩余脈沖聚類并自動確定聚類數。算法流程如下：

步驟1：輸入包含CF、PW和DOA三個參數的脈沖向量(p1,p2,…,pM)，利用式(1)計算相似性矩陣A。

步驟2：將相似性矩陣A進行離散化得到A1，應用直方圖均衡化變換相似性矩陣A1，得到Ahisteq。

步驟6：設置MinPts=3并根據式(5)確定Eps；

步驟7：從S中的任意脈沖開始，檢索所有密度可達的脈沖數據，形成一個聚類C。

步驟8：從相似性矩陣Ahisteq中刪除與C中脈沖數據相關的行和列。

步驟9：轉到步驟4，直到完成所有脈沖聚類。

4 實驗結果與分析

為了驗證算法的可行性，本節進行了軟件仿真，通過對設定的雷達信號進行聚類，來測試算法的聚類效果。由于DSets-DBSCAN算法旨在融合DSets算法和DBSCAN算法的優點，因此本節將本算法與DSets-histeq和DBSCAN算法分別進行了比較，以此來測試本算法是否達到目標。除此之外，為了驗證本文方法在高虛假脈沖比例下的聚類性能，給出了與現有方法的仿真結果對比圖。數據形式如表1所示。

表1 參數設置Tab.1 Default values for parameters

4.1 DSets-DBSCAN算法與DSets-histeq比較

4.1.1 直方圖均衡化

為了驗證直方圖均衡化消除了對σ的依賴，在下面的仿真中，將直方圖均衡化前后的算法仿真結果進行比較。在直方圖均衡化前首先對相似性矩陣進行離散化。

由于得到的相似性矩陣包含的元素數目多且元素精度大，若將其直接進行直方圖均衡化，會導致算法計算量大大增加，算法仿真時間長；若離散化的精度太小，又會削弱直方圖均衡化的意義。考慮到上述兩個方面，在進行大量仿真實驗后，本文將數據離散化為500個灰度等級。本文通過計算F-measure來評估聚類質量，并報告聚類結果。F-measure通過式(6)得到：

(6)

圖2 直方圖均衡化對算法的影響Fig.2 Influence of histogram equalization on algorithm

4.1.2 DSets-DBSCAN與DSets-histeq比較

為了查看DSets-DBSCAN算法是否解決了過度分割的問題，在圖3中給出了DSets-histeq和DSets-DBSCAN這兩個算法在相同輸入下的聚類結果對比圖。輸入的虛假脈沖比例為0，并在仿真時設置MinPts=3。

圖3 雷達混合脈沖聚類結果Fig.3 Results of radar mixed pulse clustering

圖3中每一個顏色都代表1部雷達。從圖中可以看出，Dsets算法分選得到的雷達數目大于輸入的雷達數目，本文算法分選得到的雷達數目與輸入的雷達數目相等，由此可見，本文算法解決了過度分割的問題。為了更直觀地給出兩個算法的實際聚類數目，在表2中分別給出了兩個算法獲得的集群數量。從表中可以看出，DSets-DBSCAN中的集群數量比DSets-histeq中的集群數量少得多，與設置值相符，進一步驗證了DSets-DBSCAN在克服過度分割方面的有效性。

表2 兩種算法分選結果數目對比Tab.2 Default values for parameters

4.2 DSets-DBSCAN與DBSCAN比較

在DSets-DBSCAN算法中，本文使用基于DBSCAN的集群擴展來克服過度分割并生成任意形狀的集群。盡管DBSCAN算法的擴展需要MinPts和Eps作為輸入，但在下面的仿真中可知，本文算法對MinPts參數設置不敏感，并根據優勢集自適應地確定Eps。在下面的仿真中，通過對兩個參數的分析，驗證實踐結果的有效性，如圖4所示。

圖4(a)給出了參數Eps對兩個算法的影響，從圖中可以看出，在一定的取值范圍內，隨著Eps值的增加，DBSCAN的聚類性能增強；由于DSets-DBSCAN算法中參數Eps是自適應確定的，所以參數Eps取值對DSets-DBSCAN聚類性能無影響。圖4(b)中給出了參數MinPts對兩個算法的影響，從圖中可以看出，MinPts值在0～12之間變動時，DSets-DBSCAN算法性能不隨著MinPts值改變。此外，從圖4中可看出，DSets-DBSCAN算法的性能始終優于DBSCAN，這證明了本文算法中合并DSets算法和DBSCAN算法的有效性。

(a) Eps對算法的影響(a) Effect of Eps on the algorithm

(b) MinPts對算法的影響(b) Effect of MinPts on the algorithm圖4 DSets-DBSCAN和DBSCAN對比Fig.4 DSets-DBSCAN versus DBSCAN

4.3 本文算法與已有算法對比

為了評估所提方法在高虛假脈沖比例條件下的分選性能，圖5給出了四種方法正確率平均F-measure值隨虛假脈沖比例的變化曲線。從圖5中可以看出，隨虛假脈沖比例的增加，四種方法的分選性能都有不同程度的下降，但是所提方法在不同虛假脈沖比例的條件下性能都優于其他三種方法，且DSets-DBSCAN的聚類效果受虛假脈沖比例的影響較小。這是因為DSets-histeq聚類傾向于生成僅球形的超小簇，且輸入至DBSCAN的參數Eps是由生成的超小簇自適應確定，所以算法只會將數據聚類，而不會將虛假脈沖聚類，這樣得到的聚類結果受虛假脈沖比例的影響較小。

圖5 不同虛假脈沖比例條件下分選正確率Fig.5 Sorting accuracy under different false pulse ratios

5 結論

對于沒有先驗信息的雷達信號，常規聚類方法的聚類性能嚴重依賴于外界輸入的參數。本文提出了一種基于DSets-DBSCAN無參數聚類的雷達信號分選算法，該方法將直方圖均衡化后的相似性矩陣應用于DSets，并自適應地確定DBSCAN的輸入參數，實現了無參數聚類。通過實驗仿真驗證，在沒有任何雷達信號的先驗信息及輸入參數的條件下，DSets-DBSCAN能夠有效地聚類復雜脈沖信號環境中的雷達脈沖信號，實現了無參數聚類。同時，在虛假脈沖比例不超過80%的條件下，聚類正確率達到97.56%以上。通過實驗仿真，驗證了算法的可行性。