用于雷達信號分選的連通k近鄰聚類算法

司偉建, 張 悅, 鄧志安,*

(1. 哈爾濱工程大學信息與通信工程學院, 黑龍江 哈爾濱 150001;2. 哈爾濱工程大學先進船舶通信與信息技術工業和信息化部重點實驗室, 黑龍江 哈爾濱 150001)

0 引 言

雷達信號分選是無源探測中的關鍵處理過程,其本質是依據由接收機產生的信號脈沖描述字(pulse descriptor word,PDW)數據與由已有雷達信號先驗知識中提取的雷達信號的規律性對雷達信號進行分類的過程。由于現代電子戰信號環境中信號形式復雜多樣,隨著雷達反對抗技術的發展[1-3],傳統的基于脈沖重復間隔(pulse repetition interval,PRI)的信號分選方法已無法有效提取雷達信號數據中的信息[4]。如何利用不同雷達之間參數的差異性以及同部雷達信號參數的相關性與規律性對雷達信號進行實時有效的分選,是一個有待深入研究的課題。

聚類分析的目的在于發現密切相關的觀測值簇,使得與屬于不同簇的觀測值相比,屬于同一簇的觀測值之間盡可能相似[5]。因此,信號分選領域目前的研究熱點是聚類信號分選。文獻[6]對近年來研究和發展的聚類分選算法進行了綜述。目前大多數聚類分選算法有基于原型、基于密度以及基于圖的聚類分選算法。

基于原型的聚類,簇由這樣的對象組成:簇中任何對象距離該簇的原型比距離其他簇的原型更近[5]。典型的基于原型的聚類有k均值(k-means)聚類[7]與模糊c均值(fuzzycmeans,FCM)聚類[8]。這類算法需要指定聚類數目并隨機初始化聚類中心,不適用于未知信號環境中的分選;其次,原型即為簇中心點,因此這類算法適用于球形簇,不適用于參數捷變雷達所形成的矩形簇。后續有眾多學者在聚類數目和聚類中心確定等方面進行了研究,分別采用統計直方圖[9]、自組織映射(self-organizing feature mapping,SOFM)[10]、主成分分析(principal component analysis,PCA)[11]以及支持向量聚類(support vector clustering,SVC)[12]等方法確定聚類數目與聚類中心,而上述方法均只適用于球形簇。Cao等[13]于2018年提出的基于密度的FCM多中心重聚類算法適用于非凸數據集,同時引入基于快速搜索和發現密度峰值(clustering by fast search and find of density peaks,CFSFDP)算法來生成初始中心點,解決了基于原型聚類算法的兩大缺陷,但該算法運算量較大。

基于密度的聚類,簇是對象的稠密區域,被低密度區域所環繞[5]。1996年,Ester等[14]提出經典的基于密度的聚類算法——基于密度的噪聲應用空間聚類(density-based spatial clusering of applications with noise,DBSCAN),其具有可發現任意形狀簇的優點,但其對于密度變化數據集聚類效果較差,可能造成低密度區域被丟棄或高密度區域被合并為同一簇等問題。DBSCAN需要確定兩個參數簇的半徑Eps與簇的最少點數MinPts,文獻[14]提出了基于k距離圖的確定方式,需要人工參與。為自動確定聚類參數,多位學者提出了多種方法,分別采用核密度估計[15-16]、K平均最近鄰與數學期望法[17-18]相結合的方法確定聚類參數,實現自動化聚類。2021年,王星等[19]提出了基于云模型的CMDBSCAN算法,其結合距離曲線傾角突變獲取Eps參數并根據信號密度分布設置MinPts,同時結合多維云模型對分選結果進行有效性評估,進一步優化參數設置。Chen等[20]引入差分法和反三角函數確定聚類參數,并將其用于聚類分選,提高了算法可靠性和分選精度。

基于圖的聚類,將簇定義為圖的連通分支[5]。2005年,張興華[21]提出的模糊聚類算法通過計算各數據點的相似度,將相似度高于閾值的歸為一類;實質上是在由數據點構成的圖中將相似度高于閾值的數據點連通,而簇為連通的數據點形成的集合,因此其屬于基于圖的聚類算法,適用于發現任意形狀的簇。2008年,賀宏洲等[22]將模糊聚類算法用于雷達信號分選。2009年,劉旭波等[23]提出了熵值法,用于確定聚類中各維參數的權重。2014年,尹亮等[24]提出了基于有效性函數確定最佳聚類的算法,使用Calinski-Harabasz (CH)指標確定最佳閾值完成聚類,但該方法需要多次運行模糊聚類,造成算法復雜度較高。2020年,文獻[25]提出了低復雜度模糊聚類算法,降低了時間復雜度與空間復雜度。

本文在模糊聚類算法的基礎上,將模糊聚類原有的λ鄰域范圍搜索變為λ鄰域內k近鄰搜索。在使用合適的數據結構與搜索算法[26]的情況下,以犧牲空間復雜度(擴大至k倍)為代價將時間復雜度降低(由平方階降低至線性對數階),這在計算機技術與存儲技術飛速發展的今天是可以接受的。同時,基于k距離圖提出了一種新的閾值確定方式,結合劉旭波等[23]提出的熵值法可實現無參數自適應聚類,可在復雜信號環境中進行實時、有效的信號分選。

1 低復雜度模糊聚類算法

1.1 算法原理

文獻[25]中提出的低復雜度模糊聚類算法結合文獻[23]中提出的熵值法確定參數權重后得到的算法,可表述為算法1。

算法 1 低復雜度模糊聚類算法輸入:數據集X,距離閾值λ輸出:簇標簽1. 對數據集X進行標準化與歸一化處理;2. 使用熵值法確定各維參數權重;3. 初始化并查集;4. 依次選取數據集X中兩數據點計算距離d,當距離d低于閾值λ時,進行集合歸并;5. 查詢并查集,分配簇標簽并返回。

在低復雜度模糊聚類算法中,數據集X是一個n×m的矩陣,其中每一行均為一個數據點,每個數據點具有m個維度,共n個數據點;距離閾值λ的取值范圍為[0,1],距離度量可使用各種Minkowski距離度量,通常使用曼哈頓距離或歐氏距離。對應于聚類雷達信號分選,數據集X即為脈沖描述字向量,每個數據點對應一個信號的脈沖描述字或其子集。

假設有圖1所示數據分布的數據集,其中點劃線方框所標識的是數據集中的簇,簇以外的數據點即為環境中的噪聲點或離群點。

圖1 數據分布Fig.1 Data distribution

對于低復雜度模糊聚類算法,其依次計算數據集中兩點間距離,距離小于閾值λ時,便將兩點連通。如圖2所示,數據點a與b之間的距離小于閾值λ,因此將其連通。

圖2 距離小于閾值時連通兩點Fig.2 Connecting two points when the distance is less than the threshold

聚類結束后,得到的結果如圖3所示。簇為圖中的連通分支,如簇A、簇B;而對于圖2中的噪聲點c,由于沒有數據點位于其λ鄰域內,因此形成單點簇。

圖3 聚類結果Fig.3 Result of clustering

1.2 低復雜度模糊聚類算法存在的問題

低復雜度模糊聚類算法存在如下兩點問題:

(1) 由于低復雜度模糊聚類算法需要依次計算數據集中兩點間的距離,共需要進行n(n-1)/2次距離計算與并查集歸并,具有O(n2)的時間復雜度,對于高脈沖密度的信號環境以及對實時性要求較高的場景,仍無法滿足實時性的需求。

(2) 閾值參數的確定基于文獻[24]所提出的確定最佳聚類的方法,該方法需依次調整閾值參數λ進行算法1的聚類過程,并計算聚類結果的CH指標,選取CH指標最大值所對應的閾值λ為最佳閾值,導致算法復雜度進一步增加,時間復雜度變為O(l·n2),其中l為算法迭代次數。經過實驗,閾值參數的步進會影響聚類參數的確定效果與算法復雜度,進而影響最終聚類效果。

為解決低復雜度模糊聚類算法存在的上述問題,提出了一種連通k近鄰聚類算法。

2 連通k近鄰聚類算法

2.1 連通k近鄰

低復雜度模糊聚類算法也可理解為:對于每個數據點而言,搜索位于其λ鄰域內的其他數據點并與其連通,簇為圖的連通分支。由于范圍搜索具有O(n)的時間復雜度,因此低復雜度模糊聚類算法具有O(n2)的時間復雜度。

為降低其時間復雜度,將范圍搜索變為k近鄰搜索,即連通每個數據點與其k個近鄰,簇為圖的連通分支。如圖4所示,將數據點a和噪聲點d分別與其k近鄰連通,此處k=3。

圖4 連通數據點與其k近鄰Fig.4 Connect the data point to its k nearest neighbors

在使用合適的數據結構(如kd樹、bd樹)時,k近鄰搜索的時間復雜度為O(k·log2n)[26],因此可將算法整體的時間復雜度降低至O(k·n·log2n),log2n為對n取以2為底的對數。

然而如圖4所示,僅將范圍搜索變為k近鄰搜索會導致噪聲點d也與其k近鄰連通,進而造成將信號環境中的噪聲點d與有效數據點a相連通,從而使結果簇中包含了噪聲點。在某些特殊的場景中,甚至會將數據集中所有數據點聚為一簇。為解決這一問題,仍引入距離閾值λ,即將數據點與其λ鄰域內的k近鄰相連通,如圖5所示。由于實際場景中噪聲點相對稀疏,因此可通過設置合適的距離閾值區分噪聲點與有效數據點。

圖5 將數據點與位于λ鄰域內的k近鄰連通Fig.5 Connecting the data point to the k nearest neighbors in the λ neighborhood

2.2 基于k距離圖的閾值確定

閾值λ的選取十分重要,其直接影響聚類效果。為清晰地說明聚類效果隨閾值λ變化而變化的情況,按表1所列雷達參數生成序列時長為100 ms的雷達信號并混合脈沖流密度為10 000脈沖每秒的噪聲構成測試數據集。對測試數據集在不同λ閾值下進行聚類,統計聚類結果的3個指標:簇數量nc(即聚類所得簇數量,不包括噪聲點形成的單點簇)、可能存在雷達的簇數量nr(含有10個以上數據點的簇數量)以及平均純凈度pavg(各個簇純凈度的平均值)。其中簇的純凈度定義為簇中主要雷達信號(同一簇中可能存在來自于多部雷達的信號,其中占比較大的雷達信號稱為主要雷達信號)所占的比例。

表1 雷達列表

圖6為簇數量nc、可能存在雷達的簇數量nr隨閾值λ的變化曲線圖,圖7為平均純凈度pavg隨閾值λ的變化曲線圖。從圖中可看出閾值λ的變化對聚類結果整體上有如下影響。

圖6 簇數量nc、nr隨閾值λ的變化曲線Fig.6 Change curve of the number of clusters nc andnr with the threshold λ

圖7 平均純凈度pavg隨閾值λ的變化曲線Fig.7 Change curve of the average purity pavg with the threshold λ

若λ較小,會使得聚類所形成的各個簇較小,簇的數量較多,來自于同一雷達的信號被劃分至多個簇中,但此時各個簇的純凈度較高;當λ→0時,聚類所形成的簇均為單點簇,即被視為噪聲。若λ較大,會使得聚類所形成的各個簇較大,簇的數量較少,來自于多部雷達的信號會被聚為一個簇,各個簇的純凈度較低;當λ→1時,所有數據點被聚為一個簇,純凈度達到最低。

為確定合理的距離閾值λ,引入k距離圖。即各數據點到其第k個最近鄰的距離排序后形成的曲線圖,如圖8實線所示為測試數據集的k距離圖。圖8中橫軸n為排序后k距離序號,縱軸dk為k距離。

圖8 k距離圖Fig.8 k-distance graph

由于數據集中噪聲點相對稀疏、有效數據點相對密集,因此k距離圖中k距離較小且增長較為緩慢的區域代表的是有效數據點,而增長較快的區域代表噪聲點,位于這兩部分區域之間k距離變化率急劇變化的點所對應的k距離可作為距離閾值λ,該點稱為“膝點”,即圖8中的標記點。

為確定“膝點”,文獻[15-18]提出了多種方法,但均計算復雜,為此提出一種距離確定法。如圖8虛線所示,連結k距離曲線首尾兩點,計算k距離曲線上各點到該虛線的距離,取距離最大點為“膝點”,“膝點”對應k距離為閾值λ。

由圖8可知,對測試數據集使用本文所提距離確定法得到的閾值λ為0.053。該閾值對應的圖6中的nr為10,表明聚類所發現的雷達數量為10;同時該閾值對應的圖7中的pavg為99.50%,表明各個簇均有較高的純凈度。這表明使用本文所提距離確定法確定的閾值λ在被用于第2.1節所提聚類算法時,可有效發現數據集中存在的雷達。

2.3 連通k近鄰聚類算法

綜合第2.1節、第2.2節提出的連通k近鄰聚類算法,算法描述如算法2所示。

算法 2 連通k近鄰聚類算法輸入:數據集X輸出:簇標簽1. 對數據集X進行標準化與歸一化處理;2. 使用熵值法確定各維參數權重;3. 對各數據點進行k近鄰搜索;4. 繪制k距離圖,使用距離確定法確定閾值λ;5. 初始化并查集;6. 將各數據點與位于其λ鄰域內的k近鄰連通;7. 查詢并查集,分配簇標簽并返回。

為保證各數據點能夠有效地與近鄰連通形成簇,近鄰搜索數目k與數據點維數m應滿足

k≥2m

(1)

且k越大越好。而由對kd樹的相關研究,當近鄰搜索的搜索數目k與數據集中數據點數n滿足

2k≤n

(2)

則對kd樹的近鄰搜索具有O(k·lbn)的時間復雜度。為保證算法效率與有效性,算法中k值可通過下式確定:

(3)

式中:m為數據點維數;n為數據點數。

由于基于k距離圖的閾值距離確定法只需要遍歷一條與數據點數n長度相同的曲線,因此時間復雜度為O(n);對各數據點進行k近鄰搜索的時間復雜度為O(k·n·lbn);對并查集進行歸并與查詢的時間復雜度分別為O(k·n)與O(n)。由上述分析,本算法時間復雜度為O(k·n·lbn)。

本算法需要維護各數據點的k近鄰以及并查集,空間復雜度分別為O(k·n)與O(n),因此本算法空間復雜度為O(k·n)。

3 算法仿真與對比

3.1 算法仿真

按第2.2節表1所示雷達列表生成序列時長為100 ms的雷達信號,并混合脈沖流密度為10 000脈沖每秒的噪聲。使用連通k近鄰聚類算法進行信號分選,分選所得簇標號統計結果如圖9所示,橫軸為簇標號,縱軸為簇標號頻次;分選準確率如表2所示,準確率定義為各簇中正確分選信號數量占分選所得信號數量的比例。由分選結果可知,連通k近鄰聚類算法在較為復雜的信號環境中能夠實現正確分選。

圖9 分選結果統計Fig.9 Statistics of sorting result

3.2 算法對比

為對比連通k近鄰聚類算法與低復雜度模糊聚類算法用于信號分選的分選性能,將二者用第2.2節所述表1所列雷達參數生成的雷達信號數據集(為使低復雜度模糊聚類算法能夠自動確定閾值,使用文獻[24]所提出的使用CH指標確定最佳聚類的方法,閾值λ步進為0.05),重復運行5次分選,統計分選準確率如表3和表4所示。

表3 連通k近鄰聚類Table 3 Connected k-nearest neighbor clustering

表4 低復雜度模糊聚類Table 4 Low-complexity fuzzy clustering

由表3和表4可知,連通k近鄰聚類算法與低復雜度模糊聚類算法(使用CH指標確定最佳閾值)分選準確率相近,分選性能相近。

為對比連通k近鄰聚類算法與低復雜度模糊聚類算法的時間復雜度,將連通k近鄰聚類算法、低復雜度模糊聚類算法(使用固定閾值)、低復雜度模糊聚類算法(使用CH指標確定最佳閾值)應用于不同信號數量的數據集進行聚類分選,消耗時間曲線如圖10所示。圖中橫軸為信號數量n,縱軸為算法運行消耗的時間t(由于時間差異較大,縱軸使用以s為基準的對數時間dBs)。由圖10可知,所提算法相對于低復雜度模糊聚類算法,時間復雜度明顯下降。

圖10 3種算法消耗的時間對比Fig.10 Comparison of time consumption of three algorithms

3.3 算法缺點

本文所提連通k近鄰聚類算法中,閾值的自動確定是基于噪聲點相對于有效數據點而言較為稀疏的前提實現的。當數據集密度不平衡時,即信號環境中某雷達信號密度相對于其他雷達相差較大時,該雷達信號可能被當作噪聲而丟棄。

按表5所示雷達列表生成序列時長為100 ms的雷達信號,并混合脈沖流密度為10 000脈沖每秒的噪聲。使用連通k近鄰聚類算法進行信號分選,分選準確率如表6所示。由分選結果可知,雷達5未被成功分選,這是由于雷達5的PRI較大,從而造成該雷達信號數量較少,密度較低,信號空間中分布稀疏,被連通k近鄰聚類算法視為噪聲而丟棄。因此,連通k近鄰聚類算法不適用于密度不平衡的數據集。

表5 雷達列表(密度不平衡數據集)

表6 分選準確率(密度不平衡數據集)

4 結 論

為了能夠在密集且復雜多變的信號環境中進行實時、有效的信號分選,提出了一種連通k近鄰聚類算法。

(1) 使用k近鄰搜索結合閾值的方式,相對于低復雜度模糊聚類算法,以空間復雜度增加為代價(由O(n)增加至O(k·n)),降低了時間復雜度(由O(n2)降低至O(k·n·lbn)),提高了算法的實時性;

(2) 提出了基于k距離圖的閾值距離確定法,使得算法參數可根據信號環境自適應調整。

通過算法仿真對比,驗證連通k近鄰聚類算法與使用CH指標確定最佳閾值的低復雜度模糊聚類算法分選效果差距不大、性能相近,同時時間復雜度大幅下降;所提算法具有較低的時間復雜度以及無需人工設置聚類參數的優勢,但其在面對密度不平衡的數據集時,聚類效果較差。