基于Mean Shift算法的多目標(biāo)識別與仿真

韓光威，顧力偉，劉 詠

(中國船舶重工集團公司第七二三研究所，江蘇 揚州225101)

0 引 言

隨著電子信息和計算機系統(tǒng)的迅猛發(fā)展，現(xiàn)代戰(zhàn)爭中的信息化作戰(zhàn)也越來越重要。目標(biāo)識別是指利用光學(xué)儀器、雷達(dá)、聲納和計算機等設(shè)備對目標(biāo)的敵我屬性、類型的判別[1]。目標(biāo)識別系統(tǒng)作為現(xiàn)代信息化作戰(zhàn)平臺上進行區(qū)分?jǐn)澄业闹匾侄?，對目?biāo)識別系統(tǒng)進行多目標(biāo)識別的研究具有重要的意義。

目標(biāo)識別系統(tǒng)進行目標(biāo)識別時影響因素較多，受外界地形環(huán)境的干擾復(fù)雜，不同影響因素間具有相互的干擾作用，因此基于規(guī)則或?qū)＜蚁到y(tǒng)的方法也變得越來越困難[24]?；诰垲惖姆椒軌蛲ㄟ^分析系統(tǒng)采集的數(shù)據(jù)來得到我方目標(biāo)的數(shù)據(jù)信息，而通過分析實時數(shù)據(jù)和我方目標(biāo)的差異可以進行目標(biāo)的識別。同時，由于系統(tǒng)信號傳輸?shù)牟淮_定性和一些外界因素，導(dǎo)致采集的系統(tǒng)數(shù)據(jù)中會出現(xiàn)離群數(shù)據(jù)點，這些離群點導(dǎo)致一些傳統(tǒng)的聚類方法，如DBSCAN 等存在一些不足，影響聚類的效果。

本文針對目標(biāo)識別系統(tǒng)的上述特性，提出了一種基于Mean Shift的改進聚類算法，能夠在聚類的同時診斷出離群數(shù)據(jù)點，避免其對分類效果造成不利影響；同時由于系統(tǒng)聚類比較的是通過Mean Shift算法得到的數(shù)據(jù)密度中心點，能夠進行精確的目標(biāo)識別，避免了DBSCAN 的數(shù)據(jù)邊界點造成的聚類異常；在實際在線測試過程中，也能夠達(dá)到較好的識別結(jié)果。

1 基于Mean Shift算法的建模

1.1 基于Mean Shift的聚類算法

Mean Shift算法能夠自適應(yīng)地搜索空間中樣本分布密度增加最大的方向，并最終收斂到此密度峰值點，進而識別出數(shù)據(jù)的局部聚類特征[56]。由于Mean Shift算法不需要具有任何先驗知識，并且能夠處理任意特征空間，只有移動窗口的參數(shù)需要調(diào)節(jié)，所以Mean Shift 算法比較適合處理復(fù)雜的數(shù)據(jù)。

Mean Shift向量的最基本形式可定義為：

式中：S h是一個半徑為h的高維球區(qū)域；(x i-x)是樣本點x i相對于基準(zhǔn)點x的偏移量；M h(x)是落入?yún)^(qū)域S h中的t個樣本點相對于點x的偏移向量的均值。

如圖1所示，圖中圓形區(qū)域為S h，小圓圈代表落入S h區(qū)域的t個樣本點x i，黑點是Mean Shift的基準(zhǔn)點x，箭頭表示樣本點相對于基準(zhǔn)點x的偏移向量。由圖1可看出，偏移向量M h(x)會指向樣本分布密度最大的方向。經(jīng)Mean迭代計算，不斷用M h(x)的向量計算結(jié)果更新基準(zhǔn)點x，當(dāng)滿足‖M h(x)‖小于某容許誤差條件時即可獲得收斂到的穩(wěn)態(tài)聚類中心點[7]。

圖1 Mean Shift示意圖

由于各樣本點與基準(zhǔn)點的距離不同，所以在處理偏移向量時要對不同的偏移距離取不同的權(quán)重。一般而言，離基準(zhǔn)點越近的點對估計當(dāng)前區(qū)域的密度具有較大的作用。為解決這一問題，在此引入高斯核函數(shù)G(x)。運用高斯核函數(shù)能夠單調(diào)地反映樣本點與基準(zhǔn)點之間距離與樣本點的權(quán)重關(guān)系。此時，向量M h(x)化為：

1.2 離線建模流程

多目標(biāo)識別系統(tǒng)的離線建模流程如下：

(1)采集目標(biāo)識別系統(tǒng)的歷史數(shù)據(jù)，包括我方目標(biāo)和敵方不同目標(biāo)的數(shù)據(jù)信息作為建模數(shù)據(jù)，并標(biāo)準(zhǔn)化處理。

(2)將已知我方數(shù)據(jù)信息和某一類的敵方目標(biāo)的數(shù)據(jù)信息作為輸入數(shù)據(jù)，運用Mean Shift方法得到2類輸入數(shù)據(jù)的密度中心點。

(3)將2類密度中心點作為聚類中心點，同時不斷擴大搜索半徑來賦予輸入數(shù)據(jù)標(biāo)簽，直到2類數(shù)據(jù)發(fā)生重疊或者所有數(shù)據(jù)全部分類完畢。

(4)對比分類完成后的標(biāo)簽和已知輸入標(biāo)簽，如果標(biāo)簽正確率在90%以上，則說明建模成功。此時對比分析聚類中心，找到中心距離最大的前n個特征，得到特征值的序號，作為目標(biāo)的模型f k，每一個k對應(yīng)一種敵方的目標(biāo)，即：

1.3 多目標(biāo)的在線識別

由1.2可知，本文的多目標(biāo)識別系統(tǒng)的輸入是一批已知的我方目標(biāo)的數(shù)據(jù)信息和在線的未知的一個批次的數(shù)據(jù)。在線識別時需要采集1 個批次(1個時間段)的在線數(shù)據(jù)與一批我方目標(biāo)的數(shù)據(jù)進行輸入分析，運用基于Mean Shift的算法進行在線聚類分析，如果輸入的2類數(shù)據(jù)能夠成功聚成2類，即聚類后的標(biāo)簽與輸入標(biāo)簽一致，即說明輸入的2類數(shù)據(jù)具有一定的差異性，同時得到一個與離線建模類似的模型向量f。對在線診斷得到的模型向量f匹配已離線建模的模型向量f k，這里匹配f和f k中相同的項，進而進行系統(tǒng)的多目標(biāo)識別。

2 實驗結(jié)果仿真分析

這里結(jié)合相關(guān)資料給出4組離線實驗數(shù)據(jù)，其中1組我方目標(biāo)，3組其他目標(biāo)的數(shù)據(jù)，這里定義為敵方目標(biāo)A，敵方目標(biāo)B，敵方目標(biāo)C。在每組數(shù)據(jù)中隨機取20個作為建模數(shù)據(jù)，其余數(shù)據(jù)作為測試數(shù)據(jù)。Mean Shift算法選取的核函數(shù)的主要參數(shù)為帶寬h。

經(jīng)過多次實驗比較，當(dāng)選取h=3 時能夠取得較好的聚類效果。圖2顯示了我方目標(biāo)與敵方目標(biāo)A 數(shù)據(jù)的聚類結(jié)果分析。敵方目標(biāo)A與我方目標(biāo)的密度中心點距離(采用歐氏距離)d1，樣本數(shù)據(jù)與目標(biāo)A數(shù)據(jù)的密度中心點距離d2，隸屬度即d2/(d1+d2)，在一定程度上反映了數(shù)據(jù)與我方目標(biāo)的相似程度。

圖2 基于Mean Shift算法的敵方目標(biāo)A 聚類結(jié)果

和傳統(tǒng)的Kmeans和DBSCAN 算法對比發(fā)現(xiàn)，如果采用傳統(tǒng)Kmeans聚類算法會出現(xiàn)分類異常的情況。如圖3所示，可以看到由于第25個樣本點是離群數(shù)據(jù)，與其他數(shù)據(jù)的距離較大，采用Kmeans算法進行聚類時，會把離群數(shù)據(jù)單獨分為一類，無法有效進行聚類。

圖3 敵方目標(biāo)A 的Kmeans聚類結(jié)果

和基于密度的經(jīng)典算法DBSCAN相比，DBSCAN 算法雖然也能有效處理噪聲離群點，但是需要反復(fù)調(diào)試來確定鄰域半徑和半徑內(nèi)包括的最小樣本點數(shù)。圖4給出了在2個維度上的聚類結(jié)果。

圖4 敵方目標(biāo)A 的DBSCAN 聚類結(jié)果

同時DBSCAN在某些情況下效果不佳，DBSCAN 利用密度的連通性，本質(zhì)上是通過尋找某一點周圍距離較近的點來進行算法迭代，如果某一目標(biāo)與我方目標(biāo)類似，導(dǎo)致數(shù)據(jù)與我方之間的差異不明顯，這時會導(dǎo)致出現(xiàn)某些數(shù)據(jù)與我方目標(biāo)某些數(shù)據(jù)距離較近，導(dǎo)致分類效果不佳[8]。以敵方目標(biāo)B為例來進行說明。圖5給出所有樣本點與第5個樣本點的距離，圖中前20個為我方目標(biāo)數(shù)據(jù)，其余為敵方目標(biāo)B 的數(shù)據(jù)，可以看到第21和29個樣本點距離第1個樣本點很近。所以無論如何選取鄰域半徑都無法得到較好的聚類結(jié)果。

圖5 敵方目標(biāo)B樣本點距離比較結(jié)果

而采用基于Mean Shift的改進聚類算法，本質(zhì)上是通過比較樣本數(shù)據(jù)與密度中心點的距離，可以有效地處理這種情況，聚類結(jié)果如圖6所示。

從圖2和圖6可以看到，基于Mean Shift的改進聚類算法，能夠有效處理離群點問題，避免其對聚類造成不利影響，同時診斷出離群點，方便對離群點的干擾信息進行分析。

圖6 基于Mean Shift算法的敵方目標(biāo)B聚類結(jié)果

通過選取訓(xùn)練數(shù)據(jù)進行基于Mean Shift聚類建模，可以得到敵方目標(biāo)A、敵方目標(biāo)B、敵方目標(biāo)C的模型庫，再選取各類測試數(shù)據(jù)進行測試，目標(biāo)識別結(jié)果如表1所示。

表1 多目標(biāo)識別結(jié)果分析

3 結(jié)束語

本文針對目標(biāo)識別系統(tǒng)的多目標(biāo)識別問題，提出了一種基于Mean Shift原理的改進聚類算法，能夠?qū)δ繕?biāo)進行良好的聚類，同時診斷出離群點，避免離群數(shù)據(jù)對聚類效果的不利影響，相比于傳統(tǒng)的Kmeans和DBSCAN，具有更好的聚類效果。并且通過對比分析密度中心點，得到不同目標(biāo)的模型向量，在在線識別時，通過聚類得到的模型向量進行匹配，能夠準(zhǔn)確地進行在線的多目標(biāo)識別。