基于層次聚類的航空器群識別方法

王紅勇，許 平

（中國民航大學天津市空管運行規劃與安全技術重點實驗室,天津 300300）

空中交通管理系統最根本的任務是保障空域內航空器的安全，當管制扇區內出現小范圍內航空器聚集的情況時，管制員需要付出更多的精力來判斷航空器的運行狀態，從而避免發生間隔丟失甚至碰撞。面對日益增長的空中交通服務需求，管制員的服務能力與效率正面臨巨大的挑戰，因此如何描述航空器的聚集情況和運行狀況，從而量化不同交通態勢給管制員帶來的工作負荷顯得非常重要。目前，國內外學者主要用空中交通復雜性來刻畫不同的空中交通態勢。

不同空中交通復雜性直接呈現的結果就是管制員的工作負荷差異，因此有學者將靜態扇區空域結構及動態交通流特征作為空中交通復雜性的基本指標來評估管制員的工作負荷[1?3]。扇區空域結構包括扇區的形狀、大小等空域因素及扇區的航路數量、長度、走向、交叉點的數量等航路航線因素。交通流特征包括進入或離開扇區的飛機數量、平均通過時間、航空器的沖突數量、爬升航空器比例、下降航空器比例等因素。通過對各種指標的綜合量化從而刻畫空中交通復雜性。也有一些學者從航空器最基本的內稟性特征（如相對距離及速度）出發，通過量化航空器對的相對運動狀態來刻畫空中交通復雜性。Delahaye 等[4?6]最早提出內稟性的概念，并且通過動態系統進一步對空中交通復雜性進行計算分析。張進等[7?8]、王紅勇等[9]、徐肖豪等[10]在Delahaye 研究的基礎上進一步提出運用復雜性學科的思想，提出了綜合迫近、幾率和連攜因素的二維及三維復雜性模型。Hansman 等[11?12]提出空中交通復雜性包括環境復雜性、認知復雜性和感知復雜性。其中，環境復雜性是空域中各種結構靜態復雜性的集合，認知復雜性是管制員對靜態結構分析處理的難度，感知復雜性則是完成沖突調配等針對認知復雜性的實際操作難度。

以上研究從不同角度對空中交通復雜性進行了分析。John Hansman 為了解決之前的研究只考慮扇區靜態結構來衡量復雜性而未考慮管制員認知難度的問題，提出了航空器群的概念。管制員通過對實際的交通流抽象形成認知中的空中交通狀況，通過塑造扇區內航空器的預計軌跡和預定航線，形成空域中基礎結構限制。管制員通過結構抽象來減少需要評估運行狀態的航空器數量，即通過工作思維模型來簡化認知的交通流模型，將扇區內大量的航空器分為若干數量較少、運行狀態相似的航空器群，從而輔助管制員高效率地分析扇區內航空器的運行狀態，降低管制員對交通流結構的認知復雜性。本文在傳統k-means 算法基礎上，通過改進層次聚類算法實現不同航向航空器群的自動識別，并進一步通過位置內聚度和航向輪廓系數分析航空器群的識別效果，通過與傳統k-means 方法作對比，驗證本文方法的有效性。

1 軌跡數據預處理

實際的雷達數據為一系列連續、相同時間時隔的點集，表示為：P=(P1,P2,···,Pn)，其中P表示某一架航空器的飛行軌跡，Pi=(xi,yi,zi),其中xi,yi,zi分別為某一時刻該航空器的橫、縱、高度坐標。通過對雷達數據的處理，我們可以得到某一時刻的航空器橫縱坐標、速度大小和航向。

由于管制員雷達顯示屏僅根據航空器的橫縱坐標顯示相應的位置，不同高度層但水平坐標相近的航空器也會因為雷達標牌重疊等原因增加管制員認知復雜性，因此本文僅考慮航空器橫縱坐標作為聚類的位置坐標。為了識別位置相近、速度相似的航空器群，本文將位置、速度信息都作為區分航空器群的要素。

在某一空域內，航空器可視為一個質點。將扇區內的航空器位置、速度的集合表達為下列矩陣：

式中：W為航空器信息的集合；Wn為扇區內第n架航空器的信息；xn、yn為第n架航空器的橫、縱位置坐標；vn、θn為第n架航空器的速度大小和航向。

由于每架航空器位置與速度信息的單位不同，需對數據進行標準化處理。

2 航空器群的識別

管制員對交通流的認知抽象先是根據工作模式將扇區內的航空器形成預計航線，再把位置相近、航向相似的航空器歸為一個航空器群，從而降低分析交通流特征的認知復雜性。如圖1 所示，航空器1、2、3 位置相近，航空器2、3 航向相近，航空器1 與2、3 航向相反。在管制員的認知中，將運行狀態相似的2 和3 航空器歸為一個航空器群將降低管制員對于交通態勢判斷的復雜程度。傳統以位置進行聚類確定航空器群的方法可能出現將1、2、3 航空器都歸為一個航空器群，航空器4、5 歸為另一個航空器群。在管制員的實際操作中，該方法識別出航空器群之后還需要管制員再去判斷航空器群內各航空器的運行狀態，降低管制員認知復雜性的效果不明顯。相比之下，識別出群內航空器速度相近、相對距離較短的航空器群在研究管制員認知復雜性中更有優勢。

圖1 航空器群示意

2.1 聚類算法

本算法步驟如下。

Step1 定義初始航空器群。將扇區內每一架航空器Wn視為一個初始航空器群Gn。

Step2 計算距離。采用歐式空間距離，計算扇區內所有不同航空器i與航空器j之間的距離，公式如下：

計算結果記為距離矩陣D(0)。

Step3 合并航空器群。在距離矩陣D(0)中尋找最小元素，記作：

將GO和GP合并為一個新的航空器群GQ，即GQ={GO，GP}

Step4 重新計算集合間的最小距離。計算新航空器群GQ與合集中其他航空器群GE的距離：

將計算結果對距離矩陣D(0)進行更新，將Gi和Gj所在的行列分別合并到一個新的行列。對于GE，新的與其他航空器群的距離由上式計算結果進行更新，其他行列不變。記新得到的距離矩陣為D(1)。

Step5 循環計算。對距離矩陣D(1)重復步驟（3）和（4），得到新的矩陣D(2)，如此循環，直至所有航空器群合并為一個航空器群為止。

Step6 畫譜系圖。根據以上5 步的結果畫出聚類譜系圖。

Step7 確定聚類結果。通過計算畸變程度選取響應的最優聚類群數量確定最終的聚類結果。

2.2 聚類結果確定

采用肘部法則對聚類算法結果的譜系圖進行結果分析。

畸變程度定義為某航空器群質心與其他航空器位置距離的平方和。假設將n個航空器劃分到K個航空器群中（K≤n?1，即至少有一個航空器群中有兩架航空器），用Ck表示第k個航空器群（k=1,2，···，K），且該航空器群質心的位置記為Uk，則第k個航空器群的畸變程度為：

所有航空器群的總畸變程度定義為聚合系數，記作J，表示為

則n個航空器的所有聚合系數為J=(J1,J2,···,Jn)，J1>J2>···>Jn。

定義J(i)=Ji?Ji+1(i=1,2···,n?2)，為聚類結果i的畸變趨勢，若J(n)=min{J(i)}，則最優聚類航空器群個數為n。

3 航空器群的評價指標

航空器群作為管制員對交通流特征的認知抽象，識別出的航空器群的合理性、有效性需要一個評價準則。由于劃分航空器群的目的是輔助管制員監視相應空域，減少管制員對于扇區運行狀態的認知難度，因此航空器群內的航空器運行狀態越相似，對管制員的輔助效果越好。為了評價航空器群內航空器的位置、速度指標，采用位置內聚度和速度輪廓系數來評價航空器群的聚類效果。

3.1 位置內聚度

采用位置內聚度來評價航空器群內部航空器之間的位置情況[13]，定義如下：

式中：Ci為第i個航空器群的位置內聚度值；Di為第i個航空器群內所有航空器之間的平均距離；D為扇區內所有航空器之間的平均距離。設duv為航空器u、v之間的距離，ni為第i個航空器群內航空器的數量，n為扇區內航空器的數量，則Di和D計算公式如下：

群內航空器的平均間距相對于扇區中所有航空器的平均間距越小，說明航空器群內的連接越緊密，群的內聚程度就越高，所對應的群結構越佳。

3.2 航向輪廓系數

對于位置相近的航空器群，不同群內的航空器速度差異越大，航空器群的劃分效果越好。定義航向的評價指標為航向輪廓系數，記航空器群i的航向輪廓系數為S i，表示為

式中，n為航空器群內航空器的數量。

記標準化后的第n架航空器速度信息為，記航空器i與航空器j之間的速度距離為vdij,采用歐氏距離計算兩架航空器之間的速度距離，公式如下：

記航空器u到所在航空器群的其他航空器的速度平均距離為a(u)，公式如下：

航空器群i的速度平均距離為Ai，公式如下：

Ai越小，說明航空器群i內航空器速度值越相似。

記航空器u到其他航空器群的所有航空器的速度平均距離的最小值為b(∑u),公式如下：

式中：Cw為扇區內不包含航空器u的航空器群w；nw為航空器群w內航空器的數量。

航空器群i到其他航空器群的速度平均距離的最小值為Bi，公式如下：

Bi越大，說明航空器群i與其他航空器群的速度差異越大。

記航空器u的航向輪廓系數為S(u)，表示為

S i的值介于[?1,1]之間，越接近于1 說明Bi越大Ai越小，航空器群內速度越相似，航空器群之間速度差異越大；越接近于0 說明航空器群內部和外部之間的速度類似，分界線很不明顯；越接近于?1 說明航空器群之間速度越相似，航空器群內速度反而不相似。

4 算例分析

為了驗證聚類算法的有效性，選取上海1 號扇區的實際數據進行分析。具體過程為：首先采用本文層次聚類算法對某個時刻的扇區航空器態勢進行航空器群劃分，根據聚合系數自動選取最優的航空器群數量，并畫出相應的譜系圖；再選取K-means方法進行對比，設定其聚類數量為本文選取的最優航空器群，并對兩種劃分方法的位置內聚度、航向輪廓系數進行分析。

4.1 聚類算法

以上海1 號扇區2021 年4 月12 日18:58 雷達數據為例，該扇區內航班的航班號、橫縱坐標、速度值、航向如表1 所示。

表1 4 月12 日18:58 雷達數據

根據表中的雷達數據信息，可得到航空器在扇區內的空間分布圖，如圖2 所示。

圖2 航空器雷達位置圖

根據本文中的聚類算法對上述時刻的航班信息分析可知，最小畸變趨勢值為0.307849，對應最佳航空器群數為4。因此，此時扇區內10 架航空器共被分為4 個航空器群，分別為：CSH9454、CSH9086 和CSC8153 的距離和速度相近，可歸為一個航空器群；CQH8931、CSN3374 和DKH1394歸為一個航空器群；ANA858 和LKE9731 歸為一個航空器群；CSH831 和CSH9313 歸為一個航空器群。其中：CSH9454、CSH9086 與CQH8931、CSN3374雖然位置相近，但是航向差異過大，未被歸為一個航空器群；DKH1394 與CSC8153 同樣由于航向差異過大未被歸為一個航空器群。聚類譜系圖及航空器群的位置圖如圖3—4 所示。

圖3 譜系圖

圖4 層次聚類群劃分圖

將聚類群數量設置為4，采用k-means 算法重新計算，劃分結果如圖5 所示。

圖5 k-means 群劃分圖

ANA858、LKE9731 與CSH831、CSH9313 分別被歸為一個航空器群，計算結果與層次聚類相同。另外兩個航空器群的航班不完全相同，航空器群3 和4 中航空器位置相對集中，符合聚集的基本要求，但是航空器群內部航班航向差異過大。由此得到的航空器群只是基于位置映射給管制員的最基本認知，沒有進一步縮減交通流的結構，在實際操作中，管制員還需要針對航空器群3 和4 分別判斷內部航空器運行狀態。相較之下，優化后的層次聚類算法已經自動完成航向的結構縮減，從而降低管制員的認知復雜性。

4.2 指標分析

在完成聚類算法之后，根據所得到的航空器群劃分結果，分別計算兩種方法中對應的位置內聚度Ci、航空器群i的速度平均距離Ai、航空器群i到其他航空器群的速度平均距離的最小值Bi及航空器群i的航向輪廓系數Si。時刻18：58 及之后以6min為步長共1h 的結果如圖6—7 所示。

圖6 18：58 指標結果圖

由圖6 可知，兩種方法Ci大致相等。對比群內速度平均距離Ai，航空器群1 和3 的速度平均距離Ai基本相等，航空器群2 和4 的k-means 算法所得的值明顯偏大。Ai值越小，說明航空器群內速度越相似，由此可知，層次聚類保持群內速度相似的表現較好。對比群外速度平均距離的最小值Bi，航空器群1 和3 中k-means 所得的值遠大于層次聚類，航空器群4 中層次聚類略大于k-means。Bi值越大，說明航空器群間的速度差異越大。而我們注意到，層次聚類所得的航空器群1 和2 的Bi值基本相等，也就是說兩群之間的速度幾乎沒有差異，但是卻被分為兩個不同的航空器群，說明層次聚類能夠很好地區分位置相對較遠速度一致的航空器，并分到不同的航空器群中。對比航向輪廓系數S i，觀察到層次聚類所得的航空器群S i結果更優。由圖7觀察1h 的數據可知，對比兩種方法的位置內聚度Ci可得到其取值范圍基本在[0.6，0.8]之間。位置內聚度Ci越接近1，說明劃分的群內航空器的聚集程度越接近于扇區標準水平。兩種方法劃分的位置內聚度都低于1，說明劃分的航空器群基本滿足位置相對聚集的要求，具有實際意義。此外，層次聚類的Ci高于k-means。觀察S i值層次聚類基本穩定在[0.5,0.8]，而k-means 中的S i值在[?1,1]中無規律跳動。S i值越接近于1，航空器群速度越相似、位置越聚集，群之間差異越明顯；S i值越接近于?1，說明劃分效果越差。由此可知，層次聚類在航向劃分的綜合表現中優于k-means，且更加穩定。

圖7 1h 指標圖

5 結論

針對研究空中交通復雜性中認知復雜性的航空器群識別問題，本文提出了在結構縮減中需要綜合考慮位置和航向來模擬管制員對交通流結構的認知抽象，并利用層次聚類算法，通過改進聚類結果的自動選取方式，實現了扇區內航空器群的自動識別。同時，航向因素的加入使得算法能夠區分位置相近速度差異明顯的航空器，使劃分結果更加貼近管制員的認知。此外，還避免了傳統劃分方法需要人為設定群數量的缺點。從位置內聚度、航向輪廓系數提出了群劃分指標用于反映群劃分效果。通過對上海扇區實際雷達數據分析，結果表明在識別位置聚集、速度相近的航空器中，本文提出的層次聚類算法相較于傳統方法劃分效果更優，且算法更加穩定。這對于研究管制員認知復雜性及交通流結構縮減具有十分重要的意義。