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

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

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

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

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

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

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

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

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

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

(1)

(2)

圖1 重采樣與原飛行軌跡對(duì)比

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

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

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

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

(3)

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

步驟1對(duì)矩陣T標(biāo)準(zhǔn)化。

(4)

步驟2計(jì)算核矩陣。

(5)

步驟3中心化核矩陣。

K*=K-unitK-Kunit+unitKunit

(6)

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

步驟5得到Xnew。

Xnew=K*V

(7)

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

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

圖2 不同c值時(shí)KPCA結(jié)果

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

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

3 基于DBSCAN的軌跡聚類(lèi)方法

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

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

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

表1 DBSCAN算法

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

圖3 KPCA(Gaussion)聚類(lèi)結(jié)果

4 實(shí)例分析與對(duì)比

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

4.1 實(shí)驗(yàn)分析

4.1.1 聚類(lèi)結(jié)果及異常軌跡提取

圖4是對(duì)軌跡進(jìn)行KPCA方法降維后的聚類(lèi)結(jié)果圖。圖4中，點(diǎn)代表一條軌跡，其中線條的顏色代表其所屬的類(lèi)。紅色類(lèi)別包含飛行軌跡135條，黃色類(lèi)別包含飛行軌跡226條，綠色類(lèi)別包含飛行軌跡531條，青色類(lèi)別包含飛行軌跡58條，藍(lán)色類(lèi)別包含飛行軌跡146條，粉色類(lèi)別包含飛行軌跡8條，與噪聲點(diǎn)相對(duì)應(yīng)的飛行軌跡139條。

圖4 飛行軌跡聚類(lèi)結(jié)果

其中粉色類(lèi)別的飛行軌跡僅有8條，且該軌跡飛行結(jié)構(gòu)特征與其他軌跡存在顯著差異，此類(lèi)軌跡的產(chǎn)生是由于管制員采取雷達(dá)引導(dǎo)方式導(dǎo)致其進(jìn)場(chǎng)軌跡偏離標(biāo)準(zhǔn)進(jìn)場(chǎng)航線，因此將粉色類(lèi)別作為異常軌跡。

4.1.2 噪聲點(diǎn)分析

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

首先，對(duì)原始軌跡進(jìn)行處理，提取出缺點(diǎn)軌跡162條，ADS-B設(shè)備解析問(wèn)題導(dǎo)致的干擾軌跡7條。如圖5所示。

圖5 軌跡對(duì)比

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

4.2 參數(shù)分析

4.2.1 Eps的影響

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

圖6 不同Eps聚類(lèi)結(jié)果

表2 Eps的影響

4.2.2 Minpts的影響

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

圖7 不同Minpts聚類(lèi)結(jié)果

表3 Minpts的影響

4.3 聚類(lèi)結(jié)果對(duì)比

4.3.1 與meanshift聚類(lèi)結(jié)果對(duì)比

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

圖8 meanshift聚類(lèi)結(jié)果

與圖4相比，由于沒(méi)有對(duì)軌跡數(shù)據(jù)進(jìn)行預(yù)處理，存在過(guò)多的干擾軌跡從而使meanshift聚類(lèi)結(jié)果相對(duì)雜亂，不能很好識(shí)別軌跡所屬的類(lèi)。

4.3.2 不同核函數(shù)聚類(lèi)結(jié)果對(duì)比

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

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

圖9 指數(shù)核聚類(lèi)結(jié)果

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

圖10 Sigmod核聚類(lèi)結(jié)果

4.3.3 多類(lèi)別識(shí)別

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

圖11 聚類(lèi)結(jié)果

通過(guò)實(shí)驗(yàn)證明，應(yīng)用KPCA和DBSCAN算法對(duì)飛行軌跡聚類(lèi)，可以在實(shí)現(xiàn)對(duì)交通流更精細(xì)劃分的同時(shí)，DBSCAN中自行篩除噪聲點(diǎn)的特點(diǎn)保證聚類(lèi)的質(zhì)量，為聚類(lèi)結(jié)果最終的應(yīng)用提供了更多的可能。

5 結(jié)論

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