改進的K-Means算法在特征關聯(lián)中的應用?

關 欣,孫祥威,曹昕瑩

(海軍航空工程學院信息融合技術研究所,山東煙臺264001)

0 引言

隨著現(xiàn)代科學技術在軍事領域的廣泛應用,現(xiàn)代戰(zhàn)爭已經(jīng)突破了傳統(tǒng)模式,發(fā)展成為陸、海、空、天、電磁五位一體的戰(zhàn)爭。在現(xiàn)代戰(zhàn)術系統(tǒng)中,依靠單一傳感器系統(tǒng)提供信息已無法滿足作戰(zhàn)需要,必須運用多個傳感器系統(tǒng)來提供觀測信息,這就需要對多傳感器系統(tǒng)獲取的信息進行綜合處理,實時進行目標發(fā)現(xiàn)和優(yōu)化綜合處理來獲取目標狀態(tài)估計、目標屬性及目標身份、態(tài)勢評估、威脅估計等作戰(zhàn)信息[1-3]。

特征關聯(lián)是無源多傳感器輻射源融合識別的一個關鍵環(huán)節(jié)。無源多傳感器融合識別系統(tǒng)需要直接融合來自同類信源的數(shù)據(jù),然后進行特征提取和利用融合數(shù)據(jù)進行屬性判決。為了使這種融合順利進行,首先需要利用同類信源獲取的輻射源特征信息特征進行特征關聯(lián),保證被融合的數(shù)據(jù)對應于相同的輻射源。

特征關聯(lián)產(chǎn)生于傳感器量測過程中的不確定性。理論上,源自同一輻射源的量測數(shù)據(jù)中的特征值是相同的,但由于傳感器存在測量誤差,且不同的輻射源之間本身也可能存在特征上的相似性,這些都使量測值與其源自的輻射源之間的對應關系出現(xiàn)了模糊性。特征關聯(lián)是將無源多傳感器獲取的多個輻射源的特征參數(shù)相關為一組,而每一組表示與一個單一可分辨的輻射源有關的數(shù)據(jù),確定每組觀測屬于哪個已知輻射源的觀測或是潛在輻射源的新的觀測,從而消除關聯(lián)模糊,它的本質(zhì)是分類問題。

對于分類算法選取問題,文獻[4]針對未知的雷達輻射源信號,提出了一種新的基于數(shù)據(jù)勢場聚類的未知雷達信號分選方法,解決了分類數(shù)確定的問題;文獻[5]利用改進的K-Means算法解決了參數(shù)相近、互相交疊的非常規(guī)雷達信號的分類問題。但這些分類算法都面臨著分類數(shù)確定和分類效果評估的問題。本文改進了K-Means算法,并將其應用到特征關聯(lián)上,解決了雷達輻射源數(shù)量估計和分類效果評估的問題。

1 特征關聯(lián)過程

圖1給出了特征關聯(lián)的具體過程:首先是利用雷達輻射源特征矢量,由預先定義的相似性度量計算相似度得到相似矩陣,進而確定特征矢量組中哪些是對同一雷達輻射源的描述,即確定多量測之間能否歸到一起,以表示它們是相同的潛在實體的分離觀測。這種分類結(jié)果是否合理,需要進行檢驗,如果不合理則重復分類直到輸出合理的檢驗結(jié)果。

圖1 特征關聯(lián)過程圖

2 改進的K-Means算法

2.1 K-Means算法

K-Means算法是Mac Queen提出的一種非監(jiān)督實時聚類算法,在最小化誤差函數(shù)的基礎上將數(shù)據(jù)劃分為預定的簇數(shù)k。設待分類的樣本集為X={x1,x2,…,x n},分類數(shù)目k(k≤n)是事先確定的,該方法取定k類和選取k個初始聚類中心,按最小距離原則將各樣本分配到k類中的某一類,之后不斷地計算類心和調(diào)整各樣本的類別,最終使各樣本到其所屬類別中心的距離平方之和最小[6]。

具體運算步驟如下:

(1)任選k個樣本作為初始聚類中心:z(0)1,

(2)將待分類的樣本集X中的樣本逐個按最小距離原則分劃給k類中的某一類,即若

則判

(3)計算重新分類后的各類心

在上述步驟中,雖然沒有直接運用準則函數(shù)

進行分類,但在步驟(2)中根據(jù)式(2)進行劃分可使J(c)趨于變小。

K-Means算法的時間復雜度是O(m×n×k×t),空間復雜度是O((n+k)×m)。其中n表示所有樣本點的個數(shù),k是類數(shù)目,t是迭代次數(shù),m是樣本的屬性個數(shù),通常k?n且t?n。影響K-Means算法性能的因素主要有兩個:①聚類數(shù)k的選取;②初始聚類中心的選取。針對初始聚類中心選取問題,文獻[7]通過區(qū)域劃分方法估算出k個中心點作為初始聚類中心,減少了迭代次數(shù),提高了算法質(zhì)量;文獻[8]采取對數(shù)據(jù)進行預處理的方式選取初始中心,提高了算法效率。

2.2 聚類數(shù)k的確定

在聚類數(shù)未知的情況下使用K-Means算法,可讓聚類數(shù)k從較小值逐步增加,在這個過程中,對于每個選定的k分別使用該算法。顯然,準則函數(shù)J是隨著k的增加而單調(diào)減少,如果作一條J-c曲線,其曲率變化的最大點對應的類數(shù)是比較接近從幾何分布上看最優(yōu)的類數(shù)。由于從J-c曲線上觀察曲率變化的最大點不直觀,本文使用聚類有效性指標S來確定最佳聚類數(shù)

式中,a i表示第i個樣本到其所在類中其他樣本的平均距離;b i表示第i個樣本到其他類中樣本的最小平均距離。對于不同的k值時,S值不同,S值最大時對應的k值為最佳聚類數(shù)。

2.3 灰關聯(lián)度

灰色系統(tǒng)理論是由鄧聚龍教授于1982年創(chuàng)立的,是一種研究少數(shù)據(jù)、貧信息不確定性問題的新方法。灰關聯(lián)分析根據(jù)數(shù)據(jù)列因素之間發(fā)展態(tài)勢的相似或相異程度來衡量因素間接近的程度,由于關聯(lián)分析是按發(fā)展趨勢作分析,對樣本集的大小沒有太高的要求,分析時也不需要典型的分布規(guī)律,而且分析的結(jié)果一般與定性分析相吻合。可用于每類雷達有多個模式以及偵測參數(shù)不全的場合,適應部分雷達輻射源偵察信號“少數(shù)據(jù)”、“貧信息”的特點[9]。

計算樣本間的灰關聯(lián)度,一般包括下列的計算和分析步驟。

(1)確定參考序列和比較序列

選取樣本集中的一個樣本作為參考序列,記為x i={x i(k)|i=1,2,…,n},選取樣本集中其余的樣本作為比較序列,記為x j≠i={x j(k)|j=1,2,…,n},其中k為樣本維數(shù),n為樣本集合中樣本總數(shù)。

(2)對樣本進行標準化處理

在對樣本進行處理時,量綱選取不同會改變某特征的判斷依據(jù)性,即改變該特征對判斷貢獻的大小,嚴重的可造成錯誤分類。因此,首先需要對樣本集進行標準化處理,本文用區(qū)間值變換法對樣本集進行標準化處理。

(3)求關聯(lián)系數(shù)

參考序列x i(k)和比較序列x j(k)的關聯(lián)系數(shù)定義如下:

式中,Δij(k)=|x i(k)-x j(k)|為絕對差;為兩級最小差;為兩級最大差;ρ為分辨系數(shù),且ρ∈(0,1),一般取ρ=0.5;上述定義的γ(x i(k),x j(k))稱為k點的灰色關聯(lián)系數(shù)。

(4)計算灰關聯(lián)度

將每一比較序列各個特征的關聯(lián)系數(shù)集中體現(xiàn)在一個值上以便于比較,這個值就是灰關聯(lián)度,常用的計算灰關聯(lián)度的方法是平均值法,即

2.4 改進的K-Means算法流程圖

圖2給出了改進的K-Means算法計算流程圖,K-Means算法中定義樣本之間距離d ij()的方法有絕對值距離、歐氏距離、切比雪夫距離、馬氏距離,改進的K-Means算法使用灰關聯(lián)度定義樣本間的距離。改進的K-Means算法的時間復雜度是O(m×n2×k×t),空間復雜度是O((n2+k)×m)。計算時設置分類數(shù)從2開始逐步增大,在平方誤差和準則E收斂時,輸出聚類結(jié)果,計算聚類結(jié)果的聚類有效性指標,取有效性指標值最大時對應的k值為最佳聚類數(shù) 。

平方誤差和準則定義如下:

E是數(shù)據(jù)庫中所有對象的平方誤差總和,x是空間中的樣本點,表示給定的數(shù)據(jù)對象,m i是類C i的平均值,這個準則使生成的結(jié)果類盡可能地緊湊和獨立。

3 計算機仿真及結(jié)果分析

3.1 模擬產(chǎn)生雷達輻射源特征信息

實驗中仿真模擬2部雷達偵察設備對同方向的3部復雜體制雷達輻射源信號偵察與截獲,考慮到真實環(huán)境下存在的各種噪聲和各個偵察設備的測量誤差,設定脈沖重復頻率誤差為5 Hz,載頻誤差為5 MHz,脈寬誤差為0.2μs,樣本點數(shù)值大小見表1。假設共獲取了300組特征矢量作為樣本構成樣本集,稱該樣本集為Radar-database,樣本集含有300個樣本,形成3類,并且類之間有輕微重疊,每個樣本有3個特征,每類中各有100個樣本。

圖2 改進的K-Means算法流程圖

表1 雷達輻射源類型及參數(shù)設置

為了檢驗改進的K-Means算法分類方法能否對樣本集Radar-database成功分類,使用該改進算法對樣本集進行分類,觀察分類結(jié)果。將分類結(jié)果和原始樣本集進行對比,確定分類后每個樣本的類別是否與原始樣本集中該樣本的真實類別相同,相同則稱為分類正確,否則稱為分類錯誤。

在分類之前,先定義能反映分類算法在特征關聯(lián)上性能的參數(shù)如下:

(1)關聯(lián)正確率:分類正確樣本的個數(shù)占樣本集中樣本總數(shù)的比值即為關聯(lián)正確率。

(2)關聯(lián)錯誤率:分類錯誤樣本的個數(shù)占樣本集中樣本總數(shù)的比值即為關聯(lián)錯誤率。

(3)關聯(lián)時間:每次算法運行的時間。

本文中的計算機仿真實驗都是基于Matlab7.0的軟件平臺,硬件平臺為以下配置的個人電腦:Celeron(R)CPU 3.06 GHz,512 MB內(nèi)存。

3.2 聚類數(shù)k值的確定

首先使用改進的K-Means算法對樣本集Radar-database進行聚類,由于算法要求分類前知道分類數(shù)目,采用試探法,讓分類數(shù)k值從較小值逐步增加,對于每個選取的k值分別使用該改進的算法,輸出聚類結(jié)果,計算聚類有效性指標的值。圖3顯示k值為2,3,4和5時,有效性指標值的大小。圖4顯示的是k值從2到10時,有效性指標值的大小,從圖4可以看出當k值為3時,有效性指標值最大,樣本集Radar-database最佳分為3類。

圖3 k=2,3,4,5時有效性指標

圖4 有效性指標的最大值

3.3 改進的K-Means算法性能測試

用改進的K-Means算法對樣本集Radar-database進行聚類,聚類結(jié)果如圖5所示。由圖5可知,改進的K-Means算法能對樣本集Radar-database進行有效聚類,但由于樣本集中部分樣本存在重合和交疊,出現(xiàn)了一些分類錯誤的樣本。圖中黑色的點顯示的就是分類錯誤的樣本,共23個,關聯(lián)正確率為92.33%。

圖5 樣本集Radar-database分類結(jié)果

用改進的K-Means算法和K-Means算法進行比較,同時對樣本集Radar-database進行100次分類,計算關聯(lián)正確率和程序運行時間,數(shù)據(jù)見表2。

表2 改進的K-Means算法和K-Means算法性能比較

由表2可以看出改進的K-Means用灰關聯(lián)度定義樣本點間的距離,對樣本集Radar-database進行聚類時,關聯(lián)正確率高于K-Means算法中其他的距離定義,但程序運行時間明顯提高,這是因為改進的K-Means算法的空間和時間復雜度都要高。

4 結(jié)束語

針對無源多傳感器多輻射源特征關聯(lián)問題,本文提出了一種改進的K-Means算法,用灰關聯(lián)度定義了樣本間的距離,在對樣本集Radar-database進行分類時,可以有效地估計最優(yōu)的分類數(shù)。仿真結(jié)果表明使用改進的K-Means進行分類時,關聯(lián)正確率在96%以上,高于其他的度量方式,但消耗更多的時間,在實際應用時需要綜合考慮。

[1]何友,王國宏,關欣.信息融合理論及應用[M].北京:電子工業(yè)出版社,2010:7-16,101-103.

[2]趙貴喜,王巖,于冰,等.基于人工魚群聚類的雷達信號分選算法[J].雷達科學與技術,2013,11(4):375-378.ZHAO Gui-xi,WANG Yan,YU Bing,et al.Radar Signal Sorting Algorithm Based on Artificial Fish Swarm Clustering[J].Radar Science and Technology,2013,11(4):375-378.(in Chinese)

[3]Zhang Gexiang,Li Xu.A New Recognition System for Radar Emitter Signals[J].Kybernetes,2012,41(9):1351-1360.

[4]張紅昌,阮懷林,龔亮亮,等.一種新的未知雷達輻射源聚類分選方法[J].計算機工程與應用,2008,44(27):200-202.

[5]張萬軍,樊甫華,譚營.聚類方法在雷達信號分選中的應用[J].雷達科學與技術,2004,2(4):219-223.ZHANG Wan-jun,FAN Fu-hua,TAN Ying.Application of Cluster Method to Radar Signal Sorting[J].Radar Science and Technology,2004,2(4):219-223.(in Chinese)

[6]Yang Zhutian,Wu Zhilu,Yin Zhendong,et al.Hybrid Radar Emitter Recognition Based on Rough KMeans Classifier and Relevance Vector Machine[J].Sensors,2013(13):848-864.

[7]蘇錦旗,薛惠鋒,詹海亮.基于劃分的K-均值初始聚類中心優(yōu)化算法[J].微電子學與計算機,2009,26(1):8-11.

[8]步媛媛,關忠仁.基于K-means聚類算法的研究[J].西南民族大學學報(自然科學版),2009,35(1):198-200.

[9]Wang Wenping,Wang Jiaoli,Huang Xinhuan,et al.Study on Community Structure Characteristics of Cluster Networks with Calculation and Adjustment of Trust Degree Based on the Grey Correlation Degree Algorithm[J].Grey Systems:Theory and Application,2011,1(2):129-137.