加權K-prototype-粗糙集的航班延誤等級劃分研究

王興隆，紀君柔，石宗北

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

1 引言

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

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

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

2 加權K-prototypes-粗糙集航班延誤等級劃分模型

2.1 航班延誤等級劃分指標選擇

圖1為延誤航班等級劃分流程圖。

圖1 延誤航班等級劃分流程圖

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

1)延誤時間指標

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

2)飛行時間指標

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

3)延誤人數(shù)指標

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

4)飛行距離指標

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

5)經(jīng)停指標

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

6)機型指標

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

6個航班延誤評價指標具體表示如表1所示：

表1 航班延誤等級評價指標

2.2 基于加權K-prototype的航班延誤等級劃分

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

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

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

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

(1)

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

(2)

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

(3)

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

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

2) k-prototypes算法的加權改進

在實際航班運行中，不同評價指標在對延誤航班的等級劃分中所占比重也不相同，因此本文對k-prototypes算法進行了加權改進。

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

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

(4)

式中：ai1，ai2，…aip為不同數(shù)值評價指標的權重值。

類別屬性指標之間的采用海明威距離計算，計算公式為

(5)

相異度距離為

d=d2+γd2

(6)

式中，γ為分類屬性權重值。

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

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

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

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

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

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

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

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

2.4 模型計算步驟

模型計算步驟如下：

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

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

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

Step 4：重復Step 3，直到?jīng)]有樣本對應的類再改變，聚類結束，得到每個航班對應的延誤等級。

Step 5：選取航班延誤特征和對應的延誤等級，基于粗糙集理論構建航班延誤等級識別知識表達體系。

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

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

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

3 實例驗證

3.1 數(shù)據(jù)準備

選取某大型樞紐機場一月份的航班延誤數(shù)據(jù)，共選取了4557條延誤航班數(shù)據(jù)作為樣本，因為數(shù)據(jù)值差異性過大，為了增加結果的準確性，將數(shù)值指標根據(jù)式(7)進行歸一化處理，將各數(shù)值指標取值控制在[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實現(xiàn)結果如圖3所示。

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

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

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

圖2 “手肘法”折線圖

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

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

4 實驗結果分析

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

當K=4時采用改進的加權K-Prototypes聚類算法得到聚類結果，第一類航班有35架次占比1%，第二類延誤航班有323架次占比7%，第三類延誤航班有1415架次占比31%，第四類延誤航班有2784架次占比61%。

整理每個類別里延誤航班的每個評價指標分布，并進行對比分析，確定每種類別對應的航班延誤級別。延誤等級共有4級，各類延誤指標分布圖如圖4和圖5所示。

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

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

圖5 類別屬性指標分布圖

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

(8)

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

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

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

5 結論

1)本文同時考慮數(shù)值屬性和類別屬性評估指標，采用了加權k-prototypes 算法對大量延誤航班聚類分析，為延誤航班劃分了四個延誤等級。

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

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