基于區間數聚類的目標分群算法

王海濱, 關 欣, 衣 曉

(海軍航空大學, 山東 煙臺 264001)

0 引 言

態勢認知是指揮控制活動的核心環節,是有效決策和正確行動的前提和基礎。目標分群作為態勢認知的重要基礎,其主要作用是綜合考慮目標位置、速度、屬性等要素,將各類傳感器觀測到的目標信息按照一定的規則進行劃分,得到相應的分群結果,進而有助于發現目標各類戰術意圖。

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

1 區間數描述方法

在態勢認知過程中,需要對接收到的目標實體數據進行分析,以估計要素之間的關系,進而建立要素之間的結構。由于測量、計算所帶來的數據誤差,同時由于信息不完全帶來的數據缺乏,使得接收到的目標數據往往是一些不確定的數,因此采用區間數來表示這些具有不確定性的目標數據更符合人類的思維方式,相對于實數表示也更貼近實際。

設表示一個非空集合,對于任意,∈,若存在實泛函::×→滿足下述條件:

(1) 正定性

(,)≥0,(,)=0,當且僅當=;

(2) 對稱性

(,)=(,);

(3) 三角不等式

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

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

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

(1)

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

2 基于區間數聚類目標分群算法

2.1 問題描述

(2)

對于給定的待分類目標,用表示對其進行的劃分,一個劃分則對應著一個目標分群結果。實質上劃分是一個多對一的函數。如果將每個待分類的目標用一個整數∈{1,2,…,}表示,每個分群也用一個整數表示為∈{1,2,…,},那么對于待分類目標的分群就可以描述為=()。所以目標分群聚類的模型可以看成為從目標集到分群,,…,上的泛函。

2.2 區間數及區間向量的距離度量

(3)

(4)

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

(1) 正定性

(2) 對稱性

(3) 三角不等式

證畢

(5)

2.3 IDCWKM目標分群算法

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

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

這樣對于目標集合分群的關鍵就是找到一個合理的劃分,能夠將劃分為,,…,和一系列區間均值向量{,,…,},得到最小化聚類誤差:

(6)

式中：

(7)

(8)

目標分群算法是一個迭代的過程,每次迭代包含兩個步驟,首先是選擇個類的中心,將待分類目標逐個并入與其距離最近的類,這樣就得到一個聚類結果;然后更新聚類中心;重新計算每個目標與新的聚類中心的距離,重復以上步驟,直到聚類劃分不再改變為止。具體過程如下。

數據標準化

(9)

分配初始聚類中心值

目標集={,,…,}是維的歐氏空間,則的Voronoi圖定義為將個目標劃分到多個單元中,而每個單元中只含有一個目標,由所決定的區域稱為Voronoi單元,用VOR()表示的Voronoi圖。用(,)表示空間中目標和的距離,定義隱含了在滿足(,)<(,)時一個目標隸屬于相應的目標所對應的空間。對于一個Voronoi向量頂點,定義里面不再含有中點的最大空圓為CirU()。

對目標進行聚類劃分

計算并更新聚類中心

判斷循環迭代停止條件

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

2.4 算法評價及分析

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

(10)

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

3 算法仿真

3.1 基于構造區間數據集的算法仿真

在基于構造區間數據集的仿真中,需要在二維實數空間中生成區間數據集。在實驗中生成包含4類相互獨立的數據集,分別為兩類各包含300個數據,一類包含150個數據,一類包含90個數據。生成區間數據集首先需要產生區間數據的中點數據集,而后再根據確定的區間數半徑范圍生成區間數據的半徑,進而構成區間數據集。

假設每一類區間數據的中點由兩個服從正態分布的變量所確定,變量的均值和協方差矩陣可表示為

(11)

每一個數據點(,)作為區間數據集的中心點,同時根據設定范圍生成的參數和,將其作為在軸與軸上對應中心點數據的半徑,即可擴展成一個二維區間數據([-,+],[-,+]),區間數據集半徑范圍分別為[1,5]、[1,10]、[1,15]、[1,20]。

4類數據集均值和協方差矩陣相關參數分別配置如下。

根據上述參數得到的隨機區間數據集如圖1所示。

圖1 生成的區間數據集Fig.1 Generated interval data set

圖2為生成的區間數據集的聚類結果,利用傳統的K-means和K-means++算法進行了對比,采用CR指數作為評價指標,本算法得到的CR指數值如表1所示。通過表1的CR值可以看出,利用CW距離作為度量并采用基于Voronoi圖的IDCWKM算法相較于K-means和K-means++算法具有更優的聚類效果,能夠正確將區間數據集進行分群,CR指數值最高可達0.956 0,即使當區間生成范圍為[1,20]時,CR指數值也能達到0.952 2。通過設定不同的區間范圍,可以看出基于區間數聚類目標分群算法能夠實現對于區間目標數據的有效聚類,證明了算法的準確性。采用傳統的Hausdorff距離度量的K-means算法得到的CR指數值僅為0.762 3,可以看出基于CW距離進行目標分群的有效性。

圖2 對生成區間數據集的聚類結果Fig.2 Clustering results for generated interval data sets

表1 不同算法目標分群的CR指數表

3.2 目標分群應用舉例

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

表2 部分想定目標特性區間數據

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

圖3 目標空間分群二維空間結果Fig.3 Result of target space grouping in two dimensional space

圖4 目標任務分群三維空間結果Fig.4 Result of target task grouping in three dimensional space

表3 目標分群有效性對比

4 結 論

態勢認知是指揮控制活動從信息域向認知域跨越的重要標志。本文針對態勢認知的關鍵問題,提出了一種基于區間數聚類的目標分群算法。對于傳感器測量數據具有誤差、不完全等問題,采用區間數對傳感器探測到的目標進行描述。目標分群是態勢認知的基礎環節,本質上可看作是一個聚類問題,對于聚類問題首先要給出相應的度量,針對目標區間數特征定義了CW度量距離,CW距離能充分利用區間數所包含的信息,在此基礎上提出了IDCWKM目標分群算法。為了驗證算法的有效性,首先通過構造區間數據集進行目標分群,在二維實數空間生成4類相互獨立的數據集。仿真結果表明，所提算法能夠對生成的區間數據進行準確分類;其次通過典型想定場景,設定多類目標實體,并根據目標空間位置、運動特征和屬性等要素進行空間分群和任務分群,算法能夠對多類目標進行準確分群。需要指出的是,由于數據的不完整、不確定以及目標特征的局限性,分群結果會存在一定的誤差,對于多種場景下態勢要素智能計算及目標分群問題將是下一步的研究重點。