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

(四川大学 计算机学院，成都 610065) (*通信作者电子邮箱penguest@163.com)

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

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

(四川大学 计算机学院，成都 610065) (*通信作者电子邮箱penguest@163.com)

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

航线预测；出行目的地；熵；马尔可夫链；个体轨迹

0 引言

目前，电子移动以及传感器设备的发展使得更多的用户行为被记录下来，学者们有机会对更多有价值的数据进行分析和挖掘。比如，移动电话数据，可以获取用户的位置信息，利用这些数据可以预测用户下次出行地点。……