終端區(qū)飛行軌跡聚類分析及異常軌跡識別

王志森，張召悅*，馮朝輝，崔哲

(1.中國民航大學空中交通管理學院，天津 300300；2.中國民航大學安全科學與工程學院，天津 300300)

近年來，空中交通流量快速增長，以往的空域扇區(qū)的劃分不能滿足現(xiàn)有的空中交通流量的需要，因此，導致航空器實際進場飛行軌跡偏離標準航線，并增加管制員的工作負荷。以自動相關監(jiān)視廣播(automatic dependent surveillance-broadcast，ADS-B)終端區(qū)飛行軌跡數(shù)據(jù)為基礎，可以獲取進離場盛行交通流的分布信息，優(yōu)化空域扇區(qū)的劃分和標準進離場程序設計，幫助管制員優(yōu)化進離場程序，從而達到提高空域利用率[1]和保障空中交通安全[2]的目的。

航空器的飛行軌跡包含了空中交通流時空分布規(guī)律、管制員意圖等重要空中交通信息。飛行軌跡聚類是一種通過劃分航空器飛行軌跡，達到類內(nèi)相似，類與類之間相異的一種方法。以飛行軌跡聚類分析為基礎，為掌握飛行軌跡的時空分布規(guī)律提供支撐，從而達到制訂相應的空中交通管理規(guī)則、識別盛行交通流等目的?？梢詫④壽E聚類方法分為兩大類，一種方法是將航空器的飛行軌跡簡化為線段后進行聚類，以此降低軌跡聚類的難度[3-5]。另一種則是通過構建相似度矩陣來實現(xiàn)對軌跡的聚類[6-11]。但由于地形、環(huán)境等的影響，ADS-B數(shù)據(jù)存在解析過程的錯誤、飛行軌跡點缺失、航空器運行速度不同等問題。因此原始數(shù)據(jù)中存在著大量的干擾飛行軌跡，而上述兩種方法，對數(shù)據(jù)都有著比較高的要求，需要對原始數(shù)據(jù)進行一定的處理?；诿芏瓤臻g聚類(density-based spatial clustering of applications with noise，DBSCAN)方法[8-10]可以在聚類過程中標記噪聲點，從而優(yōu)化聚類效果，但僅能針對低緯度數(shù)據(jù)點操作，不能對線段、向量等進行聚類。趙元棣等[11]對飛行軌跡進行重采樣后降維，從而對航空器飛行軌跡應用基于點的聚類方法，但其忽略了飛行軌跡的高維表示并不是線性排列。王莉莉等[12]針對飛行軌跡聚類效果易受離群點干擾的問題，選取航空器的航向和高度變化率進行飛行軌跡的模式識別。Tan等[13]則通過完善數(shù)據(jù)預處理的過程，實現(xiàn)聚類效果的提升。為解決數(shù)據(jù)質量較差和空中交通流之間差異較小的問題，Dong等[14]通過深度自編碼器完成對軌跡的重構與異常軌跡檢測。

現(xiàn)針對航空器飛行軌跡聚類普遍數(shù)據(jù)預處理和計算復雜的問題，通過DBSCAN算法簡化軌跡數(shù)據(jù)的預處理并剔除軌跡中干擾軌跡。首先，采用重采樣技術降低飛行軌跡的數(shù)據(jù)規(guī)模，并在重采樣過程中提取原始航跡點作為重采樣點代替線性插值避免產(chǎn)生新的點，破壞飛行軌跡的原始結構；其次，通過核主成分分析法(kernel principal component analysis，KPCA)對飛行軌跡數(shù)據(jù)降維處理，盡可能分離不同類別的飛行軌跡；最后，通過DBSCAN剔除數(shù)據(jù)中的干擾飛行軌跡完成聚類并提取異常軌跡。

1 數(shù)據(jù)重采樣

通過對飛行軌跡重采樣可以在保存飛行軌跡結構特征的條件下，有效縮減每條飛行軌跡包含的航跡點個數(shù)，從而減少計算量，提升了計算速度。同時，對均勻參數(shù)化法[11]進行改進，使得重采樣后，所有的飛行軌跡包含的航跡點個數(shù)一致，為利用KPCA降維提供必要條件。

若某條飛行軌跡包含n個點，則以(p1,p2,…,pn)表示該飛行軌跡，點pi包含其三維信息，即(xi,yi,zi)。如式(1)所示，對所有點累加弦長作為參數(shù)，使飛行軌跡上所有點落在區(qū)間(0,1)內(nèi)。當對飛行軌跡進行重采樣時，為保證飛行軌跡的準確起止位置，故不對飛行軌跡的第一個和最后一個飛行軌跡點進行重采樣，而是直接編入到重采樣后的數(shù)據(jù)中。

因此使用改進的均勻參數(shù)化法[11]對飛行軌跡進行重采樣，從而避免線性插值產(chǎn)生的點破壞原有軌跡結構特征。

(1)

(2)

圖1 重采樣與原飛行軌跡對比

2 基于KPCA的飛行軌跡降維方法

基于密度的聚類方法對于高維數(shù)據(jù)的處理上往往不盡如人意，故在軌跡進行聚類之前，對軌跡降維。首先，將每條軌跡整理成3m維向量，即把每條飛行軌跡視為3m維空間的一個點。但維數(shù)過高會在聚類過程中導致維數(shù)災難，為避免在聚類過程中發(fā)生維數(shù)災難，KPCA對數(shù)據(jù)進行降維。

通過KPCA對所有軌跡歸納其的前c個主成分，設存在s條軌跡，每條軌跡包含3m個點，則軌跡集合T為一個s×3m的矩陣。軌跡集合T以[x1x2x2…xmy1y2…ymz1z2…zm]形式進行排列，即

T=(T1,T2,…,Ts)=[Tij]s×3m=

(3)

為了使同一類別的點分布相近，不同類的點盡可能互相遠離，將高斯函數(shù)作為KPCA的核函數(shù)進行降維。KPCA運算步驟如下。

步驟1對矩陣T標準化。

(4)

步驟2計算核矩陣。

(5)

步驟3中心化核矩陣。

K*=K-unitK-Kunit+unitKunit

(6)

步驟4求解K*特征值，并降序排列，λ1≥λ2≥…≥λ3m，取前c個特征值對應向量V，V=(V1V2…Vk)。

步驟5得到Xnew。

Xnew=K*V

(7)

式(7)中：Xnew為航空器軌跡集合的前c個主成分。

分別以c=2、3為例，對飛行軌跡進行核主成分分析，每個數(shù)據(jù)點代表一條軌跡，如圖2所示。

圖2 不同c值時KPCA結果

c=3時，數(shù)據(jù)點集的分布則更加立體，類與類之間的差異也更加明顯，故選擇c=3作為主成分個數(shù)。

通過KPCA可以將非線性高維數(shù)據(jù)進行降維，盡可能使同類點之間分布更密集，不同類點之間更加稀疏，并保留了數(shù)據(jù)特征信息。因此數(shù)據(jù)點之間的關系即代表了飛行軌跡之間關系。同時根據(jù)圖中信息得到，軌跡點的分布密集地圍繞在幾個中心點，并以輻射狀發(fā)散，這也與終端區(qū)航空器按照標準程序進場的實際情況相吻合。

3 基于DBSCAN的軌跡聚類方法

由于各終端區(qū)進場程序間差別較大，且實際的航空器飛行軌跡與標準的進離場程序存在著較大的偏差，因此很難提前確定聚類數(shù)目，且飛行軌跡數(shù)據(jù)中包含較多由錯誤軌跡構成的噪聲點。DBSCAN可以對數(shù)據(jù)中噪聲點剔除并確定聚類個數(shù)。因此使用DBSCAN對降維后的軌跡數(shù)據(jù)聚類。

DBSCAN是一種基于密度的聚類算法，相較于其他聚類方法，DBSCAN具有高效處理噪聲點、聚類效率高、并發(fā)現(xiàn)任意形狀空間簇類的優(yōu)點。

DBSCAN通過持續(xù)搜索核心點，不斷建立新簇，并不斷對簇進行合并直到簇與簇之間密度不可達為止的過程。其算法如表 1所示。

表1 DBSCAN算法

在對飛行軌跡數(shù)據(jù)集降維后，通過DBSCAN算法對降維后的數(shù)據(jù)集進行聚類和噪聲點的識別。為確保聚類質量和噪聲點剔除的準確性，經(jīng)過分析，Eps為0.01，Minpts為7，并對數(shù)據(jù)集聚類，聚類結果如圖3所示。

圖3 KPCA(Gaussion)聚類結果

4 實例分析與對比

以某終端區(qū)4 d內(nèi)共1 243條進場飛行軌跡為例，應用MATLAB軟件進行編程，從全部數(shù)據(jù)處理到整個聚類完成，僅耗時9.38 s。實驗環(huán)境為3.20 GHz CPU，8 GB內(nèi)存的筆記本。在整個聚類過程中共涉及5個參數(shù)的設置：重采樣后點的個數(shù)m；核函數(shù)中參數(shù)σ；核主成分個數(shù)為k；DBSCAN中存在兩個參數(shù)Eps和Minpts。

4.1 實驗分析

4.1.1 聚類結果及異常軌跡提取

圖4是對軌跡進行KPCA方法降維后的聚類結果圖。圖4中，點代表一條軌跡，其中線條的顏色代表其所屬的類。紅色類別包含飛行軌跡135條，黃色類別包含飛行軌跡226條，綠色類別包含飛行軌跡531條，青色類別包含飛行軌跡58條，藍色類別包含飛行軌跡146條，粉色類別包含飛行軌跡8條，與噪聲點相對應的飛行軌跡139條。

圖4 飛行軌跡聚類結果

其中粉色類別的飛行軌跡僅有8條，且該軌跡飛行結構特征與其他軌跡存在顯著差異，此類軌跡的產(chǎn)生是由于管制員采取雷達引導方式導致其進場軌跡偏離標準進場航線，因此將粉色類別作為異常軌跡。

4.1.2 噪聲點分析

所使用的ADS-B數(shù)據(jù)，僅是剔除了飛越軌跡的原始軌跡，因此數(shù)據(jù)集T中包含很多由于地形、環(huán)境、設備解析等問題造成的不完整軌跡、地面運行軌跡等干擾軌跡。干擾軌跡的存在會對聚類效果造成不利影響，但針對問題軌跡的剔除和不完整軌跡進行補點費時費力，利用DBSCAN算法中識別噪聲點的特點對干擾軌跡進行識別，并對噪聲點進行分析。

首先，對原始軌跡進行處理，提取出缺點軌跡162條，ADS-B設備解析問題導致的干擾軌跡7條。如圖5所示。

圖5 軌跡對比

對以高斯函數(shù)為核函數(shù)的KPCA進行聚類(圖3)，產(chǎn)生了169個噪聲點，其中噪聲點包含全部因ADS-B設備解析問題導致的干擾軌跡，對于軌跡缺點問題，在不進行補點的情況下，噪聲點中包含了25條，其余缺點軌跡加入到正常軌跡的聚類中(圖4),并未產(chǎn)生明顯不利影響。

4.2 參數(shù)分析

4.2.1 Eps的影響

在通過DBSCAN方法進行聚類時，需要對Eps和Minpts進行設置，不同的參數(shù)設置對應不同的聚類結果。如表 2所示，可以看出，隨著Eps減小，聚類類別數(shù)目增加。如圖 6所示，隨著Eps增大，噪聲點數(shù)目減小，聚類類別減少。因此，數(shù)據(jù)集中，各點的實際分布情況是確定Eps的重要因素。

圖6 不同Eps聚類結果

表2 Eps的影響

4.2.2 Minpts的影響

Eps和Minpts都會對聚類結果造成影響，如表3所示，Minpts在固定Eps的條件下，對數(shù)值變化并不敏感。如圖 7所示，隨著Minpts增大，噪聲點數(shù)目增加，在具體結果上表現(xiàn)出對規(guī)模較小的類別不能有效識別、對規(guī)模較大的類別劃分更加精確的特點。

圖7 不同Minpts聚類結果

表3 Minpts的影響

4.3 聚類結果對比

4.3.1 與meanshift聚類結果對比

meanshift算法與DBSCAN同屬于基于密度的聚類方法，相較于DBSCAN算法，meanshift算法只需要設置一個參數(shù)，但meanshift算法的聚類質量受起始點選擇的影響較大，聚類質量不穩(wěn)定，且無法識別噪聲點，因此使用meanshift算法進行聚類需要較高的數(shù)據(jù)質量。meanshift聚類結果如圖8所示。

圖8 meanshift聚類結果

與圖4相比，由于沒有對軌跡數(shù)據(jù)進行預處理，存在過多的干擾軌跡從而使meanshift聚類結果相對雜亂，不能很好識別軌跡所屬的類。

4.3.2 不同核函數(shù)聚類結果對比

常見的核函數(shù)可分為4種：線性核函數(shù)、多項式核函數(shù)、徑向基函數(shù)(radial basis function，RBF)核函數(shù)和Sigmod核函數(shù)。因多項式核函數(shù)種類繁多，且需要進行較多的參數(shù)選擇并對參數(shù)敏感性較大，故不在此進行詳細討論。

(1)采用RBF核函數(shù)。RBF中包含多種核函數(shù)，除了高斯核函數(shù)，常用的還有指數(shù)核函數(shù)和拉普拉斯核函數(shù)。以指數(shù)核為例，結果如圖9所示。與圖4的DBSCAN飛行軌跡以高斯核函數(shù)為核函數(shù)聚類結果相比，以指數(shù)核函數(shù)為核函數(shù)不能很好地區(qū)分同一跑道入口的兩類軌跡(綠色類別的飛行軌跡)。

圖9 指數(shù)核聚類結果

(2)以Sigmod為核函數(shù)。其結果如圖10所示。雖然以Sigmod作為核函數(shù)，可以較好地剔除噪聲點，但不能很好地區(qū)分同一跑道入口的兩類軌跡(綠色類別的飛行軌跡)。

圖10 Sigmod核聚類結果

4.3.3 多類別識別

通過上述對比，不難看出，該機場存在5個主要交通流，但通過參數(shù)調節(jié)，將更多軌跡判定為噪聲點，可以獲得更加細致的航空器進場軌跡的類別，如圖11所示，圖4中的綠色類別可以再次劃分為4個類別，黃色類別可以再次劃分為2個類別。

圖11 聚類結果

通過實驗證明，應用KPCA和DBSCAN算法對飛行軌跡聚類，可以在實現(xiàn)對交通流更精細劃分的同時，DBSCAN中自行篩除噪聲點的特點保證聚類的質量，為聚類結果最終的應用提供了更多的可能。

5 結論

從終端區(qū)飛行軌跡非線性特征的角度和剔除異常軌跡影響的角度出發(fā)，重采樣簡化飛行軌跡數(shù)據(jù)規(guī)模，針對終端區(qū)飛行軌跡特征，利用非線性降維方法對飛行軌跡高維數(shù)據(jù)進行降維，并通過DBSCAN算法完成聚類及異常軌跡的識別。實驗結果證明，該聚類方法可以得到高質量的聚類結果，相較于其他聚類方法，可以消除錯誤軌跡的不良影響，保證聚類質量。未來的研究工作包括結合飛機性能的數(shù)據(jù)特征子集的選取、飛行軌跡質量評估等，并在此基礎上進行空中交通分析。