基于軌跡壓縮的航空器飛行軌跡聚類研究

李 楠，強懿耕，樊 瑞

(中國民航大學 空中交通管理學院，天津 300300)

0 引 言

近年來隨著我國民航業的高速發展，復雜機場已陸續實施基于性能導航(PBN)的導航技術來提高運行和指揮效率，因此需要設計新的PBN程序來簡化傳統的標準飛行程序。筆者針對飛行密度大、飛行情況比較復雜的終端區空域，通過聚類算法分析航空器歷史軌跡，挖掘航空器潛在的飛行模式，其中所蘊含的管制員指揮模式可作為評估、優化進離場程序的重要參考。

軌跡聚類分析是目標軌跡模式挖掘過程中常用的方法，用以探究隱藏在海量軌跡信息中目標的運動特征與規律，在探索人類的移動模式、颶風的運動模式和城市交通結構智能劃分等[1-3]諸多領域已經得到了廣泛的應用。目前，在航空領域中，國內外學者對航空器飛行軌跡的聚類分析多集中于兩個方面。一是借助經典的聚類方法(K-means，FCM等)來分析整條軌跡或軌跡段，挖掘軌跡的運行模式，如C. WANG等[4]針對具體的一類航跡簇，采用基于K-Means算法對航跡相似性矩陣進行聚類分析得到該類簇的中心航跡，計算中心軌跡與標準進場飛行程序(STAR)的偏差來為重新設計飛行程序提供參考；R. FRANK等[5]采用軌跡點比對的方法計算出軌跡間的相似性距離，再針對相似性距離矩陣進行聚類分析；Q. Y. YU等[6]提出了一種基于多特征軌跡相似性度量的新軌跡聚類算法，可以最大化同一聚類軌跡的相似性；A. SALAPOUR等[7]采用時間扭轉匹配的方法來度量軌跡間的相似性，提出了一種基于方向的軌跡聚類相似性度量；李楠等[8]建立了基于速度修正系數的軌跡相似性模型，再應用譜聚類實現了航空器飛行軌跡的合理分類；郭威等[9]沿用傳統的最小描述長度方法劃分軌跡，再結合密度聚類和掃描線算法得出表征目標物體運動的特征軌跡；徐濤等[10]引入懲罰弧形面積改進了在計算軌跡間相似度時軌跡航向的影響，再利用聚類方法準確地挖掘出了飛行程序軌跡。二是通過借助幾何模型或其他機器學習算法對軌跡重采樣，使重采樣后每條軌跡的軌跡點數和維度均保持一致，直接進行聚類分析，避免了使用相似性度量方法計算軌跡間的距離，如趙元棣等[11]在保持較低失真率的前提下使用主成分分析法降低數據維度,再運用均值漂移聚類算法實現飛行軌跡聚類分析并提取出異常軌跡；王濤波等[12]在采用模糊減法聚類提取軌跡特征點后，運用改進后的模糊聚類方法直接對航跡特征點進行聚類并構建相應的中心航跡，更好的反映了真實飛行中航空器的飛行模式。以上研究存在有待改進的地方，僅僅考慮軌跡間的空間距離對航空器進行聚類劃分是不夠的，時間是影響聚類結果的一個重要因素；由于軌跡點自身包含位置、速度和航向等多維特征，建立相似性模型時可以在考慮位置特征的前提下引入速度和航向等動態特征；當軌跡規模較大且噪聲點較多時，常用的聚類算法容易受初始點對噪聲敏感、多個參數輸入且需要先驗知識等因素影響，陷入局部最優搜索，導致聚類效果變差。

1 航空器飛行軌跡數據處理

1.1 航空器飛行基準軌跡

在監視數據庫中，航空器飛行軌跡是由離散的數據點依時間順序連接而成的點序列。采用某機場終端區ADS-B監視數據作為原始數據。考慮到原始軌跡中包含大量不完整軌跡、飛越航班和臨近機場起降航班的軌跡，需要進行軌跡預處理。

根據航空器飛行特點篩選出進場航班，刪除軌跡點嚴重缺失的軌跡，采用時間間隔為3 s的線性插值更新剩余軌跡。鑒于ADS-B接收機受地形和傳輸損耗的影響，導致測量值與真實值存在一定的誤差，所以結合CV卡爾曼濾波算法平滑處理軌跡，最大限度地接近飛機的真實位置，建立航空器飛行基準軌跡。

1.2 基于時間比的自頂向下飛行軌跡壓縮算法

經線性插值和平滑處理后的軌跡包含大量的軌跡點，采用Top-Down Time Ratio算法壓縮軌跡，以減小計算開銷，從根本上提高軌跡大數據分析能力。Top-Down Time Ratio算法是Douglas-Pecuker(DP)算法的擴展。與傳統DP算法不同的是，DP算法在考慮空間特性的前提下還考慮了時間特性，判斷是否為軌跡關鍵點的依據也由DP算法中的垂直距離變成了同步歐氏距離 (SED)[13]。同步歐氏距離指原始軌跡中真實軌跡點與其在軌跡首尾連接線上按時間比例所求得的歐氏距離。

如圖1，A到K為原始軌跡中相鄰的軌跡點，具體的軌跡壓縮步驟為：

圖1 Top-Down Time Ratio軌跡壓縮算法Fig. 1 Top-Down Time Ratio trajectory compression algorithm

步驟1：將軌跡首尾兩點A,K連接成一條直線，該直線稱為軌跡的弦。

步驟2：應用同步歐氏距離(如圖1中DO)，計算離弦距離最遠的點及其距離，比較該軌跡點距離與誤差閾值距離D的大小。

步驟3：若該軌跡點距離小于誤差閾值距離D，則舍棄該點，以弦作為該軌跡的近似軌跡；若大于誤差閾值距離，則以此關鍵點將曲線劃分成兩段，并對分割后的兩段軌跡分別重復步驟1～3操作。

如此循環，直到所有距離均小于誤差閾值距離，則保存這些關鍵點構成軌跡，即為壓縮后的軌跡。軌跡壓縮后的壓縮率(compression ratio，RC)計算公式如式(1)：

(1)

式中：M0和M1分別為原始軌跡壓縮前后的軌跡點數目。同時，為了表征原始軌跡與壓縮后軌跡之間的差距，引入平均距離誤差S來衡量，計算公式如式(2)：

(2)

式中：dist(pi)為原始軌跡中的第i個點距其壓縮后對應的關鍵點的歐氏距離；n為原始軌跡的軌跡點數目。

2 航空器飛行軌跡聚類方法的改進

2.1 建立多維特征的軌跡相似性模型

設航空器飛行軌跡可表示為TR，則某條飛行軌跡i可表示TRi={TRi1,TRi2,…,TRij,…,TRin}，其中n為該條軌跡的軌跡點數，且對于不同的飛行軌跡，壓縮后每條軌跡的軌跡點數不一定相同。考慮到兩軌跡點之間的位置、速度和航向屬性，定義軌跡TRx內任一點TRxa到另一條軌跡TRy內任一點TRyb的多因素距離如式(3)：

multidist(TRxa,TRyb)=wd·dist(TRxa,TRyb)+wv·dist(Vxa,Vyb)+wθ·dist(θxa,θyb)

(3)

式中：Vxa,Vyb,θxa和θyb分別為軌跡點TRxa和TRyb的速度和航向；dist(Vxa,Vyb)和dist(θxa,θyb)分別為兩點之間速度屬性和航向屬性的歐式距離；wd,wv和wθ分別為位置、速度和航向屬性的權重，權重因子的選擇主要依賴于各機場的不同標準進離場程序，滿足wd≥0,wv≥0,wθ≥0和wd+wv+wθ=1。為了消除各特征屬性之間，不同量綱會對多因素距離結果產生影響，采用歸一化處理各特征屬性，再進行距離的度量。

同樣，定義基于Hausdorff距離的軌跡相似性度量方法,計算兩條軌跡之間的距離,計算公式如式(4)：

(4)

同理，求出r(TRy,TRx)，再利用公式R(TRx,TRy)=max{r(TRx,TRy),r(TRy,TRx)}，得到兩條軌跡間的相似性距離,最后求出所有軌跡間的相似性矩陣。

2.2 模糊C-均值聚類的實現

模糊C-均值聚類算法(FCM)[14]是用隸屬度確定每個數據點屬于某個聚類程度的一種聚類算法，其聚類準則是求U，V,使得J(U,V)取得最小值。應用FCM將給定的樣本空間X={x1,x2,…,xn}劃分為c類,分類結果用隸屬度矩陣U=(μij)c×n表示；μij表示第i個樣本屬于第j類的隸屬度，μij滿足式(5)：

(5)

定義目標函數：

(6)

式中：m為冪指數，且m>1；vj(j=1,2,…,c)是聚類中心。

2.3 改進的模糊C-均值聚類

由于FCM采用的梯度法搜索方向總是沿著能量減小的方向，使得算法本身對初始值敏感。針對FCM存在的問題，采用將粒子群(PSO)算法和禁忌搜索(TS)算法相結合的組合優化算法，通過PSO算法的全局尋優能力和TS算法跳出局部極值的能力得到最優初始聚類中心，從而更加快速、有效地收斂到全局最優解。具體步驟如下：

步驟1：輸入待聚類數據，給定FCM算法和組合優化算法的初始參數，如冪指數m，最大迭代次數Tmax，學習因子c1、c2，速度上下界vmax、vmin，慣性權重w，鄰域解、候選解個數及禁忌表長。

步驟2： 初始化粒子群規模n，隨機選擇s個聚類中心組成n×s個粒子。設初始位置為Xi，并隨機產生此n個粒子的隨機速度，t=0。

步驟3： 按照式(6)計算每個粒子個體的適應度值fit(i)，并找出個體極值pbest(i)和全局極值gbest(i)。再比較當前粒子群的局部和全局最優位置和每個粒子的適應度值，最后決定是否替換。

步驟4：根據式(7)和式(8)更新每個粒子的速度和位置，如果滿足誤差閾值要求或算法的迭代次數則繼續下一步，否則返回步驟3。

V′i=w·Vi+c1·r1·[pbest(i)-Xi]+c2·r2·(gbest-Xi)

(7)

X′i=Xi+Vi

(8)

步驟5：以PSO算法的輸出解作為TS算法的初始解，置空禁忌表。

步驟6：如果滿足收斂準則直接輸出最優初始中心；如果不滿足，根據領域函數的定義得到當前解的所有(或若干)鄰域解，并從中確定若干候選解。

步驟7：根據藐視規則來判斷每個候選解是否均滿足，若滿足，則將此候選解認定為當前解，同時將最早放入禁忌表的對象用當前解的對象替換；若不滿足，則判斷候選解的禁忌屬性，此時當前解為非禁忌對象對應的最佳解，同時將最早放入禁忌表的對象用與之對應的禁忌對象替換。

步驟8：判斷是否滿足收斂準則，如果滿足則直接輸出FCM的最優初始中心；如果不滿足，返回步驟6。

3 算例仿真

3.1 飛行軌跡的壓縮處理

以華北地區某機場終端區第16R號跑道的679條進場歷史軌跡為研究對象，共有694 239個原始軌跡點。應用Top-Down Time Ratio算法壓縮飛行軌跡，誤差閾值距離D是一個很關鍵的參數指標，直接決定了是否保留某些關鍵特征點。試驗取一條軌跡點數目為941個的飛行軌跡為研究對象，選擇5個不同的誤差閾值距離來衡量其對軌跡特征點提取的影響，從而確定可以更好反映軌跡分布的軌跡特征點數目，結果如表1和圖2。

表1 軌跡壓縮算法的誤差閾值對比Table 1 Error threshold comparison of trajectory compression algorithm

圖2 不同誤差閾值距離對應的軌跡壓縮Fig. 2 Trajectory compression corresponding to different error threshold distances

由表1可以看出，隨著誤差閾值距離D的不斷增加，軌跡壓縮效果越來越好，但平均誤差距離也進一步增大。同時由圖2明顯地看到，軌跡的關鍵點多集中在曲線轉彎處，近似直線段用較少的點來表征，且隨著誤差閾值距離的減小，更多的特征點被提取出來用來描述近似直線段特征。同時為了檢驗筆者算法在軌跡壓縮時的精確性和穩定性，同現有的DP算法進行對比，以平均距離誤差S作為誤差指標，結果如圖3。

由圖3可知，在相同的壓縮率下，Top-Down Time Ratio算法的平均距離誤差更小些，能較好地還原原始軌跡。此外，隨著壓縮率的不斷增加，兩者的誤差均呈上升趨勢。因此，在保證飛行特征和有效降低數據規模的前提下，此處暫取誤差閾值距離為30 m來壓縮軌跡。

圖3 不同壓縮率下的平均距離誤差Fig. 3 Average distance error under different compression ratios

3.2 飛行軌跡聚類分析

在不同的飛行階段，要均衡體現出位置、速度和航向對軌跡的影響，需要選取不同的權重值。經試驗，取w1=0.7,w2=0.2,w3=0.1。利用式(3)計算出所有軌跡間的相似性距離，得到軌跡間的相似性矩陣。

設置FCM算法參數。取聚類數c=60，即飛行軌跡的聚類中心數；冪指數m=2；目標函數的終止容限為1×10-6；最大迭代次數Tmax=100。

設置PSO算法參數。取粒子群規模N=50；學習因子c1=2,c2=2;最大速度Vmax=2,最小速度Vmin=-2;慣性權重w=0.6；最大迭代次數Tmax=100。

設置TS算法參數。取禁忌表長為25；鄰域解和候選解均取20個；終止判據是最大迭代次數為100。

應用FCM和TSPSO_FCM算法對軌跡間的相似性距離進行聚類，已知該機場至少有3條傳統的標準進場程序，此處暫取聚類數為3類，聚類結果如圖4。

圖4 TSPSO_FCM算法的飛行軌跡聚類Fig. 4 Flight trajectory clustering of TSPSO_FCM

由于聚類算法是以最終保證組內相似度最高，組間相似度最低為聚類原則，結合FCM聚類原理及式(7)知可用目標函數值來衡量聚類效果，FCM與TSPSO_FCM算法各自的聚類性能結果如圖5。

圖5 基于目標函數值的聚類性能比較Fig. 5 Comparison of clustering performance based on objective function values

由圖4可以看出，TSPSO_FCM 算法逐漸減小并且趨于穩定。單獨 FCM 算法的目標函數值在逐步減小的過程中沒有出現反復情形，這也說明基于梯度下降的 FCM 算法在樣本空間進行聚類時就有可能陷入局部極小且目標函數值較大。

3.3 參數變化對聚類效果的影響

針對在飛行軌跡壓縮過程中不同的誤差閾值、聚類數會直接影響最終的聚類結果。因此，在其他各類參數不變的情況下，取不同的誤差閾值距離和聚類數進行試驗，結果如表2。

表2 誤差閾值距離和聚類數的影響Table 2 Influence of error threshold distance and number of clusters

由表2可以看出，當誤差閾值距離逐步增大時且對比未進行軌跡壓縮時，使用 TSPSO_FCM算法得到的目標函數值相比FCM算法更優，聚類效果更好。將飛行軌跡簇k取4類和5類進行聚類時，TSPSO_FCM算法得到的的目標函數值均小于k取3類時，這是因為隨著聚類個數的增多，各類間的緊湊性變大，導致目標函數值變小。由圖6可知，當軌跡簇分為4類時，從東南方向進場的航空器飛行軌跡分為兩簇，符合該終端區的標準進場程序；當軌跡簇分為5類時，很明顯地看到識別出了一種不同于機場傳統進場程序的新的飛行模式。經驗證可知，該飛行模式下的航空器飛行為繁忙時段需調配航空器安全間隔，由管制員直接引導航空器進場所形成。

圖6 不同聚類數對應的飛行軌跡簇Fig. 6 Flight trajectory cluster corresponding to different cluster numbers

因此，該方法通過分析參數的變化對聚類結果的影響，有效地挖掘出了該機場終端區的航空器進場飛行模式，為該機場由傳統程序向基于性能導航(PBN)程序轉變提供重要參考。

4 結 論

1)在保持較低失真率的情況下，采用基于時間比的自頂向下算法壓縮飛行軌跡降低了計算開銷，提高了軌跡數據分析能力。

2)建立基于多維特征屬性的相似性模型，并結合組合優化算法改進FCM算法，避免了單獨使用FCM聚類易于陷入局部最優的缺陷。試驗結果表明，改進的FCM算法具有很強的全局搜索能力，降低了FCM算法對初始值的敏感度，可以得到較優的滿意解。

3)飛行軌跡聚類時參數的變化會直接影響聚類算法對航空器飛行模式的挖掘能力，對于重新設計和優化傳統飛行程序具有重要參考價值。