搜索
第卷增刊系统工程理论与实践年月一文章编号：中图分类号：文献标志码：基于决策树方法的到港航班延误预测问题研究程华李艳梅，罗谦，李川中国民用航空局第二研究所，成都四川大学计算机学院，成都摘要航班延误一直是机场运营管理的一大难题，建立有效的模型实现较准确的延误预测来协助机场方面采取应对措施于机场于社会都有重要意义本研究提出一个面向机场的到港航班延误预测问题，对比现有的贝叶斯网络及朴素贝叶斯方法，结合航班数据的特点构建了基于决策树的航班延误预测模型针对国内某大型机场的真实数据集，本研究设计了大量实验，实验结果表明所提模型正确率接近较两种贝叶斯方法有进一步提升此外研究还设计实验分析了影响模型效果的因素关键词航班延误；分类；决策树，，引言近年来随着航空运输的迅速发展，航空业务不断增多，空中交通日益繁忙航班延误现象频频出现，成为机场运营管理的一大难题在多个机场构成的航空网络中，机场之间航班延误会产生波及影响，起飞机场的出港航班延误很可能会导致目的机场的到港延误目前民航各大信息系统中已经累积了大量的历史运营数据，若可以从历史数据中学习得到监督分类模型，就可以实现对未来航班的延误情况进行预测，帮助机场方面做出决策，从而尽可能降低损失关于航班延误问题，国内外目前都有不少研究如文献和研究了航班延误预警模型的评价与管理，文献研究了延误恢复问题，文献则结合机场容量研究延误预测美国的是一个航班信息相关的综合网站，用户可以由此获得包括天气在内的所有航班相关信息，该系统还通过统计历史数据获得美国各航班的延误率及机场等候时间进行航班延误预测本研究着重数据挖掘方法与航班延误预测问题的结合，主要考查分类方法进行预测的研究目前所采用的分类方法以贝叶斯分类法中的贝叶斯网络和朴素贝叶斯为主如基于贝叶斯网络的航班延误波及预测以及过站分析时间分析，基于改进贝叶斯网络结构学收稿日期资助项目：国家自然科学基金（国家“十二五”科技支撑计划项目（民航联合基金课题（作者简介：程华（男，高工，研究方向：机场运营管理；李艳梅（，女，硕士研究生，研究方向：数据挖掘；罗谦男，博士，高工研究方向：机场运行管理，通讯作者：李川（，男，博士，副教授研究方向：数据挖掘，云计算系统工程理论与实践第卷习的航班延误预警等一】贝叶斯分类法是一类基于贝叶斯定理的概率参数估计方法，选择贝叶斯分类方法实现简单，处理高效，效果较好但经调查发现该方法需假设分类样本的先验概率基本保持稳定，而在航空数据中由于航班延误原因复杂多变，航班数据往往呈现动态分布，因而考虑可能其他的方法更适合航班延误预测问题决策树分类是数据挖掘中监督分类技术的一种，是通过一组无次序、无规则的实例中推理出决策树表现实行的分类规则该分类方法具有较好的通用性，可理解性强，目前已经应用于很多分类问题当中，如遥感影像分类，财务预警等是最著名的决策树算法，它由改进而来，目前广泛应用于实践中如基于决策树的流量预测等结合航班数据特点，我们提出基于决策树的分类模型，研究针对单个机场展开，以到港延误为研究重点，针对一定时间段内国内某大型机场的真实到港数据进行决策树建模实现预测实验采用为实验平台，选用贝叶斯网络和朴素贝叶斯为对比方法，实验结果表明基于决策树进行航班延误正确率有进一步提升厲决策树分类决策树是通过对训练样本进行归纳学习生成决策树或决策规则，然后使用得到的决策树或规则对新数据进行分类的一种数学方法决策树是一个树形结构，由一个根节点，一系列的内部节点及叶子结点构成，每一结点只有一个父节点和两个或多个子节点，结点间通过分支相连决策树的每个内部结点对应一个非类别属性或属性的结合（也称为测试属性，每条边对类义苎）应该属性的每个可能取值，每个叶子结点对应一个类别属性值图丄决策树结构示例图给出了一个拥有个测试属性，个类标的决策树示例』决策树主要包括决策树学习和决策树分类两个过程决策树学习过程就是从训练样本中学习生成决策树，以训练集样本的预测属性作为输入，采用自顶向下的递归方式，根据某种方法来选择最优属性作为树的结点，在结点上进行属性的值的比较并根据训练样本对应的不同属性值判断从该结点向下的分支，每个分支子集重复建立下层结点和分支，在一定条件下停止树的生长，结论形成树形结构的叶子结点，从而输出最终的决策树分类过程以不带类标的测试集数据作为输入，从决策树的根结点自上而下地对测试样例的属性进行测试，直到测试样例最终到达一个叶子结点，叶子结点的类标就是测试样例的预测类标由于决策树的所有路径都是相斥的，因而可以保证每一条数据实例一定能得到且只会得到一个类标是最著名的决策树分类算法，思想就是在上面的决策树构造时，每次都选择信息增益率最大的属性作为分裂结点，进行子集划分生成树通过以上原理分析可知，与贝叶斯网络及朴素贝叶斯分类法相比，采用决策树分类来解决航班延误预测问题具有以下优势：决策树在模型构建和样本预测过程中不依赖样本数据的分布由于航班延误的原因往往复杂繁多航班数据往往呈现不规则的动态分布，因而算法就能很好避免航班数据分布变化带来的影响，使分类结果更稳定利用决策树模型进行分类时，仅需要属性值自顶向下进行比较，直到找到相应的叶子结点处理简单而且有高的数据处理效率基于决策树的航班延误预測模型决策树建立设用于航班延误的测试集为…，，每条航班可以由一组测试属性值来表示假设类别属性有：个不同的值则根据可以将划分为，…，共个子集，由此可得的平均信息量：⑴其中増刊程华，等基于决策树方法的到港航班延误预测问题研究决策树的构建过程，就是使划分后不确定性逐渐减小的过程以为例，若人有个不同取值，则根据将子集进一步划分为个子集每个子集表示的条件下属于第类的航班集合划分后的平均信息量为「」其中则用对进行划分以后的信息增益量为：每次选择最大信息增益率的属性作为测试属性，自上而下地完成决策树的构建评估策略我们根据测试集航班数据延误程度的真实值与预测值的比较来定义模型评估标准以一个有个预测属性、个延误程度等级的航班延误预测问题为例假设测试集中有条航班数据，得到的混淆矩阵如表表混淆矩阵预测延误等级预测延误等级预测延误等级实际延误等级…实际延误等级实际延误等级…表示实际延误等级为、被分类模型预测成的航班数据条数那么对每种延误程度我们做如下定义实际延误等级为的航班中，被预测为的航班条数实际延误等级为的航班中被预测为非的航班条数，实际延误等级不是的航班数据中，被预测为的航班条数，“⑶基于以上概念，下面给出我们用于衡量分类模型的个指标类准确率实际与预测的延误等级都为的航班数，与实际延误等级为的航班数之比有类的准确率■整体正确率所有预测正确的航班数据之和与所有测试集总数之比，有▽整体准确率二二算法说明到港航班延误预测的决策树伪代码如下：航班延误预测的决策树算法框架算法：，输入：用作训练数据的航班数据当前候选预测属性集合输出：用于航班延误预测的决策树旅：创建新结点中所有航班数据的属性相同记为返回作为叶子结点，以为类标；为空返回作为叶子结点，标记为中最多的类标计算中每个属性的信息增益率找到最高值的属性；属性为连续性找到该属性的分割阈值；每个长出的新叶子结点叶子结点的子集为空242 系统工程理论与实践第卷分裂为一个新叶子结点，标记为中最多的类标在该叶子结点上执行返回实验分析数据说明及数据预处理以国内某大型机场为目标机场，数据采用机场自年月日至年月日的条到港航班信息，每条航班包括航班日期、始发站、目的站、经停个数、机型、机号、航班任务、航空公司、进出标志、航班属性、计划起降时间及实际起降时间等个属性我们对原始数据进行如下步预处理操作：一、去除航班取消情况原始数据中存在实际到达时间为空的航班，我们认为没有实际到达时间的航班为已取消航班而不做考虑，因而剔除了这些航班数据二、属性选择说明在航班延误预测问题中，我们希望所选参与航班预测的每个属性与航班延误情况相关性越大，预测效果越好原始数据的个属性，我们进行了如下处理最后得到个属性：属性删除：删除原始属性中的冗余属性及无关属性观察原始数据所包含的个属性发现其中包含了不可用的属性，大概分为冗余属性以及无关属性两种冗余属性是指意义重复的属性如本研究只考虑特定机场的到港航班延误情况，所有到港航班数据均为进港航班，因而航班的“进出标志属性冗余，航班的“目的地”属性也为冗余属性无关属性是指经经验判断与航班延误预测无关或关联不大的属性，于某特定机场的到港航班延误问题来说，原始数据中航班在该机场的“计划到达时间”影响较大，而“航班数目”则影响较小（详见的实验分析我们删除类似“航班数目等对预测问题影响较小的属性属性优化：结合航班延误预测情况，对部分属性取值进行了优化如，原始属性“航班计划起降时间”几乎覆盖全天所有时刻取值太多容易造成过度拟合不利于分类，但不同时段的航班延误情况可能有较大差异’如下午时段相比凌晨一般航班较多，较大的流量就更可能造成延误为了充分利用这些知识帮助分类，我们将一天中的小时按每个小时进行分为个时间段，原始数据的“计划到达时间”和“计划起飞时间”则落入相应分段内时间分段及标识见表属性添加：为了尽可能多地考虑影响航班延误预测问题的因素，我们根据经验新添了属性，并设计了相应实验进行验证如，考虑同一时刻到达该机场的航班数目可能对该航班的延误有影响，因而新增了“航班数目”属性三、确定类标属性类标属性即分类目标，在本研究中就是航班的到港延误状况通过原始数据的“实际到达时间”与“计划到达时间”两个属性相减，可以得到航班到港延误的时间这里考虑到机场方面对延误预测的精确度需求’我们将延误程度分为等分别用来表示’表示不延误表示延误数字越大表示延误越严重，如表表“細划起降时间属性分段表延雕度及其細应表“实际到达时间卄划到达时间”延误等级说明小于分钟未延误分钟小时数字越大小时小时表示延误：大于小时程度越高现在我们可以把每条航班抽象为如下个属性其中前个为用于预测的非目标属性，最后一个为类标属性，具体属性说明见表增刊程华，等基于决策树方法的到港航班延误预测问题研究表数据集属性说明表编号属性名属性描述航班月份，由于所用数据是从年月日至年月日的航班故取值为或到的整数航班星期，取值为到的整数始发站取值为国内外个机场的代码航班抵达机场前经停机场的个数取值为、、机型，取值为种不同机型代码，如航班执行的飞行任务如正班、加班、补班、公务、航摄等取值为种航班任务的代码航空公司，取值为个航空公司的代码航班属性取值为种属性代码，如国际航班、国内航班计划抵达时间，取值为已分段的种标识如、等与该航班同一时刻到达该机场的航班数，时间段取为前后分钟延误等级，取值为、、、通过以上的预处理步骤我们最终得到机场的条到港航班数据时间跨度从年月日至年月日，每条航班我们抽象为个属性，其中前个为用于预测的非目标属性最后一个为类标属性，该数据集的统计信息见图所占比例■■■■■■———―――条）条）条）条）延误程度■所占比例图数据集统计信息图实验分析工具和平台数挖工具：处理器：内存：操作系统：旗舰版实验结果及分析数挖工具：实验中我们均取贝叶斯网络（以及朴素贝叶斯为对比方法，在上面得到的数据集上分别进行实验，实验设计如下正确性验证我们采用十字交叉法（进行实验，把数据集（共条数据）分成个不交叉的子集其中包括个条数据的子集和个条数据的子集每次取其中个部分作为测试集其余个部分作为训练集得到分类器，如此重复次训练集和测试集的类标属性都是已知的，由训练集的类标我们学习得到模型在测试阶段中我们假设测试集的类标属性未知而使用模型得到预测值然后通过比较预测值与实际值来判定模型正确率最后的整体正确率是次实验整体正确率的平均值在上述数据集上我们分别用以及三种算法进行了实验，每次实验我们都可以对每一条航班数据得到一个类标属性的预测值下面给出三种算法的运行截图如图所示算法一次运行截图系统工程理论与实践第卷算法一行截图■算法一次运行截图图三种算法的运行截图图方框中的前一列为航班延误程度的实际值后一列为预测值若前后两列相等则预测正确否则预测失败，此时列标记加号由于篇幅原因此处我们只截取了儿条航班数据作出说明接下来给出对条航班数据的整体预测准确率分析对每种算法分别进行十