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

郭憲超，李廷元

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

0 引言

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

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

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

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

1.1 算法主體思想

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

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

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

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

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

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

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

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

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

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

1.3 飛行航跡階段聚類

1.3.1 直線階段聚類

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

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

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

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

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

1.3.2 轉彎階段聚類

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

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

1.4 航跡預測

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

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

2 算例實驗

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

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

圖1 時間K-means++聚類結果

2.1.1 直線階段聚類

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

圖2 直線階段聚類

2.1.2 轉彎階段聚類

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

圖3 轉彎階段聚類

2.2 航跡預測

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

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

圖5 預測結果誤差

3 結語

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