王興隆，紀(jì)君柔，石宗北

(中國民航大學(xué)空中交通管理學(xué)院，天津 300300)

1 引言

隨著航班流的增多，空域資源的緊缺，航班延誤也日益增多，而對(duì)航班延誤程度進(jìn)行有效評(píng)估，制定切實(shí)可行的航班延誤等級(jí)劃分規(guī)則是減少延誤成本，進(jìn)行協(xié)同流量管理并且建立相應(yīng)的應(yīng)急預(yù)案的關(guān)鍵依據(jù)，具有很大的實(shí)際應(yīng)用價(jià)值。

2012年，Raj Bandyopadhyay[1]等使用線性回歸來確定影響航班延誤的因素，并采用分類器(SVM)來分析航班延誤，2017年，Suvojit Manna[2]等采用航班延誤的六個(gè)延誤屬性，建立梯度增強(qiáng)決策樹模型用來分析航班延誤。2014年，顧紹康[3]根據(jù)時(shí)空和空間兩個(gè)角度的評(píng)估指標(biāo)建立了航班延誤程度實(shí)時(shí)評(píng)估指標(biāo)體系，2015年，孟會(huì)芳[4]以國內(nèi)某大型樞紐機(jī)場為應(yīng)用背景，構(gòu)建了基于投票聚類的一段時(shí)間內(nèi)的航班延誤等級(jí)劃分策略，2018年，吳仁彪[5]等人提出了基于雙通道卷積神經(jīng)網(wǎng)絡(luò)(DCNN)的航班延誤預(yù)測(cè)模型，將延誤時(shí)間進(jìn)行等級(jí)劃分，將預(yù)測(cè)問題轉(zhuǎn)化為分類問題。

以上研究只是提出數(shù)值屬性指標(biāo)對(duì)航班延誤程度進(jìn)行了評(píng)估，同時(shí)并未確定具體的判斷準(zhǔn)則，本文同時(shí)提出數(shù)值屬性指標(biāo)和類別屬性指標(biāo)，利用加權(quán)k-prototypes聚類算法對(duì)航班延誤程度進(jìn)行了等級(jí)評(píng)估，并進(jìn)一步結(jié)合粗糙集理論知識(shí)，利用Rosetta軟件建立了科學(xué)有效的延誤航班等級(jí)劃分規(guī)則，確定了直觀并具有高準(zhǔn)確率的延誤等級(jí)判斷準(zhǔn)則。

2 加權(quán)K-prototypes-粗糙集航班延誤等級(jí)劃分模型

2.1 航班延誤等級(jí)劃分指標(biāo)選擇

圖1為延誤航班等級(jí)劃分流程圖。

圖1 延誤航班等級(jí)劃分流程圖

由圖1可知對(duì)航班延誤程度的等級(jí)進(jìn)行劃分，需考慮多個(gè)能反映航班延誤程度的指標(biāo)，每個(gè)指標(biāo)均能從某一方面反映延誤狀況，結(jié)合我國航空運(yùn)輸?shù)奶攸c(diǎn)和實(shí)際情況，本文提出了6個(gè)衡量延誤程度的指標(biāo)：

1)延誤時(shí)間指標(biāo)

當(dāng)延誤時(shí)間越長，航班延誤成本越高，并對(duì)后續(xù)航班造成的影響更大，波及延誤更廣，對(duì)機(jī)場，航空公司以及旅客產(chǎn)生直接的延誤經(jīng)濟(jì)損失，為此選取延誤時(shí)間為衡量延誤程度的權(quán)重最大的指標(biāo)。

2)飛行時(shí)間指標(biāo)

飛行時(shí)間越長，油耗成本越高，若延誤航班的飛行時(shí)間越長，那么在飛行中產(chǎn)生影響航班安全飛行和實(shí)際飛行時(shí)長的因素幾率就越大，且可能會(huì)導(dǎo)致航班需要過夜，增加了航空公司的延誤成本。飛行時(shí)間從航空公司角度反映了延誤程度。

3)延誤人數(shù)指標(biāo)

延誤人數(shù)越多，產(chǎn)生的旅客經(jīng)濟(jì)損失就越大，這種經(jīng)濟(jì)損失可描述為延誤時(shí)間占用了旅客正常的工作時(shí)間，延誤人數(shù)是從旅客角度評(píng)價(jià)延誤程度。

4)飛行距離指標(biāo)

延誤航班飛行距離越長，那么航班經(jīng)過的管制扇區(qū)就相對(duì)越多，需要進(jìn)行管制移交的次數(shù)就越多，受影響的管制員就越多，飛行距離是從管制員角度考慮延誤程度。

5)經(jīng)停指標(biāo)

延誤航班是否需要經(jīng)停反映了受影響的機(jī)場個(gè)數(shù)，經(jīng)停延誤航班不僅對(duì)目的地機(jī)場產(chǎn)生影響同時(shí)也會(huì)影響經(jīng)停機(jī)場，航班是否經(jīng)停是從機(jī)場角度確定延誤程度。

6)機(jī)型指標(biāo)

延誤航班機(jī)型越大，所需尾流間隔也越大，恢復(fù)航班運(yùn)行難度也相對(duì)較大，地面等待以及空中等待經(jīng)濟(jì)損失也越大，機(jī)型指標(biāo)是從等待經(jīng)濟(jì)損失角度確定延誤程度。

6個(gè)航班延誤評(píng)價(jià)指標(biāo)具體表示如表1所示：

表1 航班延誤等級(jí)評(píng)價(jià)指標(biāo)

2.2 基于加權(quán)K-prototype的航班延誤等級(jí)劃分

聚類分析是一種無監(jiān)督的學(xué)習(xí)，對(duì)應(yīng)用于大規(guī)模數(shù)據(jù)集的劃分具有很大的優(yōu)勢(shì)，一般的聚類方法如：K-means算法[6]，K-modes算法[7]，RW-CLOPE算法[8]等只能對(duì)單一屬性指標(biāo)數(shù)據(jù)進(jìn)行處理，而本文在對(duì)延誤航班進(jìn)行等級(jí)劃分時(shí)采用的六個(gè)評(píng)價(jià)指標(biāo)包含了數(shù)值屬性指標(biāo)和類別屬性指標(biāo)，k-prototype算法[9]是能夠?qū)旌蠈傩詳?shù)據(jù)進(jìn)行聚類的一種有效算法。

1)最佳聚類數(shù)K的確定

在聚類分析時(shí)，最佳聚類數(shù)的選擇具有隨機(jī)性導(dǎo)致聚類結(jié)果穩(wěn)定性較差，因此本文通過手肘法和輪廓系數(shù)法相結(jié)合對(duì)評(píng)價(jià)指標(biāo)進(jìn)行計(jì)算分析確定最佳聚類數(shù)，從而保證聚類結(jié)果穩(wěn)定可靠。

手肘法是一種基于誤差平方和(SSE)的K值選擇算法，隨著聚類數(shù)K的增大，每個(gè)類的聚合程度會(huì)逐漸提高，誤差平方和SSE自然會(huì)逐漸變小。當(dāng)K小于真實(shí)聚類數(shù)時(shí)，由于K的增大會(huì)大幅增加每個(gè)類的聚合程度，故SSE的下降幅度會(huì)很大，而當(dāng)K到達(dá)真實(shí)聚類數(shù)時(shí)，SSE的下降幅度會(huì)驟減，然后隨著K值的繼續(xù)增大而趨于平緩， SSE的計(jì)算公式如下

(1)

輪廓系數(shù)法的核心指標(biāo)是輪廓系數(shù)(Silhouette Coefficient)，某個(gè)延誤航班Xi輪廓系數(shù)定義如下

(2)

式中：a是Xi與同類中其它延誤航班的平均距離，b是Xi與最近類中所有延誤航班的平均距離。最近簇的定義為

(3)

式中：qk是某個(gè)類Ck中的一個(gè)延誤航班。

求出所有延誤航班的輪廓系數(shù)后再求平均值就得到了平均輪廓系數(shù)，平均輪廓系數(shù)越大，聚類效果越好。

2) k-prototypes算法的加權(quán)改進(jìn)

在實(shí)際航班運(yùn)行中，不同評(píng)價(jià)指標(biāo)在對(duì)延誤航班的等級(jí)劃分中所占比重也不相同，因此本文對(duì)k-prototypes算法進(jìn)行了加權(quán)改進(jìn)。

設(shè)X=[X1，X2，X3，…Xn]為n個(gè)延誤航班集合，其中Xi=[xi1，xi2，…xip，…xim]表示具有m個(gè)延誤評(píng)價(jià)指標(biāo)的第i個(gè)延誤航班，1至p下標(biāo)為數(shù)值屬性指標(biāo)，p+1至m下標(biāo)為類別屬性指標(biāo)，Y=[Y1，Y2，Y3，…Yk]為K個(gè)類的中心原型延誤航班的集合，其中Yj=[yk1，yk2，…ykp，…ykm]表示第j個(gè)類中具有m個(gè)評(píng)價(jià)指標(biāo)值的中心原型航班。

數(shù)值屬性指標(biāo)之間采用歐幾里得距離計(jì)算，計(jì)算公式為

(4)

式中：ai1，ai2，…aip為不同數(shù)值評(píng)價(jià)指標(biāo)的權(quán)重值。

類別屬性指標(biāo)之間的采用海明威距離計(jì)算，計(jì)算公式為

(5)

相異度距離為

d=d2+γd2

(6)

式中，γ為分類屬性權(quán)重值。

采用加權(quán)K-prototype聚類算法僅能對(duì)每個(gè)延誤航班的延誤等級(jí)進(jìn)行劃分，而不能建立有效航班延誤等級(jí)劃分規(guī)則。

2.3 基于粗糙集的航班延誤等級(jí)規(guī)則建立方法

本文采取粗糙集理論[10-11]對(duì)航班延誤等級(jí)進(jìn)行規(guī)則建立，粗糙集理論可以在信息不完整和信息不一致下，用來規(guī)約數(shù)據(jù)集合，發(fā)掘隱藏?cái)?shù)據(jù)相關(guān)性，以產(chǎn)生有用的分類規(guī)則。

航班延誤等級(jí)判別的知識(shí)表達(dá)系統(tǒng)為S=(U，A，V，f)，其中U為航班延誤特征論域；A為航班延誤屬性集合，由條件屬性C和決策屬性D組成，C={延誤時(shí)間，延誤人數(shù)，延誤航班機(jī)型，飛行距離，是否經(jīng)停，飛行時(shí)間}，D={延誤等級(jí)}；V為屬性對(duì)應(yīng)的值域，f：U×A→V是一個(gè)航班延誤等級(jí)信息函數(shù)，為每個(gè)航班延誤等級(jí)對(duì)象屬性賦予一個(gè)信息值。航班延誤等級(jí)規(guī)則生成步驟如下：

1)航班延誤屬性數(shù)值進(jìn)行離散化處理

2)利用Johnson算法進(jìn)行屬性約簡，屬性約簡的目的是將多余的屬性值刪除

3)等價(jià)類和上下近似集的獲取

4)生成航班延誤等級(jí)的劃分規(guī)則

2.4 模型計(jì)算步驟

模型計(jì)算步驟如下：

Step 1：輸入樣本數(shù)據(jù)，結(jié)合“手肘法”和輪廓系數(shù)法確定樣本數(shù)據(jù)最佳聚類數(shù)K，每個(gè)類選取一個(gè)中心原型。

Step 2：根據(jù)式(6)將樣本分配到距離中心原型最近的那個(gè)類，每次分配后，更新類的中心原型。

Step 3：在所有的樣本都分到各自的類中后，重新計(jì)算樣本到中心原型的距離。如果一個(gè)樣本距離新的中心原型比距原來的中心原型要近，那就重新分配到新的中心原型的類中。

Step 4：重復(fù)Step 3，直到?jīng)]有樣本對(duì)應(yīng)的類再改變，聚類結(jié)束，得到每個(gè)航班對(duì)應(yīng)的延誤等級(jí)。

Step 5：選取航班延誤特征和對(duì)應(yīng)的延誤等級(jí)，基于粗糙集理論構(gòu)建航班延誤等級(jí)識(shí)別知識(shí)表達(dá)體系。

Step 6：采用基于布爾邏輯離散化算法對(duì)延誤屬性數(shù)據(jù)的離散化。

Step 7：采用Johnson貪婪算法，對(duì)離散化的航班延誤屬性進(jìn)行約簡，刪除冗余屬性，提取航班延誤等級(jí)劃分規(guī)則。

Step 8：計(jì)算航班延誤等級(jí)規(guī)則劃分精度。

3 實(shí)例驗(yàn)證

3.1 數(shù)據(jù)準(zhǔn)備

選取某大型樞紐機(jī)場一月份的航班延誤數(shù)據(jù)，共選取了4557條延誤航班數(shù)據(jù)作為樣本，因?yàn)閿?shù)據(jù)值差異性過大，為了增加結(jié)果的準(zhǔn)確性，將數(shù)值指標(biāo)根據(jù)式(7)進(jìn)行歸一化處理，將各數(shù)值指標(biāo)取值控制在[0，1]之間。

(7)

其中x為樣本數(shù)據(jù)，xmin為所有樣本數(shù)據(jù)的最小值，xmax為所有樣本數(shù)據(jù)的最大值。經(jīng)過歸一化后部分樣本數(shù)據(jù)如表2所示。

表2 歸一化后的航班延誤數(shù)據(jù)

3.2 最佳聚類數(shù)K的確定

由圖2可以看出該類方法得到的最佳聚類的K的取值可能為3，4，5。

“手肘法”Python實(shí)現(xiàn)結(jié)果如圖3所示。

由圖3可以看出該類方法K=2時(shí)平均輪廓系數(shù)最大。

輪廓系數(shù)法Python實(shí)現(xiàn)結(jié)果如圖4所示。

手肘法具體應(yīng)用于具體的數(shù)據(jù)集時(shí)，會(huì)出現(xiàn)如圖2一樣不明顯的“肘點(diǎn)”，導(dǎo)致K值取值具有較大誤差，因此本文同時(shí)結(jié)合輪廓系數(shù)法從而準(zhǔn)確的確定最佳聚類數(shù)，由圖3可得，在K=2的時(shí)候平均輪廓系數(shù)最大，因?yàn)樵贙=2時(shí)由圖2可看出SSE過大，所以該聚類數(shù)不太理想，在K=4的時(shí)候，平均輪廓系數(shù)也較大，且也符合手肘法得到的K值范圍，綜上所述，本文的最佳聚類數(shù)選取為4類。

圖2 “手肘法”折線圖

圖3 輪廓系數(shù)法折線圖

圖4 數(shù)值屬性指標(biāo)分布圖

4 實(shí)驗(yàn)結(jié)果分析

本文結(jié)合實(shí)際航班運(yùn)行成本將平均延誤時(shí)間的權(quán)重設(shè)置為0.8，飛行距離和飛行時(shí)間的權(quán)重設(shè)置為0.1，載客人數(shù)的權(quán)重設(shè)置為0.4，γ設(shè)置為0.2。

當(dāng)K=4時(shí)采用改進(jìn)的加權(quán)K-Prototypes聚類算法得到聚類結(jié)果，第一類航班有35架次占比1%，第二類延誤航班有323架次占比7%，第三類延誤航班有1415架次占比31%，第四類延誤航班有2784架次占比61%。

整理每個(gè)類別里延誤航班的每個(gè)評(píng)價(jià)指標(biāo)分布，并進(jìn)行對(duì)比分析，確定每種類別對(duì)應(yīng)的航班延誤級(jí)別。延誤等級(jí)共有4級(jí)，各類延誤指標(biāo)分布圖如圖4和圖5所示。

由圖4圖5可知，第一類延誤航班的延誤時(shí)間遠(yuǎn)遠(yuǎn)高于其它三類，定義為重度延誤；第三類延誤航班載客人數(shù)以及大機(jī)型以及超大機(jī)型的占比也顯著多于其它兩類，但延誤時(shí)間相差不大，定義為中度延誤；第二類延誤航班的六個(gè)評(píng)價(jià)指標(biāo)均高于第四類延誤航班，定義為一般延誤，則第四類延誤航班定義為輕度延誤。

采用Rosetta 粗糙集軟件利用K-prototype聚類分析的結(jié)果作為分析樣本進(jìn)行計(jì)算分析。航班延誤屬性為延誤時(shí)間、飛行距離、飛行時(shí)間、載客人數(shù)、是否經(jīng)停以及機(jī)型，設(shè)定決策屬性為輕度延誤、一般延誤、中度延誤、重度延誤。采用Rosetta粗糙集軟件中自帶的 Boolean reasoning(布爾邏輯)算法和 Jonson 貪婪算法進(jìn)行屬性的離散化和約簡，發(fā)現(xiàn)是否經(jīng)停為冗余屬性，并設(shè)置精確度和覆蓋度，得到48條劃分規(guī)則，對(duì)這些劃分規(guī)則結(jié)合實(shí)際進(jìn)行整理分析對(duì)比得到表3航班延誤等級(jí)劃分。

圖5 類別屬性指標(biāo)分布圖

采用等級(jí)判別率GD來衡量該等級(jí)劃分規(guī)則的精度。指標(biāo)的計(jì)算公式為

(8)

其中，GID為利用等級(jí)規(guī)則對(duì)樣本延誤航班劃分的等級(jí)與原先延誤航班樣本等級(jí)的差異航班數(shù)，N為判斷延誤等級(jí)的總樣本航班數(shù)。

對(duì)樣本延誤航班進(jìn)行抽樣驗(yàn)證，得到該等級(jí)劃分規(guī)則的等級(jí)判別率為81.9%，可見該劃分規(guī)則精度較高，總體判別結(jié)果穩(wěn)定，能較為準(zhǔn)確的劃分航班延誤等級(jí)。

表3 航班延誤等級(jí)劃分規(guī)則表

5 結(jié)論

1)本文同時(shí)考慮數(shù)值屬性和類別屬性評(píng)估指標(biāo)，采用了加權(quán)k-prototypes 算法對(duì)大量延誤航班聚類分析，為延誤航班劃分了四個(gè)延誤等級(jí)。

2)利用粗糙集理論結(jié)合實(shí)際情況，制定了航班延誤等級(jí)劃分規(guī)則，該規(guī)則的等級(jí)判別率達(dá)到81.9%，提供了直觀有效的航班延誤等級(jí)判斷手段。

3)下一步的研究重點(diǎn)就是獲取更多的航班延誤數(shù)據(jù)，構(gòu)建更多的反映航班延誤程度的評(píng)價(jià)指標(biāo)，建立更為準(zhǔn)確的航班延誤等級(jí)劃分規(guī)則，提高等級(jí)判別率，并在對(duì)復(fù)雜終端區(qū)協(xié)同調(diào)度策略進(jìn)行研究時(shí)考慮航班延誤等級(jí)，提高等級(jí)劃分模型的實(shí)際應(yīng)用價(jià)值。