一種改進(jìn)的聚類目標(biāo)融合算法

劉佳媛,邢 朦,邵立琴

(中國船舶重工集團(tuán)公司第七二四研究所，南京 211153)

一種改進(jìn)的聚類目標(biāo)融合算法

劉佳媛,邢 朦,邵立琴

(中國船舶重工集團(tuán)公司第七二四研究所，南京 211153)

多源目標(biāo)數(shù)據(jù)融合技術(shù)是雷達(dá)輻射源關(guān)聯(lián)融合中的一項(xiàng)關(guān)鍵技術(shù)。以K均值算法為基礎(chǔ)，對(duì)簇中心初始化方法進(jìn)行優(yōu)化，提出了基于空間密度與歐氏距離結(jié)合的聚類初始化算法，對(duì)聚類方法進(jìn)行改進(jìn)，并將其應(yīng)用于多源目標(biāo)融合領(lǐng)域。仿真結(jié)果驗(yàn)證了該算法可以有效地提高多源融合性能。

雷達(dá)；目標(biāo)融合；K-均值；簇中心

0 引 言

雷達(dá)多目標(biāo)融合系統(tǒng)需要接收各個(gè)雷達(dá)傳感器送來的多源目標(biāo)信息并進(jìn)行實(shí)時(shí)融合處理，獲得綜合目標(biāo)特征信息。這些多源目標(biāo)信息的數(shù)據(jù)量大，并且具有多種形式。在處理時(shí)首先需要對(duì)其進(jìn)行轉(zhuǎn)換，以提取共同特征參數(shù)，并對(duì)特征參數(shù)相似的目標(biāo)完成關(guān)聯(lián)、融合處理。

在多雷達(dá)傳感器偵測(cè)多種輻射源目標(biāo)時(shí)，由于不同雷達(dá)具有不同的數(shù)據(jù)采集時(shí)間、通信時(shí)延以及測(cè)量精度，所以在一段時(shí)間內(nèi)采集到的輻射源目標(biāo)信息，包括載頻、脈寬、重復(fù)周期、方位等多種參數(shù)[1]，會(huì)在一個(gè)高維空間中以簇的形式呈現(xiàn)出來。理想情況下，各個(gè)簇會(huì)集中于各個(gè)觀測(cè)目標(biāo)的周圍，以實(shí)際目標(biāo)所在位置為簇的中心，并以一定的密度分布于目標(biāo)四周。但是，在實(shí)際情況下，由于雜波和其他干擾的影響，不同雷達(dá)的測(cè)量精度，以及多個(gè)目標(biāo)源的空間聚集程度不同，會(huì)導(dǎo)致簇呈現(xiàn)不同的分布情況。區(qū)分同一平臺(tái)觀測(cè)的不同目標(biāo)，同時(shí)對(duì)不同平臺(tái)觀測(cè)的同一目標(biāo)進(jìn)行融合關(guān)聯(lián)，是目標(biāo)融合的工作重點(diǎn)。當(dāng)目標(biāo)輻射源數(shù)量較多且位置較近，會(huì)使得這些目標(biāo)在融合處理過程中被判為同一目標(biāo)，加之不同雷達(dá)的測(cè)量精度不同，進(jìn)一步導(dǎo)致觀測(cè)數(shù)據(jù)的彌散程度提升，嚴(yán)重影響融合效果。

聚類(Clustering)[2]算法是將一個(gè)多維觀測(cè)集劃分到自然組成或者模式。聚類主要分為分割聚類和層次聚類兩種。分割聚類算法通過優(yōu)化評(píng)價(jià)函數(shù)把數(shù)據(jù)集分割為K個(gè)部分，需要K作為輸入?yún)?shù)。典型的分割聚類算法有K-means(K均值)算法[3]、 K-medoids算法和CLARANS算法，其中應(yīng)用范圍最廣的是K-means算法。該算法廣泛應(yīng)用于數(shù)據(jù)挖掘、模式識(shí)別和機(jī)器學(xué)習(xí)等多個(gè)領(lǐng)域[4-7]。本文首先將K-means算法應(yīng)用到多源多目標(biāo)融合領(lǐng)域，充分考慮多傳感器系統(tǒng)的特殊性，為提升多傳感器融合性能提出了一種改進(jìn)的基于空間密度聚類的多目標(biāo)融合算法，最后對(duì)K均值融合算法與改進(jìn)的算法進(jìn)行仿真，驗(yàn)證了所提出的多目標(biāo)融合算法的有效性。

1 傳統(tǒng)K-means聚類方法

聚類是非監(jiān)督學(xué)習(xí)的一種形式，是將一個(gè)觀測(cè)集(即數(shù)據(jù)點(diǎn))劃分到自然組成或者模式聚類。聚類的途徑是測(cè)量分配給每個(gè)聚類的觀測(cè)對(duì)之間的相似性以最小化一個(gè)指定的代價(jià)函數(shù)。

K-Means算法是最常用的聚類算法。作為期望最大化(Expectation-Maximization)算法的一個(gè)特例，其主要思想是在給定簇?cái)?shù)k和k個(gè)初始簇中心點(diǎn)μj,j=1,…,k的情況下，把每個(gè)觀測(cè)樣本按照相似度(空間距離)逐一歸類到與其最相似的簇中，根據(jù)聚類結(jié)果重新計(jì)算每個(gè)簇的中心，通過迭代不斷優(yōu)化樣本分類并更新簇中心直至聚類誤差收斂。收斂準(zhǔn)則為簇內(nèi)誤差平方和最小，即

(1)

對(duì)于給定的C，分類準(zhǔn)則為

(2)

觀測(cè)數(shù)據(jù)可定義為X=[x1,…，xn]，其中n為觀測(cè)數(shù)據(jù)的樣本總數(shù)，xi為第i個(gè)觀測(cè)樣本，且為1×m維觀測(cè)列向量，m表征了觀測(cè)目標(biāo)的參數(shù)維度，目標(biāo)參數(shù)可包含載頻、脈寬、重復(fù)周期、方位、多普勒等多種參數(shù)。

基本的K-Means算法如下：

(1) 確定迭代終止條件ε，最大迭代次數(shù)L，初始化迭代次數(shù)l=0，初始化簇?cái)?shù)k以及簇中心μj,j=1,…,k；

(2)l=l+1，對(duì)每一個(gè)觀測(cè)數(shù)據(jù)xi，分別計(jì)算其與k個(gè)簇中心μj,j=1,…,k的距離，并將該觀測(cè)數(shù)據(jù)歸類到與其距離最近的簇中。即

(3)

(3) 根據(jù)步驟2的分類結(jié)果重新計(jì)算簇中心，并計(jì)算簇內(nèi)誤差El。

(4)

(4) 判斷是否滿足迭代終止條件|El-El-1|<ε或最大迭代次數(shù)l=L，若滿足退出循環(huán)，否則執(zhí)行步驟2。

2 基于空間密度的聚類初始化算法

K均值聚類算法本身思想比較簡(jiǎn)單，但是合理的確定簇?cái)?shù)k和k個(gè)簇中心點(diǎn)對(duì)于聚類效果的好壞有很大的影響。錯(cuò)誤的簇?cái)?shù)和簇中心的選擇會(huì)導(dǎo)致聚類算法無法獲得最優(yōu)解。對(duì)于簇?cái)?shù)的選擇，傳統(tǒng)的方法是盡可能遍歷合理的簇?cái)?shù)取值，比如依次在k=2,…,K的情況下進(jìn)行聚類運(yùn)算，之后選擇具有簇內(nèi)誤差最小的簇?cái)?shù)作為最終簇?cái)?shù)。Calinski-Harabasz準(zhǔn)則就是用于進(jìn)行簇?cái)?shù)評(píng)估的方法，實(shí)際應(yīng)用中可較好地完成最優(yōu)簇?cái)?shù)選擇，另一方面簇中心初始化也會(huì)嚴(yán)重影響聚類算法的性能。除了傳統(tǒng)的隨機(jī)選擇簇中心方法，常用的初始類簇中心算法還包括最大最小距離法、最大距離積法、層次聚類法等，但仍然依賴于樣本和簇中心的歐氏距離，當(dāng)具有相似的歐式距離時(shí)無法獲得理想的效果。即便有文章[8]將空間密度引入到簇中心初始化中，但是仍然需要為算法提供基于經(jīng)驗(yàn)的參數(shù)輸入。這些參數(shù)的選擇同樣會(huì)影響簇中心的確定。本文旨在對(duì)簇中心初始化方法進(jìn)行優(yōu)化，提出了新的基于空間密度的聚類初始化算法，對(duì)聚類方法進(jìn)行改進(jìn)，并將其應(yīng)用于多目標(biāo)融合領(lǐng)域。

對(duì)于給定觀測(cè)數(shù)據(jù)可定義為X=[x1,…，xn]，其中n為觀測(cè)數(shù)據(jù)的樣本總數(shù)，xi為第i個(gè)觀測(cè)樣本，且為1×m維觀測(cè)列向量，m表征了觀測(cè)目標(biāo)的參數(shù)維度。則觀測(cè)數(shù)據(jù)集中每個(gè)點(diǎn)相對(duì)于其他點(diǎn)的密度為

(5)

其中δ表示歸一化半徑，其定義為

(6)

則基于密度的初始化簇中心算法可概括為：

(1) 計(jì)算觀測(cè)數(shù)據(jù)集中每個(gè)點(diǎn)相對(duì)于其他點(diǎn)的密度fi，并找到密度最高的點(diǎn)作為第m個(gè)簇的中心(初始值為1)，同時(shí)初始化簇?cái)?shù)k。

(7)

(4) 若m

(5) 完成k個(gè)簇的初始化過程。

3 基于空間密度聚類的多目標(biāo)融合算法

上一節(jié)闡述了傳統(tǒng)的K均值聚類方法以及基于空間密度的聚類初始化算法。為了加快簇中心初始化迭代速度，將上述方法用于多目標(biāo)融合算法，具體算法如下：

步驟1確定迭代終止條件ε，最大迭代次數(shù)L，最大簇?cái)?shù)K。初始化迭代次數(shù)l=0，初始化簇?cái)?shù)k，令k=2。

步驟2利用前一章所述的初始化方式，對(duì)給定的簇?cái)?shù)k和給定的觀測(cè)數(shù)據(jù)集X，確定簇中心μj,j=1,…,k。

步驟3l=l+1，對(duì)每一個(gè)觀測(cè)數(shù)據(jù)xi，分別計(jì)算其與k個(gè)簇中心μj,j=1,…,k的距離，并將該觀測(cè)數(shù)據(jù)歸類到與其距離最近的簇中。即

(8)

步驟4根據(jù)步驟2的分類結(jié)果重新計(jì)算簇中心，并計(jì)算簇內(nèi)誤差El。

(9)

步驟5判斷是否滿足迭代終止條件|El-El-1|<ε或最大迭代次數(shù)l=L，若滿足退出循環(huán)，否則執(zhí)行步驟3。

步驟6若k

4 仿真分析

為驗(yàn)證上述的多源融合算法進(jìn)行仿真驗(yàn)證，通過對(duì)隨機(jī)初始化的K均值算法以及基于空間密度的聚類初始化的目標(biāo)融合算法完成性能比對(duì)。

圖1給出了觀測(cè)數(shù)據(jù)集在二維空間中的分布情況，二維空間由頻率-方向域組成。目標(biāo)融合的目的就是將所有的觀測(cè)數(shù)據(jù)進(jìn)行關(guān)聯(lián)匹配，以從觀測(cè)數(shù)據(jù)中識(shí)別出多個(gè)目標(biāo)，以及每個(gè)目標(biāo)的特征參數(shù)。

圖1 觀測(cè)數(shù)據(jù)集在頻域—方向域的分布情況

圖2給出了利用隨機(jī)初始化的K均值方法得到的分類結(jié)果。由于在初始化階段每個(gè)簇的簇中心都是隨機(jī)生成，導(dǎo)致聚類的結(jié)果會(huì)以一定的概率收斂到局部最優(yōu)的，而非全局最優(yōu)，從而影響結(jié)果的可靠性，導(dǎo)致目標(biāo)識(shí)別出現(xiàn)錯(cuò)誤。

圖2 利用隨機(jī)初始化的K均值算法分類結(jié)果

圖3給出了改進(jìn)的方法得到的分類結(jié)果。由于采用了空間密度與歐氏距離結(jié)合的方式來對(duì)簇中心進(jìn)行初始化，避免了隨機(jī)初始化的不可靠性，也避免了過多的輸入?yún)?shù)，最終得到的簇中心更接近真實(shí)的簇中心。同時(shí)，根據(jù)空間密度與歐式距離迭代簇中心的方法也會(huì)進(jìn)一步降低迭代次數(shù)，加快收斂過程。

圖3 利用改進(jìn)的基于空間密度聚類的

通過蒙特卡洛仿真方法對(duì)上述聚類方法進(jìn)行對(duì)比仿真分析可以得到準(zhǔn)確率以及聚類誤差的比較結(jié)果。由表1各算法在仿真數(shù)據(jù)集上的準(zhǔn)確率和誤差的比較可見，由于傳統(tǒng)聚類算法和模糊聚類算法是隨機(jī)選擇初始聚類中心且對(duì)聚類結(jié)果影響較大，所以迭代多次后聚類結(jié)果具有不穩(wěn)定性從而導(dǎo)致平均準(zhǔn)確率較低，聚類誤差較高。本算法在仿真數(shù)據(jù)集中的準(zhǔn)確性明顯優(yōu)于前兩種聚類算法。由于在初始化過程中將樣本密度考慮到聚類初始化過程中，并同時(shí)結(jié)合AIC準(zhǔn)則可以有效提高聚類的準(zhǔn)確性，并降低迭代次數(shù)。

表1 各算法在仿真數(shù)據(jù)集的性能比較

5 結(jié)束語

本文針對(duì)原始的K均值算法的初始化簇中心采用的隨機(jī)選取問題，提出了基于密度和歐氏距離相結(jié)合的簇中心優(yōu)化的K均值算法，以此提升了K均值聚類算法的不穩(wěn)定性，在加快迭代收斂速度的同時(shí)獲得了聚類準(zhǔn)確率的大幅提升。

[1] 趙國慶.雷達(dá)對(duì)抗原理[M].西安: 西安電子科技大學(xué)出版社, 1999.

[2] Trevor Hastie, Robert Tibshirani, Jerome Friedm-an.The Elements of Statistical Learning: Data Mining, Inference, and Prediction [M]. New York: Springer, 2001.

[3] Simon O Haykin. Neural networks and learning ma-chines [M]. Pearson,2008.

[4] Zhongzhi Li, Xuegang Wang. High Resolution Ra-dar Data Fusion Based on Clustering Algorithm [C]//Database Technology and Applications (DBTA), 2010 2nd International Workshop, 2010.11:27-28.

[5] Hao Wang, Tangxing Liu, Qing Bu, Bo Yang. An algorithm based on hierarchical clustering for multi-target tracking of multi-sensor data fusion[C] //2016 35th Chinese Control Conference (CCC),2016.7.

[6] 李向東，張?jiān)吕冢瑒⒋娉? 基于聚類和統(tǒng)計(jì)理論的雷達(dá)組網(wǎng)融合方法[J].艦船電子工程,2016(1): 37-38.

[7] 舒紅平, 徐振明, 鄒書蓉, 何嘉. 網(wǎng)格聚類在多雷達(dá)數(shù)據(jù)融合算法中的應(yīng)用[J]. 電子科技大學(xué)學(xué)報(bào),2007(6): 1253-1256.

[8] McQueen. Some methods of classification and analysis of multivariate observations [C]. Proceedings of Fifth Berkeley Symposium on Mathematical Statistics and Probability,1967:281:197.

An improved algorithm of clustering target fusion

LIU Jia-yuan, XING Meng, SHAO Li-qin

(No.724 Research Institute of CSIC, Nanjing 211153)

Multi-target data fusion is one of the key techniques in the association and fusion of radar radiation sources. A new initialization method for K-means clustering by utilizing spatial density and Euclidean distance is proposed, and the initialization method of clustering center is optimized and applied in the field of multi-target data fusion. The simulation results show that this algorithm can effectively improve the multi-target data fusion performance.

radar; target fusion; K-means; clustering center

TN957.52

A

1009-0401(2017)04-0019-04

2017-10-20；

2017-11-03

劉佳媛(1988-)，女，工程師，碩士，研究方向：數(shù)據(jù)處理；邢朦(1988-)，女，工程師，碩士，研究方向：終端顯控；邵立琴(1977-)，女，工程師，研究方向：數(shù)據(jù)處理。