用于雷達(dá)信號(hào)分選的連通k近鄰聚類(lèi)算法

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

(1. 哈爾濱工程大學(xué)信息與通信工程學(xué)院, 黑龍江 哈爾濱 150001;2. 哈爾濱工程大學(xué)先進(jìn)船舶通信與信息技術(shù)工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室, 黑龍江 哈爾濱 150001)

0 引 言

雷達(dá)信號(hào)分選是無(wú)源探測(cè)中的關(guān)鍵處理過(guò)程,其本質(zhì)是依據(jù)由接收機(jī)產(chǎn)生的信號(hào)脈沖描述字(pulse descriptor word,PDW)數(shù)據(jù)與由已有雷達(dá)信號(hào)先驗(yàn)知識(shí)中提取的雷達(dá)信號(hào)的規(guī)律性對(duì)雷達(dá)信號(hào)進(jìn)行分類(lèi)的過(guò)程。由于現(xiàn)代電子戰(zhàn)信號(hào)環(huán)境中信號(hào)形式復(fù)雜多樣,隨著雷達(dá)反對(duì)抗技術(shù)的發(fā)展[1-3],傳統(tǒng)的基于脈沖重復(fù)間隔(pulse repetition interval,PRI)的信號(hào)分選方法已無(wú)法有效提取雷達(dá)信號(hào)數(shù)據(jù)中的信息[4]。如何利用不同雷達(dá)之間參數(shù)的差異性以及同部雷達(dá)信號(hào)參數(shù)的相關(guān)性與規(guī)律性對(duì)雷達(dá)信號(hào)進(jìn)行實(shí)時(shí)有效的分選,是一個(gè)有待深入研究的課題。

聚類(lèi)分析的目的在于發(fā)現(xiàn)密切相關(guān)的觀(guān)測(cè)值簇,使得與屬于不同簇的觀(guān)測(cè)值相比,屬于同一簇的觀(guān)測(cè)值之間盡可能相似[5]。因此,信號(hào)分選領(lǐng)域目前的研究熱點(diǎn)是聚類(lèi)信號(hào)分選。文獻(xiàn)[6]對(duì)近年來(lái)研究和發(fā)展的聚類(lèi)分選算法進(jìn)行了綜述。目前大多數(shù)聚類(lèi)分選算法有基于原型、基于密度以及基于圖的聚類(lèi)分選算法。

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

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

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

本文在模糊聚類(lèi)算法的基礎(chǔ)上,將模糊聚類(lèi)原有的λ鄰域范圍搜索變?yōu)棣肃徲騼?nèi)k近鄰搜索。在使用合適的數(shù)據(jù)結(jié)構(gòu)與搜索算法[26]的情況下,以犧牲空間復(fù)雜度(擴(kuò)大至k倍)為代價(jià)將時(shí)間復(fù)雜度降低(由平方階降低至線(xiàn)性對(duì)數(shù)階),這在計(jì)算機(jī)技術(shù)與存儲(chǔ)技術(shù)飛速發(fā)展的今天是可以接受的。同時(shí),基于k距離圖提出了一種新的閾值確定方式,結(jié)合劉旭波等[23]提出的熵值法可實(shí)現(xiàn)無(wú)參數(shù)自適應(yīng)聚類(lèi),可在復(fù)雜信號(hào)環(huán)境中進(jìn)行實(shí)時(shí)、有效的信號(hào)分選。

1 低復(fù)雜度模糊聚類(lèi)算法

1.1 算法原理

文獻(xiàn)[25]中提出的低復(fù)雜度模糊聚類(lèi)算法結(jié)合文獻(xiàn)[23]中提出的熵值法確定參數(shù)權(quán)重后得到的算法,可表述為算法1。

算法 1 低復(fù)雜度模糊聚類(lèi)算法輸入:數(shù)據(jù)集X,距離閾值λ輸出:簇標(biāo)簽1. 對(duì)數(shù)據(jù)集X進(jìn)行標(biāo)準(zhǔn)化與歸一化處理;2. 使用熵值法確定各維參數(shù)權(quán)重;3. 初始化并查集;4. 依次選取數(shù)據(jù)集X中兩數(shù)據(jù)點(diǎn)計(jì)算距離d,當(dāng)距離d低于閾值λ時(shí),進(jìn)行集合歸并;5. 查詢(xún)并查集,分配簇標(biāo)簽并返回。

在低復(fù)雜度模糊聚類(lèi)算法中,數(shù)據(jù)集X是一個(gè)n×m的矩陣,其中每一行均為一個(gè)數(shù)據(jù)點(diǎn),每個(gè)數(shù)據(jù)點(diǎn)具有m個(gè)維度,共n個(gè)數(shù)據(jù)點(diǎn);距離閾值λ的取值范圍為[0,1],距離度量可使用各種Minkowski距離度量,通常使用曼哈頓距離或歐氏距離。對(duì)應(yīng)于聚類(lèi)雷達(dá)信號(hào)分選,數(shù)據(jù)集X即為脈沖描述字向量,每個(gè)數(shù)據(jù)點(diǎn)對(duì)應(yīng)一個(gè)信號(hào)的脈沖描述字或其子集。

假設(shè)有圖1所示數(shù)據(jù)分布的數(shù)據(jù)集,其中點(diǎn)劃線(xiàn)方框所標(biāo)識(shí)的是數(shù)據(jù)集中的簇,簇以外的數(shù)據(jù)點(diǎn)即為環(huán)境中的噪聲點(diǎn)或離群點(diǎn)。

圖1 數(shù)據(jù)分布Fig.1 Data distribution

對(duì)于低復(fù)雜度模糊聚類(lèi)算法,其依次計(jì)算數(shù)據(jù)集中兩點(diǎn)間距離,距離小于閾值λ時(shí),便將兩點(diǎn)連通。如圖2所示,數(shù)據(jù)點(diǎn)a與b之間的距離小于閾值λ,因此將其連通。

圖2 距離小于閾值時(shí)連通兩點(diǎn)Fig.2 Connecting two points when the distance is less than the threshold

聚類(lèi)結(jié)束后,得到的結(jié)果如圖3所示。簇為圖中的連通分支,如簇A、簇B;而對(duì)于圖2中的噪聲點(diǎn)c,由于沒(méi)有數(shù)據(jù)點(diǎn)位于其λ鄰域內(nèi),因此形成單點(diǎn)簇。

圖3 聚類(lèi)結(jié)果Fig.3 Result of clustering

1.2 低復(fù)雜度模糊聚類(lèi)算法存在的問(wèn)題

低復(fù)雜度模糊聚類(lèi)算法存在如下兩點(diǎn)問(wèn)題:

(1) 由于低復(fù)雜度模糊聚類(lèi)算法需要依次計(jì)算數(shù)據(jù)集中兩點(diǎn)間的距離,共需要進(jìn)行n(n-1)/2次距離計(jì)算與并查集歸并,具有O(n2)的時(shí)間復(fù)雜度,對(duì)于高脈沖密度的信號(hào)環(huán)境以及對(duì)實(shí)時(shí)性要求較高的場(chǎng)景,仍無(wú)法滿(mǎn)足實(shí)時(shí)性的需求。

(2) 閾值參數(shù)的確定基于文獻(xiàn)[24]所提出的確定最佳聚類(lèi)的方法,該方法需依次調(diào)整閾值參數(shù)λ進(jìn)行算法1的聚類(lèi)過(guò)程,并計(jì)算聚類(lèi)結(jié)果的CH指標(biāo),選取CH指標(biāo)最大值所對(duì)應(yīng)的閾值λ為最佳閾值,導(dǎo)致算法復(fù)雜度進(jìn)一步增加,時(shí)間復(fù)雜度變?yōu)镺(l·n2),其中l(wèi)為算法迭代次數(shù)。經(jīng)過(guò)實(shí)驗(yàn),閾值參數(shù)的步進(jìn)會(huì)影響聚類(lèi)參數(shù)的確定效果與算法復(fù)雜度,進(jìn)而影響最終聚類(lèi)效果。

為解決低復(fù)雜度模糊聚類(lèi)算法存在的上述問(wèn)題,提出了一種連通k近鄰聚類(lèi)算法。

2 連通k近鄰聚類(lèi)算法

2.1 連通k近鄰

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

為降低其時(shí)間復(fù)雜度,將范圍搜索變?yōu)閗近鄰搜索,即連通每個(gè)數(shù)據(jù)點(diǎn)與其k個(gè)近鄰,簇為圖的連通分支。如圖4所示,將數(shù)據(jù)點(diǎn)a和噪聲點(diǎn)d分別與其k近鄰連通,此處k=3。

圖4 連通數(shù)據(jù)點(diǎn)與其k近鄰Fig.4 Connect the data point to its k nearest neighbors

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

然而如圖4所示,僅將范圍搜索變?yōu)閗近鄰搜索會(huì)導(dǎo)致噪聲點(diǎn)d也與其k近鄰連通,進(jìn)而造成將信號(hào)環(huán)境中的噪聲點(diǎn)d與有效數(shù)據(jù)點(diǎn)a相連通,從而使結(jié)果簇中包含了噪聲點(diǎn)。在某些特殊的場(chǎng)景中,甚至?xí)?shù)據(jù)集中所有數(shù)據(jù)點(diǎn)聚為一簇。為解決這一問(wèn)題,仍引入距離閾值λ,即將數(shù)據(jù)點(diǎn)與其λ鄰域內(nèi)的k近鄰相連通,如圖5所示。由于實(shí)際場(chǎng)景中噪聲點(diǎn)相對(duì)稀疏,因此可通過(guò)設(shè)置合適的距離閾值區(qū)分噪聲點(diǎn)與有效數(shù)據(jù)點(diǎn)。

圖5 將數(shù)據(jù)點(diǎn)與位于λ鄰域內(nèi)的k近鄰連通Fig.5 Connecting the data point to the k nearest neighbors in the λ neighborhood

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

閾值λ的選取十分重要,其直接影響聚類(lèi)效果。為清晰地說(shuō)明聚類(lèi)效果隨閾值λ變化而變化的情況,按表1所列雷達(dá)參數(shù)生成序列時(shí)長(zhǎng)為100 ms的雷達(dá)信號(hào)并混合脈沖流密度為10 000脈沖每秒的噪聲構(gòu)成測(cè)試數(shù)據(jù)集。對(duì)測(cè)試數(shù)據(jù)集在不同λ閾值下進(jìn)行聚類(lèi),統(tǒng)計(jì)聚類(lèi)結(jié)果的3個(gè)指標(biāo):簇?cái)?shù)量nc(即聚類(lèi)所得簇?cái)?shù)量,不包括噪聲點(diǎn)形成的單點(diǎn)簇)、可能存在雷達(dá)的簇?cái)?shù)量nr(含有10個(gè)以上數(shù)據(jù)點(diǎn)的簇?cái)?shù)量)以及平均純凈度pavg(各個(gè)簇純凈度的平均值)。其中簇的純凈度定義為簇中主要雷達(dá)信號(hào)(同一簇中可能存在來(lái)自于多部雷達(dá)的信號(hào),其中占比較大的雷達(dá)信號(hào)稱(chēng)為主要雷達(dá)信號(hào))所占的比例。

表1 雷達(dá)列表

圖6為簇?cái)?shù)量nc、可能存在雷達(dá)的簇?cái)?shù)量nr隨閾值λ的變化曲線(xiàn)圖,圖7為平均純凈度pavg隨閾值λ的變化曲線(xiàn)圖。從圖中可看出閾值λ的變化對(duì)聚類(lèi)結(jié)果整體上有如下影響。

圖6 簇?cái)?shù)量nc、nr隨閾值λ的變化曲線(xiàn)Fig.6 Change curve of the number of clusters nc andnr with the threshold λ

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

若λ較小,會(huì)使得聚類(lèi)所形成的各個(gè)簇較小,簇的數(shù)量較多,來(lái)自于同一雷達(dá)的信號(hào)被劃分至多個(gè)簇中,但此時(shí)各個(gè)簇的純凈度較高;當(dāng)λ→0時(shí),聚類(lèi)所形成的簇均為單點(diǎn)簇,即被視為噪聲。若λ較大,會(huì)使得聚類(lèi)所形成的各個(gè)簇較大,簇的數(shù)量較少,來(lái)自于多部雷達(dá)的信號(hào)會(huì)被聚為一個(gè)簇,各個(gè)簇的純凈度較低;當(dāng)λ→1時(shí),所有數(shù)據(jù)點(diǎn)被聚為一個(gè)簇,純凈度達(dá)到最低。

為確定合理的距離閾值λ,引入k距離圖。即各數(shù)據(jù)點(diǎn)到其第k個(gè)最近鄰的距離排序后形成的曲線(xiàn)圖,如圖8實(shí)線(xiàn)所示為測(cè)試數(shù)據(jù)集的k距離圖。圖8中橫軸n為排序后k距離序號(hào),縱軸dk為k距離。

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

由于數(shù)據(jù)集中噪聲點(diǎn)相對(duì)稀疏、有效數(shù)據(jù)點(diǎn)相對(duì)密集,因此k距離圖中k距離較小且增長(zhǎng)較為緩慢的區(qū)域代表的是有效數(shù)據(jù)點(diǎn),而增長(zhǎng)較快的區(qū)域代表噪聲點(diǎn),位于這兩部分區(qū)域之間k距離變化率急劇變化的點(diǎn)所對(duì)應(yīng)的k距離可作為距離閾值λ,該點(diǎn)稱(chēng)為“膝點(diǎn)”,即圖8中的標(biāo)記點(diǎn)。

為確定“膝點(diǎn)”,文獻(xiàn)[15-18]提出了多種方法,但均計(jì)算復(fù)雜,為此提出一種距離確定法。如圖8虛線(xiàn)所示,連結(jié)k距離曲線(xiàn)首尾兩點(diǎn),計(jì)算k距離曲線(xiàn)上各點(diǎn)到該虛線(xiàn)的距離,取距離最大點(diǎn)為“膝點(diǎn)”,“膝點(diǎn)”對(duì)應(yīng)k距離為閾值λ。

由圖8可知,對(duì)測(cè)試數(shù)據(jù)集使用本文所提距離確定法得到的閾值λ為0.053。該閾值對(duì)應(yīng)的圖6中的nr為10,表明聚類(lèi)所發(fā)現(xiàn)的雷達(dá)數(shù)量為10;同時(shí)該閾值對(duì)應(yīng)的圖7中的pavg為99.50%,表明各個(gè)簇均有較高的純凈度。這表明使用本文所提距離確定法確定的閾值λ在被用于第2.1節(jié)所提聚類(lèi)算法時(shí),可有效發(fā)現(xiàn)數(shù)據(jù)集中存在的雷達(dá)。

2.3 連通k近鄰聚類(lèi)算法

綜合第2.1節(jié)、第2.2節(jié)提出的連通k近鄰聚類(lèi)算法,算法描述如算法2所示。

算法 2 連通k近鄰聚類(lèi)算法輸入:數(shù)據(jù)集X輸出:簇標(biāo)簽1. 對(duì)數(shù)據(jù)集X進(jìn)行標(biāo)準(zhǔn)化與歸一化處理;2. 使用熵值法確定各維參數(shù)權(quán)重;3. 對(duì)各數(shù)據(jù)點(diǎn)進(jìn)行k近鄰搜索;4. 繪制k距離圖,使用距離確定法確定閾值λ;5. 初始化并查集;6. 將各數(shù)據(jù)點(diǎn)與位于其λ鄰域內(nèi)的k近鄰連通;7. 查詢(xún)并查集,分配簇標(biāo)簽并返回。

為保證各數(shù)據(jù)點(diǎn)能夠有效地與近鄰連通形成簇,近鄰搜索數(shù)目k與數(shù)據(jù)點(diǎn)維數(shù)m應(yīng)滿(mǎn)足

k≥2m

(1)

且k越大越好。而由對(duì)kd樹(shù)的相關(guān)研究,當(dāng)近鄰搜索的搜索數(shù)目k與數(shù)據(jù)集中數(shù)據(jù)點(diǎn)數(shù)n滿(mǎn)足

2k≤n

(2)

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

(3)

式中:m為數(shù)據(jù)點(diǎn)維數(shù);n為數(shù)據(jù)點(diǎn)數(shù)。

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

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

3 算法仿真與對(duì)比

3.1 算法仿真

按第2.2節(jié)表1所示雷達(dá)列表生成序列時(shí)長(zhǎng)為100 ms的雷達(dá)信號(hào),并混合脈沖流密度為10 000脈沖每秒的噪聲。使用連通k近鄰聚類(lèi)算法進(jìn)行信號(hào)分選,分選所得簇標(biāo)號(hào)統(tǒng)計(jì)結(jié)果如圖9所示,橫軸為簇標(biāo)號(hào),縱軸為簇標(biāo)號(hào)頻次;分選準(zhǔn)確率如表2所示,準(zhǔn)確率定義為各簇中正確分選信號(hào)數(shù)量占分選所得信號(hào)數(shù)量的比例。由分選結(jié)果可知,連通k近鄰聚類(lèi)算法在較為復(fù)雜的信號(hào)環(huán)境中能夠?qū)崿F(xiàn)正確分選。

圖9 分選結(jié)果統(tǒng)計(jì)Fig.9 Statistics of sorting result

3.2 算法對(duì)比

為對(duì)比連通k近鄰聚類(lèi)算法與低復(fù)雜度模糊聚類(lèi)算法用于信號(hào)分選的分選性能,將二者用第2.2節(jié)所述表1所列雷達(dá)參數(shù)生成的雷達(dá)信號(hào)數(shù)據(jù)集(為使低復(fù)雜度模糊聚類(lèi)算法能夠自動(dòng)確定閾值,使用文獻(xiàn)[24]所提出的使用CH指標(biāo)確定最佳聚類(lèi)的方法,閾值λ步進(jìn)為0.05),重復(fù)運(yùn)行5次分選,統(tǒng)計(jì)分選準(zhǔn)確率如表3和表4所示。

表3 連通k近鄰聚類(lèi)Table 3 Connected k-nearest neighbor clustering

表4 低復(fù)雜度模糊聚類(lèi)Table 4 Low-complexity fuzzy clustering

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

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

圖10 3種算法消耗的時(shí)間對(duì)比Fig.10 Comparison of time consumption of three algorithms

3.3 算法缺點(diǎn)

本文所提連通k近鄰聚類(lèi)算法中,閾值的自動(dòng)確定是基于噪聲點(diǎn)相對(duì)于有效數(shù)據(jù)點(diǎn)而言較為稀疏的前提實(shí)現(xiàn)的。當(dāng)數(shù)據(jù)集密度不平衡時(shí),即信號(hào)環(huán)境中某雷達(dá)信號(hào)密度相對(duì)于其他雷達(dá)相差較大時(shí),該雷達(dá)信號(hào)可能被當(dāng)作噪聲而丟棄。

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

表5 雷達(dá)列表(密度不平衡數(shù)據(jù)集)

表6 分選準(zhǔn)確率(密度不平衡數(shù)據(jù)集)

4 結(jié) 論

為了能夠在密集且復(fù)雜多變的信號(hào)環(huán)境中進(jìn)行實(shí)時(shí)、有效的信號(hào)分選,提出了一種連通k近鄰聚類(lèi)算法。

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

(2) 提出了基于k距離圖的閾值距離確定法,使得算法參數(shù)可根據(jù)信號(hào)環(huán)境自適應(yīng)調(diào)整。

通過(guò)算法仿真對(duì)比,驗(yàn)證連通k近鄰聚類(lèi)算法與使用CH指標(biāo)確定最佳閾值的低復(fù)雜度模糊聚類(lèi)算法分選效果差距不大、性能相近,同時(shí)時(shí)間復(fù)雜度大幅下降;所提算法具有較低的時(shí)間復(fù)雜度以及無(wú)需人工設(shè)置聚類(lèi)參數(shù)的優(yōu)勢(shì),但其在面對(duì)密度不平衡的數(shù)據(jù)集時(shí),聚類(lèi)效果較差。