基于改進馬爾可夫鏈的航線預測算法

王中強，陳繼德，彭 艦，黃飛虎，仝 博

(四川大學 計算機學院，成都 610065) (*通信作者電子郵箱penguest@163.com)

基于改進馬爾可夫鏈的航線預測算法

王中強，陳繼德，彭 艦*，黃飛虎，仝 博

(四川大學 計算機學院，成都 610065) (*通信作者電子郵箱penguest@163.com)

在交通領域，研究分析旅客的出行目的地會產(chǎn)生很多商業(yè)價值。針對旅客出行目的地的不確定性造成研究困難的問題，現(xiàn)有方法利用熵衡量移動的不確定性來描述個體的出行特性，并同時考慮個體軌跡的時空相關性，并不能達到理想的預測精度，因此，提出了基于改進馬爾可夫鏈的航線預測算法來對旅客的出行目的地進行預測。首先對旅客歷史出行的距離分布、地點分布和時間規(guī)律特性進行了分析；然后又分析了人類移動對歷史行為和當前地點的依賴性；最后將旅客的常住地特性和新航線的探索概率加入到轉移矩陣的計算中，提出并實現(xiàn)了改進的馬爾可夫鏈航線預測算法，進而對旅客的下一次出行進行預測。實驗結果顯示，該模型可以達到66.4%的平均預測精度。研究成果可以應用在航空領域的用戶出行分析中，使航空公司更好地了解和預測旅客的出行，提供個性化的出行服務。

航線預測；出行目的地；熵；馬爾可夫鏈；個體軌跡

0 引言

目前，電子移動以及傳感器設備的發(fā)展使得更多的用戶行為被記錄下來，學者們有機會對更多有價值的數(shù)據(jù)進行分析和挖掘。比如，移動電話數(shù)據(jù)，可以獲取用戶的位置信息，利用這些數(shù)據(jù)可以預測用戶下次出行地點。預測用戶出行可以產(chǎn)生很多商業(yè)價值，因此得到了企業(yè)和研究機構的廣泛關注?，F(xiàn)在越來越多的人選擇乘坐飛機出行，航空公司收集了大量的航空出行數(shù)據(jù)。但是如何從海量的出行數(shù)據(jù)中挖掘旅客出行特性是一個值得研究的問題。

很多研究者在出行數(shù)據(jù)中提出了研究模型。文獻[1]發(fā)現(xiàn)人類移動軌跡具有高度的時空規(guī)律性，文中提到每個個體返回高頻率出行地點的概率很大，這表明對旅客位置的預測是可能的。盡管很多預測算法與文獻[2]和文獻[3]不同，但主要還是利用當前或者最近的位置。文獻[4]利用用戶當前路徑和興趣點位置預測其下一次的興趣點位置。文獻[5]考慮用戶最近的位置信息預測用戶興趣點。文獻[6-9]利用多重排序馬爾可夫模型對位置進行預測，預測準確性得到了提高，但并沒有解決預測模型的階數(shù)問題。文獻[10]中，通過大量的Wi-Fi(Wireless-Fidelity)信息，獲取到用戶的位置，然后利用4種不同的預測算法對模型進行驗證。從結果來看，作者提出比馬爾可夫模型更復雜的方法對預測精度其實沒有太多貢獻。文獻[11]通過分析3種不同的信息熵，發(fā)現(xiàn)人類移動可預測性可以達到93%。但是總體來說，當前的研究具有如下三點不足：1)利用移動手機，GPS(Global Positioning System)系統(tǒng)可以記錄人類移動，但是這只是表面屬性，用戶航線屬于空間屬性。2)由于航空網(wǎng)絡與通信網(wǎng)絡具有本質(zhì)的差別，因此傳統(tǒng)的預測算法并不適合航線預測。3)下一次航線對最近的航班記錄有很強的依賴性，現(xiàn)有的算法沒有考慮這個因素。

本文利用歷史的航線數(shù)據(jù)提出了一個新的預測方法來預測旅客下一次出行所乘坐的航線。通過真實的航空數(shù)據(jù)集分析了旅客航線分布，出行次數(shù)與不同航線的關系等，隨后本文提出了一個基于改進馬爾可夫鏈的航線預測算法，實驗結果顯示該模型與其他方法相比文獻[12]具有很好的預測精度。

本文的主要創(chuàng)新點有：1)利用數(shù)據(jù)集實證了旅客下一次航線的可預測性；2)對航空旅客出行特性進行了分析；3)提出了改進的馬爾可夫航線預測算法(Improved Markov Chain Airline Predicting Algorithm, IMCAPA)。

1 預測理論分析

理論上預測的最優(yōu)值(Πmax)由人的軌跡(頻率、位置訪問的序列等)的熵來決定。Πmax可以通過計算Fano不等式的限制性情況來獲得(利用噪聲信息通道中信息減少的關系)。根據(jù)文獻[11]可以得到如下關系：

1)隨機熵Srand=lbN，通過假設每個用戶的下一次出行在Ni個不同位置中符合均勻分布來對下次出行進行預測。

給定個體i的熵，F(xiàn)ano不等式給出了i的可預測性的上限，即最佳可能的預測算法可以實現(xiàn)的精度[13]：

S=Sf(Πmax)=-[Πmax×lbΠmax+(1-Πmax)× lb (1-Πmax)]+(1-Πmax)×lb (N-1)≤SF(Π)

(1)

圖1 可預測性

2 旅客移動特性分析

本研究中的航空數(shù)據(jù)是從中國某航空公司獲得的，包含從2014年1月8日至2014年12月30日的全年旅客出行記錄。然而由于大部分乘客在一年內(nèi)只有很少的飛行記錄，所以數(shù)據(jù)非常稀疏，本文將出行頻率最高的前10 000個用戶過濾出來，這些旅客在一年內(nèi)至少有48次飛行記錄。每條記錄主要包括出發(fā)機場、到達機場、出發(fā)時間等。

本文通過乘客的出發(fā)機場和到達機場來獲取旅客的出行距離，并利用出行距離，航跡和旅行次數(shù)來分析乘客的移動特性。圖2為旅客出行距離分布，其滿足對數(shù)正態(tài)分布。其中86.13%出行距離在500和2 000 km之間。旅行長度在1 000 km左右的概率最大，而短距離旅行或很長距離旅行的概率較小。

圖2 出行距離的分布

從數(shù)據(jù)中還發(fā)現(xiàn)一些出行活躍的乘客經(jīng)常在少數(shù)地點活動。然而，有些乘客的出行地點卻很分散并沒有經(jīng)?；顒拥牡攸c。圖3中的每個節(jié)點是乘客所訪問的機場，每個節(jié)點中的概率值的大小對應于乘客往返該機場次數(shù)的百分比，概率值越大表明往返該機場次數(shù)越多。從圖3可知該乘客經(jīng)常在一兩個特定地方活動，但偶爾也會飛行到其他的城市。

圖3 N=24旅客出行分布

為了更好地了解時間這個潛在影響因素，本文統(tǒng)計了每個機場每天在不同時間段的吞吐量。把每天分為4個階段，在白天(06：00—12：00,12：00—18：00)，吞吐量很大，12：00—18：00的吞吐量通常大于06：00—12：00，00:00—06：00的吞吐量最小。這符合人的作息規(guī)律，結果如圖4所示。

3 基于改進馬爾可夫鏈的航線預測算法

3.1 馬爾可夫鏈

(2)

(3)

本節(jié)介紹了預測理論值，為了驗證馬爾可夫鏈能否適用于航空旅客航線預測，本文利用馬爾可夫鏈對航線進行預測。結果顯示該方法只能達到25%的預測精度。由于馬爾可夫鏈考慮的是歷史記錄，其預測結果的范圍只會出現(xiàn)在歷史記錄中。然而旅客出行不會只考慮以前去過的地方，還會探索新的地方。所以僅利用馬爾可夫鏈對旅客航線進行預測不能解決旅客探索新航線的問題。

圖4 出行時間規(guī)律

3.2 IMCAPA算法

在本文中實現(xiàn)了一個基于改進馬爾可夫鏈的算法(Improved Markov Chain Airline Predicting Algorithm, IMCAPA)，以根據(jù)歷史軌跡中最常訪問的位置來預測下一個位置：

(4)

其中Pk是旅客在不同位置之間的概率。

表1為某旅客(簡稱為Jack)的轉移矩陣。根據(jù)這個轉移矩陣可知，如果Jack在機場3，則根據(jù)轉移矩陣，他選擇機場2的概率是100%，但在真實的數(shù)據(jù)集，他從機場3到機場2的次數(shù)為1，這可能是偶然的。如果當前在機場2，如果選擇最大值的話，那么他將去機場3，可能的次數(shù)是4；同時，他可能去機場4的次數(shù)是3，它非常接近去機場3的次數(shù)。所有選擇機場3與選擇機場4相比是偶然的。

表1 Jack的飛行轉移矩陣

那么如何根據(jù)轉移矩陣預測下一個出行機場呢？本文對馬爾可夫鏈進行改進，通過設置一個在最大值和第二大值之間的閾值δ來解決這個問題。如果兩個值之間的差大于δ，則認為乘客的下一個機場等于轉移矩陣的最大值。當小于δ時，則根據(jù)旅客出發(fā)機場和到達機場采取不同的方法。根據(jù)旅客出發(fā)機場和到達機場的情況可以分成2個不同條件：1)當前出發(fā)機場不是常住地或當前到達機場不是常住地；2)當前出發(fā)機場是常住地。

根據(jù)這兩種不同的條件，當小于給定值時算法框架如下：

(5)

算法1 當前出發(fā)機場不是常住地或當前到達的機場不是常住地，通過分析數(shù)據(jù)可知，乘客回常住地或返回出發(fā)機場。計算轉移矩陣的兩個最大值之間的差。如果大于δ，則認為乘客的下一航班的到達機場是有最大值的機場。如果轉移矩陣最大值對應的機場是常住地或前一次出發(fā)機場，則選擇最大概率的那個值；否則，其下一次出行目的地為常住地。偽代碼如下。

輸入：旅客轉移矩陣M，閾值δ，當前出發(fā)機場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 當前出發(fā)機場是常住地，本文認為他即將開始的出行要么去以前去過的歷史城市，要么探索新航線。

根據(jù)貝葉斯理論，基于條件獨立假設，可以預測乘客將選擇歷史航線或選擇新的航線。用ck=0表示乘客將選擇歷史航線，ck=1表示乘客將選擇新航線。公式如式(6)：

(6)

如果是探索新航線，利用群集特性選擇一條新航線。定義基于距離的概率公式：

(7)

其中Pu(d(xk,xk+1)=l)是乘客u從機場xk到機場xk+1距離為l的概率。

如果是返回歷史航線，乘客的特征向量由歷史航線的長度、不同航線的數(shù)量、兩者間百分比，及其探索新航線的數(shù)量組成。下一航線的條件分布是位置和時間的混合分布：

(8)

F(X(k+1)|X(k),Ws(k),Ds(k))=F(X(k+1)|X(k))+F(X(k+1)|Ws(k),Ds(k))

(9)

(10)

(11)

輸入：旅客航線歷史數(shù)據(jù)，閾值δ，當前出發(fā)機場r。 輸出：到達機場d。

1)

對每個機場計算T_short

2)

根據(jù)Ds、Ws計算轉移矩陣M

3)

P1←旅客選擇歷史航線的概率，P2←旅客選擇新機場的概率

4)

ifP1>P2then

5)

對每個歷史機場利用式(8)計算選擇概率

6)

else then

7)

對每個新機場利用式(7)計算選擇概率

8)

end if

4 實驗與分析

4.1 實驗數(shù)據(jù)

本文獲取了國內(nèi)某航空公司的2014年全年航班記錄，其中包括機場、時間、航班號相關信息，刪除臨時航線以及信息不全的數(shù)據(jù)后，共436 869 231條記錄。

4.2 預測精度分析

本文提出了IMCAPA算法，并通過設置參數(shù)的值來調(diào)整影響因子的加權系數(shù)。訓練數(shù)據(jù)是乘客的歷史航線記錄，預測其最后5次航線。在預測下一次航線的時候也把前一次的結果加入訓練集。對比算法有二階馬爾可夫鏈MC(2)[13]、一階馬爾可夫鏈MC(1)(Markov-Chain)[14]、最常訪問的位(Most-Visited-Location, MVL)[15]、貝葉斯網(wǎng)絡(Bayesian-Network, BN)[16]。評價指標為預測精度(Accuracy)和召回率(Recall_return)，計算公式如下：

Accuracy=accurate_n/total_n

(12)

Recall_return=accurate_return/total_return

(13)

其中：accuate_n和accurate_return表示預測某個航線預測正確的個數(shù)，total_n表示預測總數(shù)，total_return表示某個航線應該被預測正確的個數(shù)。

圖5是本文算法預測精度與其他算法的比較結果，可以看出本文IMCAPA算法的準確性高于其他算法。BN的精度高于MC(1)，MC(1)的精度高于MC(2)。精度隨著預測航線數(shù)量的增加而減少，平均精確度為66.4%，當航線數(shù)量為40時最低，當數(shù)目超過50時動態(tài)地改變。其中航線數(shù)為2時，精度的最大值可達到95%。對于那些非活躍乘客預測精度相對較高。相反，當乘客活躍時預測精度較低。而當乘客過于活躍時，精度隨機地變化。這符合現(xiàn)實情況。

圖6和圖7分別是返回歷史航線和新航線預測的召回率結果圖。返回歷史航線的召回率如圖6所示。當不同航線的數(shù)量低于17個時，召回率高于55%。當不同航線的數(shù)量等于4時，召回率達到最大值是67.33%，整體召回率大于50%，并且預測精度相對穩(wěn)定，大部分的召回率都在18%到48%之間。當這個值大于48%時，召回率將動態(tài)變化，最大值為70.67%。對于不活躍的乘客，他們經(jīng)常在某些航線飛行，很少探索新航線。但是活躍的乘客，探索新航線的可能性很高。圖7顯示了探索新航線的召回程度。由于其他算法無法預測新航線，所以他們對探索新航線的召回率為0。而本文算法探索新航線的召回率從0變?yōu)?4.37%，當不同航線數(shù)量值為60時，最大召回值為70.76%。這表明活躍的乘客經(jīng)常探索新航線。

圖5 預測精度實驗結果

圖6 出行返回的召回率

圖7 探索新航線召回率

下面分析不同實驗環(huán)境參數(shù)對實驗效果的影響。圖8為不同預測長度(連續(xù)預測旅客未來多次出行的次數(shù))對實驗結果的影響。可以發(fā)現(xiàn)，當預測長度范圍從2到5變化時，預測精度會隨之下降。當長度為2時，最大值為71.77%。當預測長度較小時，具有較多的訓練數(shù)據(jù)，所以精度會隨之提高。圖9為不同數(shù)據(jù)集對實驗效果的影響。本文從10萬名匿名乘客中，分別隨機選擇10，100，500，1 000，3 000，5 000名旅客，并重復5次。實驗結果發(fā)現(xiàn)，當數(shù)據(jù)集中乘客數(shù)量為10時，預測的精度變化很大，最大值達到了72.67%。由于旅客出行具有較強的隨機性，所以精度也會相應地波動。其中小樣本對預測有更大的影響，隨著樣本數(shù)量的增加，波動變小。

5 結語

本文先利用3種不同的熵給出了數(shù)據(jù)集可預測性的理論值。通過計算馬爾可夫鏈對航空旅客出行預測的精度，發(fā)現(xiàn)其精度只能到達25%。本文通過分析10 000多名旅客的出行模式，提出了改進的馬爾可夫鏈航線預測算法。對比實驗中，MC和BN模型方法所獲得的預測精度遠小于理論值，并且二階馬爾可夫鏈模型的預測精度并沒有比一階馬爾可夫模型好，導致這樣的結果可能是受到了旅客出行特征的影響。本文的IMCAPA算法的預測精度比MC和BN有較大提升，并且還可以預測旅客下一次出行的航線。

圖8 預測長度對預測精度的影響

圖9 不同的數(shù)據(jù)集對預測精度的影響

References)

[1] GONZALEZ M C, HIDALGO C A, BARABASI A L. Understanding individual human mobility patterns [J]. Nature, 2008, 453(7196):779-82.

[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 optimalK-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.

[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] 黃志成.基于一階馬爾可夫鏈的實驗數(shù)據(jù)序列分類模型[J].計算機系統(tǒng)應用,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] 王巖韜,李蕊,盧飛,等.基于運行數(shù)據(jù)的航班運行關鍵風險因素推斷[J].交通運輸系統(tǒng)工程與信息,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.)

This work is partially supported by the National Natural Science Foundation of China (U1333113), the Science and Technology Support Program of Sichuan Province (2014GZ0111).

WANGZhongqiang, born in 1991, M. S. candidate. His research interests include big data and cloud computing.

CHENJide, born in 1990, M. S. candidate. His research interests include big data and cloud computing.

PENGJian, born in 1970, Ph. D., professor. His research interests include big data and cloud computing, wireless sensor network, mobile computing.

HUANGFeihu, born in 1990, Ph. D. candidate. His research interests include big data and cloud computing.

TONGBo, born in 1989, Ph. D. candidate. His research interests include big data and cloud computing.

AirlinepredictingalgorithmbasedonimprovedMarkovchain

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

(CollegeofComputerScience,SichuanUniversity,ChengduSichuan610065,China)

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.

airline prediction; travel destination; entropy; Markov chain; individual trajectory

TP391

:A

2017- 01- 24;

:2017- 02- 24。

國家自然科學基金資助項目(U333113)；四川省科技支撐計劃項目(2014GZ0111)。

王中強(1991—)，男，北京人，碩士研究生，主要研究方向：大數(shù)據(jù)與云計算； 陳繼德(1990—)，男，江蘇連云港人，碩士研究生，主要研究方向：大數(shù)據(jù)與云計算； 彭艦(1970—)，男,四川成都人,教授,博士,CCF高級會員,主要研究方向:大數(shù)據(jù)與云計算、無線傳感器網(wǎng)絡、移動計算； 黃飛虎(1990—)，男，四川遂寧人，博士研究生，主要研究方向：大數(shù)據(jù)與云計算； 仝博(1989—)，男，天津人，博士研究生，主要研究方向：大數(shù)據(jù)與云計算。

1001- 9081(2017)07- 2124- 05

10.11772/j.issn.1001- 9081.2017.07.2124