一種基于改進K-means 算法的空間群劃分方法

湯 奮，游 雄，李 欽，王瑋琦，唐錦波

（1.信息工程大學(xué)，鄭州 450000；2.解放軍75838 部隊，廣州 510000）

0 引言

高技術(shù)戰(zhàn)爭條件下，戰(zhàn)爭周期縮短，戰(zhàn)爭節(jié)奏加快，面對海量實時的戰(zhàn)場數(shù)據(jù)，指揮員能否快速對戰(zhàn)場態(tài)勢作出合理估計，明確敵方意圖，對戰(zhàn)爭勝負至關(guān)重要。兵力分群是將兵力按照一定的層次結(jié)構(gòu)進行劃分，以提高指揮員的態(tài)勢認知效率。兵力分群結(jié)果的優(yōu)劣，對后續(xù)的意圖識別和威脅估計等準確性和可靠性有重要影響［1］。兵力分群按低級到高級分為5 個層次［2-4］，分別是兵力對象、空間群、功能區(qū)、相互作用群和敵方/我方/中立方群。由此可見，空間群劃分是兵力分群的重要環(huán)節(jié)。

張緒亮、龍真真、劉潔莉、王曉璇、胡艮勝、孫亮［1，5-9］等人，以實際兵力或者虛擬兵力的對象，開展了空間群劃分的研究。通過分析發(fā)現(xiàn)，空間群劃分的關(guān)鍵之處在于兩點：一是構(gòu)造作戰(zhàn)單元間的“距離”函數(shù)，涉及兵力作戰(zhàn)單元的屬性信息選取及其權(quán)重的確定；二是合理確定分群數(shù)目和聚類中心，其本質(zhì)是一個算法選擇和參數(shù)優(yōu)化問題。目前多數(shù)研究都集中在這兩個方面，并積累了一定的成果，其中張緒亮通過顧及敵方兵力作戰(zhàn)單元的機動速率、機動方向和空間距離以及可能的進攻目標，對K-means 算法的距離函數(shù)進行了改進，并能實現(xiàn)分群數(shù)目的自適應(yīng)選取，但不足之處是初始聚類中心的選取依然是隨機的。對K-means算法而言，不同的初始聚類中心可能會產(chǎn)生不同的聚類結(jié)果，從而使得分群結(jié)果不穩(wěn)定，與實際情況不符。因此，需對現(xiàn)有用于空間群劃分的K-means 算法進行改進，以提高空間群劃分結(jié)果的穩(wěn)定性。

1 空間群劃分的概念

2 面向空間群劃分的K-means 算法改進方案

K-means 算法是一種基本的聚類分析算法，算法簡單，收斂速度快［2］，其具體流程此處不再詳述。為了取得最佳聚類結(jié)果，該算法需取不同的K 值和不同的初始值聚類中心進行多次嘗試，且最終的聚類結(jié)果還可能不同。為此，當利用該算法進行空間群劃分時，需對其進行改進。首先利用文獻［5］所提出的改進距離度量函數(shù)來計算“距離”，然后引入了一種快速搜尋高密度點的方法，該方法在確定空間群最佳劃分數(shù)目的同時，還能確定初始聚類中心，使空間群劃分結(jié)果不隨初始聚類中心的變化而波動，提高了分群結(jié)果的穩(wěn)定性。

2.1 距離度量函數(shù)

傳統(tǒng)K-means 算法是基于歐式距離進行聚類的，考慮空間群劃分的特殊性，通常還需考慮目標的機動方向與速率、可能目的地和空間距離進行綜合考慮，為此，此處使用了文獻［5］中的距離度量函數(shù)（距離函數(shù)并非本文創(chuàng)新點）。設(shè)表示敵方作戰(zhàn)單元ai與我方目標bj在某一時間段內(nèi)的夾角；δij表示ai與bj之間的距離參數(shù)；令φij=cos（），則定義進攻關(guān)系函數(shù)Pij=φij*δij。假設(shè)當前作戰(zhàn)地域內(nèi)，敵方進攻作戰(zhàn)單元數(shù)為n，我方防御作戰(zhàn)單元數(shù)為m，那么就可構(gòu)建一個由Pij組成的n×m 的進攻關(guān)系隸屬度矩陣P［5］：

2.2 確定初始聚類中心和聚類數(shù)目

此處引入了一種快速搜尋高密度點，以確定聚類中心和聚類數(shù)目的方法［10］，下面對該方法進行描述。該方法巧妙利用了聚類中心必須同時具備的兩個特點：一是本身的密度大，即它的密度大于周圍一定范圍內(nèi)的數(shù)據(jù)點的密度；二是與其他密度更大的數(shù)據(jù)點之間的“距離”更大。下面將利用上述兩個特點來識別聚類中心的方法進行數(shù)學(xué)描述。

其中函數(shù)

參數(shù)dc＞0 為截斷距離，需事先指定。由式（1）［10］可知，ρi表示S 中與xi之間的距離小于dc的數(shù)據(jù)點（除去xi本身）的個數(shù)。

則可定義

圖1 二維數(shù)據(jù)點

圖2 二維數(shù)據(jù)點的ρ-δ 圖

2.3 面向空間群劃分的改進K-means 算法

本算法假設(shè)待分群的敵方兵力作戰(zhàn)單元基本屬性：部隊級別、軍種類型和隸屬編制軍都相同，主要依據(jù)兵力作戰(zhàn)單元的空間屬性和速度進行空間群劃分。通過上述兩小節(jié)，面向空間群劃分的改進K-means 算法流程如下：

3 實驗與分析

某平原地形上，我方傳感器探知敵方15 個連規(guī)模的作戰(zhàn)單元，正向我方兩個營（作戰(zhàn)單元1 和作戰(zhàn)單元2）所負責(zé)的防御陣地移動，準備對我發(fā)起進攻，但主攻方向不明。通過傳感器進一步探測得到敵方15 個連在某一時刻的坐標和速度，如下頁表1 所示，其中X、Y、U、V 分別表示敵方各連的橫坐標、縱坐標、速度的水平分量、速度的垂直分量，其矢量形式如圖3 所示。

我方兵力作戰(zhàn)單元1、兵力作戰(zhàn)單元2 的坐標分別為（0.3，12.8）、（0.8，5.8）。利用結(jié)合2.3 節(jié)中的改進算法，可計算出敵方各個作戰(zhàn)單元映射到空間S 中的新坐標（Pi1，Pi2），以及局部密度ρi和距離δi，如表2 所示。

利用表2，繪制“ρ-δ”決策圖，如圖4 所示。根據(jù)2.2節(jié)確定聚類數(shù)目和聚類中心的方法，圖4 中作戰(zhàn)單元2 和作戰(zhàn)單元15 符合初始聚類中心的特征，可取這兩個為聚類中心，進而也確定了聚類數(shù)目K取值為2。在此基礎(chǔ)上，利用各點映射到S 空間中的新坐標值，就可通過K-means 算法計算出相應(yīng)的聚類結(jié)果。進過多次重復(fù)實驗，15 個敵方兵力作戰(zhàn)單元所屬的類別均保持一致，如表2 第6 列所示，最終聚類結(jié)果如圖5 所示。

表1 敵方單元坐標數(shù)據(jù)（km）及速度（km/h）

圖3 各點坐標及其速度的矢量表達形式

表2 映射到S 空間的坐標值和ρ-δ 值及分群結(jié)果

圖4 “ρ-δ”決策圖

分群的結(jié)果是，圖5 中進攻我方單元1 的敵方作戰(zhàn)單元分為了一個群，圖中用藍色對其進行了表示；進攻我方單元2 的敵方作戰(zhàn)單元分為了另一個群，圖中用綠色對其進行了表示。由圖5 可知，仿真實驗的分群結(jié)果與實際情況相符，正確體現(xiàn)了作戰(zhàn)單元屬性（機動方向與速率、空間距離、進攻目標）對分群結(jié)果的影響，表明該方法能夠較好地實現(xiàn)戰(zhàn)場敵軍兵力的空間群劃分。

圖5 最終聚類結(jié)果

4 結(jié)論

本文以提高空間群劃分結(jié)果的穩(wěn)定性為目標，對現(xiàn)有用于空間群劃分的K-means 算法進行了改進。針對當前算法無法確定初始聚類中心的問題，引入了文獻［10］中的一種新的方法，并利用已有的距離改進函數(shù)，對所引入的方法進行了適用性改造，實現(xiàn)了分群數(shù)目K 和初始聚類中心的確定，在此基礎(chǔ)上利用K-means 算法對空間群劃分進行了仿真實驗，仿真結(jié)果符合實際情況，并實現(xiàn)了提高空間群劃分結(jié)果的穩(wěn)定性的目標。

需要指出的是，對海上和空中的兵力作戰(zhàn)單元進行空間群劃分時，地理和地形環(huán)境因素對其影響不大，而陸地上的空間群劃分則受到戰(zhàn)場地理、地形環(huán)境要素的影響和制約，因此，下一步的工作還需將地理、地形環(huán)境要素對兵力分群的影響考慮進去，從而得出更為可信的空間群劃分結(jié)果。