基于反距離權值的終端區航跡預測方法仿真

李 沐

(中國民航大學，天津 300300)

1 引言

終端區域是空管系統中最復雜、管制員壓力最大的區域之一。與巡航的飛行相比，航空器在終端區域內的飛行更易受天氣、飛行沖突，流量異常等狀況的影響，飛行路線更加不確定，有時需要依靠管制員的指令脫離固定的進離場航線飛行。終端區包含大量航跡數據，這些數據中蘊含管制員的意圖，航空器的性能以及飛行員的操作習慣等諸多不易察覺的因素，通過數據挖掘的方法可以對航跡進行精確預測。而終端區內的航跡預測可以為管制員提供航空器的飛行輔助信息，為進一步實現空管自動化提供先決條件。

國內外主要有兩類航跡預測方法，第一類基于航空器動力學與運動學模型[1-3]。該類方法通過對航空器的飛行環境進行推測，考慮溫度、風向和風速等因素對航跡可能產生的影響，根據航空器飛行時所處的不同階段建立不同的空氣動力學模型。此類方法在面對不同機場的終端區時很難構建符合實際的模型。第二類方法是基于數據挖掘的航跡預測。王靜、張建偉[4]等利用遺傳算法挖掘歷史數據，通過基因表達式編程挖掘頻繁函數集建立模型，該模型利用遺傳算法對歷史飛行數據進行操作，挖掘出數據集中相對應的函數關系集合，用較好的函數模型對未來航跡進行預測。Gariel M[5]等利用聚類方法對航跡數據分類，在去除偏離航跡后提取典型航跡，然而該方法航跡的預測精度較低。Song Y[6]等人通過對不同航跡的歷史飛行數據進行分析，并基于分析得出的聚類結果，得到精度更高的預測模型。上述航跡預測方法大多適用于時間較長，距離較遠的航跡預測，在時間跨度較短，情況復雜的終端區時很難做到較為精準地預測。

針對以上問題，本文提出了一種基于反距離權值的終端區航跡預測方法，首先通過聚類算法挖掘出航跡分類信息，結合隨機森林模型給出航跡分類預測模型，然后將分類標簽結合插值后的歷史航跡數據給出典型航跡，最后通過反距離權值法求得更加精準的預測航跡。

2 航跡數據預處理

首先進行數據清洗，整理后得到可用數據，然后利用DTW算法(Dynamic Time Warping)計算航跡間距離作為航跡聚類中各航跡間的距離度量，最后通過聚類算法將終端區域內具有相似時空特征的航跡聚類，得到不同的航跡標簽，為航跡預測提供分類基礎。

2.1 數據整理與壓縮

本文數據來源于廣播式自動相關監視(Automatic Dependent Surveillance Broadcast，ADS-B)。由于地形遮擋，網絡波動等問題，真實航跡與獲取數據之間可能存在偏差，主要問題分為以下3種：

1)數據存在丟包現象，其表現為個別航跡點的缺失或中段部分航跡數據的缺失。此外，部分航跡的起點在數據開始記錄時不在終端區的邊緣，即該航班在開始記錄數據之前已經飛入終端區，此類航跡歸為不完整航跡。對于航跡點缺失較少的情況可以插值補全，對于起點不再終端區邊緣或缺失較多數據點的航跡，應進行去除。

2)數據存在重復項，重復數據在增大了計算量的同時也會影響后期對數據的處理，應去除含有完全相同信息的數據項。

3)存在干擾航跡，部分航班在同一天的飛行時間可能會執行多次航班任務，存在同一航班號對應多條航跡的現象，因此在分離不同航跡時需要在考慮航班號的同時考慮數據點之間的時間間隔，將同一航班號的不同時間段的航跡區分開，排除干擾。

由于數據量大，需要對數據進行適當的壓縮，去除包含冗余信息的數據項，只留下能夠體現航跡特征的數據。本文利用Sliding Window算法[7]壓縮航跡數據。所有留下的特征點形成壓縮后的航跡。

經過以上幾步的數據預處理得到可以用于航跡聚類和航跡插值的數據。

2.2 航跡聚類

2.2.1 航跡間距離

聚類是一種無監督學習，通過一定的規則在無先驗知識的情況下通過定義的相似性將數據分為不同類別的過程。在二維平面問題中，通常用歐式距離定義點與點之間的距離。不同航跡由數目不同的數據點構成，無法通過比較對應點的歐式距離來表示航跡間的距離，因此這里引入動態時間規整算法(Dynamic Time Warping， DTW)計算航跡間的距離[8]。該算法通過動態規劃尋找兩個不同長度序列之間的最優映射，進而計算兩個序列之間的距離。

定義歷史航跡集

C={C1，C2，…，Ci，…，Cj，…，CN}

(1)

式中，Ci和Cj分別代表第i條和第j條歷史航跡；假設Ci和Cj分別由m和n個數據點組成，則

圖1 動態時間規劃過程示意圖

(2)

定義累加距離D(p，q)，從(1，1)點開始匹配序列Ci和Cj，每到一個點，之前所有點的計算距離都會累加。

當匹配點(p，q)到達終點(m，n)后，累加距離D(m，n)為Ci和Cj之間的距離，記為γ(i，j)。

由于DTW算法用時較長，本文將采用效率更高的FastDTW算法[9]，該算法綜合限制搜索空間和數據抽象兩種較為有效的加速方法提高DTW算法的效率。經過計算，歷史航跡集trajprek中各航跡間距離可表示為如下矩陣

(3)

式中，R為N×N的對稱矩陣，矩陣對角線為航跡與自身的距離，均為0。此航跡距離矩陣將用于航跡聚類時的相似度計算。

2.2.2 航跡聚類

由于航跡數量較大，若直接計算所有航跡間距離耗時較長，所以先通過均值漂移聚類算法[10]區分不同入口處的航跡簇，再分別對每一簇航跡進行DBSCAN聚類(Density-Based Spatial Clustering of Applications with Noise)可以提高計算效率。

對航跡數據集的相似度結果進行整合，計算數據集自然簇的均值xi，進而對航跡數據集中的數值型數據進行聚類處理

(4)

以均值xi代表該自然簇，得到新的航跡數據集，采用SINGLE算法對新數據集進行聚類，對k個簇進行合并，計算自然簇質心的初步位置。

由于航跡數據集屬于局部信息，自然簇質心的真實位置相對于初始位置，會發生一定的偏離。因此必須對自然簇質心的初始位置進行偏差修正，以獲取精確度的質心的位置。

基于密度空間的數據聚類方法DBSCAN通過不斷擴張其中心區域[11]，不斷增加區域內所包含的對象的數目。該聚類可由其內部任何一個核心對象所唯一確定，當密度足夠大時，相鄰區域可通過互相連接的方式在包含噪聲干擾的空間數據庫中發現任意形狀的類簇。該方法在面對包含噪聲和異常的空間數據時，處理較為有效。

在得到不同入口點的航跡簇后，針對每一簇航跡，利用1.2.1中航跡間距離矩陣作為航跡間距離度量進行DBSCAN聚類，得到各航跡簇的不同聚類集合。經過DBSCAN聚類得到歷史航跡數據的聚類類別，即排除噪聲航跡后，每條航跡的分類標簽。

2.3 航跡插值

為了更好地利用時間信息串聯各航跡數據，需要對在時間線上缺失的數據進行插值。經過線性插值后的數據在時間層面上有相似的長度，保證了把每條航跡的第1個點記為零時刻時，每隔相同的時間段都有相應的航跡數據。將經過插值后的數據集記為Citp。為了在短時間內進行多次預測，先將插值后的數據按照時間進行分段處理。以Δt為時間間隔切分航跡數據集，保證每一段包含相同數目的數據點。

3 航跡預測算法

通過上一節航跡聚類的方法得到航跡數據的分類標簽。本節通過將數據輸入隨機森林模型得到航跡數據的分類預測，通過預測分類的標簽與經過插值的歷史航跡結合，得到典型航跡，再通過反距離權值[12]法優化典型航跡，得到最終的預測航跡。

隨機森林是一個由多個決策樹組成的分類算法，它的分類輸出標準是多個決策樹輸出分類標簽的相同的大多數，是集成學習中應用較為成功的算法。在隨機森林的構建過程中包含兩部分，一部分在訓練數據中采用有放回的方式對等量的訓練樣本進行隨機采樣，另一部分是在建立決策樹時對屬性的特征進行隨機選取。這種隨機選取樣本以及隨機選取特征的方式可以在一定程度上降低決策樹之間的相關性，可以在模型的準確性上有進一步的提高。

隨機森林分為訓練和測試兩個部分，將歷史航跡數據集分為兩個部分，訓練集和測試集，訓練時輸入訓練集航跡經度，緯度數據以及每條航跡數據所在分類標簽，輸出為航跡預測分類標簽，在訓練過后得到符合當下情況的隨機森林模型，再輸入測試集航跡數據，得到測試集預測分類標簽。

將Citp按照時間間隔Δt分段，第k段航跡數據集記為CΔtk，第k段航跡預測分類為clusterk，測試航跡記為trajt，第k段測試航跡記為trajtk，第k段典型航跡數據集記為Trajtypk，包含的航跡數目記為l，第k段典型航跡記為trajtypk，第k段預測航跡記為trajprek。

具體的航跡預測流程如下：

將第k段測試航跡trajtk輸入訓練好的隨機森林模型，輸出測試航跡的分類標簽clusterk。

找到第k段航跡數據集CΔtk中屬于clusterk類的航跡數據集，選取其中與測試航跡trajtk距離最近的l條航跡形成典型航跡數據集Trajtypk，Trajtypk包含這l條航跡所有時間段的航跡數據。

在第k+1段求這l條航跡的平均航跡得到第k+1段的典型航跡trajtypk+1。

將第k+1段典型航跡trajtypk+1作為觀測航跡，利用反距離權值法重新分配Trajtypk中所有航跡數據點的權值。

利用新的權值與典型航跡數據集Trajtypk中在第k+1段所有航跡數據求加權平均得到第k+1段trajprek+1。

4 實驗驗證與分析

選取天津濱海國際機場終端區域，數據緯度區間為北緯38°至北緯40°，經度區間為東經115°至東經119°，2017年5月4日至30日共3074條歷史航跡數據進行航跡預測。

4.1 聚類結果

針對所有航跡入口點進行均值漂移聚類，經過反復測試，設置bandwidth為0.152，每個圓內包含的點數為30，每個聚類內的數據點數目需大于20個。結果如圖2a所示，該算法將所有航跡入口處的數據分為7類。

選取航跡簇1中的航跡進行DBSCAN聚類，結果如圖2b)所示，圖中不同顏色的線分別代表同一航跡簇下3類不同的聚類，從圖中可以明顯地看出不同機場跑道入口處沒有出現分類不正確的情況，因此聚類效果是比較理想的，可以作為航跡預測分類的標準。

圖2 航跡聚類

4.2 航跡預測結果

將插值時間選為每1秒進行一次插值，Δt為60秒，l為10。選取測試集中的某條航跡，輸入航跡預測模型，將得到的典型航跡、預測航跡與實際航跡作對比。

圖3 航跡預測

圖中紅色線段為真實航跡，綠色線段為典型航跡，藍色線段為預測航跡。在整體航跡的預測過程中，典型航跡與實際航跡的距離較大，而通過圖3b也可以看出典型航跡只能大致給出航跡的走勢，但在改變權重之后，預測航跡與實際航跡非常貼合。具體誤差值如圖4所示。預測航跡每秒與實際航跡間距離差不超過1.1km。而典型航跡的差距較大，所以通過反距離權值重新分配權重方法是有效的。

圖4 預測航跡與典型航跡誤差比較

5 結束語

本文基于歷史航跡數據集研究了終端區域航跡預測問題，提出了一種結合隨機森林和反距離權值的航跡預測算法，首先闡明了通過聚類算法獲得航跡分類標簽的過程，其次將插值后的數據按照時間分段，通過隨機森林模型與插值后的歷史航跡數據相結合生成典型航跡，采用反距離權值法將典型航跡生成預測航跡，實驗驗證表明當數據量較大時，這種針對終端區的航跡預測方法效果較為理想。