基于核主成分分析的空域復雜度無監(jiān)督評估

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

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

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

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

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

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

1 算法設計

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

圖1 扇區(qū)復雜度無監(jiān)督評估方法流程圖Fig.1 Block diagram of unsupervised evaluation method for sector complexity

1.1 KPCA降維

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

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

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

(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為自變量的明確函數(shù)式計算得到。于是，求解V的問題轉(zhuǎn)化為求解W的問題：

(2)

1.2 主成分聚類

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

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

續(xù)表

2 實驗結(jié)果

2.1 實驗數(shù)據(jù)說明

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

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

續(xù)表

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

2.2 KPCA降維結(jié)果

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

(3)

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

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

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

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

圖2 扇區(qū)復雜度無監(jiān)督評估結(jié)果Fig.2 Results of unsupervised evaluation for sector complexity

3 結(jié) 論

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

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

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