郭憲超，李廷元

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

0 引言

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

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

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

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

1.1 算法主體思想

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

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

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

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

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

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

時(shí)間歸一化處理完成后，接下來需要對(duì)時(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)較大誤差。

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

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

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

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

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

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

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

1.4 航跡預(yù)測(cè)

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

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

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

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

對(duì)航跡點(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）對(duì)時(shí)間進(jìn)行歸一化處理。

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

2.1.1 直線階段聚類

首先通過采樣法對(duì)所有直線飛行的航跡數(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)彎階段聚類

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

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

2.2 航跡預(yù)測(cè)

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

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

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

3 結(jié)語

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