基于关联规则挖掘的航班协同保障数据知识发现研究

丁建立 王 曼

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