基于K-means++時間聚類的飛行航跡預測

郭憲超，李廷元

（中國民用航空飛行學院計算機學院，廣漢 618307）

0 引言

近年來，隨著我國民航業(yè)的快速發(fā)展，我國航空公司的機隊規(guī)模也在迅速壯大，航空器數(shù)量的飛速增長使飛行流量沖突問題變得越發(fā)嚴重，所以，如何在現(xiàn)有民航系統(tǒng)條件下提高飛行流量預測的準確性成為當今民航業(yè)研究的熱點。

目前對空中交通流量進行預測的主要思路是通過預測航空器的飛行航跡進而實現(xiàn)某一空域內(nèi)空中交通流量的預測。交互式多模型跟蹤濾波（IMM）航跡預測算法可以有效改善以往航跡預測算法的精度，適用于短期區(qū)域內(nèi)的飛行流量預測；也有學者通過使用深度學習神經(jīng)網(wǎng)絡算法進行航跡預測，預測模型融合了卷積神經(jīng)網(wǎng)絡算法和長短期記憶網(wǎng)絡算法，通過分析仿真實驗結(jié)果表明該組合模型相比單一算法的模型具有更高的預測精度；同樣，通過分析戰(zhàn)術(shù)預測的特點進行航跡配對也是航跡預測的一種方式，該算法綜合各種算法的特點進行4D計劃飛行航跡的構(gòu)建，可以將動態(tài)飛行數(shù)據(jù)與計劃飛行航跡相融合，最終實現(xiàn)航空器4D航跡的實時更新。目前的航跡預測算法對時間數(shù)據(jù)和航空器的飛行航跡特征的預測并不理想，而通過聚類算法對飛行航跡數(shù)據(jù)進行聚類可以有效改善上述問題。

針對目前航空器飛行航跡預測算法的不足，本文提出一種基于K-means++時間聚類的飛行航跡預測方法，通過K-means++算法對時間數(shù)據(jù)進行聚類，使用修正歐式距離算法進行航跡相似度計算的改進型聚類算法，使用實際飛行航跡歷史數(shù)據(jù)進行案例實驗，實驗結(jié)果表明，該算法具有較高的預測精度。

1 K-means++時間聚類算法

1.1 算法主體思想

由于機場區(qū)域的相關(guān)飛行限制，使得該區(qū)域內(nèi)航空器的飛行航跡具有規(guī)律性，同時ADS-B數(shù)據(jù)主要由航空器的經(jīng)度、緯度、高度和飛行時間等信息構(gòu)成，所以ADS-B航跡數(shù)據(jù)中包含了大量的時間和空間信息，符合本文對航跡進行聚類的基本要求。ADS-B數(shù)據(jù)中的每條航跡都會有單獨的一個航班號與之對應，所以每條航跡的組成格式為：

在上式中，代表某條單獨的航跡，代表其中的航跡點，該條航跡由個航跡點組成，同時每個航跡點中都三維位置信息和發(fā)布時間信息4個屬性的信息，即x,y,z,t。

如若按照時間順序排列，機場扇區(qū)內(nèi)的ADS-B數(shù)據(jù)嚴格意義上來說就是扇區(qū)內(nèi)所有航跡組成的航跡數(shù)據(jù)集，即：

對時間進行歸一化處理，使每條聚類航跡都有統(tǒng)一的起始時間，然后使用K-means++算法進行時間聚類，同時在進行時間相似度計算時使用修正歐氏距離算法，可以大大提高航跡預測過程中時間預測的準確性；再對飛行航跡階段進行劃分，在直線階段使用模糊聚類法進行航跡聚類，在轉(zhuǎn)彎階段使用DBSCAN時間序列聚類法進行航跡聚類，這樣可以提高航跡聚類結(jié)果的準確性；最后通過修正聚類航跡得到預測航跡。

1.2 時間歸一化及時間K-means++聚類

本文選取的ADS-B數(shù)據(jù)為綿陽機場扇區(qū)內(nèi)4月份的數(shù)據(jù)，進行時間聚類時首先要對時間數(shù)據(jù)進行歸一化處理，將所有航跡的起始時間定義為第1秒，這樣可以得到每條航跡的飛行時間T，然后使用K-means++算法對其進行聚類處理，可以得到更為準確的航行時間T，所有航跡的時刻點t按照下述公式來進行在［0，T］運行區(qū)間內(nèi)的歸一化：

時間歸一化處理完成后，接下來需要對時間數(shù)據(jù)進行K-means++聚類，在時間聚類階段使用修正歐氏距離作為相似度的劃分標準。

首先需要確定最終的簇類數(shù)量，從個數(shù)據(jù)中隨機挑選1個數(shù)據(jù)作為聚類中心點，然后計算剩余的-1分數(shù)據(jù)點之間的修正歐式距離：

上式中，x和x分別代表數(shù)據(jù)集中包含的-1個剩余數(shù)據(jù)的任意兩個數(shù)據(jù)點。

接下來我們需要在-1個數(shù)據(jù)點中選取剩下的-1個聚類中心，計算剩余數(shù)據(jù)點與的距離，距離越遠的數(shù)據(jù)點被選為下一個聚類中心的概率就越大，而概率計算方法為輪盤法，然后不斷重復該步驟，直到個聚類中心點,…M被選擇出來為止。按照修正歐氏距離算法來將剩余的-個數(shù)據(jù)點劃分給與之相距最近的聚類中心形成新的類，使用均值法計算每個新類的中心點，最后執(zhí)行K-means聚類算法的迭代過程，直至所有數(shù)據(jù)被分配完畢。

1.3 飛行航跡階段聚類

1.3.1 直線階段聚類

雖然航跡數(shù)據(jù)一般會出現(xiàn)數(shù)據(jù)缺失的情況，但由于飛機在直線飛行階段的飛行狀態(tài)不會出現(xiàn)大范圍波動，所以即使出現(xiàn)少量航跡點數(shù)據(jù)的缺失也不會使航跡聚類的結(jié)果出現(xiàn)較大誤差。

針對上述航空器直線飛行的特征，可以將直線階段聚類過程分為三步：

（1）通過使用采樣法在航跡數(shù)據(jù)中提取出可以代表整條航跡的特征數(shù)據(jù)點M，參照文獻［4］可以得知使用10%的特征點就可以代表整條直線階段的航跡。

（2）當完成特征點M的提取后，可以得到由特征點組成的特征航跡H，接下來對特征航跡H使用模糊C均值聚類算法進行處理。

（3）時間數(shù)據(jù)經(jīng)過了前文的歸一化過程之后，使得所有航跡的時間區(qū)間具有相似特征，因此可以將時間維度包含到空間數(shù)據(jù)點中，所以在進行模糊C均值聚類時使用修正歐氏距離來進行對應點M(x,y,z,t)和M(x,y,z,t)之間的修正歐式距離。

1.3.2 轉(zhuǎn)彎階段聚類

飛機轉(zhuǎn)彎階段航跡的集中程度較低，所以針對轉(zhuǎn)彎階段的航跡特征，該階段使用全時間序列聚類方法，具體步驟如下：

（4）當進行完所有時刻的簇類集合遍歷后可以得到他們的交集，該交集在相同時間層面上存在相同對象，所以可以稱之為目標簇集合；若出現(xiàn)遍歷結(jié)束后的空集，則自動轉(zhuǎn)為模糊聚類法作為直線階段進行聚類；運算結(jié)束時可以得到聚類航跡簇的均值航跡。

1.4 航跡預測

前文曾提到，由于機場區(qū)域內(nèi)各種特殊規(guī)定的限制，使得在機場區(qū)域內(nèi)航空器的飛行航跡具有規(guī)律性，所以我們獲得的聚類航跡具有典型性，可以通過該聚類航跡來對未來短期機場區(qū)域內(nèi)航班的飛行航跡進行預測，對未來+時刻的飛行航跡進行預測的步驟為：

注：在上式中，為未來的時間量，H 代表聚類航跡，H 代表真實航跡，H 為預測航跡，?()用來表示在時刻時真實航跡與聚類航跡對應點的誤差值

2 算例實驗

2.1 時間K-means++聚類仿真實驗

對航跡點的時間數(shù)據(jù)進行k-means++聚類，我們將所有時間數(shù)據(jù)分為三個類：時間偏大類、中間類、時間偏小類，即為3，時間K-means++聚類結(jié)果圖如圖1所示。在選取完成聚類后的時間數(shù)據(jù)時只選取中間類T作為最終的聚類統(tǒng)一時間，得到聚類時間T=1648s，最后通過公式（4）對時間進行歸一化處理。

圖1 時間K-means++聚類結(jié)果

2.1.1 直線階段聚類

首先通過采樣法對所有直線飛行的航跡數(shù)據(jù)進行特征點的提取，采樣結(jié)果使原始的30394個航跡數(shù)據(jù)點降低為2571個，然后將提取出來的2571個航跡特征數(shù)據(jù)點使用模糊C均值聚類法進行聚類處理，如圖2所示為直線第三階段的聚類結(jié)果，其中的紅色“.”代表歷史真實航跡點，而綠色“*”代表直線階段聚類航跡點。

圖2 直線階段聚類

2.1.2 轉(zhuǎn)彎階段聚類

對每條轉(zhuǎn)彎航跡數(shù)據(jù)點進行3次插值處理，對補全的航跡數(shù)據(jù)進行時間間隔為4 s的重新取樣，然后進行DBSCAN聚類；在對每個時刻的聚類結(jié)果完成遍歷搜索后，得出的轉(zhuǎn)彎階段航跡聚類結(jié)果如圖3所示，其中紅色點集為歷史航跡點，綠色點集為聚類航跡點。

圖3 轉(zhuǎn)彎階段聚類

2.2 航跡預測

如圖4所示為CSC8564航班的預測航跡與真實航跡對比圖，圖中紅色航跡為預測航跡，綠色航跡為實際航跡，圖5所示為預測航跡與真實航跡平方誤差圖，從圖中可以看出誤差方差值在0～0.3之間，由此可知，該算法具有較高的預測精度。

圖4 預測航跡與真實航跡對比

圖5 預測結(jié)果誤差

3 結(jié)語

本文針對傳統(tǒng)航跡聚類預測算法對時間數(shù)據(jù)預測不準確的問題提出了一種基于K-means++時間聚類的航跡預測算法。該算法使用ADS-B數(shù)據(jù)作為數(shù)據(jù)源，通過K-means++算法對時間數(shù)據(jù)進行聚類，使用修正歐式距離算法進行航跡相似度的計算，根據(jù)直線階段和轉(zhuǎn)彎階段的特征分配不同的聚類方法得出聚類航跡。最后對聚類航跡進行當前位置修正得到預測航跡。通過實際航跡數(shù)據(jù)進行算例試驗，結(jié)果顯示該預測算法具有較高的準確性。