基于密度聚類與匹配算法的異常飛行行為挖掘

吳欣蓬，湯新民，毛繼志，郭鴻濱，管祥民

（1.南京航空航天大學民航學院，南京 211106；2.中國航空無線電電子研究所航空電子系統綜合技術國防科技重點實驗室，上海 200241；3.中國民航管理干部學院民航通用航空運行重點實驗室，北京 100102）

伴隨著航空運輸全球化趨勢，中國民航運輸快速發展。中國民航2019年完成旅客運輸6.6 億人次，較上年增長7.9 %，其中國際航線完成的旅客運輸量則高達7425.1 萬人次，增長16.6 %［1］?？瓦\量的大幅增長給原本緊張的空域資源分配和調度帶來了巨大壓力，使得管制員和飛行員的工作負荷倍增。歷年空管不安全事件報告顯示，在這樣的背景下，飛機的異常飛行行為日益頻發，例如：因惡劣天氣、管制員指揮不當、軍民航沖突和無線電干擾等原因導致飛機在飛行過程中產生偏離既定航路，不滿足最小間隔標準等異常飛行行為。

空中交通管制的主要任務是避免異常飛行行為的發生，保障飛機的安全運行。但是，目前在空管實踐環節，自動化監視設備只能夠在戰術階段對小于間隔的異常飛行行為進行預警，不能夠發現上述多樣化異常飛行行為，難以分析其機理并制定相關針對性措施。而在理論研究環節，隨著新航行系統的發展，廣播式自動相關監視（Automatic dependent surveillance-broadcast，ADS-B）技術在民航領域廣泛推廣，每天都會產生大量的航跡運行數據。許多學者采用航跡大數據對飛機異常飛行行進行了探索性研究［2-7］。其中比較有代表性的是Ho等［8］基于ADS-B數據綜合回歸預測和鞅方法來辨識航跡空間位置不匹配數據的異常飛行行為，其異常偏航行為檢出率達81%，但是無法辨識其他類型的 異常飛行行為。Gariel等［9］以ADS-B數據中的飛行計劃航路點和航跡轉彎點來表征原始航跡，通過重采樣方法和主成分分析法獲取降維后的等長航跡序列，利用基于密度的有噪聲應用中的空間聚 類（Density-based spatial clustering of applications with noise，DBSCAN）算法的噪聲辨識功能識別異常航跡，完成空域異常飛行行為的監視。王超等［10］對航跡空間特征利用層次聚類算法來辨識航跡樣本類別，并進一步通過偏差建模來量化異常飛行的嚴重程度。潘新龍等［11］基于定義的多因素定向Hausdorff距離，構造航跡多維度局部異常因子來辨識異常飛行行為，實現航跡的異常行為檢測與挖掘，但是對多維特征采取歐氏距離度量存在誤差，同時在鄰居搜索時時間成本較高。Liu等［12］利用濾波算法剔除航跡數據的噪聲和離群點，然后采用自然語言處理中的可變長度N-Grams算法來提取正常飛行行為特征向量，通過訓練One-class SVM分類器來辨識異常飛行行為，但不適用于海量航跡的分析。

與上述研究方法不同的是，本文認為航跡是航空器在飛行員、管制員和客觀環境因素影響下所表現出來的具有時空特性的行為軌跡。而航跡變化的形成機理主要是飛機速度、航向和高度調整的結果。同時，實際飛行航跡與航路存在偏差。因此，本文首先提出帶速度、航向和高度層約束的局部異常因子改進的考慮速度、方向及高度的基于密度聚類方法（Density-based spatial clustering considering speed，direction and high level improved by local outlier factor，LOFDBSC-SDH），提取飛機正常航跡模式，并附加上相對時間特征；通過構建海量ADS-B航跡數據的快速覆蓋樹［13］來提高算法的處理速度；然后本文引入4D航跡中的過點時間［14］概念和過點時間的偏移約束開展實際航跡與正常航跡模式地相似性匹配；最終實現對航空器異常飛行行為地辨識挖掘。

1 基本概念

1.1 ADS?B航跡數據

ADS-B接收機異步解析航跡數據存在數據缺失問題，采用中值濾波算法進行填補；而對于航跡點極少的航班，即ADS-B有效接受范圍邊界處的航班數據，將視為無效數據進行剔除。最終獲得包括飛機ICAO呼號-地址、時間、經度、緯度、高度、速度和航向等航跡信息，部分示意如表1所示。由此可見，飛機的歷史航跡是一種時空大數據。

表1 ADS?B航跡數據Table1 ADS?B track data

1.2 正常航跡模式

本文定義飛機正常航跡模式是指在歷史無沖突表現的條件下，飛機在規定過點時間上位于既定的空間位置，并且速度、航向和高度特征與歷史上的正常航跡模式相一致的類簇。因此，對飛機的航跡進行定義

式中：S為飛機航跡數據集，其中第j個飛機的航跡數據集為Tj，對于Tj中第i個航跡點有經度、緯度、高度、對地速 度和真航向對應過點時間。過點時間定義為相對于當天凌晨0點的毫秒計數，取值范圍為0～86400000ms，該數據需要對表1時間數據按協調世界時（Universal time coordinated，UTC）進行轉換。故同一正常航跡模式類簇可由一個S來表示。

1.3 異常飛行行為

所謂異常飛行行為，定義為飛機在運行過程中，表現出在過點時間、空間位置、速度、航向或高度層特征與歷史正常航跡模式相異的飛行行為，即飛行表現違反1.2 節正常航跡模式定義。因此，異常飛行行為與正常航跡模式是相反關系。

鑒于航跡需分段處理，進一步給出異常飛行行為在航跡分段條件下的定義：若一飛機航跡的任意子軌跡符合上述異常飛行行為定義，則稱該飛機存在異常飛行行為。

2 基于ADS?B數據的正常航跡模式提取

2.2 正常航跡模式的提取原理

2.2.1 約束的引入

異常飛行行為的形成過程主要表現為2種形式：（1）飛機之間在原本既定的高度層、航路上產生異常飛行行為，表現為同航路前后追趕、交叉航路相互接近。這主要是速度異常改變導致的。（2）飛機未在原本既定的高度層或航路上而產生異常飛行行為，表現為飛機偏航、穿越高度層而發生飛行沖突，這主要是航向和高度異常改變導致的。因此，正常航跡模式的提取應當將高度層、速度和航向作為必要特征。

傳統DBSCAN軌跡挖掘算法［15］通過計算航跡點與其他航跡點之間的距離，將位于鄰居半徑ε范圍內的航跡點進行歸并。如果歸并結束后類簇的元素個數大于密度μ則認為聚類成功；反之，將該類簇視為噪聲剔除。該算法只考慮了航跡的空間位置關系。進一步作圖1分析可知，虛線圓圈為ε所形成的的鄰居半徑范圍，即水平間隔安全區域，而高度層下界高hk和hk+1刻畫了垂直間隔標準。當航跡Ti穿越高度層hk+1后，其子軌跡Tsubi2將不再與Tj發生聚類關系。因此，通過高度層標準來劃分航跡可以規避不必要的聚類操作。目前，國內僅有交叉航路，不存在平行航路，因此交叉航路匯聚點處會出現不同類航跡點ε鄰域的交疊，即Ti和Tj，這樣將會引起錯誤的聚類。但是通過引入速度和航向特征可以很好地區分這2種航跡，從而將其標記為不同的類型。反之，對于同航路同航向且速度近似的航跡將被聚類為同一類簇，即Tm和Tn。

圖1 軌跡特征與正常航跡模式的聯系Fig.1 Relationship between track characteristics and normal track patterns

此外，DBSCAN基于歐氏距離判定航跡點之間的鄰居關系。如果將這3個特征納入歐氏距離計算會增加算法的運算時間。因此，為了兼顧速度、航向和高度層特征而又不增加歐氏距離計算復雜度，本文將3個特征以約束形式（式（2～4））引入DBSCAN算法進行改進，以使其適用于正常航跡模式的提取

式中{hk，hk+1}?H。

式中：H為高度層約束集合；hk為第k個飛行高度層的下邊界高度值，因此對于滿足高度層約束（2）的兩航空器航跡點和將位于同一高度層中，可近似投影為hk所在平面進行DBSCAN聚類，而無須在三維空間進行空間距離計算，節省計算時間。這即是“高度層劃分策略”。速度和航向約束為式（3，4），其中δv和δθ分別為速度閾值和航向閾值?？梢砸罁w機性能參數設定，從而辨識出相同飛行行為的航跡模式。此外，算法并未讓式（1）中的時間特征參與計算，而是將其作為附加屬性，置于提取的正常航跡模式中。這主要是考慮到時間和空間度量尺不具有相同物理量綱，以及ADS-B數據的時間點由于異步解析可能無法對齊。因此，同一正常航跡模式中將存在時間不同而在空間上相似的軌跡。

2.2.2 局部異常因子

雖然，在大部分時間下，飛機的航跡數據均屬于正常航跡模式。但是過濾掉一些隱藏的異常模式，對本文借助模式匹配來辨識異常飛行行為是有必要的。原始的DBSCAN的異常點剔除能力有限，依賴于參數ε和μ。為了獲得較為干凈的正常航跡模式，繼續在DBSCAN的鄰居判別過程中引入局部異常因子（Local outlier factor，LOF）［11］lrdμ(p)=

式 中：|neighborPts(p)|為p的 鄰 居 個 數；reachDistμ(p，q)表示p和p的鄰居q之間在密度為μ條件下的可達距離；lrdμ(p)為航跡點p的局部可達 密 度；LOFμ(p)為p的 局 部 異 常 因 子。當LOFμ(p)≤1時，則p的局部可達密度與其鄰居航跡點相接近，可視為屬于同一類簇；否則，p為離群的異常點，進行剔除。

2.2.3 快速覆蓋樹

除此之外，DBSCAN和LOF的計算均以蠻力算法來尋找鄰居對象，時間成本較高，不能滿足航跡大數據的快速分析要求。本文提出構建ADS-B航跡數據集的快速覆蓋樹數據結構［13］來降低鄰居查找過程的時間消耗。對一棵快速覆蓋樹而言，任意結點均包含一個單一的航跡點數據，并且滿足3個不變量約束：

（1）層次不變量即結點a所對應的一個關聯整數level(a)。并且對結點a的子結點b存在如下等式約束關系

（2）覆 蓋 不 變 量 定 義 為covdist(a)=2level(a)。結點a和其子結點b的距離滿足如下約束關系

（3）分離不變量定義為sepdist(a)=2level(a)-1。結點a的任意兩個子結點b1、b2的距離滿足如下約束關系

依據上述結點與子結點約束關系可知，從根結點出發，每個父結點均向下覆蓋其子結點，即子結點對應航跡點為其父結點對應航跡點的鄰居?；谏鲜黾s束規則可以構建ADS-B航跡數據集對應的一棵快速覆蓋樹。

為了在快速覆蓋樹中查找航跡點p的鄰居，設結點a的子結點集合為children(a)，后代結點集合為descendant(a)，定義結點a到其后代結點之間的最大距離為

從根結點出發查找p的鄰居。分別向下按層次尋找p所屬的覆蓋結點。對某層p所屬結點a，計算該航跡點與結點a的各子結點b之間的距離，并按距離從小到大排序考察結點a及其子結點b和航跡點p是否滿足如下約束

若滿足，則該子結點是p在快速覆蓋樹下一層次所屬的覆蓋結點。重復該步驟，直到所有子結點均不滿足式（11），則該父結點為p的鄰居。依據文獻［13］可知，n結點快速覆蓋樹的查找時間復雜度為O(c6logn)，其中c為常量，一般取2。故相對于使用蠻力算法查找鄰居航跡點的冪級時間復雜度來說，使用快速覆蓋樹數據結構降低了算法查找鄰居的時間成本。

2.2.4 LOFDBSC-SDH算法

將基于上述方案改進DBSCAN提取正常航跡模式的算法稱為LOFDBSC-SDH，相關符號定義如表2所示，其偽代碼如算法1 所示。算法第2行首先基于ε鄰居半徑標準，按2.2.3 節所述方法將輸入的航跡點逐步插入到快速覆蓋樹相應結點，形成ADS-B航跡數據集對應的完整快速覆蓋樹，即建立算法的快速鄰居搜索空間。算法第7行和18～28行在鄰居搜索環節引入高度層約束[hk，hk+1]、速度約束δv和航向約束δθ，結合密度閾值μ完成同類航跡地辨識。算法8 ～11行基于上述鄰居結果計算該航跡點的LOF值，辨識異常點。將異常點及其鄰居一并剔除，節省算法聚類時間。待航跡數據中異常點剔除后，從第12～17行開始利用mergeClusters方法（34～41行）進行正常航跡類簇地合并，最終提取得到正常航跡模式。

表2 符號定義表Table2 Symbol definition

算法1LOFDBSC-SDH算法

結合LOFDBSC-SDH算法的設計思路和航空器實際運行場景，參數ε可取最小水平間隔，而參數密度閾值μ則一般依據經驗設定［16］。

3 基于匹配算法的異常飛行行為辨識

異常飛行行為雖然有偏航和間隔縮小等具體形式，但是從宏觀角度來看就是不同于正常航跡的異常模式。因此，基于匹配算法辨識實際航跡是否歸屬于正常航跡模式，將未匹配上的航跡認為存在異常飛行行為。

3.1 航跡的分割

航跡中包含航路點、轉彎起始點、轉彎結束點等有效特征，常規對全航跡實施匹配的方法可能忽略掉這些局部特征。因此，基于航跡劃分對其子軌跡實施匹配以克服該問題，同時也可降低單次匹配的時間消耗。最小描述長度（Minimum description length，MDL）［17］能夠為某種模式類中的所有成員尋找不可約、最小的特征表達方式。由于文獻［17］提出的MDL是用于二維軌跡劃分，因此本文首先采用2.2.1 節提出的高度層劃分策略提取同高度層子軌跡，然后將子軌跡投影至高度層平面按MDL算法進行劃分，獲取該子軌跡的有效特征表達。

3.2 異常飛行行為辨識

基于航跡匹配辨識異常飛行行為需要采用合適的相似性度量。由于歐式距離EucDistance對軌跡點的時間偏移敏感，動態時間規整距離時間復雜度高，最大公共子軌跡距離對稀疏軌跡度量效果較差，本文從軌跡差異度的角度進行分析，采用Hausdorff距離［17］來實現軌跡距離度量，并引入時間、速度和航向因素對其進行改進，以更好地判斷異常飛行行為。

進而得到式（13～14）構造兩航跡Hausdorff距離計算式（15）

依據相似性匹配算法，如算法2 所示，最終可分別在各高度層內完成子軌跡的相似性匹配，辨識異常飛行行為。

4 實驗分析

4.1 實驗設計

本文選取華東地區某空域ADS-B接收機所獲取的2019-12-1至2019-12-30清洗后的1776207條有效航跡數據記錄作為訓練數據集，2019-12-31清洗后56572條有效航跡數據作為測試數據集。首先基于LOFDBSC-SDH算法利用訓練數據提取正常航跡模式，其中ε取最小水平間隔10km［18］，μ取50，高度層約束H設置參考文獻［18］，依據速度航向變化 值的 統計分析，δv取100m/s，δθ取10°。然后，基于δTD=2000ms運用匹配算法辨識測試數據集中的異常飛行行為。

最后，為了驗證本文提出異常飛行行為挖掘方案的準確性，取清洗后的2019-11-31的63129條有效正常航跡（共2107個航班）數據，對其中100個航班的高度數據進行分段切分、混合后再拼接操作，構造異常飛行行為航跡樣本數據，并給定標簽1；然后繼續各選取100個航班做速度、航向數據的相同處理，其中航向異常數據，即空間位置的偏差異常，故其構造需要將航向數據連同經緯度數據一并更換，分別給定標簽2和3，最終生成300個異常飛行行為的航班航跡數據。其余未處理數據給定標簽0，視為正常飛行航跡樣。最終形成驗證數據集。按照上述相同的異常飛行行為挖掘步驟處理驗證數據集，分析本文方法的準確率。

4.2 實驗結果

4.2.1 真實場景異常飛行行為挖掘

對4.1 節所述訓練數據集，使用本文提出的LOFDBSC-SDH算法提取飛機正常航跡模式，共獲得124種正常航跡模式，其可視化結果如圖2（a）所示。從結果可知，LOFDBSC-SDH算法相較于基線算法DBSCAN，如圖2（b），所提取得到的正常航跡模式其輪廓更為清晰，離群點較少，方向性更強；圖2（c）左下角的許多航跡模式在LOFDBSC-SDH算法作用下得到強化（紅色虛線區域），同時圖2（b）中心部分的橙色航跡表征出了該空域內的交叉航路事實，具有典型的代表性。綜上所述，本文提出的LOFDBSC-SDH算法通過引入局部異常因子提高了算法DBSCAN的離群點剔除能力，可以獲取較為干凈的正常航跡模式，降低離群點對航跡匹配的干擾。

進一步采用3.2 節異常飛行行為辨識方法對華東地區某研究空域某日全天航跡進行異常飛行行為挖掘，結果如圖2（c）所示。該航班直接從常熟市和張家港市上空飛躍，而查閱航圖數據發現并無此航路，可以肯定存在異常飛行行為。

4.2.2 實驗結果分析

在正常航跡模式數據庫中，按時間節點和高度層約束進行檢索，分析數據，發現圖2（b）中的異常飛行行為主要與正常航跡模式66存在一定聯系，其所在時間、高度層、經度與模式66基本一致，但是在緯度、航向和速度分布上存在較大差異，如圖3所示。該異常飛行行為的航班的飛行速度呈現加速狀態，與正常模式66所顯示出的勻速變化狀態相異。此外，圖2（b）顯示器航跡不同于圖2（a）中的各典型正常航跡模式，即從常熟市上空直接匯入正常航跡所在航路，該事實與圖3所示與正常航跡模式存在顯著緯度差異、23200～23400ms時間區間內存在顯著航向差異的實驗結果相符。

圖2 華東地區某研究空域Fig.2 Research airspace in East China

圖3 異常飛行行為特征曲線Fig.3 Characteristic curves of abnormal flight behaviors

因此，本文所提出的方案挖掘出了實際ADSB數據中存在的違反速度和航向約束的異常飛行行為。

4.2.3 準確率分析

在驗證數據集上，按4.2.1 節相同實驗步驟進行異常飛行行為地挖掘辨識。對有效結果進行統計分析，如表3所示。本文所提出的方案在驗證數據集上能夠辨識出其中93.3 %的異常飛行行為，其中高度異常辨識準確度為91%，速度異常辨識準確度為96%，而航向異常辨識準確度為93%。需要注意的是，位置異常是這3種異常的最終表現，包含于總體準確性表述中。

表3 異常飛行行為挖掘準確性Table3 Mining accuracy of abnormal flight behaviors %

綜上所述，實驗結果表明本文所提出的異常飛行行為挖掘方法對于實際飛機的異常飛行行為挖掘是有效的；并且，從異常飛行行為的產生機理出發，挖掘辨識飛機的過點時間、高度、速度和航向特征來判定飛機的異常狀態，相較于引言中相關文獻算法只通過空間位置特征偏差判定飛機異常飛行的做法，本文的方案更為合理。

4.3 算法分析

4.3.1 聚類質量分析

對于沒有基準的數據集，一般采用內在方法來評 估 聚 類 質 量，DAVIES-BOULDIN指 標［16］，即DBI，就是一種有效的方法，其定義如下

表4 算法DBI比較Table4 Comparison of DBIs

從表4結果可知，LOFDBSC-SDH算法相較于傳統的DBSCAN算法具有更好的聚類效果，該評估結果與可視化結果圖2（a，b）一致。

4.3.2 算法運行效率分析

本文對引言中多數文獻采用的基線算法DBSCAN、所提出的LOFDBSC-SDH算法以及引入快速覆蓋樹的FCT LOFDBSC-SDH進行了運行時間分析，其結果如圖4所示?？梢姡琇OFDBSC-SDH算法引入LOF后，雖然在正常航跡模式的提取上取得了較好的效果，但是增大了算法的時間復雜度，運行時間有所增加。之后引入快速覆蓋樹數據結構，預先構建ADS-B航跡數據的鄰居搜索空間，加快了算法鄰居計算速度，降低了算法的時間復雜度，運行所需時間減少。因此，基于快速覆蓋樹的LOFDBSCSDH算法在實驗結果的優良性和算法的時間復雜度上做出一種良好地平衡，可以應用于海量ADS-B航跡數據的正常航跡模式提取，輔助異常飛行行為的辨識，規避引言相關方案［8，11-12］的不足。

圖4 算法性能比較Fig.4 Comparison of algorithm performance

5 結 論

本文提出了一套LOFDBSC-SDH密度聚類算法和匹配算法相結合的異常飛行行為挖掘方案。首先，為了克服傳統方法只以飛機空間位置偏差作為異常飛行行為判定的不足，考慮異常飛行行為的產生原因，提出在位置異?；A上進一步考慮速度、高度和航向異常特征來設計挖掘算法。其次，為了彌補傳統算法水平擴展局限性，提出高度層劃分策略規避算法不必要聚類過程，并結合局部異常因子和快速覆蓋樹提出LOFDBSC-SDH算法，對海量ADS-B航跡數據進行正常航跡模式的快速、有效提取。然后，考慮過點時間和高度、速度、航向3個異常特征，設計相似度匹配算法來挖掘辨識異常飛行模式。最后，算法的DBI指標和運行時間實驗表明，本文提出的LOFDBSC-SDH算法克服了傳統DBSCAN的水平可擴展局限性，并提高了聚類的精度；而仿真實驗結果表明所述方案能夠有效辨識存在位置、速度、高度和航向異常的飛行行為，彌補了傳統方法只能辨識空間位置偏差異常的不足；采用實際ADS-B數據的實驗表明本文的方案能夠挖掘真實運行場景中的異常飛行行為，具有良好地應用價值。

不過，本文方案還無法有效解決惡劣天氣等環境因素所帶來的影響等問題，需要在接下來的研究中引入多源數據進行進一步改進。