基于模糊ART劃分的目標(biāo)分群算法

樊振華，師本慧，陳金勇，段同樂，王長力

(1.中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081； 2.中國人民解放軍91635部隊，北京 102249)

基于模糊ART劃分的目標(biāo)分群算法

樊振華1，師本慧1，陳金勇1，段同樂1，王長力2

(1.中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081； 2.中國人民解放軍91635部隊，北京 102249)

針對目標(biāo)分群中存在的分類數(shù)未知和噪聲干擾問題，提出一種基于模糊ART劃分的目標(biāo)分群算法。通過目標(biāo)識別屬性劃分，約減分群目標(biāo)數(shù)規(guī)模，降低計算量；通過劃分?jǐn)?shù)據(jù)預(yù)處理消除尺度差異，在此基礎(chǔ)上采用基于模糊ART的目標(biāo)空間劃分，經(jīng)類選擇、匹配度檢驗和類學(xué)習(xí)等步驟實現(xiàn)對目標(biāo)的增量式動態(tài)分群。試驗結(jié)果表明，該算法對復(fù)雜環(huán)境下未知分類數(shù)的多目標(biāo)編隊分群具有良好的有效性、穩(wěn)健性和實時性。

目標(biāo)分群；空間劃分；模糊ART；屬性劃分

0 引言

態(tài)勢顯示是指揮員對實時情況把控的有效信息獲取途徑，為制定方案與決策提供基礎(chǔ)和支撐[1]。通常，目標(biāo)在執(zhí)行任務(wù)的過程中是以編隊的形式完成巡航、撤退等具體行動。如果仍將每個目標(biāo)看作孤立的個體，顯然存在信息冗余，而且密布的目標(biāo)標(biāo)識還會造成信息炫目問題，使指揮員無法快速直接地了解態(tài)勢概況，做出高效的指揮決策[2]。因此，需要將識別屬性和運(yùn)動參數(shù)等特征相近的目標(biāo)聚合歸類，劃分為若干個群目標(biāo)，與其實際執(zhí)行任務(wù)的編隊相對應(yīng)[3]。這樣，一方面可以簡化態(tài)勢顯示，利于指揮員迅速掌控全局[4]；另一方面，目標(biāo)分群后的結(jié)果能夠更為直接地體現(xiàn)其任務(wù)編隊的本質(zhì)，從海量信息中挖掘出行動意圖，為后續(xù)的態(tài)勢分析奠定基礎(chǔ)。

目標(biāo)分群[5]實質(zhì)上是一個數(shù)據(jù)聚類問題，將特征空間中分布相近的目標(biāo)聚合為一類。按照分類數(shù)是否需要預(yù)先設(shè)定，聚類方法通常可以分為：類數(shù)已知算法和類數(shù)未知算法。其中，類數(shù)已知算法中典型的方法有模糊C均值算法[6]和K均值算法[7]。該類算法存在的缺陷[8]：一方面，需要預(yù)設(shè)分類數(shù)與通常面臨分類數(shù)未知的情況不匹配[9]；另一方面，其分類結(jié)果對初始分類中心選取的依賴性較強(qiáng)，進(jìn)而造成分類結(jié)果穩(wěn)定性欠佳[10]。類數(shù)未知算法[11]中典型的方法有最近鄰算法[12]和ISODATA算法[13]。最近鄰算法通過設(shè)定閾值實現(xiàn)分群，簡單易實現(xiàn)且應(yīng)用廣泛，但缺乏有效的閾值選取方法[14]，難以有效處理不同量測尺度或情況的分群問題。ISODATA算法通過對聚類結(jié)果的合并和分裂操作實現(xiàn)類數(shù)未知情況下的動態(tài)分群，但其以樣本與聚類中心的距離作為分群依據(jù)，適合于解決球狀簇樣本分群問題，而對于常見的線型編隊分群問題存在不足[15]。

針對上述問題，本文首先通過目標(biāo)識別屬性劃分，約減參與分群目標(biāo)數(shù)的規(guī)模，從而提高計算效率；其次通過劃分?jǐn)?shù)據(jù)預(yù)處理消除尺度差異，采用基于模糊ART[16]的目標(biāo)空間劃分，經(jīng)類選擇、匹配度檢驗和類學(xué)習(xí)等步驟實現(xiàn)對目標(biāo)的增量式動態(tài)劃分，能夠在噪聲干擾下有效處理分類數(shù)未知的多編隊分群問題。

1 目標(biāo)識別屬性劃分

目標(biāo)分群主要是針對目標(biāo)位置量測和識別屬性進(jìn)行劃分。由于位置量測連續(xù)無限性和識別屬性的離散有限性，二者的劃分計算復(fù)雜度差異較大。其中，目標(biāo)識別屬性劃分計算復(fù)雜度低，而目標(biāo)空間劃分的計算復(fù)雜度則較高。因此，本文擬先進(jìn)行目標(biāo)識別屬性劃分，后進(jìn)行目標(biāo)空間劃分。這樣可以將目標(biāo)集整體的空間劃分問題分解為多個目標(biāo)子集的空間劃分問題，有效約減參與空間劃分的目標(biāo)數(shù)規(guī)模，從而降低計算量。

i=1,2,j=1,2,…,C。

(1)

式中，i為紅/藍(lán)方標(biāo)號；j為類別標(biāo)號；C為類別總數(shù)。在此基礎(chǔ)上，分別對每個紅/藍(lán)方各類目標(biāo)集Pij進(jìn)行空間劃分。

2 基于模糊ART的目標(biāo)空間劃分

自適應(yīng)諧振理論(AdaptiveResonanceTheory，ART)[16]通過模擬人類認(rèn)知信息的處理過程，構(gòu)建實時神經(jīng)網(wǎng)絡(luò)，從而實現(xiàn)無監(jiān)督的分類學(xué)習(xí)和模式認(rèn)知。ART衍生出一系列實時神經(jīng)網(wǎng)絡(luò)模型，其中具有代表性的模糊ART就是通過引入模糊集理論所形成的實時神經(jīng)網(wǎng)絡(luò)模型[17]。模糊ART劃分算法流程，如圖1所示。

圖1 模糊ART劃分算法流程

2.1 劃分?jǐn)?shù)據(jù)預(yù)處理

由于待劃分?jǐn)?shù)據(jù)的尺度及L1范數(shù)存在差異，為了保證后續(xù)處理的一致性和類學(xué)習(xí)的穩(wěn)定性，需要對待劃分?jǐn)?shù)據(jù)進(jìn)行量測歸一化和補(bǔ)充編碼。

其次，對L′進(jìn)行補(bǔ)充編碼，得到輸入向量

(2)

2.2 類選擇

每個類對應(yīng)一個權(quán)重向量wj=(wj1,wj2,…,wjd)，j=1,2,…,N，N為當(dāng)前類數(shù)，d為分類特征為數(shù)，此處d=4。wj為所有屬于該類樣本的最大模糊子集，是這些樣本所具有的共性的體現(xiàn)，因此用wj來表征該類。對于輸入向量I和權(quán)重向量wj，定義類選擇函數(shù)

(3)

(4)

2.3 匹配度檢驗

計算輸入向量I和權(quán)重向量wJ的匹配度函數(shù)

(5)

2.4 類學(xué)習(xí)

為了保證權(quán)重向量能夠有效反應(yīng)所屬類的所有樣本的共性，需要通過類學(xué)習(xí)，將新劃入該類的樣本融合到權(quán)重向量當(dāng)中，

(6)

3 仿真實驗與分析

本文實驗環(huán)境為IntelCorei3-2130 3.4GHzCPU，2GB內(nèi)存，Windows7操作系統(tǒng)，MatlabR2011a仿真實驗平臺。首先，比較和分析模糊ART劃分、模糊C均值[18]、K均值[7]和ISODATA[13]這4種算法在近距離場景下對典型多編隊群目標(biāo)進(jìn)行空間分群的性能；其次，將基于模糊ART的目標(biāo)空間劃分與目標(biāo)識別屬性劃分結(jié)合，并應(yīng)用于動態(tài)目標(biāo)分群當(dāng)中，從而進(jìn)一步驗證其在過程噪聲和觀測噪聲疊加干擾下的適用性和穩(wěn)定性。

3.1 近距離多編隊空間分群實驗

目標(biāo)空間分群實驗結(jié)果如圖2所示。在圖2中有2組目標(biāo)編隊，分別呈三角形(左側(cè))和線形(右側(cè))。由圖2可以看出，模糊ART劃分、模糊C均值和K均值均可得到較為理想的空間分群結(jié)果。然而，模糊C均值和K均值的分類數(shù)均需預(yù)設(shè)為真實值2，且分類數(shù)預(yù)設(shè)值直接影響分類結(jié)果的正確性，當(dāng)分類數(shù)設(shè)定錯誤時必然得到錯誤的分群結(jié)果，因而難以滿足實際中分類數(shù)未知情況的分群需求；而模糊ART劃分則無需預(yù)設(shè)分類數(shù)，且能夠得到正確的分群結(jié)果；ISODATA算法雖然也無需預(yù)設(shè)分類數(shù)，但其以樣本與聚類中心的距離作為分群依據(jù)，不適合解決線型編隊的分群問題，尤其當(dāng)線型編隊內(nèi)目標(biāo)最大間距與編隊間最小距離接近時，該算法的參數(shù)設(shè)置尤為困難，難以獲得理想的分群結(jié)果。

圖2 多編隊空間分群結(jié)果比較

在此基礎(chǔ)上，對上述分群場景進(jìn)行1 000次運(yùn)行，統(tǒng)計平均得到各種算法的運(yùn)行時間，如表1所示。可以看出，后3種算法均需要通過迭代計算實現(xiàn)分群，較為耗時；而模糊ART劃分結(jié)合自適應(yīng)諧振理論與模糊集理論，可以實現(xiàn)增量式動態(tài)分群，直接得到分群結(jié)果，運(yùn)行效率更高。

表1 目標(biāo)空間分群算法運(yùn)行時間比較

綜上所述，本文提出的基于模糊ART劃分的目標(biāo)空間分群算法能夠有效并快速處理分類數(shù)未知的多編隊空間分群問題，即使在編隊間距較小的復(fù)雜場景下，仍然可以獲得較好的分群結(jié)果。

3.2 動態(tài)目標(biāo)分群實驗

對靜態(tài)的近距離多編隊空間分群進(jìn)行了討論和分析，然而實際應(yīng)用中的目標(biāo)分群還需要進(jìn)行目標(biāo)識別屬性劃分，是一個更為復(fù)雜的連續(xù)動態(tài)目標(biāo)分群問題。其中，考慮到目標(biāo)受地形、氣流、自身操控和觀測誤差等影響，存在過程噪聲與觀測噪聲，這使得觀測到的編隊內(nèi)目標(biāo)間距也持續(xù)動態(tài)變化，給準(zhǔn)確分群增加了難度。

多編隊群目標(biāo)運(yùn)動軌跡如圖3所示，虛線矩形框為便于觀察實驗結(jié)果的局部區(qū)域，局部區(qū)域旁邊的字母A和字母B為局部區(qū)域所對應(yīng)的編號，黑色六角形為各群目標(biāo)觀測起始位置，各群目標(biāo)編隊情況如表2所示。仿真場景中，目標(biāo)運(yùn)動的過程噪聲標(biāo)準(zhǔn)差為1 000 m，觀測噪聲標(biāo)準(zhǔn)差為50 m。圖3所描繪的態(tài)勢情況為藍(lán)方飛機(jī)與車輛多編隊向紅方車輛編隊快速行進(jìn)，遭遇紅方飛機(jī)編隊攔截后撤退。針對上述場景，將目標(biāo)識別屬性劃分與基于模糊ART的目標(biāo)空間劃分結(jié)合，實現(xiàn)目標(biāo)分群，結(jié)果如圖3、圖4和圖5所示。

圖3 多編隊群目標(biāo)運(yùn)動軌跡及全局分群結(jié)果

圖4 局部區(qū)域A目標(biāo)分群結(jié)果

圖5 局部區(qū)域B目標(biāo)分群結(jié)果

圖4和圖5為局部放大結(jié)果。圖3、圖4和圖5中，黑點表示各目標(biāo)的位置量測，實線矩形框范圍內(nèi)的多個目標(biāo)被劃分屬于同一群目標(biāo)，各群目標(biāo)運(yùn)動軌跡旁邊的數(shù)字為群目標(biāo)所對應(yīng)的編號。可以看出，雖然受噪聲的影響，觀測得到的編隊內(nèi)目標(biāo)間距持續(xù)變化，但是本文算法能夠?qū)崿F(xiàn)增量式高效的動態(tài)分群，有效處理分類數(shù)未知的多編隊分群問題。

在此基礎(chǔ)上，對上述分群場景進(jìn)行1 000次運(yùn)行，統(tǒng)計平均得到本文算法的運(yùn)行時間為0.003 9 s。本文算法一方面通過目標(biāo)識別屬性劃分，將29個目標(biāo)的分群問題拆分成目標(biāo)數(shù)分別為7、8、8和6的4個目標(biāo)子集的分群問題，有效約減了參與空間劃分的目標(biāo)數(shù)規(guī)模；另一方面，通過模糊ART劃分實現(xiàn)增量式的目標(biāo)分群，也有效提高了算法運(yùn)行效率。

表2 各群目標(biāo)編隊情況

4 結(jié)束語

針對態(tài)勢顯示的精煉簡化需求，本文提出一種基于模糊ART劃分的目標(biāo)分群算法，并通過仿真實驗檢驗了所提算法的性能。一方面，驗證了所提算法在近距離場景下對典型多編隊群目標(biāo)進(jìn)行空間分群的性能明顯優(yōu)于傳統(tǒng)算法(模糊C均值、K均值和ISODATA)；另一方面，驗證了所提算法對于復(fù)雜環(huán)境動態(tài)多編隊目標(biāo)分群，能夠?qū)崿F(xiàn)增量式的高效處理，有效解決了目標(biāo)分群中存在的分類數(shù)未知和噪聲干擾問題。

目標(biāo)分群結(jié)果能夠有效地體現(xiàn)其任務(wù)編隊的本質(zhì)，不僅簡化了態(tài)勢顯示，而且為后續(xù)的威脅估計與意圖分析提供了技術(shù)支撐。更高層次的態(tài)勢分析需要以此為基礎(chǔ)，做更深入的研究。

[1] 田聚波.面向圖形作業(yè)的協(xié)同指揮系統(tǒng)設(shè)計與實現(xiàn)[J].無線電通信技術(shù),2016,42(2):92-95.

[2] 洪旭,柳虔林,丁洪偉,等.應(yīng)急機(jī)動指揮通信能力評估分析[J].無線電通信技術(shù),2015,41(4):20-23.

[3] 段同樂,張冬寧.二叉樹多分類SVM在目標(biāo)分群中的應(yīng)用[J].無線電工程,2015,45(6):88-91.

[4] 梁健,陳晧暉.基于全分布式處理的統(tǒng)一態(tài)勢生成技術(shù)研究[J].無線電工程,2016,46(1):12-15.

[5] 艾偉,張冬寧.一種基于分群矩陣的目標(biāo)動態(tài)分群算法[J].無線電工程,2015,45(11):64-68.

[6] CANNON R L,DAVE J V,BEZDEK J C.Efficient Implementation of the Fuzzy C-means Clustering Algorithms[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1986(2):248-255.

[7] KANUNGO T,MOUNT D M,NETANYAHU N S,et al.An Efficient K-means Clustering Algorithm:Analysis and Implementation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(7):881-892.

[8] 肖滿生,肖哲,文志強(qiáng),等.模糊C均值聚類區(qū)間型模糊化參數(shù)模型[J].系統(tǒng)工程與電子技術(shù),2015,37(4):868-873.

[9] CARVALHO M J,MELO-GON?ALVES P,TEIXEIRA J C,et al.Regionalization of Europe Based on a K-means Cluster Analysis of the Climate Change of Temperatures and Precipitation[J].Physics and Chemistry of the Earth,Parts A/B/C,2016,94(8):22-28.

[10] KUNCHEVA L I,VETROV D P.Evaluation of Stability of K-means Cluster Ensembles with Respect to Random Initialization[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(11):1 798-1 808.

[11] 張琨,王翠榮.一種自適應(yīng)分裂與合并的運(yùn)動目標(biāo)聚類分割算法[J].電子與信息學(xué)報,2014,36(3):601-609.

[12] ERTOZ L,STEINBACH M,KUMAR V.A New Shared Nearest Neighbor Clustering Algorithm and Its Applications[C]∥ Workshop on Clustering High Dimensional Data and Its Applications at 2nd SIAM International Conference on Data Mining,2002:105-115.

[13] MEMARSADEGHI N,MOUNT D M,NETANYAHU N S,et al.A Fast Implementation of the ISODATA Clustering Algorithm[J].International Journal of Computational Geometry & Applications,2007,17(1):71-103.

[14] BEYER K,GOLDSTEIN J,RAMAKRISHNAN R,et al.When is “Nearest Neighbor” Meaningful?[C]∥ International Conference on Database Theory,1999:217-235.

[15] 王曉璇.陸戰(zhàn)場裝甲目標(biāo)聚合算法研究[D].南京：南京理工大學(xué)，2007.

[16] CARPENTER G A,GROSSBERG S,ROSEN D B.Fuzzy ART:Fast Stable Learning and Categorization of Analog Patterns By an Adaptive Resonance System[J].Neural Networks,1991,4(6):759-771.

[18] BEZDEK J C,EHRLICH R,FULL W.FCM:The Fuzzy C-means Clustering Algorithm[J].Computers & Geosciences,1984,10(2-3):191-203.

A Fuzzy ART Based Target Clustering Algorithm

FAN Zhen-hua1,SHI Ben-hui1,CHEN Jin-yong1,DUAN Tong-le1,WANG Chang-li2

(1.The54thResearchInstituteofCETC,ShijiazhuangHebei050081,China; 2.Unit91635,PLA,Beijing102249,China)

Target clustering is confronted with problems of unknown category number and noise interference.To solve these problems,a fuzzy ART based target clustering algorithm is proposed.In this algorithm,the clustering target number is reduced through attribute partition to lessen the computational burden.Through data preprocessing,the scale difference is eliminated.On this basis,target space partition based on fuzzy ART is adopted,incremental dynamic clustering of targets is achieved through category choice,resonance and learning.Experimental results show the effectiveness,stability and real-time performance of the proposed algorithm in multi-formation clustering with unknown category number in complicated environment.

target clustering;space partition;fuzzy adaptive resonance theory;attribute partition

10.3969/j.issn.1003-3106.2017.09.06

樊振華,師本慧,陳金勇,等.基于模糊ART劃分的目標(biāo)分群算法[J].無線電工程,2017,47(9):27-31.[FAN Zhenhua,SHI Benhui,CHEN Jinyong,et al.A Fuzzy ART Based Target Clustering Algorithm[J].Radio Engineering,2017,47(9):27-31.]

TP391

A

1003-3106(2017)09-0027-05

2016-11-16

海洋公益性科研專項基金資助項目(201505002)。

樊振華 男，(1985—)，博士，工程師。主要研究方向：態(tài)勢估計、目標(biāo)分群、計算機(jī)視覺。

師本慧 男，(1965—)，研究員。主要研究方向：指揮控制、態(tài)勢估計、航天地面應(yīng)用和測控。