摘要
航班延误一直困扰是国际国内民航业的一个热点问题。近年间我国航空延误日益加重,已经影响到民航业的发展,改善延误状况迫在眉睫。航班延误多发生在繁忙的枢纽机场,枢纽机场又是多数航班的转乘点,是航班链中的关键环节。当航班延误发生在繁忙的枢纽机场时,延误在航班链中的波及将不可避免。减轻繁忙枢纽机场的延误,可以使整条航班链,继而整个民航系统的运行状态得到改善。本文将某繁忙的枢纽机场AIRPORTP作为主要研究对象,对其中的进、离港延误,延误波及进行建模与预测。
本文基于贝叶斯网络的理论,面向枢纽机场和航班链内的航班延误与波及,提出了多种算法与学习方法。
首先,面向繁忙的枢纽机场,本文将贝叶斯网络参数学习算法应用到航班延误的预测领域。针对基于专家经验的网络结构维度过高、运算量过大的问题,且会使每种状态下的样本量不足的问题,提出了两种解决方案:一是独立属性抽取,通过分析各属性间的相关性,分割网络结构。此方案运行速度快,方便处理大数据集;二是精简优化模型,通过回归分析,剪除关联性低的节点,以降低网络的维度,此方案正确率高,速度比方案一慢,适合处理较小的数据集。本文通过分析和建模发现进、离港拥有同样的属性和网络结构,基于方案二建立了延误波及的对称性模型PMofA。
其次,面向航班链中的延误波及问题,本文在利用贝叶斯结构学习算法对进、离港延误进行建模的基础上,使用混合学习方法建立MSP模型。同时还提出了一种改进型的K2结构算法TFK2,TFK2比传统的K2更适合为航班延误的建模,速度更快,准确率更高。继而基于TFK2算法,提出一种能够产生冗余节点的协商结构算法,由该算法生成的网络结构中,经过协商,不同条件下的节点间会存在竞争或冗余两种状态,使网络的预测准确率和速度都得以提高。
再次,基于集成学习理论和TFK2贝叶斯结构算法,本文还提出了一种带有自反馈的航班预测集成学习系统SEFS。该系统中包含有三个子学习器,通过对三个子学习器的训练,可以对航班延误情况进行预测。依据预测的结果,用颜色和概率表示对航班延误进行预警,使预警更具人性化。
最后,应用SEFS系统,以AIRPORTP为例,对其中一定时间段内的延误航班数量进行预测,面向繁忙的枢纽机场发布预警;应用SEFS系统对特定航班的延误时间进行预测,面向航空公司与乘客发布预警。
In domestic and overseas, flight delay is one of the problems that the staffs inindustry devote themselves to research. In recent years, the delays of flights indomestic become more and more serious, and have effected on the developing of thecivil aviation industry. Flight delay status needs to be researched and improvedimmediately. The flight delays are often happened in those busy hub-airports whichare important in flight chains. Many flights turn around in hub-airports. Therefore,when the delay happened in a busy hub-airport, the delay propagation will beinevitable. Relieving the delay status of busy hub-airports will lighten the pressure ofwhole flight chain, even the whole civil aviation system. Therefore, focusing on oneof those busy hub-airports named AIRPORTP, arrival/departure delays and delaypropagation have been discussed in this paper separately.
Orienting to the hub-airports and flight trains, many algorithms and methods areadvanced based on Bayesian Network:
Firstly, orienting to the busy hub-airports, Bayesian Network parameter learningalgorithm is used in the field of flight delay estimation. In order to solve the problemof high-dimension, large-computing-scale in the network constructed by experts’experiments, two methods are raised. One is named Independent Attribute TakingOut,which separates the network based on analyzing of the correlation between allattributes. This method is suit for dealing with huge data set since its speed incalculating is high. The other is named Optimized Model. The nodes with lowcorrelation are eliminated after regressive analyzing. The correct rate of estimatingwith this method is high. This method is suit for dealing with small data set since itsspeed in calculating is slower than the first method stated above. Then the dimensionof model’s structure is reduced. After analyzing and modeling, the same nodes andstructure are discovered in the arrival and departure delays models, therefore asymmetrical model named PMofA is established for the delay propagation based onOptimized Model.
Secondly, orienting to the delay propagation in flight chains, after modelingarrival delay and departure delay separately based on the Bayesian structure learningalgorithm, MSPmodel is established bya Mixed Learning Method. Then an improvedK2 structure learning algorithm named TFK2 is raised. It is proved to be more suitable to model and estimate the flight delays than the traditional K2 algorithm bothin learning speed and correct rate. Based on TFK2, a Negotiating Structure Learningalgorithm is raised. The network’s structure built by this Negotiate Structure Learningincludes redundancy nodes. The nodes change their working states as competition orredundancy in different conditions to further enhance the correct rate and the speed incalculating ulteriorly.
Thirdly, a Self-feedback Ensemble-learning Flight-delay Estimating System(SEFS) is raised based on Ensemble Learning Method and TFK2 algorithm. Thesystem includes three sub-learners. After trained,the system can be used to estimateflight delays. And according to the estimated result of SEFS, the delay of specificflight can be pre-warned with color and probability, to make pre-warning morehumanity.
Finally, pre-warning is issued for a busy hub-airport, based on the estimatednumber of delayed flights during a period time in AIRPORTP by the SEFS System.And pre-warning is issued for air companies and guests, based on the estimated delaytime of specific flights by the SEFS.
引文
[1]国家863重大项目[EB/OL], http://www.atmb.net.cn/863air/jianjie.asp.
[2]Cheslow, M., Analysis of national delay and throughput impacts of a new Denverairport,Transportation Research Record, 1990, 1296: 1~12.
[3]Shaw, S.,Airline Marketing and Management, Pitman, London, 1987
[4]Glockner, G.D., Effects of air traffic congestion delays under several flowmanagement policies, Transportation Research Record, 1993, 1517: 29~35.
[5]Venkatakrishnan, C.S., Barnett, A. and Odoni, A.R. Landing at airport: describingand increasing airport capacity, Transportation Science, 1993, 27(3): 211~227.
[6]Luo, S. and Yu, G., On the airline schedule perturbation problem caused by theground delayprogram,Transportation Science 1997, 31 (4): 298~311.
[7]Rutner, S.M., Mundy, R.A. and Whitaker, J. Alternatives for reducing delays at theUnited States' busiest airport,Transportation Journal Spring, 1997: 18~25.
[8]Ning Xu, George Donohue, Kathryn Blackmond Laskey. Estimation of DelayPropagation in the National Aviation System Using Bayesian Networks. 6thUSA/Europe Air Traffic Management Research and Development Seminar, June2005.
[9]Ning Xu, C.H.Chen, Propagation of Delays in the National Airspace System, the22nd Conference on UncertaintyinArtificial Intelligence, July2006.
[10]The Detailed Policy Assessment Tool (DPAT) User's Manual, MITRE TechnicalReport, MTR 99W00000012, Center for Advanced Aviation System Development,McLean, VA, September, 1999.
[11]Lisa Schaefer and David Millner,Flight Delay Propagation Analysis with theDetailed Policy Assessment Tool,2001 IEEE Systems, Man, and CyberneticsConference.
[12]Paul T. R. Wang, Lisa A. Schaefer, and Leonard A. Wojcik, DPAT Flight DelayModeling and Itinerary Tracking, 1st AIAA Aircraft, Technology, Integration, andOperations Forum,LosAngeles, CAOct, 2001: 16~18.
[13]Paul T. R. Wang, Lisa A. Schaefer, and Leonard A. Wojcik,Digital AvionicsSystems Conference, 2003(DASC'03,The 22nd), 5: B.4-1~5.B.4-9
[14]石丽娜.多等级模糊评价方法在航班延误中的应用.上海工程技术大学学报[J],2006.9,20(3):276~279.
[15]徐肖豪,李雄.航班地面等待模型中的延误成本分析与仿真.南京航空航天大学学报,2006,38(1):115~120.
[16]MA Zhengping, CUI Deguang, CHEN G Peng. Air traffic control commandmonito ring system based on information integration. The 5th USAEurope Air TrafficManagement R&D Seminar. Budapest, Hungary, 2003.
[17]程朋,崔德光,吴澄,一种基于优化的空中交通短期流量管理模型,清华大学学报(自然科学版),2001,41 (45):163~166
[18]许巧莺,钟惠存,黄惠如,航空公司班机误点延滞扩善与控制之研究,运输计划季刊,第三十二卷第三期民国九十二年九月:447~478
[19]胡思继,孙全欣,胡锦云等,区段内列车晚点传播理论的研究,中国铁道科学,1994年02期:41~54
[20]Higgin, A. and Kozan, E., Modeling Train Delays in Urban Network,Transportaiong Science, Vol.32, No.4, 1998: 346~357
[21]刘玉洁,何丕廉,刘春波等,基于贝叶斯网络的航班延误波及研究,计算机工程与应用,2008(17):242-245
[22]Liu, Yujie,Ma, Song,Modeling and estimating for flight delay propagation in areduced Flight Chain based on a mixed learning method,Proceedings - 2008International Symposium on Knowledge Acquisition and Modeling, KAM 2008,2008.12:491~495.
[23]Raiffa,H. and Schlaifer,R. Applied statistical Decision Therory,HarvardUniversity,Boston,1961
[24]张尧庭,陈汉峰,贝叶斯统计推断,科学出版社,1994,27~31
[25]Cooper, G. & Herskovits, E. Determination of the Entropy of a Belief Network isNP-Hard. KSL, June, 1991.
[26]Lucas P.J.F. Expert Knowledge and Its Role in Learning Bayesian Networks inMedicine: An Appraisal. In Quaglini S., Barahona P., Andreassen S. Proceedings ofthe 8th Conference on AI in Medicine in European. Springer, Cascais, Portugal.2001:156-166.
[27]Onisko A., Lucas P.J.F., Druzdzel M.J. Comparison of Rule-Based and BayesianNetwork Approaches in Medical Diagnostic Systems. In Quaglini S., Barahona P,Andreassen S. Proceedings of the 8th Conference on AI in Medicine inEuropean.Springer, Cascais, Portugal. 2001: 283-292.
[28]Neil M., Fenton N., Forey S., etc. Using Bayesian Belief Networks to Predict theReliabilityof MilitaryVehicles. Comput Control Eng. 12(1): 2001.11-20.
[29]Alberola C., Tardon L., Ruiz-Alzola J. Graphical Models for ProblemSolving.Comput Sci Eng. 2(4). 2000: 46-57.
[30]Rodrigues M.A., Liu Y., Bottaci L., etc. Learning and Diagnosis in ManufacturingProcesses - Through an Executable Bayesian Network. In Loganantharaj R., PalmG.Proceedings of the 13th International Conference on Industrial and EngineeringApplications of Artificial Intelligence and Expert Systems. Springer, New Orleans,Louisiana. USA. 2000: 390-395.
[31]Sillanpaa M.J., Corander J. Model Choice in Gene Mapping: What and Why.Trends Genet. 18(6). 2002: 301-307.
[32]Raval A., Ghahramani Z., Wild D.L. ABayesian Network Model for Protein Foldand Remote Homologue Recognition. Bioinformatics. 18(6). 2002: 788-801.
[33]Geman S., Kochanek K. Dynamic Programming and the GraphicalRepresentation of Error-correcting Codes. IEEE Transactions on Information Theory.47(2). 2001: 549-568.
[34]McCabe B. Belief Networks for Engineering Applications. International JournalofTechnologyManagement. 21(3-4). 2001: 257-270.
[35]Giudici P. Bayesian Data Mining with Application to Benchmarking and CreditScoring.Application Stochastic Model Business. 17(1). 2001: 69-81.
[36]Gemela J. Financial Analysis Using Bayesian Networks. Application StochasticModel Business. 17(1). 2001.57-67.
[37]Socher G, Sagerer G., Perona P. Bayesian Reasoning on Qualitative Descriptionsfrom Images and Speech. ImageVision Compution. 18(2). 2000: 155-172.
[38]Pham T.V, Wowing M., Smeulders A.W.M. Face Detection by AggregatedBayesian Network Classifiers. Pattern Recognition Letters. 23(4). 2002: 451-461.
[39]Wooff D.A., Goldstein M., Coolen F.P.A. Bayesian Graphical Models forSoftwareTesting. IEEE Software Engineering. 28(5). 2002. 510-525.
[40]Krause A., Guestrin C. Near-optimal Nonmyopic Value of Information inGraphical Models. In Proceedings of the 21st Conference in Uncertainty in ArtificialIntelligence.AAAI Press. Edinburgh. Scotland. 2005: 324-331.
[41]Heckerman D., wellman M.P.Bayesian Networks. Communieations of the ACM.38(3).1995: 27~30
[42]Pearl J. Causality: Models, Reasoning, and Inference. Cambridge UniversityPress.2000. 1-26.
[43]Callan R.Artificial Intelligence. Palgrave Macmillan. 2003: 76-79.
[44]李小琳,面向智能数据处理的贝叶斯网络研究与应用,学位论文,吉林大学图书馆,吉林大学,2005
[45]张连文,郭海鹏,贝叶斯网引论,第3章:70-74;第八章:184~186
[46]Quackenbush J. Computational Analysis of Microarray data. Nat ReviewsGenetics, 2001, 2: 418~427.
[47]史忠植,高级人工智能(第二版),北京:科学出版社,2006.9: 101~125
[48]刘峰,贝叶斯网络结构学习算法研究,北京邮电大学博士论文,2007.10
[49]Chickering.D.M, Learning Bayesian Networks is NP-complete. In Learning fromData:Artificial Intelligence and Statistics. 1996,Springer Verlag.
[50]Spirtes P. , Glymour C. , Scheines R.Causation , Prediction andSearch(2nd,ed).Springer Verlag. 2000.
[51]Spirtes P.,Meek C, Learning Bayesian Networks with Discrete variablesfromData.In Fayyad U.M.,Uthurusamy R. Proceedings of the First IntemationalConferenee on Knowledge Discovery and DataMining. AAAI Press,Montreal,Canada.1995:294~299.
[52]Cheng J.,Bell D.A.,LiuW.Learning Belief Networks from Data:An InformationTheoryBasedApproaeh.In Golshani F.,Makki K.Proeeedings of the 6th IntemationalConference on Information and Knowledge Management.ACM , LasVegas ,Nevada.1997:325~331.
[53]Marsaristis D. Thrun S. Bayesian Network Induction via Local Neighborhoods.InSolla S.A.,LeenT.K.,Muller K.R. Advances in Neural Information ProcessingSystems 12.MITPress,Denver,Colorado,USA.1999:505~511.
[54]Friedman N. The Bayesian Structural EM Algorithm.In Cooper G.F.,Moral S.Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. MorganKaufimann,Madison,Wisconsin,USA.1998:129~138.
[55]Friedman N.Learning Belief Networks in the Presence of Missing Values andHiddeables.In Fisher D.H.Proeeedings of the 14th International Conference ofMachine Learning.Morgan Kaufinann,Nashville,Tennessee,USA. 1997:125~133.
[56]Myers J.W.,Laskey K.B.,Levitt T.S. Learning Bayesian Networks fromIncomplete Data with Stochastic Search Algorithms. In Laskey K.B.,Prade H.Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence. MorganKaufmann,Stoeklolm,Sweden.1999: 476~485.
[57]Pernkopf,Franz; O'Leary,Paul, Search-and-score structure learning algorithm forBayesian network classifiers, Sixth International Conference on Quality Control byArtificial Vision. Edited by Tobin, Kenneth W., Jr.; Meriaudeau, Fabrice. Proceedingsof the SPIE, Volume 5132, 2003: 231-240.
[58]Cooper GF., Herskovits E. A Bayesian Method for the Induction of ProbabilisticNetworks from Data. Machine Learning. 9. 1992. 309-347.
[59]Cooper G F., Herskovits E. A Bayesian Method for Constructing Bayesian BeliefNetworks from Databases. In Ambrosio B.D., Smets P. Proceedings of the SeventhAnnual Conference on Uncertainty in Artificial Intelligence. Morgan Kaufrnann, LosAngeles, CA, USA. 1991: 86-94
[60]Heckerman D., Geiger D., Chickering D.M. Learning Bayesian Networks: TheCombination of Knowledge and Statistical Data. Machine Learning. 20(3). 1995:197-243.
[61]Mikko Koivisto,ParentAssignment Is Hard for the MDL,AIC, and NMLCosts,Springer Berlin / Heidelberg,2006,Volume 4005/2006.
[62]A.R. Khanteymoori, M.M.Homayounpour and M.B.Menhaj, Bayesian NetworkBased Approach for Data Classification Using Structural Learning, Advances inComputer Science and Engineering,13th International CSI Computer Conference,CSICC 2008 Kish Island, Iran, March 9-11, 2008 Revised Selected Papers.
[63]Friedman N , Goldszmidt M. Discretization of continuous attributes whilelearning bayesian networks [ C]/ / In Proceedings of the Thirteenth InternationalConference on Machine Learning,1996 :157-165.
[64]Daniel Grossman, Pedro Domingos,Learning Bayesian Network Classifers byMaximizing Conditional Likelihood, Proceedings of the 21st International Conferenceon Machine Learning, Banff, Canada, 2004.
[65]Friedman, N. , I. Nachman, D. Pe’er. Learning Bayesian Network Structure fromMassive Datasets: The“Sparse Candidate”Algorithm. In Proceedings of the 15 thAnnual Conference on Uncertainty in Artificial Intelligence, San Francisco, CA.1999:206-215.
[66]Tsamardinos, I., L. E. Brown, C. F. Aliferis. The Max-Min Hill-ClimbingBayesian Network Structure Learning Algorithm. Machine Learning, 2006, 65 (1):31-78.
[67]Liu, Yu-Jie,Ma, Song,Flight delay and delay propagation analysis based onBayesian network,Proceedings - 2008 International Symposium on KnowledgeAcquisition and Modeling, KAM, 2008.12: 318-322.
[68]Netica[EB/OL], http://www.norsys.com/.
[69]Yu-Jie Liu,Wei-Dong Cao,Song Ma,Estimation of Arrival Flight Delay andDelayPropagation in a BusyHub-airport,Fourth International Conference on NaturalComputation, 2008.10: 500~505
[70]Yu-Jie Liu,FanYang,Initial Flight DelayModeling and Estimating Based on anImproved Bayesian Network Structure Learning Algorithm,Proceedings - FifthInternational Conference on Natural Computation, 2009.8
[71]Dienerich T G. Machine learning research four current directions. AI Magazine,1997, 18(4):97-136.
[72]G. Valentini and F. Masulli, "Ensembles of learning machines," in Neural NetsWIRN Vietri-02, Series Lecture Notes in Computer Sciences, M. Marinaro and R.Tagliaferri, Eds.: Springer-Verlag, Heidelberg (Germany), 2002,. Invited Review.
[73]Kearns M, Valiant L Cx Learning Boolean formulae or factoring. AikenComputation Laboratory, Harvard University, Cambridge, MA, Technical Report:TR-1488, 1988
[74]Kearns M, Valiant LG. Crytographic limitation on learning Boolean formulae andfinite antomata. In: Proceedings of the 21 St Annual ACM Sysposium on Theory ofComputing, NewYork, NY:ACM press,1989: 433-444.
[75]Schapire R E. The Strength of Weak Learnability. Machine Learning, 1990, 5(2):197-227.
[76]Freund Y. Boosting a weak algorithm by majority. Inforniation and Cmputation,1995, 121(2):256-285.
[77]Freund Y and Schapire R E. Adecision-theoretic generalization of on-line learninand an Application to boosting. Journal of Computer and System Sciences, 1997,SS(1): 119-139.
[78]Breinmn L. Arcing the Edge. Teehnical Reprot, No.486, Statistics Department,Universityof CaIifomia, Berkeley, 1997.
[79]Quinlan J R. Bagging, Boosting, and C4.5. In: Proc of 14th National ConferenceonArtificial Intelligence. Portland,OR,1996: 725-730.
[80]Schapire R E, Singer Y. Improved Boosting Algorithms Using Confidence-RatedPredictions.Machine Learning, 1999, 37(3): 297-336.
[81]Freund Y. An Adaptive Version of the Boost by Majority lgorithm. MachineLearning,2001, 43(3): 293-318.
[82]Friedman J H, Hastie T, Tibshirani R. Additive Logistic Regression:A StatisticalView of Boosting.Annals of Statistics, 2000, 28(2): 337-374.
[83]Breiman L.Arcing Classifiers.Annals of Statisties, 1998, 26(3):801-849.
[84]Thomas G. Dietterich.”Ensemble learning”, In The Handbook of Brain Theoryand Neural Networks, Second Edition, 2002.
[85]T.G. Dietterich. Machine Learning Research: Four Current Directions. AIMagazine, 1997,18(4): 97-136.
[86]Thomas G. Dietterich. Ensemble learning. In The Handbook of Brain Theory andNeural Networks, Second Edition, 2002.
[87]T.G. Dietterich. Ensemble Methods in Machine Learning. In Multiple ClassierSystems, Cagliari, Italy, 2000.
[88]ShiXin Yu: Feature Selection and Classifier Ensembles: AStudy on HyperspectralRemote Sensing Data (2003) Available athttp://143.129.203.3/visielab/theses/shixin/thesis_yu.pdf
[89]H.S. Seung, M. Opper, and H. Sompolinsky. Query by committee. In Proceedingsof the Fifth Workshop on Computaional Learning Theory, pages 287--294, San Mateo,California, 1992. Morgan Kaufmann.
[90]Kittler, J., Hatef, M., Duin, R. P., and Matas, J. 1998. On Combining Classifiers.IEEETrans. PatternAnal. Mach. Intell. 20, 1998.3: 226-239.
[91]Breiman, L. (1996a), Bagging Predictors, Machine Learning, Vol. 24, No. 2, pp.123-140.
[92]Robert E. Schapire. The Strength of Weak Learnability. Machine Learning,1990.5(2):197-227.
[93]Alexey T., Mykola P., Padraig C.: Sequential Genetic Search for EnsembleFeature Selection. In Proceedings of the Nineteenth International Joint Conference onArtificial Intelligence (IJCAI-05)..
[94]Hiroshi Mamitsuka. "Empirical Evaluation of Ensemble Feature Subset SelectionMethods for Learning from a High-Dimensional Database in Drug Design," bibe,Third IEEE Symposium on BioInformatics and BioEngineering (BIBE'03), 2003:253.
[95]Xu, L., et al, Methods of Combining Multiple Classifiers and Their Applicationsto Handwriting Recognition, IEEE Transactions on Systems, Man and Cybernetics(1992),May/June.
[96]Alan Fern and Robert Givan. Online Ensemble Learning: An Empirical Study. InProceedings of the Seventeenth International Conference on Machine Learning, 2000.
[97]Tsymbal, A., Puuronen, S.: Bagging and Boosting with Dynamic Integration ofClassifiers, Principles of Data Mining and Knowledge Discovery, Proc. PKDD 2000.
[98]LIBSVM[EB/OL], http://www.csie.ntu.edu.tw/~cjlin/libsvm/.
[99]V N Vapnik, The Nature of Statistical Learning Theory, New York: SpringerVerlag, 1995.
[100]Bernhard Scholkope , Alex Smola. Learning with Kernels:Support VectorMachines, Regularization, Optimizati on and Beyond.Mit Press, Cambridge, MA,2002.
[101]马正平,崔德光,机场航班延误优化模型,清华大学学报(自然科学版)2004,44(4): 474~477.