融合氣象數(shù)據(jù)的并行化航班延誤預測模型

吳仁彪 李佳怡 屈景怡

(中國民航大學天津市智能信號與圖像處理重點實驗室，天津 300300)

1 引言

根據(jù)美國航空數(shù)據(jù)網(wǎng)站Flightstats列出的2016年全球航空公司延誤率排名顯示，中國四家航空公司航班延誤時長排世界前十，可見我國航班延誤問題十分嚴重。雖然民航總局和各機場、航空公司針對航班延誤問題都采取了一定的應急措施，但事后的狀況料理效果有限。航班延誤預測可使相關(guān)部門提前知曉可能延誤的時間，做好應對措施并進行航班計劃和機位指派的優(yōu)化，具有重要的現(xiàn)實意義[1]。

國內(nèi)外已有大量學者投入到航班延誤預測的工作中[2-3]。文獻[4]考慮同一架飛機的連續(xù)航班情況，利用貝葉斯網(wǎng)絡進行航班延誤波及分析，可反映連續(xù)航班延誤原因分布及波及分布。文獻[5]提出一種針對機場繁忙時段的航班延誤免疫預測算法，可針對一天不同時段繁忙程度的差異性，自適應調(diào)整算法中的檢測參數(shù)。以上方法雖都取得了較高的正確率，但都沒有考慮到氣象因素對航班延誤預測的影響?？裳芯勘砻鳉庀笠蛩貙τ诤桨嘌诱`預測十分重要，在諸多影響原因中占比例較大，融入氣象數(shù)據(jù)有利于正確率的進一步提高[6]。

當融入更多特征后，不可避免地導致數(shù)據(jù)量增大。一方面可基于大數(shù)據(jù)挖掘更多有效信息，以提高預測正確率[7]；另一方面又將導致運算量的成倍增長，使傳統(tǒng)數(shù)據(jù)處理方式和預測算法面臨計算瓶頸。例如，文獻[8]采用支持向量機算法進行航班延誤預測，同時考慮航空網(wǎng)絡信息擴展特征，降低預測誤差。但受數(shù)據(jù)處理能力限制，需要采用PCA(Principal Component Analysis)方法對擴展特征后的數(shù)據(jù)進行有效降維。隨著大數(shù)據(jù)技術(shù)的快速發(fā)展，并行計算框架已作為應對計算瓶頸的有效手段應用于諸多行業(yè)[9-11]。文獻[10]在Spark并行計算框架基礎上，采用大規(guī)模機器學習進行藥物靶目標識別；文獻[11]利用改進的并行化聚類算法辨識電力系統(tǒng)的不良數(shù)據(jù)。這些應用都表明使用大數(shù)據(jù)處理技術(shù)可有效增強模型的數(shù)據(jù)處理能力并增強算法效果。但較少有人基于大數(shù)據(jù)平臺進行航班延誤預測。文獻[12] 率先采用深度學習方法預測機場延誤狀態(tài)，使用長短時記憶網(wǎng)絡(long short term memory，LSTM)考慮時間維度特征，但該模型沒有克服深度加深時模型無法收斂的難題，且實現(xiàn)的是機場延誤狀態(tài)的預測，并沒有給出單個航班的延誤時間范圍。

本文基于Spark并行架構(gòu)進行了航班延誤數(shù)據(jù)和氣象數(shù)據(jù)的融合，并使用并行化隨機森林算法[13]構(gòu)建航班延誤預測模型?？稍跓o需數(shù)據(jù)降維的情況下挖掘海量航班延誤數(shù)據(jù)中的數(shù)據(jù)特征，并通過并行化計算快速進行到港航班延誤等級預測。

2 數(shù)據(jù)預處理

航班延誤預測模型的整個流程都在Spark并行計算框架中完成，原始航班數(shù)據(jù)和氣象數(shù)據(jù)存于Hadoop分布式文件系統(tǒng)(Hadoop Distributed File System，HDFS)，每步輸出的中間數(shù)據(jù)以數(shù)據(jù)框的形式存儲于集群內(nèi)存，可快速進行算法迭代和后續(xù)的數(shù)據(jù)再利用。

2.1 數(shù)據(jù)定義

為方便后文敘述，現(xiàn)對數(shù)據(jù)定義如下：

定義 1航班數(shù)據(jù)F中包含〈C,So,Sd,Ao,Ad,tsd,tad,tsa,taa〉，其中，C代表航空器型號，So代表起飛機場所在州；Sd代表目的機場所在州；Ao代表起飛機場；Ad代表目的機場；tsd代表計劃起飛時間；tad代表實際起飛時間；tsa代表計劃到達時間；taa代表實際到達時間。

定義 2氣象數(shù)據(jù)O中包含〈A,t,T,H,Wd,Ws,P,S,V〉，其中，A代表觀測站所在機場；t代表觀測時間；T代表溫度；H代表濕度；Wd代表風向；Ws代表風速；P代表氣壓；S代表天空狀況；V代表能見度。

定義 3在數(shù)據(jù)融合時，考慮航班到達前n個小時內(nèi)目的機場氣象數(shù)據(jù)，其定義如下

Wd,n=〈O(Ad,tsa),…,O(Ad,tsa-nh)〉

(1)

其中，O(Ad,tsa)代表目的機場Ad在到達時間tsa的氣象數(shù)據(jù)；O(Ad,tsa-nh)代表目的機場Ad在到達時間tsa向前追溯n個小時后所在時刻的氣象數(shù)據(jù)。

定義 4航班離港延誤時間DD(F)定義為實際起飛時間和計劃起飛時間的差值：

DD(F)=F.tad-F.tsd

(2)

定義 5航班到港延誤時間AD(F)定義為實際到達時間和計劃到達時間的差值：

AD(F)=F.taa-F.tsa

(3)

定義 6給定一次航班F和時間閾值Th，若AD(F)≥Th則判定航班延誤，否則判為不延誤。

2.2 數(shù)據(jù)融合

首先，需要完成數(shù)據(jù)清洗和標準化。在樣本量足夠大的情況下，數(shù)據(jù)清洗時直接對數(shù)據(jù)中有空值的航班數(shù)據(jù)和氣象數(shù)據(jù)刪除。同時本文只關(guān)注延誤數(shù)據(jù)，因此對于數(shù)據(jù)集中取消和改航數(shù)據(jù)進行過濾處理，并依據(jù)起飛機場所在州和目的機場所在州進行各州州時轉(zhuǎn)換，保證全部時間的時區(qū)一致。

由于航班數(shù)據(jù)和氣象數(shù)據(jù)分別具有不同的量綱和標識方式，因此對名義變量進行編碼，編碼采用頻次統(tǒng)計的方式，每一變量中出現(xiàn)頻次最高的變量值編碼為0，其次為1，依次類推。這種編碼方式可保證特征的稀疏性，增強魯棒性。最后對所有特征按公式(4)進行標準化處理。

(4)

數(shù)據(jù)融合之前需將航班數(shù)據(jù)和氣象數(shù)據(jù)建立關(guān)聯(lián)，以保證信息的時空一致性?？臻g維度上以航班數(shù)據(jù)中的目的機場和氣象數(shù)據(jù)中的觀測站所在機場確定相同位置；時間維度上以航班計劃到達時間和氣象觀測時間作為關(guān)聯(lián)參數(shù)。數(shù)據(jù)融合過程在Spark并行架構(gòu)中使用數(shù)據(jù)框和Spark sql程序自動完成，底層以Map和Reduce過程實現(xiàn)。

圖1 數(shù)據(jù)融合Fig.1 Data fusion

數(shù)據(jù)融合過程如圖1所示。首先在Map階段對不同分區(qū)數(shù)據(jù)建立關(guān)聯(lián)主鍵，航班數(shù)據(jù)以Ad和tsa作為關(guān)聯(lián)主鍵，氣象數(shù)據(jù)以A和t作為關(guān)聯(lián)主鍵；構(gòu)建主鍵后依據(jù)主鍵將數(shù)據(jù)分區(qū)(Partition)，將相同主鍵數(shù)據(jù)放入同一Partition；最后在Partition內(nèi)進行Reduce操作，完成氣象數(shù)據(jù)和航班數(shù)據(jù)的融合。當考慮到達機場n個小時的氣象數(shù)據(jù)時，將公式(1)中定義的Wd,n-1輸入Map1中，Map2中關(guān)聯(lián)主鍵變?yōu)锳d和tsa-nh，Reduce階段輸入不變，從而得到Wd,n。

3 并行化隨機森林算法

本文的航班延誤預測模型采用并行化隨機森林算法進行分類預測。模型訓練時，使用HDFS將融合后數(shù)據(jù)均勻分布于集群機器中。然后利用訓練集構(gòu)建決策樹，用測試集進行分類能力評估，如圖2所示。

在訓練基決策樹時采用并行化的訓練方式，每步中間數(shù)據(jù)以數(shù)據(jù)框形式存儲。為盡可能利用Spark并行框架的計算優(yōu)勢，本文采用并行樹策略和并行切分策略兩種優(yōu)化方法，如圖3所示。

表1 并行化隨機森林算法

(1)并行樹策略。傳統(tǒng)單機構(gòu)建隨機森林時，采用深度優(yōu)先方式遞歸調(diào)用，逐個生成樹。在并行框架下，可在訓練數(shù)據(jù)時將數(shù)據(jù)緩存于不同分區(qū)，采用廣度優(yōu)先策略。每個分區(qū)的數(shù)據(jù)單獨訓練一棵基決策樹，每棵樹的訓練互不影響，之后進行聚合形成隨機森林模型。此時，隨機森林模型構(gòu)建時間等于單個決策樹的生成時間。

(2)并行切分策略。在進行基決策樹分類器的屬性切分時，傳統(tǒng)對連續(xù)特征屬性所有值進行排序再分裂的方法在分布式環(huán)境下并不可行。因為大量且高維數(shù)據(jù)情況下將產(chǎn)生高額計算代價和通信開銷，算法效率低下。因此，將多個分區(qū)并行進行屬性劃分，根據(jù)分裂準則選取最優(yōu)分裂點，并轉(zhuǎn)化為根據(jù)最優(yōu)分裂點劃分的分區(qū)。最后再將每個分區(qū)選擇的最優(yōu)分裂點聚合，選出全局最優(yōu)分裂點。

圖2 航班延誤預測模型Fig.2 Flight delay prediction model

圖3 并行策略Fig.3 Parallel strategy

并行化后的算法原理如表1所示。首先，給定一個原始數(shù)據(jù)集D，使用自助采樣法進行T次有放回采樣，生成T個包含m個樣本的采樣集Dt，并將每個采樣集存儲于不同分區(qū)；然后同時使用各個分區(qū)數(shù)據(jù)訓練基決策樹，訓練時假設每個樣本有d個屬性，則在訓練基決策樹的每個結(jié)點時先從該結(jié)點的屬性集合中隨機選擇包含d′個屬性的子集dt，再從dt中按并行切分策略選擇一個最優(yōu)屬性進行劃分；最后返回每個基決策樹的訓練結(jié)果ht并按公式(5)進行聚合計算。

(5)

其中，arg maxf(x)表示當f(x)取最大時x的取值，Y代表類別集合，y代表預測樣本的實際類別。

在步驟5中選取劃分屬性時，數(shù)據(jù)集D′t的純度使用基尼指數(shù)(Gini index)度量。

(6)

其中，py表示樣本集合D′t中第y類樣本所占比例，py′代表第y′類樣本所占比例，y，y′=1,2，…,|Y|。Gini(D′t)反映了數(shù)據(jù)集D′t中隨機抽取兩個樣本其類別標記不一致的概率。Gini(D′t)越小則數(shù)據(jù)集D′t的純度越高。

(7)

在每次劃分時，按公式(8)計算數(shù)據(jù)不純度減少程度。

ΔGini(a)=Gini(D′t)-Gini_index(D′t,a)

(8)

選取劃分后基尼指數(shù)降低最大的特征作為最優(yōu)劃分特征，即：

(9)

在測試時同樣將多個分區(qū)的數(shù)據(jù)并行輸入隨機森林模型同時測試，從而提高算法效率。由于采用自助采樣法進行抽樣，每個決策樹的訓練樣本Dt中包含原數(shù)據(jù)集D中63.2%的樣本，則剩下的約36.8%樣本則可作為圖2模型中的測試集使用各基學習器進行預測。另Hoob(x)表示預測函數(shù)，則有：

(10)

4 實驗

本文模型使用數(shù)據(jù)為美國交通運輸統(tǒng)計局(Bureau of Transportation Statistics，BTS)提供的航班準時表現(xiàn)數(shù)據(jù)(Airline On-Time Performance Data，AOTP)和美國國家海洋和大氣管理局(National Oceanic and Atmospheric Administration，NOAA)提供的本地氣候質(zhì)量監(jiān)控數(shù)據(jù)(Quality Controlled Local Climatological Data，QCLCD)[12]。從AOTP中提取一次航班的所有信息，包括起飛和降落時間、航空器型號、起飛機場、目的機場、起飛城市、目的城市等，構(gòu)建航班數(shù)據(jù)。從QCLCD中提取每個航班計劃到達時刻目的機場的天氣情況、溫度、能見度、濕度、風速、風向等信息，構(gòu)建氣象數(shù)據(jù)。

其中，AOTP包含從1987年至今的航班數(shù)據(jù)，QCLCD包含美國1600個氣象觀測站的氣象數(shù)據(jù)，氣象數(shù)據(jù)每小時進行一次更新。本文使用兩個數(shù)據(jù)源中2015-2016年數(shù)據(jù)，數(shù)據(jù)信息如表2所示。

表2 數(shù)據(jù)源信息

實驗環(huán)境為包括一個主節(jié)點和四個從節(jié)點的Spark集群，集群的調(diào)度模式為standalone[14]。每臺計算機的硬件配置為內(nèi)存8GB，處理器6核。軟件配置為操作系統(tǒng)Centos6.5，并安裝Hadoop2.6.3和Spark2.0版本。本模型采用深度為16，決策樹個數(shù)為50的隨機森林模型。

4.1 模型正確率和召回率

由于航班延誤預測是偏分類問題，如將大部分航班判為不延誤，雖然模型正確率很高但是沒有實際預測意義。因此引入延誤召回率作為模型衡量指標。

預測結(jié)果混淆矩陣如表3所示。實際為延誤預測也為延誤的航班為真正例(true positive，TP)，實際為延誤預測為不延誤的為假反例(false negative，F(xiàn)N)，實際為不延誤預測也為不延誤的為真反例(true negative，TN)，實際為不延誤預測為延誤的為假正例(false positive，F(xiàn)P)。

表3 預測結(jié)果混淆矩陣

圖4 考慮氣象因素時預測性能變化Fig.4 Predicts performance changes when consideringweather factors

正確率Acc用以衡量所有判斷正確的航班數(shù)占總航班數(shù)的百分比，按如下公式計算：

(11)

航班延誤預測召回率Rec代表延誤航班判斷正確數(shù)量占總延誤航班數(shù)的百分比，按公式(12)計算。

(12)

取Th為60，融合不同小時的天氣數(shù)據(jù)后，Acc和Rec變化曲線如圖4所示。在不考慮氣象因素時，正確率就已達到90%以上，但召回率卻相對較低。這是由于航班延誤預測屬于偏分類問題，有大量樣本預測為不延誤。這也說明了引入召回率作為衡量指標的重要性。

隨著考慮氣象因素小時數(shù)的增加，離港延誤預測和到港延誤預測的正確率變化不大，但召回率都顯著提高，且到港延誤預測的提升優(yōu)于離港延誤預測。這一方面驗證了高維氣象特征對衡量指標的重要影響，另一方面說明了起飛和降落受氣象因素影響程度的差異性。

分別選取Th=15、30、45、60時，Acc和Rec變化曲線如圖5所示。隨著閾值的增大，離港延誤預測和到港延誤預測正確率和召回率提高，且趨勢基本一致。當Th=15時，離港延誤預測可取得73.05%的召回率和90.1%的正確率；到港延誤預測可取得83.2%的召回率和93.7%的正確率。當在Th=60時，離港延誤預測可取得84.8%的召回率和95.4%的正確率；到港延誤預測可取得93.1%的召回率和99.0%的正確率。當閾值增加時，不延誤樣本和延誤樣本的不均衡比例減小，模型性能得以進一步提高。

圖5 不同閾值對預測性能影響Fig.5 Influence of different thresholds on prediction Performance

4.2 泛化誤差性能

使用分類強度s、決策樹之間的相關(guān)性ρ以及ρ/s2比率度量隨機森林測試時的泛化誤差性能。隨機森林各決策樹之前相關(guān)性越小，單個決策樹強度越高，則ρ/s2越小，代表隨機森林性能越好。

分類強度定義為：

(13)

其中，K代表測試樣本中樣本數(shù)量。s衡量了測試集中將樣本分類正確的平均票數(shù)和錯分為其他類的平均票數(shù)之最小差值，s越大分類器性能越好。

相關(guān)性定義為：

(14)

其中，

(15)

(16)

(17)

表4給出了本文模型的泛化誤差性能。可以看出本文模型各個決策樹之前關(guān)聯(lián)性較弱，且每個決策樹的分類性能較好，具有較好的泛化誤差性能。

表4 泛化誤差性能

4.3 特征分析

取Th為60，融合到港時刻前3個小時的天氣數(shù)據(jù)后，分別去除某個氣象特征的數(shù)據(jù)進行到港延誤預測，并和使用全部氣象特征進行預測的結(jié)果進行比對，則查全率會有不同程度的下降變化。用下降百分比表征此特征對于延誤預測的影響程度，如圖6所示。

圖6 氣象特征分析Fig.6 Analysis of meteorological features

從實驗結(jié)果可以看出，風向、風速和能見度對延誤預測影響較大，濕度和氣壓其次。從實際情況分析，風速和風向的變化會引起風切變等氣象情況，使飛機無法起降。同時，降雨、降雪和風暴等極端惡劣天氣也都伴隨著風向、風速和能見度的改變。

4.4 加速比

為驗證模型可擴展性和并行化優(yōu)勢，實驗采用加速比作為指標，用以衡量同一數(shù)據(jù)集下增加節(jié)點時算法的表現(xiàn)。加速比是指同一任務在單處理器系統(tǒng)和并行處理器系統(tǒng)中運行消耗的比率，其計算公式為：

Ssp=Ts/Tp

(18)

其中Ts表示單機環(huán)境下串行算法的運行時間，Tp表示在p個相同節(jié)點上計算所需時間。Ssp越大表明并行計算消耗時間越少，并行效率和性能提升越高。

航班延誤預測模型的加速比變化曲線如圖7所示。隨著云集群節(jié)點數(shù)的增加，實驗的運行時間減小，Ssp皆大于1且持續(xù)增加。理想情況下隨節(jié)點數(shù)的增加，加速比應呈成倍變化趨勢。但節(jié)點數(shù)越大實際運行情況和理想情況差距越大，這主要是由于集群間通信時IO開銷逐漸增大導致。

圖7 加速比Fig.7 Speedup

實際運行情況雖未達到理想化標準，但仍成線性變化，因此可以預期，對更大規(guī)模的數(shù)據(jù)進行并行化處理時，加速比性能會進一步提升。實驗結(jié)果表明本文模型具有良好的可擴展性。

5 結(jié)論

本文提出了基于Spark并融合氣象數(shù)據(jù)的航班延誤預測模型，通過考慮單個航班到達目的機場時刻的氣象數(shù)據(jù)，提高了航班延誤預測的正確率和查全率；并在Spark并行計算架構(gòu)上利用并行化隨機森林算法進行模型生成，克服了海量高維數(shù)據(jù)的計算難度。實驗表明該模型加入氣象數(shù)據(jù)后，預測效果明顯增強，且使用并行化算法后，提高了數(shù)據(jù)處理能力，滿足了航班延誤預測模型處理海量高維數(shù)據(jù)的需求，具有十分重要的應用價值。

[1] 李軍會, 朱金福, 陳欣. 基于航班延誤分布的機位魯棒指派模型[J]. 交通運輸工程學報, 2014, 14(6): 74- 82.

Li Junhui, Zhu Jinfu, Chen Xin. Robust assignment model of airport gate based on flight delay distribution[J]. Journal of Traffic and Transportation Engineering, 2014, 14(6): 74- 82.(in Chinese)

[2] 程華, 李艷梅, 羅謙, 等. 基于C4.5決策樹方法的到港航班延誤預測問題研究[J]. 系統(tǒng)工程理論與實踐, 2014, 34(s1): 239-247.

Cheng Hua, Li Yanmei, Luo Qian, et al. Study on flight delay with C4.5 decision tree based prediction method[J]. System Engineering-Theory & Practice, 2014, 34(s1): 239-247.(in Chinese)

[3] 羅赟騫, 陳志杰, 湯錦輝, 等. 采用支持向量機回歸的航班延誤預測研究[J]. 交通運輸系統(tǒng)工程與信息, 2014, 15(1): 143-149.

Luo Yunqian, Chen Zhijie, Tang Jinhui, et al. Flight delay prediction using support vector machine regression[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 15(1): 143-149.(in Chinese)

[4] 曹衛(wèi)東, 賀國光. 連續(xù)航班延誤與波及的貝葉斯網(wǎng)絡分析[J]. 計算機應用, 2009, 29(2): 606- 610.

Cao Weidong, He Guoguang. Bayesian networks analysis for sequence flight delay and propagation[J]. Journal of Computer Applications, 2009, 29(2): 606- 610.(in Chinese)

[5] 丁建立, 王曼, 曹衛(wèi)東, 等. 面向機場時段差異的航班延誤免疫預測算法[J]. 計算機工程與設計, 2015, 36(4): 1037-1041.

Ding Jianli, Wang Man, Cao Weidong, et al. Immune prediction algorithm of flight delay for hub airport in different periods[J]. Computer Engineering and Design, 2015, 36(4): 1037-1041.(in Chinese)

[6] Khanmohammadi S, Tutun S, Kucuk Y. A new multilevel input layer artificial neural network for predicting flight delays at JFK airport[J]. Procedia Computer Science, 2016,95:237-244.

[7] Rebollo J J, Balakrishnan H. Characterization and prediction of air traffic delays[J]. Transportation Research Part C: Emerging Technologies, 2014, 44:231-241.

[8] 羅謙, 張永輝, 程華, 等. 基于航空信息網(wǎng)絡的樞紐機場航班延誤預測模型[J].系統(tǒng)工程理論與實踐, 2014, 34(S1):143-150.

Luo Qian, Zhang Yonghui, Cheng Hua, et al. Study on flight delay prediction model based on flight networks[J]. Systems Engineering-Theory & Practice, 2014, 34(s1):143-150.(in Chinese)

[9] 劉宏波, 李玉, 林文杰,等. 并行MCMC算法的SAR影像分割[J]. 信號處理, 2016, 32(8): 998-1006.

Liu Hongbo, Li Yu, Lin Wenjie, et al. SAR image segmentation with parallel MCMC algorithm[J]. Journal of Signal Processing, 2016, 32(8): 998-1006.(in Chinese)

[10] Harnie D, Saey M, Vapirev A E, et al. Scaling machine learning for target prediction in drug discovery using apache spark[J]. Future Generation Computer Systems, 2017, 67:409- 417.

[11] 孟建良, 劉德超. 一種基于Spark 和聚類分析的辨識電力系統(tǒng)不良數(shù)據(jù)新方法[J]. 電力系統(tǒng)保護與控制, 2016, 44(3): 85-91.

Meng Jianliang, Liu Dechao. A new method for identifying bad data of power system based on Spark and clustering analysis[J]. Power System Protection and Control, 2016, 44(3): 85-91.(in Chinese)

[12] Kim Y J, Choi S, Briceno S, et al. A deep learning approach to flight delay prediction[C]∥IEEE. 2016 IEEE/AIAA 35th Digital Avionics Systems Conference. New York: IEEE, 2016: 1- 6.

[13] Breiman L. Random forests[J]. Machine Learning, 2001, 45(1): 5-32.

[14] Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[C]∥Usenix Conference on Networked Systems Design and Implementation. Lombard: Usenix Association, 2012:2-2.