一種基于多重距離聚類的多源偵察結(jié)果融合算法

徐　英

(中國人民解放軍電子工程學(xué)院 304教研室，合肥　230037)

?

【信息科學(xué)與控制工程】

一種基于多重距離聚類的多源偵察結(jié)果融合算法

徐英

(中國人民解放軍電子工程學(xué)院 304教研室，合肥230037)

由于來自不同傳感器的偵察圖像獲取和傳輸?shù)姆菍?shí)時(shí)性以及圖像情報(bào)分析結(jié)果的非連續(xù)性，反偵察監(jiān)視裁決需要對來自不同傳感器的偵察結(jié)果進(jìn)行空間和屬性綜合聚類，合并屬于同一目標(biāo)的偵察結(jié)果。考慮空間位置和多個非空間屬性的相似性，提出了基于空間和屬性多重距離的空間聚類算法MDBSC(Multiple Distance Based Spatial Clustering)，用于多源偵察結(jié)果的關(guān)聯(lián)融合，給出了算法步驟和實(shí)例。

多重距離; 空間聚類; 多源融合; 關(guān)聯(lián)融合

復(fù)雜電磁環(huán)境下的作戰(zhàn)訓(xùn)練向電磁對抗和體系對抗延伸[1]，開展復(fù)雜電磁環(huán)境下的對抗演習(xí)和對抗裁決是信息化條件下戰(zhàn)斗力生成和提高的重要保證，反偵察監(jiān)視裁決是進(jìn)行對抗裁決的重要組成部分。反偵察監(jiān)視裁決利用專門設(shè)備模擬主要作戰(zhàn)對手的偵察衛(wèi)星和無人機(jī)的偵察監(jiān)視行動，對受訓(xùn)部隊(duì)重要目標(biāo)和作戰(zhàn)行動進(jìn)行偵察，檢驗(yàn)部隊(duì)在不同天候、地形條件下實(shí)施植被、變形、迷彩等偽裝的反偵察效果，從而增強(qiáng)部隊(duì)隱蔽作戰(zhàn)意圖的能力，提升戰(zhàn)場綜合防護(hù)水平。

反偵察監(jiān)視裁決時(shí)首先要獲得對偵察圖像進(jìn)行人工或自動情報(bào)分析后的偵察結(jié)果，再將偵察結(jié)果與同一時(shí)刻實(shí)際目標(biāo)的位置和屬性進(jìn)行比對，若匹配則認(rèn)為偵察到目標(biāo)。來自不同圖像傳感器的偵察結(jié)果包括圖像中發(fā)現(xiàn)和識別的目標(biāo)位置、目標(biāo)識別類型、目標(biāo)屬性等信息，由于不同來源的偵察圖像獲取和傳輸?shù)臅r(shí)間不同步、數(shù)據(jù)率不一致，且圖像情報(bào)分析結(jié)果是非實(shí)時(shí)和非連續(xù)的，在進(jìn)行偵察結(jié)果與實(shí)際目標(biāo)位置、屬性比對前，需要對來自不同傳感器的偵察結(jié)果進(jìn)行關(guān)聯(lián)融合，合并屬于同一目標(biāo)的偵察結(jié)果。

偵察目標(biāo)具有空間位置和非空間屬性多重特性，進(jìn)行多源偵察結(jié)果融合的原則是：不同傳感器在近似同一時(shí)刻時(shí)對同一目標(biāo)的偵察結(jié)果既要在空間位置上盡量接近，又要在識別屬性上具有最大的相似度。因此，進(jìn)行多源偵察結(jié)果融合時(shí)需要進(jìn)行基于空間位置和非空間屬性的多重聚類。

傳統(tǒng)的空間聚類方法[2-30]大多僅依據(jù)對象的空間位置之間或其他特征屬性之間的距離相似度進(jìn)行聚類，前者忽略了對象的非空間特征屬性，后者忽視了空間鄰近性。目前能夠兼顧空間屬性和非空間屬性的空間聚類方法主要有分治法和一體化法兩類。分治法[31-32]在分別進(jìn)行空間位置和非空間屬性的聚類后綜合生成最終聚類結(jié)果，如DC(Dual Clustering)算法和DCAD(Dual Clustering Algorithm for Distributed Spatial Databases)算法，這類算法計(jì)算量大，輸入?yún)?shù)多，可擴(kuò)展性不好；一體化法[33]將空間位置和非空間屬性都視為空間要素的屬性數(shù)據(jù)，使用屬性距離函數(shù)計(jì)算相似度，再結(jié)合K均值算法進(jìn)行聚類。該方法弱化了要素的空間特性，相似度計(jì)算權(quán)重帶有主觀性，且隨機(jī)選取初始聚類中心導(dǎo)致存在聚類不確定性。此外，DDBSC算法[34]提出雙重距離的概念，使用染色策略遞歸檢索每個核要素的所有雙重距離直接可達(dá)或相連的要素，并聚為簇，但是該算法僅考慮了一種非空間屬性，且在開始或完成一輪遞歸搜索后，都要檢查所有空間要素是否染色，計(jì)算效率較低。本文在DDBSC算法的基礎(chǔ)上進(jìn)行改進(jìn)，綜合考慮空間位置和多個非空間屬性的相似性，分別計(jì)算空間和多個非空間屬性多重距離，并提高算法計(jì)算效率，提出了基于多重距離的空間聚類算法MDBSC(Multiple Distance Based Spatial Clustering)，用于多源偵察結(jié)果的融合。

1　算法原理

設(shè)有多源偵察結(jié)果構(gòu)成空間要素集合F={f1(X1,Y1),f2(X2,Y2),…,fn(Xn,Yn)}(n≥2)，其中X={x1,x2}為空間位置二維坐標(biāo)向量，Y={y1,y2,…,ym}為m維非空間屬性向量(如目標(biāo)運(yùn)動速度，目標(biāo)發(fā)現(xiàn)時(shí)間等)，則fi到fj(1≤i,j≤n)的空間距離和第k維非空間屬性距離分別為DistX(Xi,Xj)和Distyk(yik,yjk)，定義為：

(1)

(2)

式中：(xi1,xi2)表示fi的空間位置坐標(biāo)；yik表示fi的第k維非空間屬性。

當(dāng)兩個空間要素空間距離接近，且所有非空間屬性距離相似時(shí)，可劃分為同一類簇。空間上不相鄰的空間要素之間可能通過其他要素相連，從而也歸為同一類簇。這里引入距離直接可達(dá)和距離相連的概念，當(dāng)且僅當(dāng)空間和多個非空間屬性多重距離直接可達(dá)或相連時(shí)，空間要素才劃分為同一類簇。定義如下：

6) 核：選取一個未歸屬任何簇的空間要素fc作為新簇的搜索起始點(diǎn)，若至少存在一個要素fd，滿足fd?fc，則要素fc稱為核。

7) 簇：每個核要素的所有多重距離直接可達(dá)或相連的要素，并聚為簇cluster={fc,?fi:fi?fc∪fi～fc}

8) 孤立點(diǎn)：未歸屬任何簇的要素。

2　算法步驟

在進(jìn)行目標(biāo)聚類時(shí)，依次搜索各空間要素，判斷各要素之間的多重距離是否直接可達(dá)或相連，從而獲得染色空間要素集，即聚簇結(jié)果。定義空間要素的數(shù)據(jù)結(jié)構(gòu)包括要素的空間位置向量、非空間屬性向量、核屬性標(biāo)識bisCore(布爾型)和著色值nColor，當(dāng)要素為核時(shí)標(biāo)識bisCore為真，當(dāng)要素尚未著色時(shí)nColor值為0。算法過程如下：

1) 按時(shí)間先后順序建立包含所有空間要素的染色隊(duì)列用于存儲要素信息，并設(shè)置所有要素的bisCore=FALSE，nColor=0，初始化i=0，C=0；

2) 抽取隊(duì)列中第i個要素，若已染色，直接轉(zhuǎn)步驟(3)，若未染色(nColor=0)，令C=C+1，并設(shè)置fi的顏色fi.nColor=C，第C個染色要素集FC={fi}；

6)i=i+1，若i≥n，直接轉(zhuǎn)步驟(7)，若i

7) 將第C個融合要素集中所有要素的空間位置進(jìn)行融合得到第C個目標(biāo)的融合位置，將所有要素的非空間屬性值求平均得到第C個目標(biāo)的融合屬性值，得到融合結(jié)果隊(duì)列。

3　算法實(shí)例

設(shè)有紅外(I)、可見光(II)、超光譜(III)、SAR(IV)成像的3類偵察結(jié)果(見表1)，偵察目標(biāo)類型用數(shù)字1～5代替，以運(yùn)動速度(m/s)和發(fā)現(xiàn)時(shí)間(s)作為目標(biāo)非空間屬性。設(shè)置距離容差為10m，非空間屬性速度容差為1.5 m/s，假設(shè)采集時(shí)間最小間隔為1 s，只對間隔時(shí)間小于1 s內(nèi)的偵察結(jié)果進(jìn)行融合，即非空間屬性目標(biāo)發(fā)現(xiàn)時(shí)間容差為1 s。利用本文方法進(jìn)行多源偵察結(jié)果的融合，融合結(jié)果見表2，“融合結(jié)果”列中“()”內(nèi)為參與融合的目標(biāo)序號，以“-”符號連接。

表1　偵察結(jié)果中的空間位置和非空間屬性

表2　融合結(jié)果

由表1可以看出，偵察目標(biāo)1、2和3在空間位置上相近，目標(biāo)速度和發(fā)現(xiàn)時(shí)間屬性也近似，對應(yīng)同一實(shí)際目標(biāo)；偵察目標(biāo)6、7和8在空間位置上相近，但是由于目標(biāo)7的速度屬性與目標(biāo)6和8的速度屬性差距較大，因此將目標(biāo)6和8聚類，目標(biāo)7和目標(biāo)4、5一樣均視為孤立點(diǎn)，最終將來自多源偵察的8個目標(biāo)聚類后得到5個目標(biāo)。實(shí)驗(yàn)結(jié)果表明，本文所提出的MDBSC方法能夠根據(jù)多源偵察結(jié)果在目標(biāo)位置和非空間屬性上的相似性，有效融合多源偵察結(jié)果，聚類算法效率高，且結(jié)果較為合理。

4　結(jié)論

本文提出了基于空間和屬性多重距離的聚類方法用于反偵察監(jiān)視裁決中的多源偵察結(jié)果融合。給出了多重距離直接可達(dá)和多重距離相連的概念，當(dāng)且僅當(dāng)多重距離直接可達(dá)或相連時(shí)，空間要素才劃分為同一類簇，利用對多源偵察結(jié)果的距離直接可達(dá)和距離相連的判斷，將同一目標(biāo)的偵察結(jié)果聚類融合得到目標(biāo)的融合情報(bào)。通過試驗(yàn)驗(yàn)證了算法的可用性和合理性。

[1]李靖,張坤平,田軍.中國陸軍復(fù)雜電磁環(huán)境下訓(xùn)練取得突破性進(jìn)展[N].解放軍畫報(bào)，2010-02-15.

[2]MACQUEEN J.Some Methods for Classification and Analysis of Multivariate Observations [C]//Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability.Berkeley:University of California Press,1967:281-297.

[3]KAUFMAN L,ROUSSEEUW P J.Finding Groups in Data:An Introduction to Cluster Analysis[M].New York:John Wiley & Sons,1990.

[4]NG R,HAN J.CLARANS:A method for clustering objects for spatial data mining[J].IEEE Trans.Knowledge & Data Engineering,2002,14(5):1003-1016.

[5]HOPEENER F,KLAWONN F,KRUSE R.Fuzzy Cluster Analysis:Methods for Classification,Data Analysis and Image Recognition[Z].1999.

[6]ZHANG T,RAMAKRISHNAN R,LIVNY M.BIRCH:An Efficient Data Clustering Method for Very Large Databases [C]//Proceeding of the International Conference Management of Data.Montreal:[s.n.],1996:103-114.

[7]GUHA S,RASTOGI R,SHIM K.CURE:An Efficient Clustering Algorithm for Large Databases [C]//Proceedings of 1998 ACM-SIGMOD International Conference on Management of Data (SIGMOD’ 98).New York:ACM,1998:73-84.

[8]GUHA S,RASTOGI R,SHIM K.ROCK:A Robust Clustering Algorithm for Categorical Attributes [C]//Proceedings of the International Conference of Data Engineering (ICDE’ 99).Washington:IEEE Computer Society,1999:512-521.

[9]KARYPIS G,HAN E H,KUMAR V.CHAMELEON:A hierarchical clustering algorithm using dynamic modeling.Compute[Z].1999:68-75.

[10]SUDIPTO G,RASTOGI R,SHIM K.ROCK:A robust clustering algorithm for categorical attributes[C]//Proc.1999 Int’l Conf.Data Engineering(IDCE’ 99).[S.l.]:[s.n.],1999:512-521.

[11]ESTER M,KRIEGEL H P,SANDER J,XU X.A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise [C]//Proceedings of the 2nd the International Conference on Knowledge Discovery and Data Mining.[s.l.]:AAAI Press,1996:226-231.

[12]ANKERST M,BREUNIG M,KRIEGEL H P,etal.OPTICS:Ordering Points to Identify the Clustering Structure [C]//Proceedings of the 1999 ACM-SIGMOD International Conference on Management of Data (DIGMOD’ 99).New York:ACM,1999:49-60.

[13]HINNEBURG A,KEIM D A.An Efficient Approach to Clustering in Large Multimedia Databases with Noise [C]// Proceedings of the 1998 International Conference on Knowledge Discovery and Data Mining (KDD’98).New York:AAAI Press,1998:58-65.

[14]WANG W,YANG J,MUNTZ R.STING:A Statistical Information Grid Approach to Spatial Data Mining [C]// Proceedings of the 1997 International Conference on Very Large Data Bases (VLDB’97).San Francisco:Morgan Kaufmann Publishers Inc,1997:186-195.

[15]SHEIKHOLESLAMI G,CHATTERJEE S,ZHANG A.WaveCluster:A Multi-resolution Clustering Approach for Very Large Spatial Databases [C]//Proceedings of the 24th International Conference on Very Large Database.New York:Morgan Kaufmann Publishers Inc,1998:428-439.

[16]AGRAWAL R,GEHRKE J,GUNOPULOS D,et al.Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications[C]//Proceedings of the 1998 ACM-SIGMOD International Conference on Management of Data (SIGMOD’98).New York:ACM,1998:94-105.

[17]XU X W,ESTER M,KRIEGE H P,et al.A Distribution-based Clustering Algorithm for Mining in Large Spatial Databases [C]//Proceedings of the 14th International Conference on Data Engineering (ICDE’98).Washington:IEEE Computer Society,1998:324-331.

[18]FISHER D.Improving inference through conceptual clustering[C]// Proc.AAAI Conf.Seattle.WA,1987:461-465.

[19]CHEESEMAN P,STUTZ J.Bayesian classification (Autoclass):Theory and results.Advances in Knowledge Discovery and Data Mining[Z].MA:AAAI/MIT Press,1996:153-180.

[21]DAVéR.Adaptive Fuzzy C-Shells Clustering and Detection of Ellipses [J].IEEE Transaction Neural Network,1992,3(5):643-662.

[22]CHERNG J S,LO M J.A Hypergraph Based Clustering Algorithm for Spatial Data Sets [C]//Proceedings of the IEEE International Conference on Data Mining (ICDM’ 01).Washington:IEEE Computer Society,2001:83-90.

[23]HARTUV E,SHAMIR R.A Clustering Algorithm Based on Graph Connectivity [J].Information Processing Letters,2000,76 (426):175-181.

[24]SHARAN R,SHAMIR R.CLICK:A Clustering Algorithm with Applications to Gene Expression Analysis[C]// Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology (ISMB).San Diego:AAAI Press,2000:307-316.

[25]AMIR B D,ZOHAR Y.Clustering Gene Expression Patterns [J].Journal of Computational Biology,1999,6(324):281-297.

[26]SONG G,YING X.GDCIC:A Grid-based Density-Confidence-Interval Clustering Algorithm for Multi-density Dataset in Large Spatial Databases [C]// Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications (ISDA’ 06).Washington:IEEE Computer Society,2006:713-717.

[27]UNCU O,GRUVER W A,KOTAK D B,etal.GRIDBSCAN:Grid Density-based Spatial Clustering of Applications with Noise [C]//Proceeding of the IEEE International Conference on Systems,Man and Cybernetics (ICSMC’ 06).Taipei:[s.n.],2006:2976-2981.

[28]TSAI C F,YEN C C.ANGEL:A New Effective and Efficient Hybrid Clustering Technique for Large Databases[M].Berlin:Springer Press,2007.

[29]駱劍承,梁怡,周成虎.基于尺度空間的分層聚類方法及其在遙感影像分類中的應(yīng)用[J].測繪學(xué)報(bào),1999,28(4):319-314.

[30]駱劍承,周成虎,梁怡.多尺度空間單元區(qū)域劃分方法[J].地理學(xué)報(bào),2002,54(2):167-173.

[31]LIN C R,LIU K H,CHEN M S.Dual Clustering:Integrating Data Clustering over Optimization and Constraint Domains[C]//Proceedings of the IEEE Transactions on Knowledge and Data Engineering.Piscataway:IEEE Educational Activities Department,2005:628-637.

[32]ZHOU J G,GUAN J H,LI P X.DCAD:A Dual Clustering Algorithm for Distributed Spatial Databases [J].Geo-spatial Information Science,2007,10(2):137-144.

[33]李新運(yùn),鄭新奇,閆弘文.坐標(biāo)與屬性一體化的空間聚類方法研究[J].地理與地理信息科學(xué),2004,20(2):38-40.

[34]李光強(qiáng),鄧敏,程濤,等.一種基于雙重距離的空間聚類方法[J].測繪學(xué)報(bào),2008,37(4):482-488.

(責(zé)任編輯楊繼森)

An Algorithm of Multiple Sensor Reconnaissance Results Fusion Based on Multiple Distances Based Spatial Clustering

XU Ying

(304 Teaching and Research Section, Electronic Engineering Institute of PLA, Hefei 230037, China)

During the counter reconnaissance assessment，in order to merge the reconnaissance results belong to the same target, reconnaissance results from different sensor should be clustered based on the spatial position and attributes on account of the non-real time inconstant of the acquisition and transmission of reconnaissance images, and the time non-continuity of image information analysis results. Taking into account of the similitude of the spatial position and multiple non-spatial attributes, MDBSC (Multiple Distances Based Spatial Clustering) algorithm was proposed and used to achieve the reconnaissance results fusion of multi-sensor, and procedure and example of the algorithm were provided.

multiple distance; spatial clustering; fusion of multi-sensor; association and fusion

2016-04-16；

2016-04-30

徐英(1979—),女,博士,講師,主要從事裝備電磁環(huán)境適應(yīng)性與評估研究。

10.11809/scbgxb2016.09.020

format:XU Ying.An Algorithm of Multiple Sensor Reconnaissance Results Fusion Based on Multiple Distances Based Spatial Clustering[J].Journal of Ordnance Equipment Engineering,2016(9):83-86.

TP753

A

2096-2304(2016)09-0083-04

本文引用格式：徐英.一種基于多重距離聚類的多源偵察結(jié)果融合算法[J].兵器裝備工程學(xué)報(bào)，2016(9):83-86.