劉佳媛,邢 朦,邵立琴

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

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

劉佳媛,邢 朦,邵立琴

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

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

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

0 引 言

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

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

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

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

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

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

(1)

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

(2)

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

基本的K-Means算法如下：

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

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

(3)

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

(4)

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

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

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

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

(5)

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

(6)

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

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

(7)

(4) 若m

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

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

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

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

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

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

(8)

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

(9)

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

步驟6若k

4 仿真分析

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

[1] 趙國慶.雷達(dá)對抗原理[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] 李向東，張月磊，劉存超. 基于聚類和統(tǒng)計理論的雷達(dá)組網(wǎng)融合方法[J].艦船電子工程,2016(1): 37-38.

[7] 舒紅平, 徐振明, 鄒書蓉, 何嘉. 網(wǎng)格聚類在多雷達(dá)數(shù)據(jù)融合算法中的應(yīng)用[J]. 電子科技大學(xué)學(xué)報,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ù)處理。