基于反距離權(quán)值的終端區(qū)航跡預(yù)測方法仿真

李 沐

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

1 引言

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

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

針對以上問題，本文提出了一種基于反距離權(quán)值的終端區(qū)航跡預(yù)測方法，首先通過聚類算法挖掘出航跡分類信息，結(jié)合隨機(jī)森林模型給出航跡分類預(yù)測模型，然后將分類標(biāo)簽結(jié)合插值后的歷史航跡數(shù)據(jù)給出典型航跡，最后通過反距離權(quán)值法求得更加精準(zhǔn)的預(yù)測航跡。

2 航跡數(shù)據(jù)預(yù)處理

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

2.1 數(shù)據(jù)整理與壓縮

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

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

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

3)存在干擾航跡，部分航班在同一天的飛行時間可能會執(zhí)行多次航班任務(wù)，存在同一航班號對應(yīng)多條航跡的現(xiàn)象，因此在分離不同航跡時需要在考慮航班號的同時考慮數(shù)據(jù)點(diǎn)之間的時間間隔，將同一航班號的不同時間段的航跡區(qū)分開，排除干擾。

由于數(shù)據(jù)量大，需要對數(shù)據(jù)進(jìn)行適當(dāng)?shù)膲嚎s，去除包含冗余信息的數(shù)據(jù)項，只留下能夠體現(xiàn)航跡特征的數(shù)據(jù)。本文利用Sliding Window算法[7]壓縮航跡數(shù)據(jù)。所有留下的特征點(diǎn)形成壓縮后的航跡。

經(jīng)過以上幾步的數(shù)據(jù)預(yù)處理得到可以用于航跡聚類和航跡插值的數(shù)據(jù)。

2.2 航跡聚類

2.2.1 航跡間距離

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

定義歷史航跡集

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

(1)

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

圖1 動態(tài)時間規(guī)劃過程示意圖

(2)

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

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

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

(3)

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

2.2.2 航跡聚類

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

對航跡數(shù)據(jù)集的相似度結(jié)果進(jìn)行整合，計算數(shù)據(jù)集自然簇的均值xi，進(jìn)而對航跡數(shù)據(jù)集中的數(shù)值型數(shù)據(jù)進(jìn)行聚類處理

(4)

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

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

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

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

2.3 航跡插值

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

3 航跡預(yù)測算法

通過上一節(jié)航跡聚類的方法得到航跡數(shù)據(jù)的分類標(biāo)簽。本節(jié)通過將數(shù)據(jù)輸入隨機(jī)森林模型得到航跡數(shù)據(jù)的分類預(yù)測，通過預(yù)測分類的標(biāo)簽與經(jīng)過插值的歷史航跡結(jié)合，得到典型航跡，再通過反距離權(quán)值[12]法優(yōu)化典型航跡，得到最終的預(yù)測航跡。

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

隨機(jī)森林分為訓(xùn)練和測試兩個部分，將歷史航跡數(shù)據(jù)集分為兩個部分，訓(xùn)練集和測試集，訓(xùn)練時輸入訓(xùn)練集航跡經(jīng)度，緯度數(shù)據(jù)以及每條航跡數(shù)據(jù)所在分類標(biāo)簽，輸出為航跡預(yù)測分類標(biāo)簽，在訓(xùn)練過后得到符合當(dāng)下情況的隨機(jī)森林模型，再輸入測試集航跡數(shù)據(jù)，得到測試集預(yù)測分類標(biāo)簽。

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

具體的航跡預(yù)測流程如下：

將第k段測試航跡trajtk輸入訓(xùn)練好的隨機(jī)森林模型，輸出測試航跡的分類標(biāo)簽clusterk。

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

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

將第k+1段典型航跡trajtypk+1作為觀測航跡，利用反距離權(quán)值法重新分配Trajtypk中所有航跡數(shù)據(jù)點(diǎn)的權(quán)值。

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

4 實驗驗證與分析

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

4.1 聚類結(jié)果

針對所有航跡入口點(diǎn)進(jìn)行均值漂移聚類，經(jīng)過反復(fù)測試，設(shè)置bandwidth為0.152，每個圓內(nèi)包含的點(diǎn)數(shù)為30，每個聚類內(nèi)的數(shù)據(jù)點(diǎn)數(shù)目需大于20個。結(jié)果如圖2a所示，該算法將所有航跡入口處的數(shù)據(jù)分為7類。

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

圖2 航跡聚類

4.2 航跡預(yù)測結(jié)果

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

圖3 航跡預(yù)測

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

圖4 預(yù)測航跡與典型航跡誤差比較

5 結(jié)束語

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