王時(shí)敏，林 彬

(南京航空航天大學(xué) 民航學(xué)院，南京 210016)

氣象條件影響的航段延誤高維異常檢測(cè)

王時(shí)敏，林 彬

(南京航空航天大學(xué) 民航學(xué)院，南京 210016)

海量航班延誤數(shù)據(jù)中包含著少部分在惡劣天氣條件下，仍有著較低延誤水平的記錄，這些案例為后期研究管制員在惡劣天氣下的應(yīng)對(duì)策略提供了學(xué)習(xí)樣本.因涉及的變量較多，在分析高維空間特性的基礎(chǔ)上，詳述了高維屬性在運(yùn)用傳統(tǒng)異常檢測(cè)算法時(shí)的不適應(yīng)性，重點(diǎn)闡述了一種基于譜聚類投影的異常檢測(cè)算法，先將高維屬性依此投影到低維空間，再運(yùn)用局部離群因子作為隸屬度函數(shù)進(jìn)行異常檢測(cè)，不僅能有效地處理高維數(shù)據(jù)的稀疏性問(wèn)題，也能處理混合型的數(shù)據(jù)集，可解釋性強(qiáng).最后運(yùn)用此算法高效地識(shí)別出了惡劣氣象條件下低延誤值的實(shí)例.

異常檢測(cè)；高維數(shù)據(jù)；稀松性；譜聚類

天氣是影響延誤不可控的因素，但是在交通需求量大且氣象條件惡劣的情況下，仍然有很多記錄有著較低的延誤值，這些案例為后期研究管制員在惡劣天氣下的應(yīng)對(duì)策略提供了學(xué)習(xí)樣本.本實(shí)驗(yàn)旨在找到影響單航段延誤的全局關(guān)鍵因素，通過(guò)在日均流量較大的機(jī)場(chǎng)之間建立受惡劣氣象條件影響的延誤網(wǎng)絡(luò)，找出此網(wǎng)絡(luò)中的異常點(diǎn)，即那些不利天氣下的低延誤記錄，為進(jìn)一步改進(jìn)管制手段提供參考.

所謂異常檢測(cè)，即從大規(guī)模數(shù)據(jù)中找到少量的關(guān)鍵異常樣本.有時(shí)所謂異常正是人們真正關(guān)心的部分，為進(jìn)一步探究其原因提供了切入口，本例即是如此.近些年來(lái)，異常檢測(cè)算法作為一個(gè)獨(dú)立分支逐漸成型，而不再只是作為聚類算法的應(yīng)用之一.傳統(tǒng)的異常挖掘主要是基于統(tǒng)計(jì)模型、密度分布、距離測(cè)量等.這些方法主要針對(duì)低維數(shù)值型數(shù)據(jù)集，在處理高維大規(guī)模數(shù)據(jù)集時(shí)計(jì)算效率低下，表現(xiàn)出種種不適應(yīng)性.

維災(zāi)[1]是高維空間幾何學(xué)產(chǎn)生的，泛指在數(shù)據(jù)分析中因?qū)傩赃^(guò)多而引起的所有問(wèn)題.數(shù)據(jù)集要在高維空間中生成相同密度的數(shù)據(jù)點(diǎn)，則該數(shù)據(jù)集的大小隨維數(shù)呈指數(shù)增長(zhǎng)，若一個(gè)一維樣本包n含個(gè)數(shù)據(jù)點(diǎn)，要在k維空間里獲得同樣的密度，因數(shù)據(jù)在高維空間中的稀疏性，就需要nk個(gè)數(shù)據(jù)點(diǎn)，也就是說(shuō)即使在一個(gè)很大的范圍內(nèi)很可能連一個(gè)點(diǎn)也不包含.或者說(shuō)如果體積是一定的，高維空間的物體比低維空間的物體擁有更大的表面積，導(dǎo)致樣本密度低，往往不符合數(shù)據(jù)挖掘的要求.

在低維空間中，異常點(diǎn)的概念大多指與別的樣本在距離或密度上差異過(guò)大，過(guò)分依賴于網(wǎng)格劃分或是索引結(jié)構(gòu).當(dāng)維度劇增時(shí)，樣本之間因高維稀疏性幾乎是等距離的[1]，傳統(tǒng)的基于距離的聚類方法不再適用，因?yàn)槊總€(gè)樣本基于在距離或密度的層面都可以看作是異常，必須重新定義異常的概念并設(shè)計(jì)適當(dāng)?shù)乃惴?對(duì)于高維數(shù)據(jù)，一般通過(guò)以下兩種方式處理：降維、子空間投影等.

傳統(tǒng)的降維方法分為兩類：特征選擇和特征變換.特征選擇方法依據(jù)是否會(huì)影響到后續(xù)學(xué)習(xí)算法分為過(guò)濾式和封裝式兩種.前者與獨(dú)立于后續(xù)算法，直接采用全部訓(xùn)練數(shù)據(jù)的屬性特征參與運(yùn)算，計(jì)算速度快但與之后的學(xué)習(xí)算法結(jié)果偏差較大；后者偏差較小但計(jì)算量較大，并不適合于大數(shù)據(jù)量.特征變換不同于特征選擇之處在于其輸出結(jié)果不是原有的屬性，而是基于某種變換原則所產(chǎn)生的新屬性.由于變換后的屬性改變了原有屬性的物理特性，同時(shí)一些特征變換方法通常針對(duì)連續(xù)屬性數(shù)據(jù)，再此不考慮特征變換方法.

其他主要缺陷在于：1)需先驗(yàn)知識(shí)才能確定相關(guān)參數(shù)，算法適應(yīng)性較差；2)無(wú)法控制分類的正確率，沒(méi)有給出如何通過(guò)控制錯(cuò)分概率達(dá)到分類效果最優(yōu)化；3)可解釋性差，不能直觀簡(jiǎn)潔地反映異常數(shù)據(jù)產(chǎn)生的原因；4)能處理的數(shù)據(jù)類型單一，或者是數(shù)值型、或者離散型.本例中涉及的變量龐雜，屬于高維異常檢測(cè)的范疇，這些算法應(yīng)用于高維分析時(shí)檢測(cè)性能顯著下降，可解釋性更無(wú)從談起.分析高維數(shù)據(jù)的特性，并以此設(shè)計(jì)適用于高維屬性的異常檢測(cè)很有現(xiàn)實(shí)意義.R·Agrawal[2]在其關(guān)于高維度數(shù)據(jù)的自動(dòng)子空間聚類論文中給出了CLIQUE算法、包括單調(diào)性定理及其證明.Kriegel等人[3]認(rèn)為，基于角度的測(cè)量在高維空間比基于距離的測(cè)量更穩(wěn)定，利用余弦角度方差作為判斷依據(jù)，可避免基于距離計(jì)算時(shí)出現(xiàn)的維災(zāi).Aggarwal 和Yu[4]討論了將高維屬性集投影到低維子空間，在基于子空間投影的稀疏程度識(shí)別孤立點(diǎn).Jiawei Han等[5]對(duì)常用的異常檢測(cè)方法及其適用范圍做了較為完整的總結(jié).陳圣楠[6]在基于角度方差的高維異常檢測(cè)算法基礎(chǔ)上，結(jié)合了粗糙集理論，為屬性的重要度進(jìn)行排序，提出了多層次異常數(shù)據(jù)檢測(cè)算法HODA；通過(guò)對(duì)數(shù)據(jù)進(jìn)行網(wǎng)格劃分來(lái)分析數(shù)據(jù)在各維度上的分布，尋找潛存著異常點(diǎn)的網(wǎng)格；最后通過(guò)對(duì)這些網(wǎng)格計(jì)算角度方差異常因子識(shí)別異常點(diǎn).

1 研究數(shù)據(jù)及檢測(cè)原理

1.1研究數(shù)據(jù)

本文所用的航班信息數(shù)據(jù)為2014年上半年旅客吞吐量位居全國(guó)前20名的機(jī)場(chǎng)的航班信息，每條樣本包括實(shí)際起落時(shí)間、計(jì)劃起落時(shí)間、航空器注冊(cè)號(hào)、起飛機(jī)場(chǎng)、目的地機(jī)場(chǎng)、計(jì)劃備降機(jī)場(chǎng)、經(jīng)停次數(shù)、機(jī)型、航班類型、實(shí)際滑出時(shí)間和計(jì)劃滑出時(shí)間等屬性，其中航班延誤時(shí)間定義為實(shí)際滑出時(shí)間與計(jì)劃滑出時(shí)間的差，篩選出延誤不大于15 min的樣本.

本文所用的氣象報(bào)文數(shù)據(jù)為2014年上半年旅客吞吐量位居中國(guó)前20位機(jī)場(chǎng)的METAR報(bào)文以及TAF報(bào)文，數(shù)據(jù)由自動(dòng)氣象站采集而來(lái)，它由傳感器、數(shù)據(jù)采集處理器和顯示終端組成，能自動(dòng)收集和傳遞氣象信息，主要用于觀測(cè)：氣壓、氣溫、相對(duì)濕度、風(fēng)向風(fēng)速等，以中國(guó)民航氣象報(bào)的方式發(fā)布.

1.2檢測(cè)原理

將METAR報(bào)和TAF報(bào)的氣象條件部分與飛行計(jì)劃數(shù)據(jù)庫(kù)相對(duì)應(yīng).報(bào)文以半小時(shí)為間隔發(fā)布一次，將每個(gè)發(fā)布時(shí)刻前后15 min內(nèi)起飛的航班認(rèn)定為受此氣象條件影響.本文使用2014年上半年旅客吞吐量位居中國(guó)前20位機(jī)場(chǎng)的航班信息集合和與之對(duì)應(yīng)METAR報(bào)文.METAR報(bào)文經(jīng)處理后提取出以下幾列信息：機(jī)場(chǎng)名稱、時(shí)間、風(fēng)向風(fēng)速、能見(jiàn)度、氣象信息、云層、溫度/露點(diǎn)、修正海壓、近期天氣等，其中氣象信息可細(xì)分為降雨、雪、霧、霾、雷暴、積冰、顛簸等.

不同的天氣類型及其發(fā)生的時(shí)段導(dǎo)致的延誤程度不同.高峰小時(shí)的天氣狀況會(huì)更顯著的影響航班延誤程度，惡劣天氣的持續(xù)時(shí)間決定了機(jī)場(chǎng)高峰時(shí)段的需求在多大程度上能被滿足,并由此決定了機(jī)場(chǎng)延誤水平.本文將需求交通量分為機(jī)場(chǎng)的和航路的，將一天24 h等分成12個(gè)區(qū)間，每個(gè)區(qū)間對(duì)應(yīng)兩個(gè)交通運(yùn)量，分別是機(jī)場(chǎng)離場(chǎng)需求交通量和機(jī)場(chǎng)進(jìn)場(chǎng)需求交通量，此外還有航段需求交通量，定義為所在時(shí)段內(nèi)飛經(jīng)該航段的航空器架次，三者共同構(gòu)成了交通運(yùn)量分布.

按時(shí)間段，將每一航段涉及的機(jī)場(chǎng)及其氣象條件、交通量、航班信息連接，再將10個(gè)機(jī)場(chǎng)之間的所有航段兩兩相連，最終建成由20個(gè)氣象數(shù)據(jù)、5個(gè)交通需求量數(shù)據(jù)、8個(gè)航班信息、20個(gè)機(jī)場(chǎng)OD對(duì)間延誤時(shí)間組成的高維向量.對(duì)以上采集的樣本數(shù)據(jù)經(jīng)預(yù)處理后，依次為每個(gè)屬性編號(hào)，并對(duì)其主要屬性歸類.見(jiàn)表1.

本文主要針對(duì)高維屬性的特點(diǎn)，給出了一種兩階段的異常檢測(cè)算法.第一階段對(duì)數(shù)據(jù)集在各屬性維上的投影聚類，分別進(jìn)行初始聚類優(yōu)化，依次對(duì)各屬性維聚類結(jié)果計(jì)算笛卡爾交集，在計(jì)算笛卡爾交集的過(guò)程中，根據(jù)事先設(shè)定的剪枝策略對(duì)中間結(jié)果集進(jìn)行剪枝，剔除掉包含數(shù)據(jù)點(diǎn)數(shù)低于閾值的候選集，直到所有維組合完畢，最終得到在整個(gè)維空間聚類結(jié)果；第二階段依據(jù)全維聚類結(jié)果計(jì)算剪枝點(diǎn)的隸屬度，隸屬度函數(shù)選取局部離群因子函數(shù)(LOF)，根據(jù)設(shè)定的隸屬度閾值τ，對(duì)檢測(cè)出的點(diǎn)區(qū)分噪聲和異常點(diǎn)，并對(duì)異常點(diǎn)做出解釋.

首先，將空間中的所有屬性編號(hào)，若屬性維Vi是如能見(jiàn)度、云高、風(fēng)速、溫度等的數(shù)值型屬性；對(duì)屬性維Vi進(jìn)行單維投影聚類，如果屬性維是型如雷暴、霧、風(fēng)切變等類別屬性，則對(duì)其概念化分類.

其次，依次對(duì)所有維度投影聚類，因?yàn)槊恳环N屬性的數(shù)據(jù)特征各異，屬性按照能在任意形狀的樣本空間上聚類的譜分解聚類，得到類集Cn.譜聚類算法是聚類分析中一個(gè)嶄新的分支,建立在譜圖理論基礎(chǔ)上，其本質(zhì)是將聚類問(wèn)題轉(zhuǎn)化為圖的最優(yōu)劃分問(wèn)題，具收斂于全局最優(yōu)解.這種算法不用對(duì)數(shù)據(jù)的全局結(jié)構(gòu)作假設(shè)，非常適合于許多實(shí)際問(wèn)題.通常的聚類算法等都是只適用于凸球形的樣本空間，否則常常會(huì)陷入局部最優(yōu)而非全局最優(yōu).

1) 定義相似度矩陣W，其中wij為標(biāo)準(zhǔn)化的樣本ai和aj之間的歐幾里得距離.

表1 經(jīng)過(guò)處理后的每個(gè)航班數(shù)據(jù)集合字段信息

2) 由相似度矩陣計(jì)算Laplacian矩陣L

L=D-W

3) 對(duì)上述矩陣進(jìn)行特征值分解，分別求得特征值和特征向量，構(gòu)建特征向量空間；

4) 將原樣本集的數(shù)據(jù)通過(guò)譜分析投影到由所選取的特征向量生成的新的子空間上，對(duì)新的子空間中的數(shù)據(jù)聚類得到最終的聚類結(jié)果.

再次，依次選取相鄰的屬性Vi和Vi+l(i=1,2,3,…,n)，對(duì)其相應(yīng)的類集計(jì)算笛卡爾積Ci?Ci+l，對(duì)得到的中間結(jié)果Mi設(shè)定閾值τ.若Mi<τ，即該分支的數(shù)量過(guò)少，被剔除.迭代計(jì)算余下的屬性與保留的Mi的笛卡兒積，剪枝過(guò)程也隨之迭代進(jìn)行.

最后，計(jì)算每個(gè)最終組合的樣本數(shù)目Qi的隸屬度Pi，判斷是否為異常點(diǎn). 此部分相應(yīng)的偽代碼如表2、圖1所示：

for(dimension fromV1toVn)//共n個(gè)維度

{

if(Viis numerical)

{

//將Vi進(jìn)行單維數(shù)據(jù)投影聚類，生成對(duì)應(yīng)的聚類，記錄相應(yīng)的聚類信息

for (neighbor clustersDa,DbinVidimension)

{

If(Da,b

{

聚類合并

}

}

把Vi的聚類結(jié)果保存到Mi

}

else if (Viis Boolean ||Viis other type){

概念化分類，聚類結(jié)果保存到Mi

}

}

for(M1toMn)

{

//在該維度計(jì)算笛卡爾積 (共有L個(gè)組合,Qi表示每個(gè)最終組合的樣本數(shù)目)

for(Q1toQL)

{

If(Qi<閾值1，)

{

計(jì)算Qi的隸屬度Pi

If (Pi<閾值2)

{

確定為異常點(diǎn)

}

else

{

計(jì)算與最接近的聚類的差異程度

}

}

}

因同樣氣象條件及需求分布條件下，不同航班記錄的延誤分布規(guī)律差異很大，關(guān)于隸屬度Pi，本文采用一種針對(duì)密度分散情況迥異集合的異常點(diǎn)識(shí)別方式，即局部異常因子算法-Local Outlier Factor(LOF)來(lái)衡量.相關(guān)算法如下：

1)d(a,o)為樣本a和樣本o之間的距離；

2)對(duì)于樣本a的第k距離dk(a)定義為距離樣本a第k遠(yuǎn)的樣本(不含樣本a)的距離.

3)樣本a的第k距離鄰域Nk(a)，即以樣本a為圓心，以dk(a)為半徑所涵蓋范圍內(nèi)包含的全部樣本，也包括其邊界.顯然，這一范圍內(nèi)所包含的樣本個(gè)數(shù)不少于k.

4) 樣本o到樣本a的第k可達(dá)距離定義為：reach-distk(a,o)=max{dk(a),d(a,o)} 可以理解為至少是樣本o的第k距離，或是樣本o與a樣本間的歐幾里得距離.也就是說(shuō)，樣本o到離其最近k的個(gè)樣本的可達(dá)距離都為d(o).

5) 樣本的局部可達(dá)密度表示為：

即樣本a的Nk(a)到樣本a的平均可達(dá)距離取倒數(shù).如果樣本a不是異常點(diǎn)，那么其可達(dá)距離取dk(o)的概率越大，此時(shí)分母較小，局部可達(dá)密度越大；反之，如果樣本a是潛在異常點(diǎn)，那么其可達(dá)距離取d(a,o)的概率越大，此時(shí)分母較大，局部可達(dá)密度較小.

6)樣本a的局部離群因子表示為：

表示樣本a的鄰域點(diǎn)Nk(a)的局部可達(dá)密度與樣本a的局部可達(dá)密度之比的平均數(shù).若比值越接近1，該樣本點(diǎn)越可能和鄰域同屬一簇；若比值越遠(yuǎn)小于1，說(shuō)明此樣本比其領(lǐng)域內(nèi)的其他樣本平均密度大；若比值越遠(yuǎn)大于1，說(shuō)明此樣本比其領(lǐng)域內(nèi)的其他樣本平均密度小，也就潛在的異常點(diǎn).

2 驗(yàn)證結(jié)果

根據(jù)上述算法，在2012年上半年旅客吞吐量位居全國(guó)前20名的機(jī)場(chǎng)的航班信息中，當(dāng)τ≤3時(shí)共檢測(cè)出的312條惡劣天氣下的低延誤樣本，再依據(jù)數(shù)據(jù)編號(hào)在數(shù)據(jù)庫(kù)中識(shí)別出對(duì)應(yīng)記錄.部分異常樣本如表2，圖1所示：

表2 檢測(cè)出的異常樣本部分示例匯總

剔除掉異常點(diǎn)之后，可觀測(cè)到全國(guó)主要機(jī)場(chǎng)OD對(duì)間的宏觀延誤水平，為了便于對(duì)比，本文將延誤分為五個(gè)等級(jí)，依次為小于15 min；大于15 min小于30 min；大于30 min小于45 min；大于45 min小于60 min；60 min以上.

圖1 剔除異常點(diǎn)前后的延誤網(wǎng)絡(luò)對(duì)比

3 結(jié) 語(yǔ)

海量航班延誤數(shù)據(jù)中包含著少部分在惡劣天氣條件下，仍有著較低延誤水平的記錄，這些案例為后期研究管制員在惡劣天氣下的應(yīng)對(duì)策略提供了學(xué)習(xí)樣本.因涉及的變量較多，本文在分析高維空間特性的基礎(chǔ)上，詳述了高維屬性在運(yùn)用傳統(tǒng)異常檢測(cè)算法時(shí)的不適應(yīng)性，重點(diǎn)闡述了一種基于譜聚類投影的異常檢測(cè)算法，先將高維屬性依此投影到低維空間，再運(yùn)用局部離群因子作為隸屬度函數(shù)進(jìn)行異常檢測(cè)，不僅能有效地處理高維數(shù)據(jù)的稀疏性問(wèn)題，也能處理混合型的數(shù)據(jù)集，可解釋性強(qiáng).最后運(yùn)用此算法高效地識(shí)別出了惡劣氣象條件下低延誤值的實(shí)例.

[1] BELLMAN R. Adaptive control processes: a guided tour [M]. Princeton: Princeton University Press, 1961.

[2] AGRAWAL R, GEHRKE J, GUNOPULOS D,etal. Automatic subspace clustering of high dimensional data for data mining applications [P]. United States Patent: 6003029, 1999-12-14.

[3] KRIEGEL H P, HUBERT M S, ZIMEK A. Angle-based outlier detection in high-dimensional data[C]// Las Vegas: 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2008. 444-452.

[4] AGGARWAL C C, YU P. Outlier detection for high dimensional data [J]. ACM SIGMOD Record, 2001, 30(2): 37-46.

[5] 丁 潔, 王 磊, 沈荻帆, 等. A一種大數(shù)據(jù)異常檢測(cè)系統(tǒng)的研究與實(shí)現(xiàn)[J]. 海南大學(xué)學(xué)報(bào)：自然科學(xué)版, 2015, 33(1): 24-27+33.

[6] 陳圣楠, 錢紅燕, 李 偉. 基于角度方差的多層次高維數(shù)據(jù)異常檢測(cè)算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2016, 33(11): 3383-3386.

Researchonoutlierdetectionforhighdimensionalweather-impactedflightsegmentdelay

WANG Shi-min, LIN Bin

(School of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)

Massive delays data contains a few valuable information of low delay level in bad weather conditions, which provides ATC with learning samples for the later research about the best solution in severe weather atmosphere. Due to vast variable involved, based on the characteristics of high-dimensional space, it was analyzed why traditional anomaly detection algorithm was not suitable for high dimensional attribute. And this paper explored an anomaly detection algorithm based on spectral cluster and projection, which firstly projects the high-dimensional attributes to low dimensional space, and uses local outlier factor as membership functions in anomaly detection. The result could not only effectively handle data sparseness of high-dimensional data, also could deal with both numeric and Boolean type attribute, and explain the abnormal. An application example of low delay level of flight segment affected by bad weather is given to validate the feasibility and effectiveness of the algorithm.

outlier detection; high dimensional data; sparseness; spectral clustering

2016-11-14.

王時(shí)敏(1989-)，女，碩士，研究方向：空域規(guī)劃與管理.

V355

：A

1672-0946(2017)04-0502-05