基于區(qū)間數(shù)聚類的目標(biāo)分群算法

王海濱, 關(guān) 欣, 衣 曉

(海軍航空大學(xué), 山東 煙臺(tái) 264001)

0 引 言

態(tài)勢(shì)認(rèn)知是指揮控制活動(dòng)的核心環(huán)節(jié),是有效決策和正確行動(dòng)的前提和基礎(chǔ)。目標(biāo)分群作為態(tài)勢(shì)認(rèn)知的重要基礎(chǔ),其主要作用是綜合考慮目標(biāo)位置、速度、屬性等要素,將各類傳感器觀測(cè)到的目標(biāo)信息按照一定的規(guī)則進(jìn)行劃分,得到相應(yīng)的分群結(jié)果,進(jìn)而有助于發(fā)現(xiàn)目標(biāo)各類戰(zhàn)術(shù)意圖。

目標(biāo)分群作為態(tài)勢(shì)認(rèn)知中的難點(diǎn)和重點(diǎn),目前比較成熟的研究成果主要有：基于空間數(shù)據(jù)挖掘技術(shù)的目標(biāo)分群方法、基于模糊集理論的目標(biāo)分群方法、基于多屬性的目標(biāo)分群方法等。文獻(xiàn)[3]根據(jù)目標(biāo)位置和速度信息,采用基于模糊等價(jià)關(guān)系的方法實(shí)現(xiàn)目標(biāo)分群。文獻(xiàn)[4]將目標(biāo)分群轉(zhuǎn)化為數(shù)據(jù)集聚類問題,通過計(jì)算目標(biāo)間的流形距離來衡量目標(biāo)間的相似度。文獻(xiàn)[5]利用目標(biāo)與目標(biāo)之間的相似度構(gòu)建目標(biāo)分群矩陣,通過分群矩陣運(yùn)算實(shí)現(xiàn)對(duì)目標(biāo)分群的判斷。文獻(xiàn)[6]通過引入核函數(shù)和CNM(Clauset-Newman-Moore)算法,給出了目標(biāo)分群的具體實(shí)現(xiàn)。文獻(xiàn)[7]通過基于改進(jìn)空間劃分方法,改善了目標(biāo)分群類別數(shù)未知和閾值選取欠缺有效方法的問題。文獻(xiàn)[8]采用基于自組織競爭神經(jīng)網(wǎng)絡(luò),以目標(biāo)運(yùn)動(dòng)狀態(tài)為依據(jù)進(jìn)行自組織聚類。通過分析發(fā)現(xiàn),國內(nèi)外目標(biāo)分群算法主要是以目標(biāo)空間位置作為分群的基本依據(jù),而隨著傳感器功能的不斷豐富,目標(biāo)屬性等信息日益成為重要的信息來源。另外,傳感器探測(cè)到的目標(biāo)數(shù)據(jù)大多都是不確定或不精確的數(shù)據(jù)。因此,本文著眼目標(biāo)分群中信息不確定的問題,提出一種基于區(qū)間數(shù)聚類的目標(biāo)分群算法,通過利用目標(biāo)的多維特征信息,對(duì)不確定區(qū)間數(shù)據(jù)的聚類分析處理實(shí)現(xiàn)態(tài)勢(shì)認(rèn)知中的目標(biāo)分群。

1 區(qū)間數(shù)描述方法

在態(tài)勢(shì)認(rèn)知過程中,需要對(duì)接收到的目標(biāo)實(shí)體數(shù)據(jù)進(jìn)行分析,以估計(jì)要素之間的關(guān)系,進(jìn)而建立要素之間的結(jié)構(gòu)。由于測(cè)量、計(jì)算所帶來的數(shù)據(jù)誤差,同時(shí)由于信息不完全帶來的數(shù)據(jù)缺乏,使得接收到的目標(biāo)數(shù)據(jù)往往是一些不確定的數(shù),因此采用區(qū)間數(shù)來表示這些具有不確定性的目標(biāo)數(shù)據(jù)更符合人類的思維方式,相對(duì)于實(shí)數(shù)表示也更貼近實(shí)際。

設(shè)表示一個(gè)非空集合,對(duì)于任意,∈,若存在實(shí)泛函::×→滿足下述條件:

(1) 正定性

(,)≥0,(,)=0,當(dāng)且僅當(dāng)=;

(2) 對(duì)稱性

(,)=(,);

(3) 三角不等式

(,)≤(,)+(,),∈。

則稱(,)為兩點(diǎn),之間的度量。

將一般非空集上的度量的定義限制在區(qū)間向量空間(),設(shè){}是度量空間((),)中的點(diǎn)列,如果對(duì)任意>0,存在>0,使得當(dāng),>時(shí),有(,)<,則稱{}是()中的Cauchy列;如果()中任何Cauchy列都收斂于()中的點(diǎn),則稱((),)為完備的度量空間。

(1)

根據(jù)上述給出的區(qū)間數(shù)距離定義可以看出,兩個(gè)區(qū)間數(shù)之間的距離僅僅利用了邊緣信息,未能充分利用區(qū)間數(shù)中心、寬度等信息,因此對(duì)于區(qū)間數(shù)距離度量還存在改進(jìn)的空間。

2 基于區(qū)間數(shù)聚類目標(biāo)分群算法

2.1 問題描述

(2)

對(duì)于給定的待分類目標(biāo),用表示對(duì)其進(jìn)行的劃分,一個(gè)劃分則對(duì)應(yīng)著一個(gè)目標(biāo)分群結(jié)果。實(shí)質(zhì)上劃分是一個(gè)多對(duì)一的函數(shù)。如果將每個(gè)待分類的目標(biāo)用一個(gè)整數(shù)∈{1,2,…,}表示,每個(gè)分群也用一個(gè)整數(shù)表示為∈{1,2,…,},那么對(duì)于待分類目標(biāo)的分群就可以描述為=()。所以目標(biāo)分群聚類的模型可以看成為從目標(biāo)集到分群,,…,上的泛函。

2.2 區(qū)間數(shù)及區(qū)間向量的距離度量

(3)

(4)

基于CW的區(qū)間數(shù)距離不僅考慮了區(qū)間數(shù)的中點(diǎn)值之差,還考慮了其寬度差,使得區(qū)間數(shù)的距離刻畫更全面和細(xì)致。在給出CW度量距離的基礎(chǔ)上,進(jìn)而根據(jù)目標(biāo)區(qū)間特征進(jìn)行目標(biāo)聚類分析,提出了基于CW度量的區(qū)間數(shù)K-means(K-means method for interval data using CW metric,IDCWKM)。

(1) 正定性

(2) 對(duì)稱性

(3) 三角不等式

證畢

(5)

2.3 IDCWKM目標(biāo)分群算法

目標(biāo)分群是將目標(biāo)按照任務(wù)和組織等進(jìn)行分類,一般是按照類型、運(yùn)動(dòng)狀態(tài)相近或執(zhí)行相同任務(wù)的目標(biāo)進(jìn)行分群,以精簡態(tài)勢(shì)信息,因此目標(biāo)分群本質(zhì)上是一個(gè)數(shù)據(jù)聚類問題。本文在對(duì)目標(biāo)數(shù)據(jù)進(jìn)行區(qū)間化描述之后,進(jìn)而定義了新的區(qū)間數(shù)距離度量。根據(jù)區(qū)間數(shù)聚類模型,可設(shè)計(jì)不同的聚類算法,聚類算法之間的不同主要體現(xiàn)在目標(biāo)函數(shù)的選擇上,但遵循的原則基本上都是最小化群內(nèi)目標(biāo)間的距離,同時(shí)最大化不同群目標(biāo)間的距離。與傳統(tǒng)的聚類分析目標(biāo)特征均用實(shí)數(shù)表示不同,這里研究的是采用區(qū)間數(shù)據(jù)表示的目標(biāo)特征,而區(qū)間目標(biāo)數(shù)據(jù)之間的度量是聚類算法的核心問題,因此這里采用前面提出的CW距離作為待分類目標(biāo)樣本之間的距離。

對(duì)于聚類有很多實(shí)現(xiàn)算法,如K-means就是一種典型聚類算法,K-means聚類的思想是通過損失函數(shù)的最小化選取最優(yōu)的劃分。該算法需要事先指定分類數(shù)的值,但對(duì)于目標(biāo)分群而言,事先由于缺乏先驗(yàn)知識(shí),并不能給出目標(biāo)群的值,這給使用者帶來諸多不便,并且還可能出現(xiàn)針對(duì)同一批目標(biāo)分群,由于不同使用者理解的不同可能出現(xiàn)不同的分群結(jié)果。另外，K-means算法在初始中心選擇時(shí)呈現(xiàn)隨機(jī)性特點(diǎn),導(dǎo)致聚類結(jié)果也將出現(xiàn)隨機(jī)性,進(jìn)而得不到全局最優(yōu)解。因此，在目標(biāo)分群中有必要對(duì)K-means算法進(jìn)行改進(jìn)和優(yōu)化。Voronoi圖是由一組由連接兩鄰點(diǎn)直線的垂直平分線組成的連續(xù)多邊形組成,在數(shù)據(jù)分析中有重要作用。本文在區(qū)間數(shù)目標(biāo)分群中提出了一種基于Voronoi圖的改進(jìn)聚類方法,利用Voronoi圖對(duì)目標(biāo)數(shù)據(jù)空間進(jìn)行劃分。該算法能夠依據(jù)Voronoi圖對(duì)聚類初始中心點(diǎn)進(jìn)行優(yōu)化選擇,避免了K-means算法在初始中心點(diǎn)選擇呈現(xiàn)隨機(jī)性進(jìn)而導(dǎo)致分群結(jié)果不準(zhǔn)確的問題。

這樣對(duì)于目標(biāo)集合分群的關(guān)鍵就是找到一個(gè)合理的劃分,能夠?qū)澐譃?,…,和一系列區(qū)間均值向量{,,…,},得到最小化聚類誤差:

(6)

式中：

(7)

(8)

目標(biāo)分群算法是一個(gè)迭代的過程,每次迭代包含兩個(gè)步驟,首先是選擇個(gè)類的中心,將待分類目標(biāo)逐個(gè)并入與其距離最近的類,這樣就得到一個(gè)聚類結(jié)果;然后更新聚類中心;重新計(jì)算每個(gè)目標(biāo)與新的聚類中心的距離,重復(fù)以上步驟,直到聚類劃分不再改變?yōu)橹?。具體過程如下。

數(shù)據(jù)標(biāo)準(zhǔn)化

(9)

分配初始聚類中心值

目標(biāo)集={,,…,}是維的歐氏空間,則的Voronoi圖定義為將個(gè)目標(biāo)劃分到多個(gè)單元中,而每個(gè)單元中只含有一個(gè)目標(biāo),由所決定的區(qū)域稱為Voronoi單元,用VOR()表示的Voronoi圖。用(,)表示空間中目標(biāo)和的距離,定義隱含了在滿足(,)<(,)時(shí)一個(gè)目標(biāo)隸屬于相應(yīng)的目標(biāo)所對(duì)應(yīng)的空間。對(duì)于一個(gè)Voronoi向量頂點(diǎn),定義里面不再含有中點(diǎn)的最大空?qǐng)A為CirU()。

對(duì)目標(biāo)進(jìn)行聚類劃分

計(jì)算并更新聚類中心

判斷循環(huán)迭代停止條件

如果迭代收斂或符合停止條件,則停止迭代;否則,令=+1,轉(zhuǎn)步驟3。

2.4 算法評(píng)價(jià)及分析

為了評(píng)價(jià)目標(biāo)分群算法的有效性,可以選取不同的評(píng)價(jià)指標(biāo)。評(píng)價(jià)指標(biāo)一般有兩類,一類是將分群結(jié)果與某個(gè)參考模型進(jìn)行比較,稱為“外部指標(biāo)”;另一類是直接考察分群結(jié)果而不利用參考模型,稱為“內(nèi)部指標(biāo)”。為了更為客觀評(píng)價(jià)目標(biāo)分群算法,這里采用CR(corrected rand)指數(shù),CR指數(shù)可以對(duì)同一個(gè)數(shù)據(jù)集的不同劃分之間的差距進(jìn)行度量。令={,…,…,}和={,…,…,}分別代表同一目標(biāo)集合的不同劃分,分別包含類和類,則CR指數(shù)定義如下:

(10)

通過分析可以看出,本文算法的時(shí)間復(fù)雜度主要包括在選取初始中心的Voronoi圖算法和自動(dòng)聚類算法的時(shí)間開銷。對(duì)于選取初始中心的Voronoi圖算法,時(shí)間復(fù)雜度為(log),而對(duì)于自動(dòng)聚類算法,其復(fù)雜度為(),其中是目標(biāo)的特征維數(shù),是目標(biāo)個(gè)數(shù),是類別數(shù),因此本文算法的總復(fù)雜度為()。

3 算法仿真

3.1 基于構(gòu)造區(qū)間數(shù)據(jù)集的算法仿真

在基于構(gòu)造區(qū)間數(shù)據(jù)集的仿真中,需要在二維實(shí)數(shù)空間中生成區(qū)間數(shù)據(jù)集。在實(shí)驗(yàn)中生成包含4類相互獨(dú)立的數(shù)據(jù)集,分別為兩類各包含300個(gè)數(shù)據(jù),一類包含150個(gè)數(shù)據(jù),一類包含90個(gè)數(shù)據(jù)。生成區(qū)間數(shù)據(jù)集首先需要產(chǎn)生區(qū)間數(shù)據(jù)的中點(diǎn)數(shù)據(jù)集,而后再根據(jù)確定的區(qū)間數(shù)半徑范圍生成區(qū)間數(shù)據(jù)的半徑,進(jìn)而構(gòu)成區(qū)間數(shù)據(jù)集。

假設(shè)每一類區(qū)間數(shù)據(jù)的中點(diǎn)由兩個(gè)服從正態(tài)分布的變量所確定,變量的均值和協(xié)方差矩陣可表示為

(11)

每一個(gè)數(shù)據(jù)點(diǎn)(,)作為區(qū)間數(shù)據(jù)集的中心點(diǎn),同時(shí)根據(jù)設(shè)定范圍生成的參數(shù)和,將其作為在軸與軸上對(duì)應(yīng)中心點(diǎn)數(shù)據(jù)的半徑,即可擴(kuò)展成一個(gè)二維區(qū)間數(shù)據(jù)([-,+],[-,+]),區(qū)間數(shù)據(jù)集半徑范圍分別為[1,5]、[1,10]、[1,15]、[1,20]。

4類數(shù)據(jù)集均值和協(xié)方差矩陣相關(guān)參數(shù)分別配置如下。

根據(jù)上述參數(shù)得到的隨機(jī)區(qū)間數(shù)據(jù)集如圖1所示。

圖1 生成的區(qū)間數(shù)據(jù)集Fig.1 Generated interval data set

圖2為生成的區(qū)間數(shù)據(jù)集的聚類結(jié)果,利用傳統(tǒng)的K-means和K-means++算法進(jìn)行了對(duì)比,采用CR指數(shù)作為評(píng)價(jià)指標(biāo),本算法得到的CR指數(shù)值如表1所示。通過表1的CR值可以看出,利用CW距離作為度量并采用基于Voronoi圖的IDCWKM算法相較于K-means和K-means++算法具有更優(yōu)的聚類效果,能夠正確將區(qū)間數(shù)據(jù)集進(jìn)行分群,CR指數(shù)值最高可達(dá)0.956 0,即使當(dāng)區(qū)間生成范圍為[1,20]時(shí),CR指數(shù)值也能達(dá)到0.952 2。通過設(shè)定不同的區(qū)間范圍,可以看出基于區(qū)間數(shù)聚類目標(biāo)分群算法能夠?qū)崿F(xiàn)對(duì)于區(qū)間目標(biāo)數(shù)據(jù)的有效聚類,證明了算法的準(zhǔn)確性。采用傳統(tǒng)的Hausdorff距離度量的K-means算法得到的CR指數(shù)值僅為0.762 3,可以看出基于CW距離進(jìn)行目標(biāo)分群的有效性。

圖2 對(duì)生成區(qū)間數(shù)據(jù)集的聚類結(jié)果Fig.2 Clustering results for generated interval data sets

表1 不同算法目標(biāo)分群的CR指數(shù)表

3.2 目標(biāo)分群應(yīng)用舉例

為了進(jìn)一步驗(yàn)證提出的基于區(qū)間數(shù)聚類目標(biāo)分群算法的有效性,設(shè)計(jì)了一個(gè)典型場(chǎng)景應(yīng)用。在此例中,假設(shè)共有60個(gè)實(shí)體目標(biāo),編號(hào)為T1～T60,目標(biāo)類型有空中目標(biāo)和海上目標(biāo)兩種,60個(gè)實(shí)體目標(biāo)根據(jù)空間屬性分為4個(gè)空間群,根據(jù)任務(wù)屬性可分為兩個(gè)任務(wù)群。想定目標(biāo)實(shí)體特征包含目標(biāo)的三維空間坐標(biāo)(,,)、目標(biāo)速度、目標(biāo)航向、雷達(dá)截面積、通信頻率,且對(duì)于想定目標(biāo)實(shí)體特性均由區(qū)間數(shù)據(jù)進(jìn)行表征,表2給出了部分目標(biāo)特性數(shù)據(jù)。目標(biāo)分群的主要任務(wù)首先是對(duì)目標(biāo)實(shí)體進(jìn)行空間分群,在此基礎(chǔ)上得到空間分群的聚類中心,進(jìn)而實(shí)現(xiàn)對(duì)目標(biāo)實(shí)體的任務(wù)分群。

表2 部分想定目標(biāo)特性區(qū)間數(shù)據(jù)

圖3為目標(biāo)空間分群二維空間顯示結(jié)果,可以看出空間中不同群目標(biāo)相互交疊,算法實(shí)現(xiàn)了把60個(gè)目標(biāo)實(shí)體的空間分群,把60個(gè)目標(biāo)分為4類,分別為空間群S1、S2、S3、S4。圖4為目標(biāo)任務(wù)分群三維空間顯示結(jié)果,可以看出算法能夠在空間分群的基礎(chǔ)上,進(jìn)一步實(shí)現(xiàn)了對(duì)目標(biāo)的任務(wù)分群,分別為任務(wù)群A1和A2。為了評(píng)價(jià)算法的有效性,采用CR指數(shù)和準(zhǔn)確率作為評(píng)價(jià)指標(biāo),具體數(shù)據(jù)如表3所示?？梢钥闯隼脗鹘y(tǒng)距離度量的目標(biāo)分群K-means算法CR指數(shù)值為0.488 5,準(zhǔn)確率僅為74.2%,而本文提出的基于區(qū)間數(shù)聚類的目標(biāo)分群IDCWKM算法實(shí)現(xiàn)的目標(biāo)空間分群和任務(wù)分群結(jié)果與設(shè)定相一致,CR指數(shù)值為1,準(zhǔn)確率為100%。由此可以看出算法對(duì)于典型場(chǎng)景目標(biāo)分群的有效性。

圖3 目標(biāo)空間分群二維空間結(jié)果Fig.3 Result of target space grouping in two dimensional space

圖4 目標(biāo)任務(wù)分群三維空間結(jié)果Fig.4 Result of target task grouping in three dimensional space

表3 目標(biāo)分群有效性對(duì)比

4 結(jié) 論

態(tài)勢(shì)認(rèn)知是指揮控制活動(dòng)從信息域向認(rèn)知域跨越的重要標(biāo)志。本文針對(duì)態(tài)勢(shì)認(rèn)知的關(guān)鍵問題,提出了一種基于區(qū)間數(shù)聚類的目標(biāo)分群算法。對(duì)于傳感器測(cè)量數(shù)據(jù)具有誤差、不完全等問題,采用區(qū)間數(shù)對(duì)傳感器探測(cè)到的目標(biāo)進(jìn)行描述。目標(biāo)分群是態(tài)勢(shì)認(rèn)知的基礎(chǔ)環(huán)節(jié),本質(zhì)上可看作是一個(gè)聚類問題,對(duì)于聚類問題首先要給出相應(yīng)的度量,針對(duì)目標(biāo)區(qū)間數(shù)特征定義了CW度量距離,CW距離能充分利用區(qū)間數(shù)所包含的信息,在此基礎(chǔ)上提出了IDCWKM目標(biāo)分群算法。為了驗(yàn)證算法的有效性,首先通過構(gòu)造區(qū)間數(shù)據(jù)集進(jìn)行目標(biāo)分群,在二維實(shí)數(shù)空間生成4類相互獨(dú)立的數(shù)據(jù)集。仿真結(jié)果表明，所提算法能夠?qū)ι傻膮^(qū)間數(shù)據(jù)進(jìn)行準(zhǔn)確分類;其次通過典型想定場(chǎng)景,設(shè)定多類目標(biāo)實(shí)體,并根據(jù)目標(biāo)空間位置、運(yùn)動(dòng)特征和屬性等要素進(jìn)行空間分群和任務(wù)分群,算法能夠?qū)Χ囝惸繕?biāo)進(jìn)行準(zhǔn)確分群。需要指出的是,由于數(shù)據(jù)的不完整、不確定以及目標(biāo)特征的局限性,分群結(jié)果會(huì)存在一定的誤差,對(duì)于多種場(chǎng)景下態(tài)勢(shì)要素智能計(jì)算及目標(biāo)分群問題將是下一步的研究重點(diǎn)。