艾　偉，張冬寧

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

?

一種基于分群矩陣的目標(biāo)動(dòng)態(tài)分群算法

艾偉，張冬寧

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

摘要針對(duì)態(tài)勢(shì)估計(jì)中目標(biāo)動(dòng)態(tài)分群?jiǎn)栴}，提出了一種基于分群矩陣的目標(biāo)分群算法。利用目標(biāo)與目標(biāo)之間的相似度構(gòu)建目標(biāo)分群矩陣；通過(guò)分群矩陣運(yùn)算實(shí)現(xiàn)對(duì)目標(biāo)分群的判斷；隨著目標(biāo)數(shù)據(jù)的動(dòng)態(tài)更新，在多個(gè)目標(biāo)分群周期上利用目標(biāo)分群矩陣運(yùn)算，可以實(shí)現(xiàn)對(duì)目標(biāo)分群的維持、分裂和合并等動(dòng)態(tài)維護(hù)；提出了利用分群矩陣實(shí)現(xiàn)目標(biāo)聚合的算法過(guò)程。通過(guò)仿真試驗(yàn)證明該方法正確，能夠自適應(yīng)產(chǎn)生目標(biāo)分群數(shù)量。

關(guān)鍵詞目標(biāo)分群；分群矩陣；目標(biāo)聚合；動(dòng)態(tài)分群

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引言

識(shí)別目標(biāo)編隊(duì)是態(tài)勢(shì)估計(jì)中的一個(gè)重要應(yīng)用問(wèn)題，目標(biāo)分群是實(shí)現(xiàn)識(shí)別目標(biāo)編隊(duì)的重要技術(shù)手段之一[1]，現(xiàn)有目標(biāo)分群方法主要有聚類方法和模板方法2類。大多數(shù)聚類算法[2-6]由于初始狀態(tài)隨機(jī)給定會(huì)造成目標(biāo)分群結(jié)果的不確定性，例如K-means 算法需要事先指定最終的分群數(shù)k，Chameleon 算法需要給定合并閾值，這些限制影響了分群結(jié)果的連續(xù)性和實(shí)時(shí)性；基于模板方法的目標(biāo)分群算法具有分群精度高、分群結(jié)果可理解性強(qiáng)的優(yōu)點(diǎn)，但其缺點(diǎn)是制定模板非常繁雜困難，該方法很難推廣和實(shí)用[7-12]?，F(xiàn)有目標(biāo)分群方法大都屬于靜態(tài)解決方案，存在分群時(shí)間長(zhǎng)、存儲(chǔ)消耗大的缺陷，不適用于實(shí)時(shí)態(tài)勢(shì)的目標(biāo)分群應(yīng)用。

目標(biāo)分群本質(zhì)上是對(duì)隨時(shí)間變化的目標(biāo)數(shù)據(jù)進(jìn)行周期性動(dòng)態(tài)分群處理的過(guò)程，過(guò)程中有群的維持、分裂和合并等操作。文獻(xiàn)[13]把目標(biāo)分群看作數(shù)據(jù)流聚類問(wèn)題，提出了一種動(dòng)態(tài)目標(biāo)分群框架和比較復(fù)雜的運(yùn)算規(guī)則。本文提出了基于分群矩陣運(yùn)算的動(dòng)態(tài)目標(biāo)分群方法，通過(guò)矩陣運(yùn)算能實(shí)現(xiàn)群的維持、分裂和合并，物理含義貼近實(shí)際需求，方法簡(jiǎn)單、易實(shí)現(xiàn)。

1算法描述

目標(biāo)分群主要涉及到2個(gè)問(wèn)題：① 如何判定2個(gè)目標(biāo)或2個(gè)以上目標(biāo)是否屬于同一個(gè)目標(biāo)群；② 如何根據(jù)目標(biāo)時(shí)序數(shù)據(jù)流動(dòng)態(tài)維護(hù)目標(biāo)分群過(guò)程。針對(duì)第1個(gè)問(wèn)題，提出了基于連續(xù)屬性和離散屬性混合計(jì)算的目標(biāo)分群相似度計(jì)算方法；針對(duì)第2個(gè)問(wèn)題，提出了基于分群矩陣運(yùn)算的目標(biāo)動(dòng)態(tài)分群算法，來(lái)解決目標(biāo)群的維持、分裂和合并等動(dòng)態(tài)維護(hù)問(wèn)題。

1.1目標(biāo)分群相似度計(jì)算

主要根據(jù)目標(biāo)的多個(gè)屬性來(lái)計(jì)算目標(biāo)分群的相似度，常用的屬性項(xiàng)包括位置坐標(biāo)、速度、航向、時(shí)間、類型、型號(hào)、國(guó)別和性質(zhì)等，這些屬性項(xiàng)中有的是用連續(xù)值表示，如位置、速度和航向等，有的是用離散值表示，如類型、型號(hào)、國(guó)別和性質(zhì)等，在進(jìn)行目標(biāo)分群相似度計(jì)算時(shí)，不管是離散的屬性項(xiàng)還是連續(xù)的屬性項(xiàng)都起著重要作用。因此，采用基于連續(xù)屬性和離散屬性混合計(jì)算的目標(biāo)分群相似度計(jì)算方法[14]，通過(guò)距離度量目標(biāo)之間的相似度。

目標(biāo)Oi和目標(biāo)Oj之間的距離定義為：

(1)

(2)

目標(biāo)連續(xù)屬性的距離計(jì)算帶有一定的物理含義，因此需要進(jìn)行歸一化處理才能計(jì)算相似度。相似度定義如下：

(3)

(4)

(5)

式中，βl為每個(gè)離散屬性的權(quán)重，可以根據(jù)實(shí)際的目標(biāo)分群規(guī)則定義不同離散屬性在計(jì)算相似度時(shí)的權(quán)重。

1.2目標(biāo)動(dòng)態(tài)分群矩陣算法

1.2.1分群矩陣構(gòu)建

根據(jù)目標(biāo)分群相似度計(jì)算結(jié)果可以構(gòu)造分群矩陣A，矩陣A的第1行元素是目標(biāo)的編號(hào)，第1列元素同樣是對(duì)應(yīng)的目標(biāo)編號(hào)，對(duì)角線上的元素均為1，其他元素要么是1，要么是0，1表示對(duì)應(yīng)行和列上的目標(biāo)相似，0表示對(duì)應(yīng)行和列上的目標(biāo)不相似。

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

(6)

式中，ON為第N個(gè)目標(biāo)的編號(hào)；σij為目標(biāo)Oi和目標(biāo)Oj編在一組的相似度，按式(3)進(jìn)行計(jì)算。

分群矩陣具有如下性質(zhì)：

性質(zhì)1：當(dāng)i=j時(shí)，σij=1，矩陣A對(duì)角線上元素都為1，即表示目標(biāo)本身和本身肯定屬于同一組；

性質(zhì)2：矩陣A中，由σij構(gòu)成的元素只有0和1，1表示行和列對(duì)應(yīng)的目標(biāo)是同一群，0表示行和列對(duì)應(yīng)的目標(biāo)不在同一群；

性質(zhì)3：矩陣A是對(duì)稱矩陣。

1.2.2分群矩陣運(yùn)算

對(duì)矩陣A進(jìn)行矩陣行行交換和列列交換，可以形成對(duì)N個(gè)目標(biāo)的分群結(jié)果。分群矩陣運(yùn)算符合如下定理：

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

定理2：經(jīng)過(guò)定理1的矩陣運(yùn)算后所形成矩陣A′，在矩陣A′中，從第2行第3列元素開(kāi)始，如果σ1j連續(xù)為1，則行和列所對(duì)應(yīng)的目標(biāo)為一群，即如果不同目標(biāo)為一群，則其所在的行和列元素所構(gòu)成的局部矩陣為單位矩陣，依次類推，直到所有的元素全部遍歷完畢；如果單位矩陣中只有一個(gè)元素，說(shuō)明其所對(duì)應(yīng)的目標(biāo)單獨(dú)為一個(gè)群。

1.2.3目標(biāo)分群維護(hù)

目標(biāo)分群維護(hù)主要包括群維持、群分裂和群合并。根據(jù)定理2可以比較容易地實(shí)現(xiàn)群的動(dòng)態(tài)維護(hù)。

定理3：在連續(xù)3個(gè)周期的分群矩陣中，群成員沒(méi)有變化，則群達(dá)到穩(wěn)定狀態(tài)，群處于維持狀態(tài)。

定理4：當(dāng)相鄰2個(gè)周期的分群矩陣中，群成員減少，則群處于分裂狀態(tài)，群成員減少有2種結(jié)果：① 分裂成獨(dú)立的2個(gè)或多個(gè)群；② 分裂出去的群成員合并到其他群中。根據(jù)定理3可以判定分裂群的穩(wěn)定狀態(tài)。

定理5：當(dāng)相鄰2個(gè)周期的分群矩陣中，群成員增加，則群處于合并狀態(tài)，群成員增加有3種情況：第1種情況是之前2個(gè)獨(dú)立的群合并成一個(gè)群；第2種情況是新出現(xiàn)的目標(biāo)合并到群中，第3種情況是其他群分裂出來(lái)的成員合并到群中。根據(jù)定理3可以判定合并群的穩(wěn)定狀態(tài)。

2目標(biāo)分群算法流程

關(guān)于目標(biāo)分群的方法大多采用聚類的方法來(lái)實(shí)現(xiàn)，但是在實(shí)際應(yīng)用中，目標(biāo)數(shù)據(jù)不是一次性獲取，而是按照一定的周期進(jìn)行獲取的，這樣采用聚類算法來(lái)進(jìn)行目標(biāo)動(dòng)態(tài)分群存在計(jì)算復(fù)雜、目標(biāo)群維護(hù)困難的問(wèn)題，同時(shí)，采用聚類算法不太容易實(shí)現(xiàn)目標(biāo)多層級(jí)的聚合問(wèn)題，而采用目標(biāo)分群矩陣算法可以很容易地實(shí)現(xiàn)目標(biāo)分群的動(dòng)態(tài)維護(hù)和目標(biāo)聚合的動(dòng)態(tài)維護(hù)。

2.1目標(biāo)分群計(jì)算和動(dòng)態(tài)維護(hù)流程

假設(shè)有N個(gè)目標(biāo)Oi(i∈[1，N])，設(shè)定分群周期為時(shí)間T，目標(biāo)Oi的數(shù)據(jù)更新周期為t，分群周期與目標(biāo)數(shù)據(jù)的更新周期可以相同也可以不相同。按照分群矩陣算法進(jìn)行目標(biāo)分群計(jì)算，目標(biāo)分群計(jì)算和動(dòng)態(tài)維護(hù)的流程如圖 1所示。

圖1　目標(biāo)分群計(jì)算和動(dòng)態(tài)維護(hù)流程

在圖1的目標(biāo)分群計(jì)算和動(dòng)態(tài)維護(hù)的流程中主要包括如下步驟：

第1步：持續(xù)接收所有目標(biāo)的狀態(tài)更新數(shù)據(jù)；

第2步：按照分群周期T，獲取當(dāng)前周期目標(biāo)數(shù)據(jù)，計(jì)算目標(biāo)相似度，構(gòu)建當(dāng)前周期的分群矩陣A；

第3步：根據(jù)定理1，對(duì)分群矩陣A進(jìn)行行列交換運(yùn)算形成矩陣A′；

第4步：根據(jù)定理2，對(duì)矩陣A′進(jìn)行目標(biāo)群標(biāo)識(shí)；

第5步：對(duì)照上一周期T-1的目標(biāo)群標(biāo)識(shí)，根據(jù)定理3、定理4和定理5判斷目標(biāo)群的合并、分裂以及維持狀態(tài)，并記錄本周期的目標(biāo)群標(biāo)識(shí)；

第6步：重復(fù)第2步~第5步的過(guò)程，直到中斷退出。

2.2目標(biāo)聚合計(jì)算和動(dòng)態(tài)維護(hù)流程

在實(shí)際應(yīng)用中會(huì)存在對(duì)目標(biāo)進(jìn)行多個(gè)層級(jí)分群的情況，也就是目標(biāo)聚合的過(guò)程。目標(biāo)聚合就是根據(jù)一定的規(guī)則把目標(biāo)群再次逐級(jí)分群聚合，形成多個(gè)層級(jí)的越來(lái)越抽象的目標(biāo)群。

利用分群矩陣算法可以很容易地實(shí)現(xiàn)目標(biāo)聚合及其動(dòng)態(tài)維護(hù)過(guò)程。經(jīng)過(guò)第一層級(jí)的目標(biāo)分群過(guò)程后，在向下一層級(jí)聚合時(shí)，以目標(biāo)群為計(jì)算單元，對(duì)多個(gè)目標(biāo)群再進(jìn)行相似度計(jì)算來(lái)構(gòu)造分群矩陣，再進(jìn)行分群矩陣運(yùn)算后，就得到這一層級(jí)目標(biāo)群，依次類推直到不能再進(jìn)行聚合分群為止。目標(biāo)聚合計(jì)算和及其動(dòng)態(tài)維護(hù)的流程如圖 2所示。

在圖 2的目標(biāo)聚合計(jì)算和動(dòng)態(tài)維護(hù)的流程中主要包括如下步驟：

第1步：把目標(biāo)分群或聚合的結(jié)果當(dāng)作再次分群對(duì)象，按照分群周期T，計(jì)算目標(biāo)群之間的相似度，構(gòu)建目標(biāo)聚合矩陣A；

第2步：根據(jù)定理1，對(duì)聚合矩陣A進(jìn)行行列交換運(yùn)算形成矩陣A′；

第3步：根據(jù)定理2，對(duì)矩陣A′進(jìn)行目標(biāo)聚合群標(biāo)識(shí)；

第4步：對(duì)照上一周期T-1的目標(biāo)聚合群標(biāo)識(shí)，根據(jù)定理3、定理4和定理5判斷目標(biāo)聚合群的合并、分裂以及維持狀態(tài)，并記錄本周期的目標(biāo)聚合群標(biāo)識(shí)；

第5步：重復(fù)第1步~第5步的過(guò)程，直到目標(biāo)聚合群不能再深度聚合為止。

圖2　目標(biāo)聚合計(jì)算和動(dòng)態(tài)維護(hù)流程

3仿真試驗(yàn)

仿真試驗(yàn)通過(guò)設(shè)計(jì)一個(gè)試驗(yàn)場(chǎng)景來(lái)進(jìn)行，仿真場(chǎng)景假設(shè)有10批目標(biāo)，這10批目標(biāo)在隸屬關(guān)系上屬于同一方，從場(chǎng)景設(shè)置上，把目標(biāo)O3、O5、O7和O9設(shè)置為一群，把目標(biāo)O2、O4和O10設(shè)置為一群，目標(biāo)O1和O8是一群，目標(biāo)O6是單獨(dú)一群。在設(shè)計(jì)仿真過(guò)程時(shí)，這10批目標(biāo)按照設(shè)置的速度運(yùn)動(dòng)，按照時(shí)間周期T輸出目標(biāo)的狀態(tài)數(shù)據(jù)。在Tk時(shí)刻的目標(biāo)位置空間分布如圖 3所示，目標(biāo)點(diǎn)后拖的軌跡表示目標(biāo)的歷史航跡。

圖3　仿真場(chǎng)景目標(biāo)空間分布示意

假設(shè)僅依據(jù)目標(biāo)位置屬性來(lái)計(jì)算目標(biāo)分群的相似度，目的是驗(yàn)證目標(biāo)分群矩陣運(yùn)算法的正確性。根據(jù)式(3)和式(6)，構(gòu)建如下分群矩陣：

1O1O2O3O4O5O6O7O8O9O10O11000000100O20101000001O30010101010O40101000001O50010101010O60000010000O70010101010O81000000100O90010101010O100101000001

對(duì)矩陣O2與O8進(jìn)行行行交換和列列交換后形成如下矩陣：

1O1O8O3O4O5O6O7O2O9O10O11100000000O81100000000O30010101010O40001000101O50010101010O60000010000O70010101010O20001000101O90010101010O100001000101

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

1O1O8O3O5O7O9O4O2O10O6O11100000000O81100000000O30011110000O50011110000O70011110000O90011110000O40000001110O20000001110O100000001110O60000000001

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

對(duì)目標(biāo)分群維護(hù)來(lái)說(shuō)，需要在下一個(gè)分群計(jì)算周期再次進(jìn)行上述分群矩陣構(gòu)建和分群矩陣運(yùn)算即可，然后再通過(guò)前后2個(gè)周期的分群矩陣對(duì)比，即可知道目標(biāo)分群的維持、分類和合并狀態(tài)。在圖 3所示的仿真場(chǎng)景設(shè)計(jì)中，目標(biāo)O6在經(jīng)過(guò)k+n個(gè)周期后，逐漸與目標(biāo)O1和O8合為一個(gè)編隊(duì)，從而可以驗(yàn)證目標(biāo)分群維護(hù)。

對(duì)目標(biāo)聚合來(lái)說(shuō)，對(duì)于分出來(lái)的4個(gè)群，再次根據(jù)式(3)進(jìn)行相似度計(jì)算，構(gòu)建分群矩陣，進(jìn)行分群矩陣運(yùn)算，可以實(shí)現(xiàn)目標(biāo)聚合，即在圖 3所示的仿真場(chǎng)景中，4個(gè)群聚合后同屬于一個(gè)更大的群，從而實(shí)現(xiàn)目標(biāo)多層次聚合。

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

提出基于分群矩陣運(yùn)算的目標(biāo)分群算法進(jìn)行目標(biāo)的動(dòng)態(tài)分群和動(dòng)態(tài)聚合，具有易實(shí)現(xiàn)、易理解和分群準(zhǔn)確的特點(diǎn)，而且實(shí)時(shí)性好，不需要事先制定模板和指定分群的個(gè)數(shù)，群的分離與合并通過(guò)分群矩陣可以直接得到，非常適合目標(biāo)數(shù)量較大時(shí)的目標(biāo)分群計(jì)算。在形成目標(biāo)分群矩陣時(shí)，主要通過(guò)兩兩目標(biāo)或兩兩目標(biāo)群之間的相似度來(lái)進(jìn)行構(gòu)造，相似度計(jì)算參數(shù)的選擇與實(shí)際的應(yīng)用密切結(jié)合，在實(shí)際應(yīng)用過(guò)程中可以根據(jù)不同的目標(biāo)分群規(guī)則，選擇合適的目標(biāo)屬性來(lái)進(jìn)行計(jì)算，同時(shí)還可以對(duì)不同的屬性項(xiàng)附加以不同的權(quán)重，這樣可以更有效地提高分群的正確率。

參考文獻(xiàn)

[1]黃雷,郭雷.一種面向態(tài)勢(shì)估計(jì)中分群?jiǎn)栴}的聚類方法[J].計(jì)算機(jī)應(yīng)用,2006,26(5):1 109-1 111.

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

[3]趙鵬,常天慶,魏巍,等.基于多Agent的戰(zhàn)場(chǎng)目標(biāo)分群方法[J].計(jì)算機(jī)工程,2011,37(21):152-158.

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

[5]李啟元,楊亞橋,楊露菁.基于聚類的海戰(zhàn)場(chǎng)目標(biāo)分群方法[J].微計(jì)算機(jī)信息,2008,24(5-3):42-44.

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

[7]劉秀文.基于目標(biāo)分群與模糊匹配的態(tài)勢(shì)評(píng)估技術(shù)[J].無(wú)線電工程,2012,42 (12):61-64.

[8]熊紅強(qiáng),耿伯英,王文濤.海戰(zhàn)場(chǎng)目標(biāo)分群方法研究[J].電光與控制,2012,19(2):26-28.

[9]龍真真,張策,王維平.基于層次聚類態(tài)勢(shì)估計(jì)中的目標(biāo)分群算法[J].彈箭與制導(dǎo)學(xué)報(bào),2009,29(3):209-211.

[10]吉軍,李剛,吳言鳳.海戰(zhàn)場(chǎng)多目標(biāo)聚類-匹配分群研究[J].四川兵工學(xué)報(bào),2013,34(2):104-106.

[11]王新為,楊紹清,林洪文,等.海戰(zhàn)場(chǎng)目標(biāo)分群技術(shù)研究[J].艦船電子工程,2013,33(11):25-27.

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

[13]龍真真,張策,王維平,等.一種基于數(shù)據(jù)流聚類的動(dòng)態(tài)目標(biāo)分群框架[J].上海交通大學(xué)學(xué)報(bào),2010,44 (7):921-925.

[14]楊春宇,周杰.一種混合屬性數(shù)據(jù)流聚類算法[J].計(jì)算機(jī)學(xué)報(bào),2007,30 (8):1 364-1 371.

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

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

作者簡(jiǎn)介

基金項(xiàng)目：國(guó)防973計(jì)劃基金資助項(xiàng)目(613147)。

收稿日期：2015-09-22

中圖分類號(hào)TN391.9

文獻(xiàn)標(biāo)識(shí)碼A

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

doi:10.3969/j.issn.1003-3106.2015.12.17

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