一種基于分群矩陣的目標動態分群算法

艾　偉，張冬寧

(中國電子科技集團公司第五十四研究所，河北 石家莊050081)

?

一種基于分群矩陣的目標動態分群算法

艾偉，張冬寧

(中國電子科技集團公司第五十四研究所，河北 石家莊050081)

摘要針對態勢估計中目標動態分群問題，提出了一種基于分群矩陣的目標分群算法。利用目標與目標之間的相似度構建目標分群矩陣；通過分群矩陣運算實現對目標分群的判斷；隨著目標數據的動態更新，在多個目標分群周期上利用目標分群矩陣運算，可以實現對目標分群的維持、分裂和合并等動態維護；提出了利用分群矩陣實現目標聚合的算法過程。通過仿真試驗證明該方法正確，能夠自適應產生目標分群數量。

關鍵詞目標分群；分群矩陣；目標聚合；動態分群

A Dynamic Target Grouping Approach Based on Grouping Matrix

AI Wei，ZHANG Dong-ning

(The54thResearchInstituteofCETC，ShijiazhuangHebei050081，China)

AbstractA dynamic target grouping approach based on the grouping matrix is presented in order to solve the dynamic target grouping problem in the situation assessment.A target grouping matrix is created with the similar degrees between the two targets，the result of the target grouping is judged after matrix computation.The target grouping matrix is computed in a number of processing cycle for implementing such dynamic maintenance as target group retaining，target group splitting and target group merging.This paper also presents a target aggregating algorithm process based on grouping matrix.The simulation test results show that this method is correct，and can generate the number of target groups adaptively.

Key wordstarget grouping;grouping matrix;target aggregating;dynamic grouping

0引言

識別目標編隊是態勢估計中的一個重要應用問題，目標分群是實現識別目標編隊的重要技術手段之一[1]，現有目標分群方法主要有聚類方法和模板方法2類。大多數聚類算法[2-6]由于初始狀態隨機給定會造成目標分群結果的不確定性，例如K-means 算法需要事先指定最終的分群數k，Chameleon 算法需要給定合并閾值，這些限制影響了分群結果的連續性和實時性；基于模板方法的目標分群算法具有分群精度高、分群結果可理解性強的優點，但其缺點是制定模板非常繁雜困難，該方法很難推廣和實用[7-12]。現有目標分群方法大都屬于靜態解決方案，存在分群時間長、存儲消耗大的缺陷，不適用于實時態勢的目標分群應用。

目標分群本質上是對隨時間變化的目標數據進行周期性動態分群處理的過程，過程中有群的維持、分裂和合并等操作。文獻[13]把目標分群看作數據流聚類問題，提出了一種動態目標分群框架和比較復雜的運算規則。本文提出了基于分群矩陣運算的動態目標分群方法，通過矩陣運算能實現群的維持、分裂和合并，物理含義貼近實際需求，方法簡單、易實現。

1算法描述

目標分群主要涉及到2個問題：① 如何判定2個目標或2個以上目標是否屬于同一個目標群；② 如何根據目標時序數據流動態維護目標分群過程。針對第1個問題，提出了基于連續屬性和離散屬性混合計算的目標分群相似度計算方法；針對第2個問題，提出了基于分群矩陣運算的目標動態分群算法，來解決目標群的維持、分裂和合并等動態維護問題。

1.1目標分群相似度計算

主要根據目標的多個屬性來計算目標分群的相似度，常用的屬性項包括位置坐標、速度、航向、時間、類型、型號、國別和性質等，這些屬性項中有的是用連續值表示，如位置、速度和航向等，有的是用離散值表示，如類型、型號、國別和性質等，在進行目標分群相似度計算時，不管是離散的屬性項還是連續的屬性項都起著重要作用。因此，采用基于連續屬性和離散屬性混合計算的目標分群相似度計算方法[14]，通過距離度量目標之間的相似度。

目標Oi和目標Oj之間的距離定義為：

(1)

(2)

目標連續屬性的距離計算帶有一定的物理含義，因此需要進行歸一化處理才能計算相似度。相似度定義如下：

(3)

(4)

(5)

式中，βl為每個離散屬性的權重，可以根據實際的目標分群規則定義不同離散屬性在計算相似度時的權重。

1.2目標動態分群矩陣算法

1.2.1分群矩陣構建

根據目標分群相似度計算結果可以構造分群矩陣A，矩陣A的第1行元素是目標的編號，第1列元素同樣是對應的目標編號，對角線上的元素均為1，其他元素要么是1，要么是0，1表示對應行和列上的目標相似，0表示對應行和列上的目標不相似。

假設有N個目標Oi(i∈[1，N])，則矩陣A可以表示為：

(6)

式中，ON為第N個目標的編號；σij為目標Oi和目標Oj編在一組的相似度，按式(3)進行計算。

分群矩陣具有如下性質：

性質1：當i=j時，σij=1，矩陣A對角線上元素都為1，即表示目標本身和本身肯定屬于同一組；

性質2：矩陣A中，由σij構成的元素只有0和1，1表示行和列對應的目標是同一群，0表示行和列對應的目標不在同一群；

性質3：矩陣A是對稱矩陣。

1.2.2分群矩陣運算

對矩陣A進行矩陣行行交換和列列交換，可以形成對N個目標的分群結果。分群矩陣運算符合如下定理：

定理1：從矩陣A的第2行第3列元素開始，如果σ12=1，則保持矩陣A行和列不變；如果σ12=0，則依次往后找σ1j元素，如果σ1j=1，則第3列元素和第j列元素交換位置，同時第3行元素和第j行元素交換位置；如果σ1j=0，則不進行行交換和列列交換。接著從矩陣A的第2行第4列元素開始進行上述矩陣元素值判斷及行行和列列交換，依次往后直至找到第N+1列為止。

定理2：經過定理1的矩陣運算后所形成矩陣A′，在矩陣A′中，從第2行第3列元素開始，如果σ1j連續為1，則行和列所對應的目標為一群，即如果不同目標為一群，則其所在的行和列元素所構成的局部矩陣為單位矩陣，依次類推，直到所有的元素全部遍歷完畢；如果單位矩陣中只有一個元素，說明其所對應的目標單獨為一個群。

1.2.3目標分群維護

目標分群維護主要包括群維持、群分裂和群合并。根據定理2可以比較容易地實現群的動態維護。

定理3：在連續3個周期的分群矩陣中，群成員沒有變化，則群達到穩定狀態，群處于維持狀態。

定理4：當相鄰2個周期的分群矩陣中，群成員減少，則群處于分裂狀態，群成員減少有2種結果：① 分裂成獨立的2個或多個群；② 分裂出去的群成員合并到其他群中。根據定理3可以判定分裂群的穩定狀態。

定理5：當相鄰2個周期的分群矩陣中，群成員增加，則群處于合并狀態，群成員增加有3種情況：第1種情況是之前2個獨立的群合并成一個群；第2種情況是新出現的目標合并到群中，第3種情況是其他群分裂出來的成員合并到群中。根據定理3可以判定合并群的穩定狀態。

2目標分群算法流程

關于目標分群的方法大多采用聚類的方法來實現，但是在實際應用中，目標數據不是一次性獲取，而是按照一定的周期進行獲取的，這樣采用聚類算法來進行目標動態分群存在計算復雜、目標群維護困難的問題，同時，采用聚類算法不太容易實現目標多層級的聚合問題，而采用目標分群矩陣算法可以很容易地實現目標分群的動態維護和目標聚合的動態維護。

2.1目標分群計算和動態維護流程

假設有N個目標Oi(i∈[1，N])，設定分群周期為時間T，目標Oi的數據更新周期為t，分群周期與目標數據的更新周期可以相同也可以不相同。按照分群矩陣算法進行目標分群計算，目標分群計算和動態維護的流程如圖 1所示。

圖1　目標分群計算和動態維護流程

在圖1的目標分群計算和動態維護的流程中主要包括如下步驟：

第1步：持續接收所有目標的狀態更新數據；

第2步：按照分群周期T，獲取當前周期目標數據，計算目標相似度，構建當前周期的分群矩陣A；

第3步：根據定理1，對分群矩陣A進行行列交換運算形成矩陣A′；

第4步：根據定理2，對矩陣A′進行目標群標識；

第5步：對照上一周期T-1的目標群標識，根據定理3、定理4和定理5判斷目標群的合并、分裂以及維持狀態，并記錄本周期的目標群標識；

第6步：重復第2步~第5步的過程，直到中斷退出。

2.2目標聚合計算和動態維護流程

在實際應用中會存在對目標進行多個層級分群的情況，也就是目標聚合的過程。目標聚合就是根據一定的規則把目標群再次逐級分群聚合，形成多個層級的越來越抽象的目標群。

利用分群矩陣算法可以很容易地實現目標聚合及其動態維護過程。經過第一層級的目標分群過程后，在向下一層級聚合時，以目標群為計算單元，對多個目標群再進行相似度計算來構造分群矩陣，再進行分群矩陣運算后，就得到這一層級目標群，依次類推直到不能再進行聚合分群為止。目標聚合計算和及其動態維護的流程如圖 2所示。

在圖 2的目標聚合計算和動態維護的流程中主要包括如下步驟：

第1步：把目標分群或聚合的結果當作再次分群對象，按照分群周期T，計算目標群之間的相似度，構建目標聚合矩陣A；

第2步：根據定理1，對聚合矩陣A進行行列交換運算形成矩陣A′；

第3步：根據定理2，對矩陣A′進行目標聚合群標識；

第4步：對照上一周期T-1的目標聚合群標識，根據定理3、定理4和定理5判斷目標聚合群的合并、分裂以及維持狀態，并記錄本周期的目標聚合群標識；

第5步：重復第1步~第5步的過程，直到目標聚合群不能再深度聚合為止。

圖2　目標聚合計算和動態維護流程

3仿真試驗

仿真試驗通過設計一個試驗場景來進行，仿真場景假設有10批目標，這10批目標在隸屬關系上屬于同一方，從場景設置上，把目標O3、O5、O7和O9設置為一群，把目標O2、O4和O10設置為一群，目標O1和O8是一群，目標O6是單獨一群。在設計仿真過程時，這10批目標按照設置的速度運動，按照時間周期T輸出目標的狀態數據。在Tk時刻的目標位置空間分布如圖 3所示，目標點后拖的軌跡表示目標的歷史航跡。

圖3　仿真場景目標空間分布示意

假設僅依據目標位置屬性來計算目標分群的相似度，目的是驗證目標分群矩陣運算法的正確性。根據式(3)和式(6)，構建如下分群矩陣：

1O1O2O3O4O5O6O7O8O9O10O11000000100O20101000001O30010101010O40101000001O50010101010O60000010000O70010101010O81000000100O90010101010O100101000001

對矩陣O2與O8進行行行交換和列列交換后形成如下矩陣：

1O1O8O3O4O5O6O7O2O9O10O11100000000O81100000000O30010101010O40001000101O50010101010O60000010000O70010101010O20001000101O90010101010O100001000101

依次對矩陣O4與O5、O4與O7、O6與O9、O6與O10進行行行交換和列列交換后形成如下矩陣：

1O1O8O3O5O7O9O4O2O10O6O11100000000O81100000000O30011110000O50011110000O70011110000O90011110000O40000001110O20000001110O100000001110O60000000001

經過若干次行行和列列交換后，即按照定理1直到不能交換為止，從最后的矩陣中可以看出，根據定理2可以知道目標O1和O8是一群，目標O3、O5、O7和O9是一群，目標O4、O2和O10是一群，目標O6單獨是一群。從而能夠說明所提出的目標分群矩陣算法正確、可行，并且計算效率很高。

對目標分群維護來說，需要在下一個分群計算周期再次進行上述分群矩陣構建和分群矩陣運算即可，然后再通過前后2個周期的分群矩陣對比，即可知道目標分群的維持、分類和合并狀態。在圖 3所示的仿真場景設計中，目標O6在經過k+n個周期后，逐漸與目標O1和O8合為一個編隊，從而可以驗證目標分群維護。

對目標聚合來說，對于分出來的4個群，再次根據式(3)進行相似度計算，構建分群矩陣，進行分群矩陣運算，可以實現目標聚合，即在圖 3所示的仿真場景中，4個群聚合后同屬于一個更大的群，從而實現目標多層次聚合。

4結束語

提出基于分群矩陣運算的目標分群算法進行目標的動態分群和動態聚合，具有易實現、易理解和分群準確的特點，而且實時性好，不需要事先制定模板和指定分群的個數，群的分離與合并通過分群矩陣可以直接得到，非常適合目標數量較大時的目標分群計算。在形成目標分群矩陣時，主要通過兩兩目標或兩兩目標群之間的相似度來進行構造，相似度計算參數的選擇與實際的應用密切結合，在實際應用過程中可以根據不同的目標分群規則，選擇合適的目標屬性來進行計算，同時還可以對不同的屬性項附加以不同的權重，這樣可以更有效地提高分群的正確率。

參考文獻

[1]黃雷,郭雷.一種面向態勢估計中分群問題的聚類方法[J].計算機應用,2006,26(5):1 109-1 111.

[2]龍真真,張策.兵力聚合中的目標分群方法研究[J].計算機工程與應用,2011,47(20):225-230.

[3]趙鵬,常天慶,魏巍,等.基于多Agent的戰場目標分群方法[J].計算機工程,2011,37(21):152-158.

[4]龍真真,張 策,吳偉勝,等.基于多幀數據的目標分群算法[J].計算機工程,2009,35(23):168-171.

[5]李啟元,楊亞橋,楊露菁.基于聚類的海戰場目標分群方法[J].微計算機信息,2008,24(5-3):42-44.

[6]張松良,王付明,魯柯,等.城市戰場目標分群的組合聚類方法[J].指揮控制與仿真,2009,31(5):37-41.

[7]劉秀文.基于目標分群與模糊匹配的態勢評估技術[J].無線電工程,2012,42 (12):61-64.

[8]熊紅強,耿伯英,王文濤.海戰場目標分群方法研究[J].電光與控制,2012,19(2):26-28.

[9]龍真真,張策,王維平.基于層次聚類態勢估計中的目標分群算法[J].彈箭與制導學報,2009,29(3):209-211.

[10]吉軍,李剛,吳言鳳.海戰場多目標聚類-匹配分群研究[J].四川兵工學報,2013,34(2):104-106.

[11]王新為,楊紹清,林洪文,等.海戰場目標分群技術研究[J].艦船電子工程,2013,33(11):25-27.

[12]胡艮勝,劉建平,胡睿.面向智能化推演仿真的敵軍兵力分群研究[J].系統仿真學報,2013,25(S):125-128.

[13]龍真真,張策,王維平,等.一種基于數據流聚類的動態目標分群框架[J].上海交通大學學報,2010,44 (7):921-925.

[14]楊春宇,周杰.一種混合屬性數據流聚類算法[J].計算機學報,2007,30 (8):1 364-1 371.

艾偉男，(1977—)，碩士，高級工程師。主要研究方向：信息融合與態勢仿真。

張冬寧女，(1981—)，碩士，高級工程師。主要研究方向：信息融合與態勢處理。

作者簡介

基金項目：國防973計劃基金資助項目(613147)。

收稿日期：2015-09-22

中圖分類號TN391.9

文獻標識碼A

文章編號1003-3106(2015)12-0064-05

doi:10.3969/j.issn.1003-3106.2015.12.17

引用格式：艾偉，張冬寧.一種基于分群矩陣的目標動態分群算法[J].無線電工程,2015,45(12):64-68.