基于改進(jìn)譜聚類的終端區(qū)航空器飛行軌跡分析*

李樹(shù)仁 盧朝陽(yáng) 任廣建

(南京航空航天大學(xué)民航學(xué)院 南京 210016)

0 引 言

隨著我國(guó)空中交通流量的急速增長(zhǎng)和空管信息化建設(shè)的快速推進(jìn)，空中交通流量管理逐步從實(shí)時(shí)戰(zhàn)術(shù)的流量調(diào)配模型研究拓展至預(yù)戰(zhàn)術(shù)階段流量管理決策和觸發(fā)機(jī)制研究中[1].機(jī)場(chǎng)終端區(qū)運(yùn)行環(huán)境復(fù)雜，是進(jìn)離場(chǎng)飛行程序運(yùn)行和空域規(guī)劃管理的基礎(chǔ)，對(duì)終端區(qū)海量高復(fù)雜度的運(yùn)行數(shù)據(jù)進(jìn)行技術(shù)研究，有助于深度認(rèn)知交通流組織模式，精細(xì)描述終端區(qū)交通態(tài)勢(shì)，把握交通特性變化規(guī)律和時(shí)空分布特征.飛行軌跡分析是反應(yīng)終端區(qū)空域宏觀特性和智能決策分析的關(guān)鍵部分，新航行技術(shù)和雷達(dá)引導(dǎo)在空中交通管理中的應(yīng)用使得飛行軌跡和標(biāo)準(zhǔn)進(jìn)離場(chǎng)程序差異度較大，因此找出能夠有效整合航空器行為的聚類學(xué)習(xí)方法成為空中數(shù)據(jù)挖掘的重點(diǎn).

目前關(guān)于航跡聚類方法核心在于離散軌跡點(diǎn)降維處理、相似度模型的建立(如基于部分特征點(diǎn)提取、最長(zhǎng)公共子序列、點(diǎn)對(duì)歐式距離等)和高效的聚類算法(如k-means、DBSCAN和層次聚類等)，Rehm[2]提出基于航跡點(diǎn)比對(duì)的相似性度量算法，Gariel等[3]以提取轉(zhuǎn)彎點(diǎn)為聚類分析對(duì)象表示軌跡間差異度，趙元棣等[4]通過(guò)主成分分析對(duì)飛行數(shù)據(jù)的降維，采用MeanShift方法實(shí)現(xiàn)軌跡聚類.針對(duì)航跡聚類中不同軌跡數(shù)據(jù)集規(guī)模參數(shù)選取困難和計(jì)算效率低的問(wèn)題，提出一種基于自然鄰自適應(yīng)的軌跡譜聚類分析方法.

1 航空器飛行數(shù)據(jù)預(yù)處理

航空器飛行數(shù)據(jù)通常是由二次雷達(dá)或ADS-B等監(jiān)視設(shè)備實(shí)時(shí)獲取，由相同時(shí)間間隔的離散數(shù)據(jù)點(diǎn)構(gòu)成，包含了記錄時(shí)間、空間位置(x,y,z)、航向，地速、上升下降率等飛行特征信息.相較于航路飛行，終端區(qū)內(nèi)航空器起降頻繁，進(jìn)離場(chǎng)航班匯聚，飛行流量異常(軍方活動(dòng)或惡劣天氣等)時(shí)航空器需脫離標(biāo)準(zhǔn)進(jìn)離場(chǎng)飛行程序，按照管制員指令實(shí)施機(jī)動(dòng)飛行，由此產(chǎn)生的軌跡數(shù)據(jù)具有數(shù)據(jù)量大、時(shí)序性強(qiáng)、異常率高等特點(diǎn).為保證數(shù)據(jù)處理速度和計(jì)算精度，在飛行軌跡聚類之前，需要對(duì)飛行數(shù)據(jù)進(jìn)行清洗和預(yù)處理.

1.1 有效航跡提取分析

結(jié)合終端區(qū)空域結(jié)構(gòu)對(duì)雷達(dá)數(shù)據(jù)點(diǎn)集合進(jìn)行空間裁剪，保留歸屬終端區(qū)內(nèi)的雷達(dá)數(shù)據(jù)集A.水平投影以終端區(qū)邊界點(diǎn)構(gòu)成的多邊形區(qū)域?yàn)閰⒖?，?duì)于無(wú)終端區(qū)設(shè)置的繁忙機(jī)場(chǎng)，以機(jī)場(chǎng)基準(zhǔn)點(diǎn)為中心，按照半徑50 n mile進(jìn)行界定.垂直投影以高度6 000 m為上限.若為取得更明顯聚類效果，可以先向外延伸終端區(qū)范圍，以區(qū)域管制數(shù)據(jù)為基礎(chǔ)用于軌跡分類，然后在以終端邊界進(jìn)行軌跡選取.提取雷達(dá)數(shù)據(jù)集A所有單個(gè)航空器飛行軌跡序列，構(gòu)造航跡初始樣本集合P=(p1,p2,…,pn)，每條航跡pi={pi1,pi2,…,pim}，n為數(shù)據(jù)集內(nèi)航空器軌跡數(shù)量，m為單條航空器軌跡pi含有的雷達(dá)點(diǎn)數(shù)量，每個(gè)雷達(dá)點(diǎn)pim為pim=(t,x,y,z,v,φ,η)，由記錄時(shí)間t、空間坐標(biāo)(x,y,z)、速度v、航向φ、垂直上升下降率η等特征信息，按時(shí)間先后順序排列.由于監(jiān)視設(shè)備在采集數(shù)據(jù)過(guò)程中采取固定時(shí)間間隔，采集過(guò)程可能受地形、天氣等影響導(dǎo)致雷達(dá)信息丟失，需對(duì)數(shù)據(jù)進(jìn)行有效清洗.

1) 單條航跡pi中連續(xù)兩點(diǎn)時(shí)間間隔不超過(guò)10次以上雷達(dá)間隔，數(shù)據(jù)在可接受的容錯(cuò)修復(fù)范圍內(nèi).

2) 單條航跡pi軌跡點(diǎn)數(shù)量m需要大于平均航跡雷達(dá)點(diǎn)數(shù)的1/2，避免掛牌錯(cuò)誤，清除連續(xù)兩點(diǎn)間位置不合理跳變數(shù)據(jù).

1.2 航跡重采樣與歸一化處理

提取航跡后需保證航空器飛行特征信息前提下縮減數(shù)據(jù)規(guī)模，將軌跡集集時(shí)間歸一化，轉(zhuǎn)化到[0,1]時(shí)間片序列中，滿足聚類相似度計(jì)算要求.

基于文獻(xiàn)[4]的方法使用均勻參數(shù)化對(duì)飛行軌跡進(jìn)行重采樣，將每條軌跡pi={pi1,pi2,…,pim}中各軌跡點(diǎn)空間坐標(biāo)pil=(xl,yl,zl)，l=1,2,…,m坐標(biāo)進(jìn)行累加弦長(zhǎng)，得到位于[0,1]區(qū)間的參數(shù)λl.

λ1=0

λl=λl-1+

(1)

圖1 航跡重采樣示意

2 基于自然鄰的改進(jìn)譜聚類交通流學(xué)習(xí)方法

2.1 飛行軌跡相似度模型

譜聚類核心是親和度矩陣變換得到拉普拉斯矩陣，進(jìn)行特征分解后得到的特征向量進(jìn)行聚類[5].

飛行軌跡相似度模型是影響聚類結(jié)果的關(guān)鍵因素，通常軌跡間的相似度可通過(guò)歐式距離、最小外包矩形距離和最長(zhǎng)公共子序列距離等.文獻(xiàn)[6]提出基于3D網(wǎng)格的軌跡間相似性模型，將終端區(qū)空域劃分為多個(gè)大小相等的3D空間網(wǎng)格，依據(jù)占據(jù)度判斷不同軌跡間的相似性.文獻(xiàn)[7]提出基于轉(zhuǎn)彎點(diǎn)最長(zhǎng)公共子序列的軌跡聚類模型，依據(jù)公共子序列個(gè)數(shù)計(jì)算差異度.終端區(qū)內(nèi)交通密度大，飛行軌跡具有差異化和強(qiáng)機(jī)動(dòng)性特征，不同扇區(qū)之間走廊口位置不同且移交高度有所區(qū)別，相比之下，兩條航跡間的歐式距離更為較好適應(yīng)軌跡數(shù)據(jù)結(jié)構(gòu)，計(jì)算不便捷.

(2)

式中：D(X)為歐式距離集合方差；H為航跡點(diǎn)對(duì)間速度相差50節(jié)出現(xiàn)的點(diǎn)對(duì)數(shù)量；Δ為航跡點(diǎn)對(duì)間距離小于5 n mile，航向夾角小于20°點(diǎn)對(duì)數(shù)量.rij越大，表明兩條軌跡間差異度越明顯，rij越低，說(shuō)明兩條軌跡在空間距離上更加吻合.由于相似度rij基于歐式距離計(jì)算，由此構(gòu)建的相似度矩陣R為對(duì)稱陣.

2.2 基于自然鄰自適應(yīng)的飛行軌跡譜聚類

考慮到飛行數(shù)據(jù)中噪聲影響，不同走廊口間軌跡緊密程度不同，為保證聚類結(jié)果準(zhǔn)確性，相似度矩陣需要進(jìn)行降噪處理.傳統(tǒng)譜聚類算法通常使用高斯核函數(shù)獲得親和度矩陣W[8]，即

(3)

式中：rij為上述飛行軌跡相似度；σ為軌跡尺度參數(shù)，需根據(jù)經(jīng)驗(yàn)手動(dòng)設(shè)置，聚類效果易受到主管因素影響.軌跡點(diǎn)的分布圖見(jiàn)圖2.

圖2 軌跡點(diǎn)分布圖

由圖2可知，傳統(tǒng)譜聚類算法僅僅依靠點(diǎn)對(duì)間距離構(gòu)建親和度矩陣，即Wab=Wac，若引入密度條件則實(shí)際Wab

表1 自然鄰算法

根據(jù)密度分布情況，同處高密度區(qū)域的數(shù)據(jù)點(diǎn)相似度更大，由此構(gòu)造新的親和度矩陣：

(4)

(5)

(6)

(7)

將親和度矩陣W規(guī)范化求出其特征值及特征向量，在實(shí)際處理中遇到大量含有雷達(dá)引導(dǎo)的飛行數(shù)據(jù)往往無(wú)法確定聚類數(shù)k，可以采用特征間隙思想[10]，將特征值λt從大到小順序排列，計(jì)算每?jī)蓚€(gè)相鄰值之差構(gòu)成本征間隙序列，即ηi=λi-λi+1，本征間隙序列的第一個(gè)極大值點(diǎn)就是特征間隙，其對(duì)應(yīng)下標(biāo)為聚類數(shù)目k，若先驗(yàn)知識(shí)充足，可結(jié)合飛行程序中走廊口的設(shè)定確定最終聚類數(shù)目k.將特征向量V歸一化后，取前k個(gè)特征向量，采用k-means對(duì)進(jìn)行聚類，得到最終聚類結(jié)果.具體算法過(guò)程為

步驟1有效軌跡提取，設(shè)置采樣數(shù)c對(duì)航跡進(jìn)行重采樣與歸一化處理，得到新軌跡集P′.

步驟2結(jié)合軌跡集空間特征信息，依據(jù)式(2)計(jì)算航跡相似度r，構(gòu)建相似度度矩陣R.

步驟3結(jié)合2.2算法得出軌跡集nb,supk，rate，改進(jìn)高斯核函數(shù)得出親和度矩陣W.

步驟5依據(jù)特征間隙或先驗(yàn)知識(shí)設(shè)置聚類數(shù)k，獲取前k個(gè)最大特征值對(duì)應(yīng)特征向量并歸一化處理，得到Y(jié)=[y1,y2,…,yk].

步驟6將Y中的每一行對(duì)應(yīng)一條飛行軌跡，采用k-means聚成k類，若Y中第i行屬于第k類，則軌跡i分為第k類.

3 飛行軌跡聚類實(shí)例分析

圖3 航跡重采樣示意

對(duì)重采樣的新軌跡P′求取相似度矩陣，結(jié)合3.2節(jié)自然鄰思想求出親和度矩陣，并對(duì)親和度矩陣W規(guī)范化得出拉普拉斯矩陣L，計(jì)算其特征值λt，并將特征值從大到小順序排列，求本征間隙，結(jié)果見(jiàn)表2.

表2 特征值和本征間隙值

表2中特征間隙為0.203 5，對(duì)應(yīng)下標(biāo)標(biāo)號(hào)5，通過(guò)實(shí)驗(yàn)測(cè)試發(fā)現(xiàn)部分軌跡之間存在較多的重合部分，出現(xiàn)二義性，參照昆明長(zhǎng)水機(jī)場(chǎng)NAIP進(jìn)離場(chǎng)走廊口的設(shè)定，最終設(shè)聚類數(shù)目為k=6，依據(jù)重采樣軌跡P′構(gòu)建親和度矩陣W并規(guī)范正交化，采用k-means聚類算法對(duì)前六個(gè)特征向量子空間進(jìn)行聚類，得到北側(cè)進(jìn)場(chǎng)交通流MEBNA，XISLI，西側(cè)進(jìn)場(chǎng)交通流有GUILOT、P297，東側(cè)進(jìn)場(chǎng)交通流LXI，南側(cè)進(jìn)場(chǎng)交通流ELASU，基于聚類結(jié)果，提取南北向進(jìn)場(chǎng)交通流，見(jiàn)圖4，由圖4可知，該方法對(duì)所有進(jìn)場(chǎng)軌跡實(shí)行有效劃分，各分類簇可準(zhǔn)確刻畫不同方向進(jìn)場(chǎng)軌跡特征.部分交通流和盛行交通流見(jiàn)圖5～6.

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

圖5 部分交通流提取

圖6 盛行交通流

針對(duì)聚類結(jié)果，采用核密度估計(jì)對(duì)盛行交通流進(jìn)行識(shí)別.由于軍航活動(dòng)或危險(xiǎn)天氣原因，在航班流量過(guò)大情況下管制員對(duì)進(jìn)場(chǎng)航空器實(shí)施較大程度的雷達(dá)引導(dǎo).由聚類結(jié)果可知雷達(dá)引導(dǎo)時(shí)軌跡偏置與跑道運(yùn)行模式相關(guān)，北向03進(jìn)場(chǎng)和南向21進(jìn)場(chǎng)方式對(duì)應(yīng)盛行交通流有所差異.北側(cè)走廊口MEBNA，XISLI方向異常軌跡往往中心線兩側(cè)大量偏置，可能是北側(cè)進(jìn)場(chǎng)交通流占比較大，走廊口繁忙時(shí)段管制員命令部分航空器繞飛拉開(kāi)間隔，實(shí)現(xiàn)航班排序.

通過(guò)飛行軌跡聚類分析，昆明長(zhǎng)水機(jī)場(chǎng)南側(cè)ELASU、東側(cè)LXI進(jìn)場(chǎng)軌跡較為集中，北側(cè)MEBNA、XISLI進(jìn)場(chǎng)航跡出現(xiàn)大量偏置，呈現(xiàn)發(fā)散趨勢(shì)，為進(jìn)場(chǎng)飛行程序管制適用性提供另一個(gè)視角，同時(shí)可進(jìn)一步分析飛行軌跡偏置出現(xiàn)原因和飛行軌跡偏置時(shí)空分布特性，研究管制員特殊情況下指揮偏好及交通流動(dòng)態(tài)特征.

4 結(jié) 束 語(yǔ)

文中結(jié)合終端區(qū)航空器飛行特點(diǎn)，采用重采樣方法保留航跡飛行特征，提出了基于自適應(yīng)改進(jìn)譜聚類的航跡聚類方法，以昆明長(zhǎng)水機(jī)場(chǎng)為例，該方法能夠減少規(guī)模參數(shù)選取，得到滿意的聚類結(jié)果，從龐雜的進(jìn)場(chǎng)軌跡中提取盛行交通流和識(shí)別異常軌跡，為航空器運(yùn)行特性分析提供數(shù)據(jù)支持，后續(xù)研究可結(jié)合交通流相態(tài)變化，進(jìn)一步分析終端區(qū)交通特性變化規(guī)律和時(shí)空分布特征.