基于K-means++時(shí)間聚類的飛行航跡預(yù)測

郭憲超，李廷元

（中國民用航空飛行學(xué)院計(jì)算機(jī)學(xué)院，廣漢 618307）

0 引言

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

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

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

1 K-means++時(shí)間聚類算法

1.1 算法主體思想

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

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

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

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

1.2 時(shí)間歸一化及時(shí)間K-means++聚類

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

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

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

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

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

1.3 飛行航跡階段聚類

1.3.1 直線階段聚類

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

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

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

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

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

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

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

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

1.4 航跡預(yù)測

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

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

2 算例實(shí)驗(yàn)

2.1 時(shí)間K-means++聚類仿真實(shí)驗(yàn)

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

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

2.1.1 直線階段聚類

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

圖2 直線階段聚類

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

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

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

2.2 航跡預(yù)測

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

圖4 預(yù)測航跡與真實(shí)航跡對比

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

3 結(jié)語

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