基于核主成分分析的空域復雜度無監督評估

張矚熹，朱熙，朱少川，張明遠，杜文博

1.北京航空航天大學 綜合交通大數據應用技術國家工程實驗室，北京 100083 2.中國人民解放軍32751單位 3.北京航空航天大學 前沿科學技術創新研究院，北京 100083 4.北京航空航天大學 交通科學與工程學院，北京 100083 5.北京航空航天大學 電子信息工程學院，北京 100083

隨著全球經濟一體化的推進，世界航空運輸蓬勃發展。中國航空運輸產業增長尤為迅猛。2017年，中國航班執行總量超過500萬架次[1]，近五年年均增長率接近10%[1-2]。航空運輸蓬勃增長的同時，也給空中交通管理系統帶來了嚴峻的挑戰。當前空管系統將空域劃分為若干扇區，每個扇區的交通疏導由一位管制員負責。若扇區的空域復雜度超出管制員的管制能力，則極易導致空中交通安全事件發生，例如2014年的武漢機場管制員“睡崗”事件與2016年因管制失誤導致的上海虹橋機場跑道入侵事件[3-4]。因此，空域復雜度評估是保障航空交通安全運行的前提與基礎。

由于影響空域復雜度的動靜態因素眾多(涵蓋扇區/航路航線/限制區等空域要素、飛行性能/飛行任務/飛行狀態等航空器要素、風/云/降水/能見度等氣象要素、通信/導航/監視等設備要素)，不同因素對復雜度的影響機理不同，且因素間耦合關系極為復雜，因此空域復雜度的準確評估被公認為航空領域的挑戰性問題。

針對空域復雜度評估，國內外學者提出了多種方法，這些方法可分為兩類。第一類方法是從單一角度來定義空域復雜度，代表性工作包括米蘭理工大學Prandini教授等提出的航班沖突概率指標[5-6]、法國國立民航大學Delahaye教授等提出的Lyapunov指數指標[7-8]，南京航空航天大學張進等提出的迫近及連攜度指標[9]。此類方法往往會給出明確的復雜度計算公式，但計算角度的單一性導致對復雜度的度量較為片面。第二類方法是綜合多種因素提取高層復雜度指標，代表性方法包括線性回歸、機器學習。線性回歸方法通過線性加權多復雜度因素獲得復雜度值[10-11]，但由于因素與復雜度間非線性關聯，此類線性模型往往不夠準確。相比之下，機器學習模型能夠構建因素與復雜度間的非線性關聯[12-16]，是目前準確度較高的空域復雜度評估方法。

但是，現有基于機器學習的空域復雜度評估模型的性能嚴重依賴標定樣本。而空域復雜度的樣本標定需要空中交通管制專家在細致查看管制信息的基礎上進行人工標定，獲取成本很高。另一方面，由于空域靜態結構與運行機理的動態演變，已有標定樣本會陸續過期，當需要訓練新的復雜度評估模型時，很難保證有標定樣本可用。本文提出了一種不依賴標定樣本的扇區復雜度無監督評估方法。首先，根據扇區復雜度樣本特點，采用核主成分分析(Kernel-based Principal Component Analysis，KPCA)對包含了多種因素的高維原始樣本進行非線性降維，獲得最大化復雜度評估信息量的主成分。然后根據實際空管業務需求，通過對降維后樣本進行定制化聚類，獲得各條樣本對應的復雜度等級。進一步，通過在中國西南區域4個扇區的真實運行數據集上與管制專家標定的結果進行對比，驗證了本文方法的有效性。

1 算法設計

扇區復雜度無監督評估方法步驟如圖1所示：首先采用KPCA從原始樣本中抽取能夠最大化復雜度評估信息量的主成分，然后基于所評估扇區特點按需設置聚類參數，執行針對主成分(即降維樣本)的定制型聚類，獲得各樣本對應的復雜度等級。

圖1 扇區復雜度無監督評估方法流程圖Fig.1 Block diagram of unsupervised evaluation method for sector complexity

1.1 KPCA降維

影響扇區復雜度的關鍵因素多達數十個，各因素對于扇區復雜度評估任務的信息貢獻程度不同，且耦合關聯復雜，所蘊含復雜度評估知識重疊。以上特點使得在無監督條件下提取扇區復雜度評估知識非常困難。為從高維原始樣本中挖掘扇區復雜度評估知識，需對樣本進行降維，抽取能夠準確表征扇區復雜度評估知識的主成分，降低復雜度評估難度。

主成分分析(Principal Component Analysis,PCA)是挖掘高維樣本數據中主成分的常用方法[17]。然而，傳統PCA的主成分提取過程是線性的，不適用于各維度間非線性耦合的扇區復雜度樣本。因此本文采用非線性的PCA方法——KPCA[18]，先將原始樣本非線性映射至超高維樣本空間中，再由此轉換至最大化復雜度評估信息量的低維子空間中，獲得在統計上不相關的主成分。KPCA具體步驟如下。

首先，基于高斯核函數將原始樣本映射至無限維的再生核希爾伯特空間(Reproducing Kernel Hilbert Space,RKHS)中[19-20]。令該核函數為k，某一條原始樣本x被映射至RKHS后為k(x,·)。繼而在RKHS中通過樣本維度轉換獲得主成分，求解主成分的表達式為

(1)

由此，特別令V=k(X,·)W(W∈Rn×m)，則主成分VTk(X,·)=WTk(X,·)Tk(X,·)=WTK，其中，K=k(X,·)Tk(X,·)=[k(xi,·)Tk(xj,·)]1≤i,j≤n=[k(xi,xj)]1≤i,j≤n∈Rn×n為核矩陣；K中各個元素k(xi,xj)能夠通過以xi和xj為自變量的明確函數式計算得到。于是，求解V的問題轉化為求解W的問題：

(2)

1.2 主成分聚類

通過KPCA提取出m個主成分后，若直接采用傳統聚類算法處理扇區復雜度樣本，則會忽略掉實際空管中不同扇區對于復雜度等級劃分的差異性要求。因此，我們在聚類算法中設計了多種可調參數，能夠根據所評估扇區運行特點實現按需配置。參數包括復雜度等級數量、各復雜度等級樣本比例，以及初始簇中心。其中，初始簇中心為聚類算法提供不同復雜度等級簇所處樣本空間位置的指導信息。基于文獻[15]中附錄A可知，“航空器數量”“航空器密度”這兩個因素與復雜度有著強烈的正向關聯，且“航空器數量”也是當前空管系統中唯一的被實際用于衡量扇區復雜度的指標。因此，我們提出參照“航空器數量”與“航空器密度”兩個因素來設置初始簇中心參數。該參數設置方法為，首先對原始樣本進行排序，排序標準為“航空器數量”從低到高，對于“航空器數量”因素取值相同的樣本，按“航空器密度”從低到高排序；接著按照設置的復雜度等級數量、各復雜度等級樣本比例參數，基于排序后樣本初步劃分樣本的復雜度等級；然后將該樣本集整體映射到高維核空間后，求解每一復雜度等級樣本簇對應m個主成分的均值，作為初始簇中心。聚類算法步驟如表1所示。

表1 聚類算法步驟Table 1 Procedures of clustering algorithm

續表

2 實驗結果

2.1 實驗數據說明

本文基于中國西南區域4個扇區(扇區代碼：GY01、GY02、KM03、CD02)在2010年7月28日8:00～24:00 GMT的運行數據進行復雜度評估實驗。這一數據集擁有3 840(960分鐘×4扇區)條復雜度樣本，其中的每一條樣本包含28個空域復雜度因子(由文獻[12]總結，如表2所示)的取值，對應某一個扇區在某一分鐘內的運行態勢。

表2 空域復雜度因子列表Table 2 Set of spatial complexity factors

續表

為驗證所提出的扇區復雜度無監督評估方法的準確性，邀請了管制專家對4個扇區樣本的復雜度等級進行標定，包括“低復雜度”、“中復雜度”和“高復雜度”3種。

2.2 KPCA降維結果

針對每一個扇區，對其960條復雜度樣本采用KPCA方法進行主成分提取(降維)。所用高斯核函數的帶通參數設置為

(3)

式中：xi、xj為樣本集中兩條樣本；n為樣本集大小。表3展示了對應各個扇區樣本集的主成分的貢獻率(從大到小排序，僅展示前10個)。可見，對任意扇區，前兩個主成分貢獻率之和均超過88%，因此僅抽取前兩個主成分(m=2)即能夠保留原始樣本蘊含的絕大部分復雜度評估知識。

表3 從各扇區樣本所提取主成分的貢獻率Table 3 Contribution rates of principal components extracted from each sector’s samples

2.3 基于主成分聚類的復雜度等級劃分結果

按照4個扇區樣本集被管制專家標定的情況設置聚類參數。聚類輸出的結果如圖2所示，橫軸為樣本被聚類算法判定的復雜度等級(“L/M/H”分別對應“低/中/高復雜度”)，縱軸為樣本被管制專家評判的等級，圓面積正比于樣本數量。可見，在4個扇區樣本集上實驗的結果顯示，無監督模型在4個扇區樣本集上平均評估準確率高達74%。實驗結果說明所提出模型具有較好的扇區復雜度無監督評估性能，能夠為空域劃分、流量管理等實際空管業務提供有效的技術支撐。

圖2 扇區復雜度無監督評估結果Fig.2 Results of unsupervised evaluation for sector complexity

3 結 論

1)提出了一種基于核主成分分析的空域復雜度無監督評估方法，在不依賴標定樣本的基礎上通過主成分提取與主成分聚類對指定空域的復雜度等級進行劃分，解決了由標定樣本采集困難所導致的空域復雜度難以準確評估的問題。

2)采用的核主成分分析方法能夠從多維因素中提取最大化空域復雜度評估知識的主成分；所設計的主成分聚類方法能夠根據實際空域運行特點進行配置，滿足模型用戶對于不同扇區復雜度評估的具體要求。

3)基于西南區域4個扇區實際運行數據的實驗結果表明，本方法能夠在無監督條件下實現對扇區復雜度等級的準確劃分。