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

王紅勇，許 平

（中國民航大學(xué)天津市空管運行規(guī)劃與安全技術(shù)重點實驗室,天津 300300）

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

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

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

1 軌跡數(shù)據(jù)預(yù)處理

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

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

在某一空域內(nèi)，航空器可視為一個質(zhì)點。將扇區(qū)內(nèi)的航空器位置、速度的集合表達為下列矩陣：

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

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

2 航空器群的識別

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

圖1 航空器群示意

2.1 聚類算法

本算法步驟如下。

Step1 定義初始航空器群。將扇區(qū)內(nèi)每一架航空器Wn視為一個初始航空器群Gn。

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

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

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

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

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

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

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

Step6 畫譜系圖。根據(jù)以上5 步的結(jié)果畫出聚類譜系圖。

Step7 確定聚類結(jié)果。通過計算畸變程度選取響應(yīng)的最優(yōu)聚類群數(shù)量確定最終的聚類結(jié)果。

2.2 聚類結(jié)果確定

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

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

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

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

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

3 航空器群的評價指標

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

3.1 位置內(nèi)聚度

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

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

群內(nèi)航空器的平均間距相對于扇區(qū)中所有航空器的平均間距越小，說明航空器群內(nèi)的連接越緊密，群的內(nèi)聚程度就越高，所對應(yīng)的群結(jié)構(gòu)越佳。

3.2 航向輪廓系數(shù)

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

式中，n為航空器群內(nèi)航空器的數(shù)量。

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

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

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

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

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

式中：Cw為扇區(qū)內(nèi)不包含航空器u的航空器群w；nw為航空器群w內(nèi)航空器的數(shù)量。

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

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

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

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

4 算例分析

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

4.1 聚類算法

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

表1 4 月12 日18:58 雷達數(shù)據(jù)

根據(jù)表中的雷達數(shù)據(jù)信息，可得到航空器在扇區(qū)內(nèi)的空間分布圖，如圖2 所示。

圖2 航空器雷達位置圖

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

圖3 譜系圖

圖4 層次聚類群劃分圖

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

圖5 k-means 群劃分圖

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

4.2 指標分析

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

圖6 18：58 指標結(jié)果圖

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

圖7 1h 指標圖

5 結(jié)論

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