改進的K-Means算法在特征關聯中的應用?

關 欣,孫祥威,曹昕瑩

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

0 引言

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

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

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

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

1 特征關聯過程

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

圖1 特征關聯過程圖

2 改進的K-Means算法

2.1 K-Means算法

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

具體運算步驟如下:

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

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

則判

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

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

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

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

2.2 聚類數k的確定

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

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

2.3 灰關聯度

灰色系統理論是由鄧聚龍教授于1982年創立的,是一種研究少數據、貧信息不確定性問題的新方法。灰關聯分析根據數據列因素之間發展態勢的相似或相異程度來衡量因素間接近的程度,由于關聯分析是按發展趨勢作分析,對樣本集的大小沒有太高的要求,分析時也不需要典型的分布規律,而且分析的結果一般與定性分析相吻合?？捎糜诿款惱走_有多個模式以及偵測參數不全的場合,適應部分雷達輻射源偵察信號“少數據”、“貧信息”的特點[9]。

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

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

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

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

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

(3)求關聯系數

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

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

(4)計算灰關聯度

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

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

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

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

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

3 計算機仿真及結果分析

3.1 模擬產生雷達輻射源特征信息

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

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

表1 雷達輻射源類型及參數設置

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

在分類之前,先定義能反映分類算法在特征關聯上性能的參數如下:

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

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

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

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

3.2 聚類數k值的確定

首先使用改進的K-Means算法對樣本集Radar-database進行聚類,由于算法要求分類前知道分類數目,采用試探法,讓分類數k值從較小值逐步增加,對于每個選取的k值分別使用該改進的算法,輸出聚類結果,計算聚類有效性指標的值。圖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進行聚類,聚類結果如圖5所示。由圖5可知,改進的K-Means算法能對樣本集Radar-database進行有效聚類,但由于樣本集中部分樣本存在重合和交疊,出現了一些分類錯誤的樣本。圖中黑色的點顯示的就是分類錯誤的樣本,共23個,關聯正確率為92.33%。

圖5 樣本集Radar-database分類結果

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

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

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

4 結束語

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

[1]何友,王國宏,關欣.信息融合理論及應用[M].北京:電子工業出版社,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-均值初始聚類中心優化算法[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.