目前，电子移动以及传感器设备的发展使得更多的用户行为被记录下来，学者们有机会对更多有价值的数据进行分析和挖掘。比如，移动电话数据，可以获取用户的位置信息，利用这些数据可以预测用户下次出行地点。预测用户出行可以产生很多商业价值，因此得到了企业和研究机构的广泛关注。现在越来越多的人选择乘坐飞机出行，航空公司收集了大量的航空出行数据。但是如何从海量的出行数据中挖掘旅客出行特性是一个值得研究的问题。
很多研究者在出行数据中提出了研究模型。文献[1]发现人类移动轨迹具有高度的时空规律性，文中提到每个个体返回高频率出行地点的概率很大，这表明对旅客位置的预测是可能的。尽管很多预测算法与文献[2]和文献[3]不同，但主要还是利用当前或者最近的位置。文献[4]利用用户当前路径和兴趣点位置预测其下一次的兴趣点位置。文献[5]考虑用户最近的位置信息预测用户兴趣点。文献[6-9]利用多重排序马尔可夫模型对位置进行预测，预测准确性得到了提高，但并没有解决预测模型的阶数问题。文献[10]中，通过大量的Wi-Fi(Wireless-Fidelity)信息，获取到用户的位置，然后利用4种不同的预测算法对模型进行验证。从结果来看，作者提出比马尔可夫模型更复杂的方法对预测精度其实没有太多贡献。文献[11]通过分析3种不同的信息熵，发现人类移动可预测性可以达到93%。但是总体来说，当前的研究具有如下三点不足：1) 利用移动手机，GPS(Global Positioning System)系统可以记录人类移动，但是这只是表面属性，用户航线属于空间属性。2) 由于航空网络与通信网络具有本质的差别，因此传统的预测算法并不适合航线预测。3) 下一次航线对最近的航班记录有很强的依赖性，现有的算法没有考虑这个因素。
本文利用历史的航线数据提出了一个新的预测方法来预测旅客下一次出行所乘坐的航线。通过真实的航空数据集分析了旅客航线分布，出行次数与不同航线的关系等，随后本文提出了一个基于改进马尔可夫链的航线预测算法，实验结果显示该模型与其他方法相比文献[12]具有很好的预测精度。
本文的主要创新点有：1) 利用数据集实证了旅客下一次航线的可预测性；2) 对航空旅客出行特性进行了分析；3) 提出了改进的马尔可夫航线预测算法(Improved Markov Chain Airline Predicting Algorithm, IMCAPA)。
1 预测理论分析理论上预测的最优值(Πmax)由人的轨迹(频率、位置访问的序列等)的熵来决定。Πmax可以通过计算Fano不等式的限制性情况来获得(利用噪声信息通道中信息减少的关系)。根据文献[11]可以得到如下关系：
1) 随机熵Srand=lb N，通过假设每个用户的下一次出行在Ni个不同位置中符合均匀分布来对下次出行进行预测。
2) 不确定熵
3) 真实熵
给定个体i的熵，Fano不等式给出了i的可预测性的上限，即最佳可能的预测算法可以实现的精度[13]：
| $ \begin{array}{l} S = {S_f}\left( {{\mathit{\mathit{\Pi}} _{\max }}} \right) = - [{\mathit{\mathit{\Pi}} _{\max }} \times {\mathop{\rm l}\nolimits} {\rm{b}}{\mathit{\Pi} _{\max }} + \left( {1-{\mathit{\Pi} _{\max }}} \right) \times \\ {\mathop{\rm l}\nolimits} {\rm{b}}\left( {1-{\mathit{\Pi} _{\max }}} \right)] + \left( {1 - {\mathit{\Pi} _{\max }}} \right) \times {\mathop{\rm l}\nolimits} {\rm{b}}(N - 1) \le {S_F}(\mathit{\Pi} ) \end{array} $ | (1) |
其中：Πmax表示预测的最大值，SF是Fano函数。如图 1所示，Πmaxreal≥Πmaxunc≥Πmaxrand。这3个可预测性测量之间的关系，使本研究可以通过研究空间分布和时间相关性来提高个人轨迹的预测能力。
|
图 1 可预测性 Figure 1 Predictability |
本研究中的航空数据是从中国某航空公司获得的，包含从2014年1月8日至2014年12月30日的全年旅客出行记录。然而由于大部分乘客在一年内只有很少的飞行记录，所以数据非常稀疏，本文将出行频率最高的前10000个用户过滤出来，这些旅客在一年内至少有48次飞行记录。每条记录主要包括出发机场、到达机场、出发时间等。
本文通过乘客的出发机场和到达机场来获取旅客的出行距离，并利用出行距离，航迹和旅行次数来分析乘客的移动特性。图 2为旅客出行距离分布，其满足对数正态分布。其中86.13%出行距离在500和2000km之间。旅行长度在1000km左右的概率最大，而短距离旅行或很长距离旅行的概率较小。
|
图 2 出行距离的分布 Figure 2 Distribution of trip distance |
从数据中还发现一些出行活跃的乘客经常在少数地点活动。然而，有些乘客的出行地点却很分散并没有经常活动的地点。图 3中的每个节点是乘客所访问的机场，每个节点中的概率值的大小对应于乘客往返该机场次数的百分比，概率值越大表明往返该机场次数越多。从图 3可知该乘客经常在一两个特定地方活动，但偶尔也会飞行到其他的城市。
|
图 3 N=24旅客出行分布 Figure 3 Travel destination distribution for traveler N=24 |
为了更好地了解时间这个潜在影响因素，本文统计了每个机场每天在不同时间段的吞吐量。把每天分为4个阶段，在白天(06：00—12：00, 12：00—18：00)，吞吐量很大，12：00—18：00的吞吐量通常大于06：00—12：00，00:00—06：00的吞吐量最小。这符合人的作息规律，结果如图 4所示。
|
图 4 出行时间规律 Figure 4 Travel time characteristics |
在马尔可夫链中，个体在Li位置之间的移动是具有有限记忆的过程，该位置将被访问的概率取决于在前n个访问位置, Xit=xt, Xit-1=xt-1, …, Xit-n+1=xt-n+1，即：
| $ \begin{array}{l} P(X_i^{t + 1} = {x^{t + 1}}|X_i^t = {x^t}, X_i^{t - 1} = {x^{t - 1}}, ..., X_i^1 = {x^1}) = \\ P(X_i^{t + 1} = {x^{t + 1}}|X_i^t = {x^t}, X_i^{t - 1} = {x^{t - 1}}, ..., X_i^{t - n + 1} = {x^{t - n + 1}}) \end{array} $ | (2) |
其中Xit表示个体i的位置的随机变量。然后通过转移矩阵确定预测目的地位置，使概率最大化：
| $ \mathop {\max }\limits_{k = 1}^{{L_i}} P(X_i^{t + 1} = {x^{t + 1}}|X_i^t = {x^t}, X_i^{t - 1} = {x^{t - 1}}, ..., X_i^{t - n + 1} = {x^{t - n + 1}}) $ | (3) |
本节介绍了预测理论值，为了验证马尔可夫链能否适用于航空旅客航线预测，本文利用马尔可夫链对航线进行预测。结果显示该方法只能达到25%的预测精度。由于马尔可夫链考虑的是历史记录，其预测结果的范围只会出现在历史记录中。然而旅客出行不会只考虑以前去过的地方，还会探索新的地方。所以仅利用马尔可夫链对旅客航线进行预测不能解决旅客探索新航线的问题。
3.2 IMCAPA算法在本文中实现了一个基于改进马尔可夫链的算法(Improved Markov Chain Airline Predicting Algorithm, IMCAPA)，以根据历史轨迹中最常访问的位置来预测下一个位置：
| $ P({x^{{\rm{pre}}}}) = \mathop {\max }\limits_{k = 1}^{{L_i}} ({P_k}|X_i^t = {x^t}, X_i^{t - 1} = {x^{t - 1}}, ..., X_i^1 = {x^{\rm{1}}}) $ | (4) |
其中Pk是旅客在不同位置之间的概率。
表 1为某旅客(简称为Jack)的转移矩阵。根据这个转移矩阵可知，如果Jack在机场3，则根据转移矩阵，他选择机场2的概率是100%，但在真实的数据集，他从机场3到机场2的次数为1，这可能是偶然的。如果当前在机场2，如果选择最大值的话，那么他将去机场3，可能的次数是4；同时，他可能去机场4的次数是3，它非常接近去机场3的次数。所有选择机场3与选择机场4相比是偶然的。
|
表 1 Jack的飞行转移矩阵 Table 1 Jack's flight transition matrix |
那么如何根据转移矩阵预测下一个出行机场呢？本文对马尔可夫链进行改进，通过设置一个在最大值和第二大值之间的阈值δ来解决这个问题。如果两个值之间的差大于δ，则认为乘客的下一个机场等于转移矩阵的最大值。当小于δ时，则根据旅客出发机场和到达机场采取不同的方法。根据旅客出发机场和到达机场的情况可以分成2个不同条件：1) 当前出发机场不是常住地或当前到达机场不是常住地；2) 当前出发机场是常住地。
根据这两种不同的条件，当小于给定值时算法框架如下：
| $ f({x_{k + 1}} = j|{x_k} = i) = \left\{ {\begin{array}{*{20}{c}} {算法1,}\\ {算法2,} \end{array}} \right.\begin{array}{*{20}{c}} {条件1}\\ {条件2} \end{array} $ | (5) |
算法1 当前出发机场不是常住地或当前到达的机场不是常住地，通过分析数据可知，乘客回常住地或返回出发机场。计算转移矩阵的两个最大值之间的差。如果大于δ，则认为乘客的下一航班的到达机场是有最大值的机场。如果转移矩阵最大值对应的机场是常住地或前一次出发机场，则选择最大概率的那个值；否则，其下一次出行目的地为常住地。伪代码如下。
输入：旅客转移矩阵M，阈值δ，当前出发机场r；
输出：到达机场d。
1) A ←M中第r行值最大的机场，值为val1, B ←M中第r行值第二大的机场, 值为val2
2) if |val1-val2|>δ then
3) d ←A
4) else then
5) if机场A是常住地或者上一次出行的目的机场then
6) d ←A
7) else then
8) d ←常住地机场
9) end if
10) end if
算法2 当前出发机场是常住地，本文认为他即将开始的出行要么去以前去过的历史城市，要么探索新航线。
根据贝叶斯理论，基于条件独立假设，可以预测乘客将选择历史航线或选择新的航线。用ck=0表示乘客将选择历史航线，ck=1表示乘客将选择新航线。公式如式(6)：
| $ y = \arg {\rm{ }}\mathop {\max }\limits_{{c_k}} \prod\limits_j {P({X^j} = {x^j}|Y = {c_k})} $ | (6) |
如果是探索新航线，利用群集特性选择一条新航线。定义基于距离的概率公式：
| $ {P_D}({x_{k + 1}} = j|{x_k} = i) = \sum\limits_{u = 1}^m {\sum\limits_{k = 1}^m {{P_u}(d({x_k}, {x_{k + 1}}) = l)} } $ | (7) |
其中Pu(d(xk, xk+1)=l)是乘客u从机场xk到机场xk+1距离为l的概率。
如果是返回历史航线，乘客的特征向量由历史航线的长度、不同航线的数量、两者间百分比，及其探索新航线的数量组成。下一航线的条件分布是位置和时间的混合分布：
| $ \begin{array}{l} P( \cdot ){\rm{ = [}}\alpha \times Att{\rm{ + (1-}}\alpha {\rm{)}} \times F(X(k + 1)|X(k), {W_s}(k), \\ {D_s}(k))]/T_i^k\_short \end{array} $ | (8) |
| $ \begin{array}{l} F(X(k + 1)|X(k), {W_s}(k), {D_s}(k)){\rm{ = }}F(X(k + 1)|\\ X(k)){\rm{ + }}F(X(k + 1)|{W_s}(k), {D_s}(k)) \end{array} $ | (9) |
| $ \begin{array}{l} F(X(k + 1)|{W_s}(k), {D_s}(k)){\rm{ = }}\sum\limits_{{W_s}} {\sum\limits_{{D_s}} {F(X(k + 1)|} } \\ {W_s}(k), {D_s}(k)) \end{array} $ | (10) |
| $ T_i^k - short = \min (abs|Loc\_cur - Loc\_{x_k}|) $ | (11) |
其中：α∈[0, 1]是比例参数；Att是代表城市的吸引力，表示为
输入：旅客航线历史数据，阈值δ，当前出发机场r。
输出：到达机场d。
1) 对每个机场计算T_short
2) 根据Ds、Ws计算转移矩阵M
3) P1 ←旅客选择历史航线的概率，P2 ←旅客选择新机场的概率
4) if P1 > P2 then
5) 对每个历史机场利用式(8) 计算选择概率
6) else then
7) 对每个新机场利用式(7) 计算选择概率
8) end if
4 实验与分析 4.1 实验数据本文获取了国内某航空公司的2014年全年航班记录，其中包括机场、时间、航班号相关信息，删除临时航线以及信息不全的数据后，共436869231条记录。
4.2 预测精度分析本文提出了IMCAPA算法，并通过设置参数的值来调整影响因子的加权系数。
训练数据是乘客的历史航线记录，预测其最后5次航线。在预测下一次航线的时候也把前一次的结果加入训练集。对比算法有二阶马尔可夫链MC(2)[13]、一阶马尔可夫链MC(1)(Markov-Chain)[14]、最常访问的位(Most-Visited-Location, MVL)[15]、贝叶斯网络(Bayesian-Network, BN)[16]。评价指标为预测精度(Accuracy)和召回率(Recall_return)，计算公式如下：
| $ Accuracy = accurate\_n/total\_n $ | (12) |
| $ Recall\_return = accurate\_return/total\_return $ | (13) |
其中：accuate_n和accurate_return表示预测某个航线预测正确的个数，total_n表示预测总数，total_return表示某个航线应该被预测正确的个数。
图 5是本文算法预测精度与其他算法的比较结果，可以看出本文IMCAPA算法的准确性高于其他算法。BN的精度高于MC(1)，MC(1) 的精度高于MC(2)。精度随着预测航线数量的增加而减少，平均精确度为66.4%，当航线数量为40时最低，当数目超过50时动态地改变。其中航线数为2时，精度的最大值可达到95%。对于那些非活跃乘客预测精度相对较高。相反，当乘客活跃时预测精度较低。而当乘客过于活跃时，精度随机地变化。这符合现实情况。
|
图 5 预测精度实验结果 Figure 5 Experimental result of prediction accuracy |
图 6和图 7分别是返回历史航线和新航线预测的召回率结果图。返回历史航线的召回率如图 6所示。当不同航线的数量低于17个时，召回率高于55%。当不同航线的数量等于4时，召回率达到最大值是67.33%，整体召回率大于50%，并且预测精度相对稳定，大部分的召回率都在18%到48%之间。当这个值大于48%时，召回率将动态变化，最大值为70.67%。对于不活跃的乘客，他们经常在某些航线飞行，很少探索新航线。但是活跃的乘客，探索新航线的可能性很高。图 7显示了探索新航线的召回程度。由于其他算法无法预测新航线，所以他们对探索新航线的召回率为0。而本文算法探索新航线的召回率从0变为24.37%，当不同航线数量值为60时，最大召回值为70.76%。这表明活跃的乘客经常探索新航线。
|
图 6 出行返回的召回率 Figure 6 Recall of returning |
|
图 7 探索新航线召回率 Figure 7 Recall of exploring new airlines |
下面分析不同实验环境参数对实验效果的影响。图 8为不同预测长度(连续预测旅客未来多次出行的次数)对实验结果的影响。可以发现，当预测长度范围从2到5变化时，预测精度会随之下降。当长度为2时，最大值为71.77%。当预测长度较小时，具有较多的训练数据，所以精度会随之提高。图 9为不同数据集对实验效果的影响。本文从10万名匿名乘客中，分别随机选择10，100，500，1000，3000，5000名旅客，并重复5次。实验结果发现，当数据集中乘客数量为10时，预测的精度变化很大，最大值达到了72.67%。由于旅客出行具有较强的随机性，所以精度也会相应地波动。其中小样本对预测有更大的影响，随着样本数量的增加，波动变小。
|
图 8 预测长度对预测精度的影响 Figure 8 Effect of predicted length on prediction accuracy |
|
图 9 不同的数据集对预测精度的影响 Figure 9 Effect of different dataset on prediction accuracy |
本文先利用3种不同的熵给出了数据集可预测性的理论值。通过计算马尔可夫链对航空旅客出行预测的精度，发现其精度只能到达25%。本文通过分析10000多名旅客的出行模式，提出了改进的马尔可夫链航线预测算法。对比实验中，MC和BN模型方法所获得的预测精度远小于理论值，并且二阶马尔可夫链模型的预测精度并没有比一阶马尔可夫模型好，导致这样的结果可能是受到了旅客出行特征的影响。本文的IMCAPA算法的预测精度比MC和BN有较大提升，并且还可以预测旅客下一次出行的航线。
| [1] | GONZALEZ M C, HIDALGO C A, BARABASI A L. Understanding individual human mobility patterns[J]. Nature, 2008, 453(7196): 779-82. DOI:10.1038/nature06958 |
| [2] | ASAHARA A, MARUYAMA K, SATO A, et al. Pedestrian-movement prediction based on mixed Markov-chain model[C]//GIS'11:Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York:ACM, 2011:25-33. |
| [3] | ASHBROOK D, SATRNER T. Learning significant locations and predicting user movement with GPS[C]//ISWC 2002:Proceedings of the 2002 International Symposium on Wearable Computers. Piscataway, NJ:IEEE, 2002:101-108. |
| [4] | SIMMONS R, BROWNING B, ZHANG Y, et al. Learning to predict driver route and destination intent[C]//ITSC'06:Proceedings of the 2006 IEEE Intelligent Transportation Systems Conference. Piscataway, NJ:IEEE, 2006:127-132. |
| [5] | KRUMM J. A Markov model for driver turn prediction[C]//Society of Automotive Engineers (SAE) 2008 World Congress. Detroit:[s.n.], 2008:1-25. |
| [6] | GAMBS S, KILLIJIAN M O, DEL PRADO CORTEZ M N. Show me how you move and I will tell you who you are[C]//SPRINGL'10:Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS. New York:ACM, 2010:34-41. |
| [7] | GAMBS S, KILLIJIAN M O, DEL PRADO CORTEZ M N. Next place prediction using mobility Markov chains[C]//MPM'12:Proceedings of the First Workshop on Measurement, Privacy, and Mobility. New York:ACM, 2012:Article No. 3. |
| [8] | KRUMM J, HORVITZ E. Predestination:inferring destinations from partial trajectories[C]//UbiComp 2006:Proceedings of the 8th International Conference on Ubiquitous Computing. Berlin:Springer, 2006:243-260. |
| [9] | MEYERSON A, WILLIAMS R. On the complexity of optimal K-anonymity[C]//PODS'04:Proceedings of the Twenty-Third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York:ACM, 2004:223-228. |
| [10] | SONG L, KOTZ D, JAIN R, et al. Evaluating next-cell predictors with extensive Wi-Fi mobility data[J]. IEEE Transactions on Mobile Computing, 2007, 5(12): 1633-1649. |
| [11] | SONG C M, QU Z H, BLUMM N, et al. Limits of predictability in human mobility, science[J]. Science, 2010, 327(5968): 1018-1021. DOI:10.1126/science.1177170 |
| [12] | LU X, WETTER E, BHARTI N, et al. Approaching the limit of predictability in human mobility[J]. Scientific Reports, 2013, 3(10): 2923. |
| [13] | 孙永雄, 申晨, 黄丽平, 等. 基于二阶马尔可夫模型的模糊时间序列预测[J]. 计算机工程与应用, 2015, 51(6): 120-123. (SUN Y X, SHEN C, HUANG L P, et al. Second-order Markov model based fuzzy time series prediction[J]. Computer Engineering and Applications, 2015, 51(6): 120-123.) |
| [14] | 黄志成. 基于一阶马尔可夫链的实验数据序列分类模型[J]. 计算机系统应用, 2014, 23(5): 227-230. (HUANG Z C. Sequence classifying model of experimental data based on first order Markov chain[J]. Computer Systems and Applications, 2014, 23(5): 227-230.) |
| [15] | SRIVASTAVA S, AHUJA S, MITTAL A. Determining Most Visited Locations Based on Temporal Grouping of GPS Data[M]. Berlin: Springer, 2012: 63-72. |
| [16] | 王岩韬, 李蕊, 卢飞, 等. 基于运行数据的航班运行关键风险因素推断[J]. 交通运输系统工程与信息, 2016, 16(1): 182-188. (WANG Y T, LI R, LU F, et al. Flight operation key risk factors inference based on operation data[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(1): 182-188.) |