基于關聯規則挖掘的航班協同保障數據知識發現研究

丁建立 王 曼

1(中國民航大學計算機科學與技術學院 天津 300300)2(中國民航信息科研基地 天津 300300)

?

基于關聯規則挖掘的航班協同保障數據知識發現研究

丁建立 王 曼*

1(中國民航大學計算機科學與技術學院 天津 300300)2(中國民航信息科研基地 天津 300300)

隨著我國民航業的迅猛發展，各大樞紐機場累積了海量的航班協同保障數據，挖掘其中潛在隱藏的知識具有重要意義。結合機場航班協同保障業務規則及航班協同保障數據的特征，利用關聯規則挖掘技術，挖掘隱藏在航班協同保障數據中的知識，進而借助其優化航班保障流程，提升機場服務保障質量。通過實例驗證，關聯規則算法能夠較好地發掘隱藏在航班協同保障數據中的潛在知識，將其應用于實際中能夠為優化航班保障流程、提高航班準點率、提升機場服務保障能力提供有效的支撐和決策依據。

航班保障數據 關聯規則 知識發現 航班準點率

0 引 言

近年來，隨著我國民航業的迅猛發展，航班運行協同決策CDM[1](Collaborative Decision Making)系統越來越廣泛地應用于各大樞紐機場。與此同時，在航班運行保障過程中會累積大量的航班運行保障數據，如何科學合理地處理利用這些數據是擺在民航各部門面前的一道難題。因此，航班協同保障數據的知識發現研究具有重要意義，其不僅有助于航班保障流程的優化、機場服務保障能力的提升，同時有助于我國民航業的可持續發展。

數據知識發現KDD(Knowledge Discovery in Database)，也叫數據挖掘，是從各種表示的數據信息中，根據不同的需求獲得知識。針對知識發現及其相關應用問題，國內外相關學者已開展了相關研究，并取得了一定的成果。Kumar S等人在文獻[2]中研究了將數據挖掘技術與螞蟻算法、遺傳算法相結合，挖掘分析生產調度過程中產生的大量數據，進而優化調度過程；Ni JC等人在文獻[3]中采用數據挖掘技術對產品制造業的數據進行分析，提取系統中數據之間的關聯規則，用于指導產品制造的調度過程；夏英等在文獻[4]中研究了智能交通系統中的時空數據挖掘分析，通過對時空數據進行智能分析，獲取運動軌跡、交通流量、道路擁堵狀態等不同數據元素的時空相似性、時空相關性和時空關聯性，進而進行路網擁堵趨勢、短時交通流量預測等；王成龍等人在文獻[5]中研究了作業車間調度規則挖掘問題，基于決策樹的調度規則挖掘方法，提取調度方案中新的調度規則，指導作業車間調度過程。通過分析發現，基于關聯規則的數據挖掘方法在民航及作業優化調度領域具有較好的研究及應用，因此，可以借助關聯規則挖掘方法，挖掘隱藏在海量歷史航班協同保障數據中的潛在的、有用的知識，進而指導優化航班保障流程。

通過分析航班保障流程[6]及航班協同保障數據的特征，本文利用Apriori算法，從大量的航班協同保障數據中發現航班保障各環節之間的關聯關系，進而借助其優化航班保障流程，提升航班放行正常率。

1 基本概念及理論

1.1 航班保障流程及航班協同保障數據的定義

航班保障工作復雜而繁瑣，每個保障環節都將會對航班是否能夠準點起飛產生影響，且各關鍵環節之間相互關聯。分析各航班協同保障環節之間的復雜關系，有必要對航班協同保障屬性進行定義。航班從準備到起飛的整個保障過程中涉及到的各保障環節稱為航班協同保障屬性FCSA(Flight Collaborative Security Attribute)，其主要包括航班清潔屬性(CL)、航班加油屬性(FO)、航班配餐屬性(FD)、機務放行屬性(MA)、指揮上客屬性(LD)、關艙門屬性(CO)、撤輪檔屬性(BL)、航班滑行道滑行屬性(TA)和航班起飛屬性(TO)。

航班協同保障數據是指機場、空管、航空公司的信息集成系統對航班協同保障屬性的預計完成時間、實際完成時間及該航班運行狀況的記錄。一般情況下，一條航班保障記錄數據可由十九元組P(FNO,CLTs,CLTa,FOTs,FOTa,FDTs,FDTa,MATs,

MATs,MATa,LDTs,LDTa,COTs,COTa,BLTs,BLTa,TATs,TATa,TOTs,TOTa)表示。

其中：FNO表示該條保障記錄數據所對應航班的航班號，表1給出了航班保障記錄數據的說明。

表1 航班協同保障記錄數據說明表

航班協同保障屬性的取值用九元組M(δcl,δfo,δfd,δma,δld,δco,δbl,δta,δto)表示，針對航班保障屬性的各環節，若其實際完成時間>計劃完成時間，則對應屬性取值為yes；否則，對應屬性取值為no。即：

(1)

其中，i=(cl,fo,fd,ma,ld,co,bl,ta,to)

正常放行航班的定義：假設機場航班延誤標準為t，若TOTa>TOTs+t，則認為航班FNO延誤；否則，認為該航班正常放行。

1.2 關聯規則

關聯規則[7]是表示數據的一組屬性之間某種關聯關系的規則，其數學模型描述如下：設I={i1,i2,i3,…,im}是m個不同屬性項的集合，數據集D是數據庫事務的集合，其中每個事務T是屬性項的集合，即T?I。關聯規則表示為蘊涵式X?Y，其中X?I,Y?I,X∩Y=?。數據集D中的規則X?Y受支持度supp和置信度conf的約束。其中，支持度supp(X?Y)定義為D中事務包含X∪Y的百分比；置信度conf(X?Y)定義為D中包含X的事務同時也包含Y的百分比。

在實際研究中，滿足一定支持度和置信度的關聯規則才有意義[8]。為此定義兩個閾值，最小支持度minsupp和最小置信度minconf。如果supp(X?Y)≥minsupp,conf(X?Y)≥minconf則稱規則X?Y是成立的。關聯規則的挖掘就是在事務數據集D中找出滿足給定最小支持度和最小置信度的關聯規則。

2 基于關聯規則的航班協同保障數據挖掘算法

2.1 數據預處理

現實世界中的數據通常是有噪聲、不完全、不一致的，航班協同保障數據也不例外。例如工作人員誤錄入等操作，使得獲得的數據存在缺值、含有臟數據等問題。因此，在利用數據挖掘方法對其進行挖掘之前有必要進行數據清洗。

航班協同保障數據的各屬性為連續性數值，目前針對連續性數值數據的知識發現挖掘問題，大都首先借助數據歸約方法將連續性數值屬性離散化，然后再通過數據挖掘算法挖掘隱藏的知識。在此，本文采用預定義的概念分層方式對航班保障數據各屬性進行離散化處理。數據預處理步驟如下：

(1) 針對航班保障數據存在數據缺失的問題，將無效的航班保障數據過濾清洗掉；

(2) 根據式(2)計算每條航班保障數據對應時間段內的航班放行正常率λ，用“正常率標識”屬性(Level)標識，Level表示該航班起飛時間所對應時間段的放行正常率等級，Level取值為δle={Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ}。航班放行正常率等級如表2所示。

(2)

其中，Nr表示該航班起飛時間段內放行正常航班數目，N表示該航班起飛時間段內保障航班數目總量。

表2 航班放行正常率等級表

(3) 根據式(1)將原始航班保障記錄P轉化為航班協同保障屬性取值的元組M，數據預處理后，關聯規則挖掘的事務數據集如表3所示。

表3 航班協同保障事務數據集

2.2 關聯規則挖掘算法

在對航班協同保障數據進行關聯規則挖掘分析過程中，采用Apriori算法，通過掃描數據庫累積每個項的計數，采用逐層搜索的迭代方法收集滿足最小支持度的項，生成頻繁項集。一旦找出頻繁項集，便可直接產生滿足最小支持度和最小置信度的強關聯規則。

具體操作步驟如下：

步驟1取航班協同保障數據進行數據預處理，得到關聯規則挖掘的航班協同保障事務數據集；

步驟2輸入所挖掘關聯規則的最小支持度minsupp和最小置信度minconf；

步驟3依次掃描航班協同保障事務數據集D，數據集共有r事務，對每個事務DTID(TID=1…r)的每個屬性取值項δcl[a]、δfo[a]、δfd[a]、δma[a]、δld[a]、δco[a]、δbl[a]、δta[a]、δto[a](a={yes,no})、δle[b](b={Ⅰ、Ⅱ、Ⅲ、Ⅳ、Ⅴ})等出現次數進行候選支持度計數，比較各項的支持度計數與最小支持度計數min_supp(min_supp=minsupp×r)，將候選支持度計數大于min_supp的取值項生成頻繁1項集L1；

步驟4對Lk-1(k≥2)進行自身連接，產生候選項集Ck，再依次掃描航班協同保障事務數據集，對Ck項集的每個子集進行候選支持度計數，與最小支持度計數比較后生成Lk，直至Ck=?；

步驟5輸出D下的頻繁項集Lk，由Lk生成滿足最小置信度minconf的關聯規則lk:Ak?Bk，其中Ak?S,Bk?S，Ak∩Bk=?，S={δcl[a],δfo[a],δfd[a],δma[a],δld[a],δco[a],δbl[a],δta[a],δto[a],δle[b]}。

3 實驗結果分析及應用舉例

3.1 實驗結果與分析

選取國內某樞紐機場2014年9月-12月的航班協同保障數據作為實驗數據，并對保障數據進行數據預處理，然后借助Apriori算法挖掘在樞紐機場不同協同狀況等級下各關鍵環節之間的關聯關系。同時選取該機場2015年某月的航班保障數據作為驗證數據，用于驗證所發現的關聯規則的有效性及魯棒性。其中，為了保證各保障環節之間關聯規則結果的客觀性，實驗數據中不包括由于天氣或軍事活動等客觀原因造成長時間(3小時以上)延誤的航班數據。

實驗參數設置如下：航班延誤標準t為30 min，最小支持度minsupp為0.4，最小置信度minconf為0.7，最大規則數20。實驗結果：表4所示為所生成的置信度大于0.85的最大關聯規則集；圖1所示為驗證數據集數量分別為500、2000、5000、10000條時，最大關聯規則集在數據集中的準確率；圖2所示為調整最小支持度參數分別為0.1～0.7、最小置信度為0.75，在不同的最小支持度參數下得到的關聯規則數量對比圖。

表4 最大關聯規則集

圖1 關聯規則的魯棒性驗證結果

從表4所示的關聯規則集可以看出，在航班協同保障數據集中存在一定量置信度較高的關聯規則知識，并且通過數據分析手段可以挖掘出這些知識。其中，規則1-規則5是航班協同保障屬性與航班放行正常率之間的關系：由規則1可知，在航班的關艙門、撤輪檔、滑行時間均正常的情況下，航班的正常放行率在80%～100%之間，為Ⅰ等級；由規則2可知當航班放行正常率降為Ⅱ級(60%～80%)時，其主要原因是航班配餐及關艙門屬性沒有按計劃時間完成；而由規則3可知，當航班清潔、配餐及指揮上客時間晚于計劃時間時，航班放行正常率在Ⅲ級(40%～60%)；同時，對比規則3和規則4可以發現，關艙門屬性是影響航班放行正常率的一個重要環節；由規則5可知，當航班保障的各環節沒有按時完成時，航班放行正常率嚴重下降。另外，從規則6-規則8中可以發現，航班保障的某些屬性環節之間是會產生相互影響和制約的；由規則6可知，當航班的清潔、配餐和機務放行能夠按時完成時，航班才能夠按時指揮上客；由規則7可知，當指揮上客、關艙門和撤輪檔按計劃完成時，航班能夠按計劃起飛時間起飛，一般情況下不會延誤。

利用歷史航班運行數據對所挖掘的關聯規則知識進行魯棒性驗證，從圖1中的結果可以看出，航班協同保障數據集中挖掘出的關聯規則在不同數量級驗證數據中的準確率較穩定。規則1-規則8的最大準確率和最小準確率之間的差值分別為0.11、0.1、0.07、0.05、0.07、0.07、0.06、0.07，平均差值僅為0.067，說明關聯規則的魯棒性較好。另外，由圖2可以看出，航班協同保障數據中存在一定數量的關聯規則知識，即航班協同保障各環節之間及與航班放行正常率是有一定關聯關系的，隨著Apriori算法最小支持度設置的不同，可以獲取到一定數量的有價值的關聯規則知識。

圖2 不同支持度下的關聯規則結果數量

3.2 應用舉例

基于關聯規則挖掘的知識發現技術在各行業領域都得到了廣泛的研究及應用，包括網絡信息資源[9]的知識發現，醫療健康數據[10]、網絡用戶行為數據[11]、聲音數據[12]等等。通過關聯規則挖掘，在航班運行保障數據中發現的航班保障與航班放行狀態的關聯規則知識，對于航班保障流程的優化和航班準點率的提高具有重要意義。例如，由規則1可以知道，當航班的關艙門、撤輪檔、滑行時間均在計劃時間內完成時，航班的放行正常率較高。同時，通過與規則2進行對比可以發現，航班正常率的下降主要由于配餐準備和關艙門沒有按時完成的影響，這就提示航班運行保障部門對于配餐準備環節的重視，在適當的時候應該增加相應的資源，確保該環節的保障完成情況，進而提升保障效率。除此之外，結合規則6與規則7發現，當航班的清潔、配餐和機務放行工作均正常地按時完成后，航班才能夠及時指揮上客，才能保證之后的按時撤輪檔、滑出及起飛。因此，在航班沒有完成配餐或機務放行工作前，航空公司應該暫時推遲指揮旅客登機，這樣就能夠避免旅客登機完成后由于機組或機務原因導致旅客在飛機上等待。

4 結 語

本文結合關聯規則的知識發現算法對CDM系統中大量的航班協同保障數據進行分析，發現航班保障環節的潛在規律，進而緩解由于航班保障不當等因素造成的航班延誤問題。實驗證明，該方法可以準確快速地挖掘出航班協同保障數據中大量有意義的規則，這些規則可以作為先驗知識用來指導航班保障流程的優化，具有一定的參考價值。由于條件局限，本文對數據進行處理時尚未考慮機場繁忙與非繁忙時段差異性方面的知識發現，這有待進一步研究。

[1] 閆然. 民航協同決策(CDM)概念及分析[J]. 中國科技術語, 2012,6(3):50-53.

[2] Kumar S, Rao C S P. Application of ant colony, genetic algorithm and data minging-based techniques for scheduling[J].Robotics and Computer-Integrated Manufacturing, 2009,25(6):901-908.

[3] Li L, Sun Z J, Ni J C, et al. Data-based scheduling framework and adaptive dispatching rule of complex manufacturing systems[J].The International Journal of Advanced Manufacturing Technology, 2013,66(9-12):1891-1905.

[4] 夏英. 智能交通系統中的時空數據分析關鍵技術研究[D]. 成都: 西南交通大學,2012.

[5] 王成龍, 李誠, 馮毅萍,等.作業車間調度規則的挖掘方法研究[J]. 浙江大學學報:工學版, 2015, 49(3):421-429.

[6] 張偉航. 航班運行保障新模式——航班運行協同決策系統核心理念介紹[J].科技資訊, 2014，25(18)：230-232.

[7] JiaWei Han, Micheline Kamber. Data Mining Concepts and Techniques[M].Beijing：China Machine Press, 2011.

[8] 王培吉,趙玉琳,呂劍峰.基于Apriori算法的關聯規則數據挖掘研究[J]. 統計與決策, 2011(23):19-21.

[9] 葉麗莎, 王學東, 方婧. 網絡信息資源知識發現機理研究[J]. 現代情報, 2014, 12(8):13-16.

[10] 劉洋, 張卓, 周清雷. 醫療健康數據的模糊粗糙集規則挖掘方法研究[J].計算機科學, 2014,23(12):66-70.

[11] 丁麗. 基于Apriori算法的用戶行為數據挖掘研究[J]. 科技通報, 2013,29(12):214-217.

[12] Usama Fayyad, Gregory Piatetsky-Shapiro, Padhraic Smyth. The KDD process for extracting useful knowledge from volumes of data[J].Communications of the ACM,1996,39(11):27-34.

RESEARCH ON KNOWLEDGE DISCOVERY OF FLIGHT COOPERATIVE SECURITY DATA BASED ON ASSOCIATION RULE MINING

Ding Jianli Wang Man*

1(College of Computer Science and Technology，Civil Aviation University of China, Tianjin 300300,China)2(The Research Base of Civil Aviation Information Scientific of China, Tianjin 300300,China)

With the rapid development of civil aviation in our country, the major hub airports have accumulated massive flight cooperative security data, and it is of significant meaning to mine the potential hidden knowledge in them. Aiming at this issue, we combine the airport flight cooperative security business regulations with the features of flight cooperative security data, mined the knowledge hidden in flight cooperative security data by using association rule mining technology, and further got the help from the mined knowledge to optimise flight security process and to improve the quality of airport service support. It is verified trough example that the association rule algorithm can well mine the potential knowledge hidden in flight cooperative security data, and the application of it in practices can provide effective support and decision-making basis for optimising the flight security process, increasing the flight punctuality, and enhancing the capability of airport service support.

Flight security data Association rules Knowledge discovery Flight punctuality

2015-08-07。國家自然科學基金項目(60879015)；中國民航科技重大專項(MHRD201241)。丁建立，教授，主研領域：民航智能信息處理與航空物聯網。王曼，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2016.11.005