近鄰數(shù)據(jù)分類(lèi)器在多目標(biāo)跟蹤中的應(yīng)用研究

韓春雷，蔚 婧

(1.中國(guó)電子科技集團(tuán)公司第二十研究所，陜西 西安 710068；2.西北工業(yè)大學(xué) 航海學(xué)院，陜西 西安 710072)

在分布式的多傳感器多目標(biāo)探測(cè)系統(tǒng)中，一個(gè)關(guān)鍵問(wèn)題是如何判斷探測(cè)到的數(shù)據(jù)來(lái)自哪個(gè)目標(biāo)，它實(shí)際上是要確定空間傳感器探測(cè)到的信號(hào)與不同目標(biāo)之間的對(duì)應(yīng)關(guān)系[1-5]。

多目標(biāo)探測(cè)在智能監(jiān)控、視頻檢索、導(dǎo)航、定位等多個(gè)領(lǐng)域都有重要的應(yīng)用，只有將探測(cè)到的目標(biāo)進(jìn)行正確分類(lèi)，后續(xù)的目標(biāo)特性提取、參數(shù)估計(jì)等后續(xù)處理工作才有價(jià)值。然而，在多目標(biāo)、干擾、交叉航跡等場(chǎng)合下，由于運(yùn)動(dòng)場(chǎng)景及目標(biāo)數(shù)目的不確定性，多目標(biāo)分類(lèi)問(wèn)題往往變得十分困難[6-8]。因此，針對(duì)多目標(biāo)的快速、高效分類(lèi)方法值得科研人員進(jìn)行更進(jìn)一步的研究。

現(xiàn)有的目標(biāo)分類(lèi)方法，主要?jiǎng)澐譃閮深?lèi)：基于概率密度的方法和基于判別函數(shù)的方法?；诟怕拭芏鹊姆椒ㄖ饕柚谪惾~斯理論體系，采用潛在的類(lèi)條件概率密度函數(shù)的知識(shí)進(jìn)行分類(lèi)；基于判別函數(shù)的方法使用訓(xùn)練數(shù)據(jù)估計(jì)分類(lèi)的邊界來(lái)完成分類(lèi)[9-12]。目前被證實(shí)有效的分類(lèi)算法有近鄰分類(lèi)器、樸素貝葉斯分類(lèi)器、支持向量機(jī)、決策樹(shù)算法等。其中近鄰數(shù)據(jù)分類(lèi)器計(jì)算量小，便于實(shí)現(xiàn)，在實(shí)際工程中廣泛采用。

1 近鄰分類(lèi)算法

近鄰法是距離度量學(xué)習(xí)方法中的一種，其在對(duì)樣本進(jìn)行分類(lèi)時(shí)，是根據(jù)查詢(xún)樣本最近的k個(gè)近鄰的標(biāo)簽來(lái)將其分類(lèi)[13]。因此近鄰法又被稱(chēng)為k近鄰法。當(dāng)k=1時(shí)，稱(chēng)最近鄰法。

近鄰法由Cover和Hart提出，具體思路是：對(duì)于一個(gè)待識(shí)別目標(biāo)，系統(tǒng)在訓(xùn)練集中找到最近的k個(gè)近鄰，看這k個(gè)近鄰中的多數(shù)屬于哪一類(lèi)，就把待識(shí)別的目標(biāo)歸為哪一類(lèi)。

其數(shù)學(xué)表達(dá)為：設(shè)有n個(gè)樣本{(x1,y1),(x2,y2),…,(xn,yn)}和一個(gè)待分類(lèi)樣本x0。k近鄰法對(duì)樣本進(jìn)行分類(lèi)時(shí)，首先要計(jì)算x0與每個(gè)樣本的距離，然后找出距x0最近的k個(gè)樣本，即k個(gè)近鄰。設(shè)共有C個(gè)類(lèi)別{w1,w2,L,wc}，w1，w2，L，wc是k個(gè)近鄰中屬于類(lèi)別{w1,w2,L,wc}的個(gè)數(shù)，則判別函數(shù)可寫(xiě)為

gi(x)=mi,i=1,2,…,c

(1)

決策函數(shù)為

(2)

則x0=wj，即x0歸入wj類(lèi)。

圖1 k近鄰法示意圖

如圖1所示，圓圈代表待分類(lèi)樣本，方塊和三角形分別為兩類(lèi)已經(jīng)分類(lèi)的樣本。根據(jù)近鄰方法的思想 ，當(dāng)k=3時(shí)，有2個(gè)樣本屬于三角形，1個(gè)樣本歸于方塊，則圓圈歸類(lèi)到三角型類(lèi)。當(dāng)k=5時(shí)，有2個(gè)樣本屬于三角形，3個(gè)樣本屬于方塊，則圓圈歸到方塊類(lèi)。

可見(jiàn)，近鄰法當(dāng)選取的k值不同時(shí)，會(huì)有不同的分類(lèi)結(jié)果，由此造成分類(lèi)算法的不穩(wěn)定性。

2 基于質(zhì)心分布的近鄰分類(lèi)算法

定義質(zhì)心為待分類(lèi)樣本與最近的m個(gè)已分類(lèi)樣本的距離均值

(3)

在原始的k近鄰法中，針對(duì)一個(gè)待分類(lèi)樣本可能存在多個(gè)k值都能將其正確分類(lèi)，這時(shí)普遍采用的方法是隨機(jī)取一個(gè)最小的k值將其分類(lèi)。但這樣隨機(jī)的選擇會(huì)使分類(lèi)存在較大波動(dòng)，不利于正確分類(lèi)。

式(3)所定義的質(zhì)心，實(shí)質(zhì)上是k個(gè)近鄰樣本距待測(cè)樣本距離的均值。此時(shí)，如果待測(cè)樣本越靠近近鄰樣本的中心，則對(duì)待分類(lèi)樣本的分類(lèi)預(yù)測(cè)會(huì)越準(zhǔn)確。

將質(zhì)心的概念引入之后，改進(jìn)的近鄰法的實(shí)現(xiàn)方法為：用待分類(lèi)樣本與質(zhì)心的距離來(lái)代替待分類(lèi)樣本與訓(xùn)練樣本之間的距離。這一做法實(shí)質(zhì)是將k個(gè)近鄰樣本之間的距離變小，而拉大了類(lèi)間的距離，這一改近更有利于正確分類(lèi)。

實(shí)現(xiàn)步驟：

(1) 設(shè)定參數(shù)k；

(2) 計(jì)算待分類(lèi)樣本x0與所有已分類(lèi)樣本的距離di；

(3) 選取k個(gè)最短距離d1，d2，L，dk，確定k個(gè)最短距離樣本所在的類(lèi)別{w1,w2,L,wc}；

(4) 計(jì)算在每個(gè)類(lèi)別wi中，樣本的質(zhì)心dwi；

3 分布式多目標(biāo)跟蹤系統(tǒng)

由于近年來(lái)傳感器網(wǎng)絡(luò)的廣泛應(yīng)用，分布式目標(biāo)跟蹤系統(tǒng)在目標(biāo)跟蹤領(lǐng)域成為主要的研究對(duì)象。分布式目標(biāo)跟蹤系統(tǒng)由多個(gè)分布在一定距離范圍的傳感器對(duì)同一區(qū)域進(jìn)行觀(guān)測(cè)，對(duì)觀(guān)測(cè)到的目標(biāo)進(jìn)行聯(lián)合跟蹤[14-16]。

圖2 分布式多目標(biāo)跟蹤系統(tǒng)示意圖

如圖2所示，為典型的分布式多目標(biāo)跟蹤系統(tǒng)示意圖，其中有3個(gè)觀(guān)測(cè)站對(duì)兩個(gè)目標(biāo)進(jìn)行觀(guān)測(cè)。以直角坐標(biāo)系，勻速運(yùn)動(dòng)目標(biāo)1為例來(lái)分析分布式多目標(biāo)跟蹤系統(tǒng)的數(shù)學(xué)模型。系統(tǒng)的動(dòng)態(tài)模型可以描述為

X(k)=F(k,k-1)X(k-1)+W(k)

(4)

(5)

其為系統(tǒng)的轉(zhuǎn)移矩陣，Ts代表采樣周期。

假設(shè)觀(guān)測(cè)站位于坐標(biāo)(0,0)處，觀(guān)測(cè)量為目標(biāo)斜距和目標(biāo)方位角，系統(tǒng)的觀(guān)測(cè)模型可以描述為

(6)

其中N(k)為高斯白噪聲序列，并滿(mǎn)足E[N(k)]=0，E[v(k),v(j)]=σ2δkj。

k時(shí)刻，量測(cè)集合可以表示為Z(k)=[z1(k),L,zm(k)]，其中m表示觀(guān)測(cè)站的數(shù)目。而針對(duì)每個(gè)觀(guān)測(cè)站，量測(cè)集合中也是包含了多個(gè)目標(biāo)的量測(cè)數(shù)據(jù)。

目標(biāo)跟蹤的目的是要根據(jù)當(dāng)前時(shí)刻對(duì)目標(biāo)的觀(guān)測(cè)，估計(jì)出目標(biāo)的運(yùn)動(dòng)狀態(tài)，進(jìn)而對(duì)下一時(shí)刻目標(biāo)的位置、速度等信息進(jìn)行預(yù)測(cè)。因此，首先要對(duì)各觀(guān)測(cè)站的觀(guān)測(cè)數(shù)據(jù)按不同目標(biāo)進(jìn)行分類(lèi)，分類(lèi)的準(zhǔn)確性直接影響后續(xù)目標(biāo)跟蹤及航跡預(yù)測(cè)，所以具有相當(dāng)重要的意義。

4 應(yīng)用與分析

基于質(zhì)心分布的近鄰分類(lèi)算法應(yīng)用于分布式多目標(biāo)跟蹤系統(tǒng)，驗(yàn)證其分類(lèi)有效性。

4.1 數(shù)據(jù)分類(lèi)實(shí)驗(yàn)

為證明本文提出的基于質(zhì)心分布的近鄰分類(lèi)算法的有效性， 對(duì)如圖3所示的3類(lèi)樣本進(jìn)行分類(lèi)實(shí)驗(yàn)，圖中的3類(lèi)樣本分別用圓圈、星號(hào)、方塊表示。

圖3 3類(lèi)樣本示意圖

用近鄰分類(lèi)算法對(duì)圖3的樣本分類(lèi)結(jié)果如圖4所示，分到同一類(lèi)的樣本用直線(xiàn)相連接，從圖4所示，共有27個(gè)樣本，其中23個(gè)樣本分類(lèi)正確，4個(gè)樣本分類(lèi)錯(cuò)誤，分類(lèi)正確率為85%。

圖4 近鄰分類(lèi)算法分類(lèi)結(jié)果

用本文提出的基于質(zhì)心分布的近鄰分類(lèi)算法分類(lèi)結(jié)果如圖5所示，同樣將分到同一類(lèi)的樣本用直線(xiàn)連接，27個(gè)樣本全部分類(lèi)正確，分類(lèi)正確率達(dá)100%。由此可見(jiàn)，本文所提出的改進(jìn)算法具有良好的分類(lèi)特性。

圖5 基于質(zhì)心分布的近鄰分類(lèi)算法

4.2 多目標(biāo)跟蹤實(shí)驗(yàn)

實(shí)驗(yàn)參數(shù)：觀(guān)測(cè)站數(shù)目2，目標(biāo)數(shù)據(jù)3，采樣間隔1 s，角度觀(guān)測(cè)方差1°，距離觀(guān)測(cè)方差10 m，3個(gè)目標(biāo)做勻速直線(xiàn)運(yùn)動(dòng)，速度分別為20 m/s，15 m/s，20 m/s。

圖6 多目標(biāo)分類(lèi)示意圖

如圖6所示，虛線(xiàn)表示目標(biāo)的實(shí)際運(yùn)動(dòng)軌跡，星號(hào)表示觀(guān)測(cè)到的目標(biāo)樣本，由于在觀(guān)測(cè)環(huán)境中存在3個(gè)運(yùn)動(dòng)目標(biāo)，所以將運(yùn)用基于質(zhì)心分布的目標(biāo)分類(lèi)方法分類(lèi)后的目標(biāo)用帶圈實(shí)線(xiàn)連接起來(lái)，如圖所示，本文方法能夠較好地區(qū)分3類(lèi)目標(biāo)，即使在目標(biāo)距離比較近的情況下也能很好的區(qū)分，再一次驗(yàn)證了算法的有效性。

5 結(jié)束語(yǔ)

本文針對(duì)近鄰數(shù)據(jù)分類(lèi)器進(jìn)行了深入研究，對(duì)其分類(lèi)不穩(wěn)定性進(jìn)行了分析，并提出了改進(jìn)的基于質(zhì)心分布的近鄰數(shù)據(jù)分類(lèi)方法。該方法用待分類(lèi)樣本與質(zhì)心的距離來(lái)代替待分類(lèi)樣本與訓(xùn)練樣本之間的距離，從根本上減小了樣本間距離，增大了類(lèi)間距離，提高了分類(lèi)正確率。然后，將提出的改進(jìn)分類(lèi)算法應(yīng)用于分布式多目標(biāo)跟蹤中，將同一個(gè)觀(guān)測(cè)站對(duì)不同目標(biāo)的觀(guān)測(cè)數(shù)據(jù)進(jìn)行分類(lèi)，提高了后續(xù)跟蹤處理結(jié)果的可靠性。計(jì)算機(jī)仿真分析驗(yàn)證了所提方法的有效性，同時(shí)表明該分類(lèi)方法在多目標(biāo)跟蹤系統(tǒng)中具有一定的應(yīng)用價(jià)值。

[1] Hlinka O,Hlawatsch F,Djuric P M.Distributed particle filtering in agent networks:A survey, classification, and comparison[J].IEEE Signal Processing Magazine,2013,30(1):61-81.

[2] Olfati-Saber R,Jalalkamali P.Coupled distributed estimation and control for mobile sensor networks[J]. IEEE Transactions on Automatic Control,2012,57(10):2609-2614.

[3] Wenling L,Yingmin J.Consensus-based distributed multiple model UKF for jump Markov nonlinear systems[J].IEEE Transactions on Automatic Control,2012,7(1):227-233.

[4] Dimakis A G,Kar S,Moura J M F,et al.Gossip algorithms for distributed signal processing[J].Proceedings of the IEEE,2010,98(11):1847-1864.

[5] 方德亮,冉曉旻,李鷗.一種能量有效的分布式傳感器管理算法[J].西安電子科技大學(xué)學(xué)報(bào),2017,44(2):171-177.

[6] 司錫才,陳玉坤,李志剛.數(shù)據(jù)關(guān)聯(lián)算法的研究[J].哈爾濱工程大學(xué)學(xué)報(bào),2007,28(7):813-817.

[7] 陳曉,李亞安,蔚婧.一種海雜波背景下的目標(biāo)跟蹤數(shù)據(jù)關(guān)聯(lián)方法[J].魚(yú)雷技術(shù),2016,24(5):334-339.

[8] Boumediene M, Ouamri A, Dahnoun N. Lane boundary detection and tracking using NNF and HMM approaches[C].Istanbul:2007 IEEE Intelligent Vehicles Symposium,2007.

[9] 曹作寶,包曉敏,汪亞明,等.基于Kalman預(yù)測(cè)和K-近鄰的多目標(biāo)跟蹤[J].浙江理工大學(xué)學(xué)報(bào),2011,28(3):384-388.

[10] Liu Qingfeng,Liu Chengjun.A novel locally linear KNN method with applications to visual recognition[J].IEEE Transactions on Neural Networks and Learning Systems, 2017,28(9):2010-2021.

[11] Mao Rui,Xiang Peng,Zhang Dian.Precise transceiver-free localization in complex indoor environment[J].China Communications,2016,13(5): 28-37.

[12] 張慶久.近鄰法與多視角學(xué)習(xí)的理論與算法研究[D].上海:華東師范大學(xué),2011.

[13] Liu Xianglong,Li Zhujin,Deng Cheng,et al.Distributed adaptive binary quantization for fast nearest neighbor search[J].IEEE Transactions on Image Processing,2017,26(11):5324-5336.

[14] Cai He,Hu Guoqiang.Distributed tracking control of an interconnected leader-follower multiagent system[J].IEEE Transactions on Automatic Control,2017,62(7): 3494-3501.

[15] Wen Guanghui,Yu Wenwu,Xia Yuanqing,et al.Distributed tracking of nonlinear multiagent systems under directed switching topology: an observer-based protocol[J].IEEE Transactions on Systems, Man and Cybernetics: Systems, 2017,47(5):869-881.

[16] 付強(qiáng),王剛,郭相科,等.臨空高速目標(biāo)協(xié)同探測(cè)跟蹤需求分析[J].系統(tǒng)工程與電子技術(shù), 2015,37(4):757-762.