基于集成學(xué)習(xí)算法的航路網(wǎng)絡(luò)航段交通擁擠識(shí)別方法研究

李桂毅，郭銘宇，羅一帆

(南京航空航天大學(xué)a.民航/飛行學(xué)院；b.航空學(xué)院，南京211106)

0 引言

航路網(wǎng)絡(luò)交通擁擠帶來的航班延誤直接影響空中交通運(yùn)行安全與效率.傳統(tǒng)解決空中交通擁擠的方法主要是控制起飛時(shí)間或飛行間隔，其決策缺乏精確的交通態(tài)勢(shì)信息支持，效果欠佳.如何快速、精準(zhǔn)地識(shí)別航路網(wǎng)絡(luò)交通擁擠狀態(tài)與節(jié)點(diǎn)，進(jìn)而制定交通擁擠的管控策略已成為重要研究課題.

在空中交通領(lǐng)域，徐肖豪[1]提出了基于FCM(Fuzzy C-means Clustering)算法的終端區(qū)交通擁擠狀態(tài)評(píng)價(jià)方法，Jiang[2]基于復(fù)雜網(wǎng)絡(luò)構(gòu)建了空中交通擁擠識(shí)別模型，李善梅[3]提出了基于灰色聚類算法的交叉航路擁擠識(shí)別模型，張兆寧[4]提出了交通擁擠判定方法及不同交通狀態(tài)下交通流參數(shù)閾值區(qū)間，李桂毅[5]等提出了基于FCM與粗糙集理論的多扇區(qū)交通擁擠識(shí)別模型；在地面交通領(lǐng)域，Eleonora[6]提出了基于車輛或駕駛員手機(jī)GPS數(shù)據(jù)的道路交通擁擠探測(cè)方法，F(xiàn)elix[7]提出了基于浮動(dòng)車數(shù)據(jù)和時(shí)空聚類算法的地面路網(wǎng)交通擁擠識(shí)別方法，Wang[8]建立了基于神經(jīng)網(wǎng)絡(luò)的道路通行時(shí)間預(yù)測(cè)模型，預(yù)測(cè)路網(wǎng)交通擁擠狀態(tài)，董春嬌[9]基于交通流率、速度和占有率等參數(shù)和SVM算法建立了城市快速路網(wǎng)交通狀態(tài)的判別模型，Kumar[10]基于人工神經(jīng)網(wǎng)絡(luò)模型實(shí)現(xiàn)城市高速公路交通流參數(shù)的短時(shí)預(yù)測(cè).以上成果為航路網(wǎng)絡(luò)交通擁擠識(shí)別研究奠定了較好基礎(chǔ).

航路網(wǎng)絡(luò)交通易受惡劣天氣、軍航活動(dòng)等諸多因素影響，具有非線性、多變性、復(fù)雜性等特征.機(jī)器學(xué)習(xí)處理大樣本數(shù)據(jù)能力強(qiáng)，較適用于擬合非線性復(fù)雜函數(shù)，具有良好的泛化能力.集成學(xué)習(xí)算法通過構(gòu)建多個(gè)基學(xué)習(xí)器可提升機(jī)器學(xué)習(xí)效果,提高識(shí)別精度,在城市道路交通擁擠預(yù)測(cè)、城市人流行為分析方面得到成功應(yīng)用[11-12].本文基于集成學(xué)習(xí)算法構(gòu)建航路網(wǎng)絡(luò)交通擁擠識(shí)別模型，識(shí)別路網(wǎng)航段交通擁擠狀態(tài).

1 航路網(wǎng)絡(luò)交通擁擠識(shí)別思路和框架

航路網(wǎng)絡(luò)交通擁擠識(shí)別的總體思路為基于路網(wǎng)航跡數(shù)據(jù)，構(gòu)建航段交通擁擠評(píng)價(jià)指標(biāo)，結(jié)合FCM和集成學(xué)習(xí)算法構(gòu)建路網(wǎng)航段交通擁擠等級(jí)劃分與識(shí)別模型，實(shí)現(xiàn)航段交通擁擠識(shí)別.具體流程如下：

(1)選定航路網(wǎng)絡(luò)區(qū)域范圍，采集ADS-B航跡數(shù)據(jù)，統(tǒng)計(jì)航路網(wǎng)絡(luò)交通流參數(shù)；

(2)建立路網(wǎng)航段交通擁擠評(píng)價(jià)指標(biāo)，涵蓋交通流量、交通密度、交通接近率、交通飽和度，結(jié)合航跡數(shù)據(jù)計(jì)算評(píng)價(jià)指標(biāo)值；

(3)構(gòu)建基于路網(wǎng)航段FCM交通擁擠劃分模型，聚類劃分路網(wǎng)航段交通擁擠等級(jí)；

(4)構(gòu)建路網(wǎng)航段集成學(xué)習(xí)交通擁擠識(shí)別模型，基于路網(wǎng)交通擁擠評(píng)價(jià)指標(biāo)和擁擠等級(jí)數(shù)據(jù)完成模型訓(xùn)練，識(shí)別航段交通擁擠狀態(tài).

圖1為航路網(wǎng)絡(luò)航段交通擁擠識(shí)別總體框架.

圖1 航路網(wǎng)絡(luò)航段交通擁擠狀態(tài)識(shí)別總體框架Fig.1 Overall framework of air traffic congestion identification in air route network segment

2 航路網(wǎng)絡(luò)交通擁擠狀態(tài)劃分方法

2.1 航路網(wǎng)絡(luò)航段交通擁擠評(píng)價(jià)指標(biāo)

分別從路網(wǎng)航段交通流量、交通密度、交通飽和度、交通接近率4個(gè)指標(biāo)維度評(píng)價(jià)路網(wǎng)航段交通擁擠等級(jí).指標(biāo)定義如下.

(1)航段交通流量.路網(wǎng)航段斷面單位時(shí)間內(nèi)通過的航空器的架次數(shù)，反映路網(wǎng)內(nèi)部交通的流動(dòng)負(fù)荷.

(2)航段交通密度.路網(wǎng)中航段單位長(zhǎng)度內(nèi)單位時(shí)間內(nèi)航空器的架次數(shù)，反映路網(wǎng)內(nèi)部航段飛行密集程度.

(3)航段交通飽和度.路網(wǎng)某航段單位時(shí)間內(nèi)交通量同容量限制閾值的比值，用于度量航段交通負(fù)荷強(qiáng)度.

(4)航段交通接近率.路網(wǎng)中某航段單位時(shí)間內(nèi)航空器之間的接近程度，反映航段交通分布的密集特性.依據(jù)我國空管法規(guī)，雷達(dá)管制條件下航空器之間最小安全間隔距離為水平方向10 km或垂直方向300 m，至少滿足其一，否則構(gòu)成不安全事件.基于橢球面計(jì)算航空器間的相對(duì)間距，負(fù)指數(shù)函數(shù)計(jì)算航段交通接近率.當(dāng)航段內(nèi)航空器相對(duì)距離接近1時(shí)，航空器相對(duì)間隔接近最低安全間隔，航段交通接近率就越大，管制員需要較多精力監(jiān)視和調(diào)配飛行沖突，航段交通狀態(tài)表現(xiàn)越擁擠；當(dāng)航段內(nèi)航空器相對(duì)距離越大，航段交通接近率也就越小，交通擁擠程度也就越低.

式中：dij為航空器i與j之間的空間相對(duì)距離；,為航空器i與j的位置向量；SH,SV分別為航段最小水平間隔距離和最小垂直間隔距離，分別取10 km和300 m；(xi,xj),(yi,yj)分別為航空器i與j的坐標(biāo)值；(zi,zj)為航空器i與j的飛行高度；Pd為航段交通接近度；Pseg為航段交通接近率；n為航段內(nèi)航空器數(shù)量.

圖2為我國某航段交通接近率和交通流量變化趨勢(shì)，可知航段交通接近率同其交通流量的總體變化趨勢(shì)基本一致，能夠從交通分布均勻性維度反映交通擁擠程度.

圖2 我國某航段交通接近率和交通流量的變化趨勢(shì)Fig.2 Trend of traffic approaching rate and traffic flow in an air route of China

2.2 航路網(wǎng)絡(luò)航段交通擁擠劃分模型

FCM算法屬于無監(jiān)督學(xué)習(xí)算法，適用于模糊、無清晰界限的交通擁擠狀態(tài)的劃分.假定航段交通擁擠評(píng)價(jià)指標(biāo)矩陣為X，即

式中：qseg為航段交通流量；kseg為航段交通密度；sseg為航段交通飽和度；Pseg為航段交通接近率.

基于FCM算法對(duì)矩陣X在一定時(shí)間內(nèi)的歷史數(shù)據(jù)進(jìn)行聚類分析，確定最佳的聚類劃分類別數(shù)，明確航段交通擁擠等級(jí)劃分.將X聚類劃分為β個(gè)簇，交通擁擠狀態(tài)劃分算法為

式中：Jα(?)為FCM算法的目標(biāo)函數(shù)；U是每個(gè)聚類樣本數(shù)據(jù)與相應(yīng)聚類簇的隸屬度；l為聚類數(shù)據(jù)樣本序號(hào)；c為聚類數(shù)據(jù)樣本數(shù)量；x為聚類劃分簇的序號(hào)；μxl為第l個(gè)聚類數(shù)據(jù)樣本屬于第x個(gè)聚類簇的隸屬度，μxl∈[0,1]；dxl為第l個(gè)聚類數(shù)據(jù)樣本到第x個(gè)聚類簇的歐式距離；α為加權(quán)指數(shù)，其值越大，聚類模糊性越強(qiáng).

基于肘部法則確定最佳聚類簇?cái)?shù)，即擁擠等級(jí)數(shù).肘部法則通過計(jì)算聚類簇內(nèi)誤差平方和(ESSE)確定最佳劃分簇?cái)?shù)，即

式中：Cx為聚類劃分的第x個(gè)簇；p為Cx中的樣本點(diǎn)；mx為Cx中的所有樣本點(diǎn)的質(zhì)心；k為聚類劃分的簇?cái)?shù).

從小到大設(shè)定不同的簇?cái)?shù)進(jìn)行聚類分析，計(jì)算ESSE值.隨著聚類簇?cái)?shù)的增多，各簇內(nèi)樣本數(shù)量會(huì)越來越少，樣本點(diǎn)距離聚類中心的距離也越來越近，ESSE值隨劃分簇?cái)?shù)增多而減少.當(dāng)劃分類別數(shù)小于最佳簇?cái)?shù)時(shí)，類別數(shù)增加會(huì)大幅增加每個(gè)簇的聚合程度，ESSE值下降幅度會(huì)很大.當(dāng)劃分簇?cái)?shù)到達(dá)最佳簇?cái)?shù)時(shí)，再增加簇?cái)?shù)，每個(gè)簇的聚合程度增幅會(huì)迅速變小，ESSE值下降幅度會(huì)趨于平緩，進(jìn)而形成一個(gè)拐點(diǎn)，拐點(diǎn)對(duì)應(yīng)的劃分簇?cái)?shù)，即為最佳劃分簇?cái)?shù).

3 航路網(wǎng)絡(luò)交通擁擠狀態(tài)識(shí)別方法

3.1 航段交通擁擠狀態(tài)識(shí)別模型

集成學(xué)習(xí)算法原理是構(gòu)建一系列基學(xué)習(xí)器對(duì)訓(xùn)練樣本學(xué)習(xí)，挖掘訓(xùn)練樣本的內(nèi)部規(guī)律，并使用集成算法把各基學(xué)習(xí)器學(xué)習(xí)結(jié)果整合起來，從而獲得比單學(xué)習(xí)器模型更好的學(xué)習(xí)效果，算法原理如圖3所示.

圖3 路網(wǎng)航段交通擁擠狀態(tài)集成學(xué)習(xí)識(shí)別原理Fig.3 Principle of ensemble learning identification for traffic congestion in air route network segment

集成學(xué)習(xí)識(shí)別模型可采用決策樹或k近鄰算法構(gòu)建基學(xué)習(xí)器，集成學(xué)習(xí)算法采用Bagging算法，結(jié)合算法采用Stacking學(xué)習(xí)法，如圖4所示.基于交通擁擠評(píng)價(jià)指標(biāo)和擁擠等級(jí)數(shù)據(jù)訓(xùn)練模型，結(jié)合指標(biāo)數(shù)據(jù)進(jìn)行交通擁擠等級(jí)識(shí)別.

圖4 路網(wǎng)航段交通擁擠集成學(xué)習(xí)識(shí)別模型結(jié)構(gòu)Fig.4 Structure of ensemble learning identification model for traffic congestion in air route network segment

3.2 Bagging學(xué)習(xí)策略和Stacking結(jié)合策略

Bagging學(xué)習(xí)策略重復(fù)產(chǎn)生樣本作為訓(xùn)練樣本集，從大小為n的原始訓(xùn)練樣本集中隨機(jī)地抽取m個(gè)樣本作為每次訓(xùn)練的樣本集，訓(xùn)練相互獨(dú)立的基學(xué)習(xí)器，完成基學(xué)習(xí)器的集成.首先，對(duì)原始訓(xùn)練樣本集進(jìn)行有放回的抽樣；然后，針對(duì)同一原始訓(xùn)練樣本集，每次從中隨機(jī)抽取相同數(shù)量的訓(xùn)練樣本子集訓(xùn)練一個(gè)基學(xué)習(xí)器；最后，集成訓(xùn)練好的基學(xué)習(xí)器，如表1所示.

基學(xué)習(xí)器結(jié)合策略是指將訓(xùn)練好的基學(xué)習(xí)器輸出結(jié)合起來的方法，如Stacking結(jié)合算法，其原理為使用另外一個(gè)學(xué)習(xí)算法將基學(xué)習(xí)器的結(jié)果結(jié)合在一起.首先，基于初始訓(xùn)練樣本集訓(xùn)練生成各基學(xué)習(xí)器；然后，將各基學(xué)習(xí)器的輸出作為新的訓(xùn)練樣本集，初始訓(xùn)練樣本集訓(xùn)練樣本標(biāo)記仍作為樣本標(biāo)記，生成Stacking學(xué)習(xí)器；最后，將訓(xùn)練好的Stacking學(xué)習(xí)器結(jié)合各基學(xué)習(xí)器輸出，結(jié)合成集成學(xué)習(xí)模型.

表1 Bagging集成算法Table 1 Bagging ensemble algorithms

4 實(shí)證分析

如圖 5所示，選取我國 A599、R343、R474、R399、B330航路共9條航段組成的航路網(wǎng)絡(luò)進(jìn)行航段交通擁擠識(shí)別驗(yàn)證分析.實(shí)驗(yàn)數(shù)據(jù)為2018年3月1～14日路網(wǎng)ADS-B數(shù)據(jù).擁擠指標(biāo)為14 d，共10 296組，時(shí)間間隔為15 min.

圖5 實(shí)驗(yàn)航路網(wǎng)絡(luò)結(jié)構(gòu)Fig.5 Experimental air route network architecture

(1)確定航段交通擁擠最佳劃分等級(jí)數(shù).

對(duì)14 d擁擠指標(biāo)數(shù)據(jù)進(jìn)行聚類分析，劃分類別數(shù)k分別取1～9.圖6給出了k值與ESSE值的關(guān)系：k=1～4，ESSE值下降很快；當(dāng)k=4之后，ESSE值下降趨于平緩.可知最佳劃分擁擠等級(jí)數(shù)為4，對(duì)應(yīng)為嚴(yán)重?fù)頂D、輕度擁擠、暢通、非常暢通.

圖6 航段交通擁擠指標(biāo)聚類手肘分析拐點(diǎn)圖Fig.6 Air route traffic congestion index cluster elbow analysis inflection point diagram

(2)進(jìn)行航段交通擁擠等級(jí)聚類劃分.

對(duì)14 d擁擠指標(biāo)數(shù)據(jù)進(jìn)行聚類分析，擁擠等級(jí)數(shù)為4，指標(biāo)數(shù)據(jù)標(biāo)準(zhǔn)化后的聚類結(jié)果如圖7所示，分別從流量—密度、流量—接近度、流量—飽和度、密度—接近度、密度—飽和度、接近度—飽和度6個(gè)維度展現(xiàn)聚類結(jié)果，進(jìn)而完成航段交通擁擠等級(jí)的劃分.

圖7 路網(wǎng)航段交通擁擠指標(biāo)聚類結(jié)果Fig.7 Clustering results of traffic congestion indicators in air route network segment

(3)進(jìn)行集成學(xué)習(xí)識(shí)別模型參數(shù)設(shè)定.

模型參數(shù)共有5種設(shè)定，如表2所示，驗(yàn)證模型不同基學(xué)習(xí)器設(shè)置的識(shí)別性能.訓(xùn)練數(shù)據(jù)為3月1～4日共3 456組指標(biāo)和對(duì)應(yīng)的擁擠等級(jí)數(shù)據(jù)，其中80%為訓(xùn)練樣本，20%為測(cè)試樣本.

表2 路網(wǎng)航段交通擁擠識(shí)別模型參數(shù)設(shè)定Table 2 Parameter setting of traffic congestion identification model for air route network segment

模型識(shí)別性能評(píng)價(jià)指標(biāo)如下.

①識(shí)別準(zhǔn)確率.

②平均絕對(duì)誤差.

③最大絕對(duì)誤差.

④均方根誤差.

式中：λacc為交通擁擠識(shí)別正確的樣本數(shù)；λ為擁擠識(shí)別總樣本數(shù)；yt為擁擠等級(jí)實(shí)測(cè)值；為擁擠等級(jí)識(shí)別值.

表3為在5種參數(shù)下，模型識(shí)別性能的比較.識(shí)別性能依次為 Model 1、Model 2、Model 5、Model 3、Model 4，其中，Model 1識(shí)別精度最高為98.34%.可知決策樹基學(xué)習(xí)器識(shí)別精度高于k近鄰基學(xué)習(xí)器，Stacking學(xué)習(xí)集成方法識(shí)別精度高于投票法.本文選用決策樹基學(xué)習(xí)器和Stacking結(jié)合算法構(gòu)建集成學(xué)習(xí)識(shí)別模型.

表3 5種設(shè)定下的集成學(xué)習(xí)模型識(shí)別性能Table 3 Identification performance of ensemble learning model under five settings

驗(yàn)證基學(xué)習(xí)器數(shù)量對(duì)模型識(shí)別精度的影響，結(jié)果如表4所示.隨著基學(xué)習(xí)器數(shù)量增加，準(zhǔn)確率逐步增加，誤差逐漸減小，當(dāng)選取9個(gè)基學(xué)習(xí)器時(shí)，準(zhǔn)確率為98.34%.

表4 不同基學(xué)習(xí)器數(shù)量的集成學(xué)習(xí)模型識(shí)別性能Table 4 Performance of ensemble learning model with different number of base learners

(4)比較分析集成學(xué)習(xí)模型同其他模型的識(shí)別性能.選取BP神經(jīng)網(wǎng)絡(luò)識(shí)別模型進(jìn)行比較分析，性能對(duì)比如表5所示.可知集成學(xué)習(xí)模型識(shí)別準(zhǔn)確率和識(shí)別誤差均優(yōu)于BP神經(jīng)網(wǎng)絡(luò)模型，故選用集成學(xué)習(xí)構(gòu)建識(shí)別模型具有一定優(yōu)勢(shì).

表5 集成學(xué)習(xí)識(shí)別模型與BP神經(jīng)網(wǎng)絡(luò)識(shí)別模型性能對(duì)比Table 5 Performance comparison between ensemble learning model and BP neural network model

路網(wǎng)航段3月4日交通擁擠集成學(xué)習(xí)模型識(shí)別結(jié)果如圖8所示.通過實(shí)證分析可知，航段交通擁擠集成學(xué)習(xí)識(shí)別模型能夠較好地實(shí)現(xiàn)路網(wǎng)航段交通擁擠的識(shí)別.

圖8 路網(wǎng)航段3月4日的交通擁擠等級(jí)集成學(xué)習(xí)識(shí)別結(jié)果Fig.8 Ensemble learning identification of traffic congestion level in air route network segment on March 4

5 結(jié)論

本文基于集成學(xué)習(xí)算法提出了航路網(wǎng)絡(luò)航段交通擁擠識(shí)別方法，利用路網(wǎng)航跡數(shù)據(jù)，建立航段交通擁擠評(píng)價(jià)指標(biāo)，實(shí)現(xiàn)路網(wǎng)航段交通擁擠綜合劃分與識(shí)別.實(shí)證研究表明，路網(wǎng)航段交通擁擠集成學(xué)習(xí)識(shí)別模型的識(shí)別準(zhǔn)確率可達(dá)98.34%，優(yōu)于BP神經(jīng)網(wǎng)絡(luò)識(shí)別模型，識(shí)別精度較高，識(shí)別性能優(yōu)良，可用于航段交通擁擠識(shí)別，為航路網(wǎng)絡(luò)交通擁擠綜合管控提供決策支持.