Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (7): 2124-2128.DOI: 10.11772/j.issn.1001-9081.2017.07.2124

Previous Articles    

Airline predicting algorithm based on improved Markov chain

WANG Zhongqiang, CHEN Jide, PENG Jian, HUANG Feihu, TONG Bo   

  1. College of Computer Science, Sichuan University, Chengdu Sichuan 610065, China
  • Received:2017-01-24 Revised:2017-02-24 Online:2017-07-10 Published:2017-07-18
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (U1333113), the Science and Technology Support Program of Sichuan Province (2014GZ0111).

基于改进马尔可夫链的航线预测算法

王中强, 陈继德, 彭舰, 黄飞虎, 仝博   

  1. 四川大学 计算机学院, 成都 610065
  • 通讯作者: 彭舰
  • 作者简介:王中强(1991-),男,北京人,硕士研究生,主要研究方向:大数据与云计算;陈继德(1990-),男,江苏连云港人,硕士研究生,主要研究方向:大数据与云计算;彭舰(1970-),男,四川成都人,教授,博士,CCF高级会员,主要研究方向:大数据与云计算、无线传感器网络、移动计算;黄飞虎(1990-),男,四川遂宁人,博士研究生,主要研究方向:大数据与云计算;仝博(1989-),男,天津人,博士研究生,主要研究方向:大数据与云计算。
  • 基金资助:
    国家自然科学基金资助项目(U333113);四川省科技支撑计划项目(2014GZ0111)。

Abstract: In the transportation field, analyzing passengers' travel destinations brings a lot of commercial value. However, research on the passengers' travel destinations is difficult because of its uncertainty. In order to solve this problem, in existing studies, entropy is used to measure the uncertainty of human mobility to describe individuals' travel features, and the spatiotemporal correlation of individual trajectories is taken into account simultaneously, which can not achieve the desired accuracy. Therefore, an algorithm for airline prediction based on improved Markov chain was proposed to predict passengers' travel destinations. First, the distance distribution, site distribution and temporal regularity on history records of passengers' travels were analyzed. Then, the dependence of human mobility on historical behavior and current location was analyzed. Finally, the characteristics of passengers' permanent residence and the exploration probability of new airlines were added into the calculation transition matrix, and an algorithm based on improved Markov chain was proposed and realized to predict passengers' next travels. The experimental results show that the average prediction accuracy of the proposed model can reach 66.4%. Applying in the field of customer travel analysis, airline company can benefit from the research to predict passenger travel better and provide personalized travel services.

Key words: airline prediction, travel destination, entropy, Markov chain, individual trajectory

摘要: 在交通领域,研究分析旅客的出行目的地会产生很多商业价值。针对旅客出行目的地的不确定性造成研究困难的问题,现有方法利用熵衡量移动的不确定性来描述个体的出行特性,并同时考虑个体轨迹的时空相关性,并不能达到理想的预测精度,因此,提出了基于改进马尔可夫链的航线预测算法来对旅客的出行目的地进行预测。首先对旅客历史出行的距离分布、地点分布和时间规律特性进行了分析;然后又分析了人类移动对历史行为和当前地点的依赖性;最后将旅客的常住地特性和新航线的探索概率加入到转移矩阵的计算中,提出并实现了改进的马尔可夫链航线预测算法,进而对旅客的下一次出行进行预测。实验结果显示,该模型可以达到66.4%的平均预测精度。研究成果可以应用在航空领域的用户出行分析中,使航空公司更好地了解和预测旅客的出行,提供个性化的出行服务。

关键词: 航线预测, 出行目的地, 熵, 马尔可夫链, 个体轨迹

CLC Number: