王中強(qiáng)，陳繼德，彭 艦，黃飛虎，仝 博

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

基于改進(jìn)馬爾可夫鏈的航線預(yù)測(cè)算法

王中強(qiáng)，陳繼德，彭 艦*，黃飛虎，仝 博

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

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

航線預(yù)測(cè)；出行目的地；熵；馬爾可夫鏈；個(gè)體軌跡

0 引言

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

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

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

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

1 預(yù)測(cè)理論分析

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

1)隨機(jī)熵Srand=lbN，通過(guò)假設(shè)每個(gè)用戶的下一次出行在Ni個(gè)不同位置中符合均勻分布來(lái)對(duì)下次出行進(jìn)行預(yù)測(cè)。

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

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

(1)

圖1 可預(yù)測(cè)性

2 旅客移動(dòng)特性分析

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

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

圖2 出行距離的分布

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

圖3 N=24旅客出行分布

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

3 基于改進(jìn)馬爾可夫鏈的航線預(yù)測(cè)算法

3.1 馬爾可夫鏈

(2)

(3)

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

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

3.2 IMCAPA算法

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

(4)

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

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

表1 Jack的飛行轉(zhuǎn)移矩陣

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

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

(5)

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

輸入：旅客轉(zhuǎn)移矩陣M，閾值δ，當(dāng)前出發(fā)機(jī)場(chǎng)r； 輸出：到達(dá)機(jī)場(chǎng)d。

1)

A←M中第r行值最大的機(jī)場(chǎng)，值為val1,B←M中第r行值第二大的機(jī)場(chǎng),值為val2

2)

if |val1-val2|>δthen

3)

d←A

4)

else then

5)

if 機(jī)場(chǎng)A是常住地或者上一次出行的目的機(jī)場(chǎng)then

6)

d←A

7)

else then

8)

d←常住地機(jī)場(chǎng)

9)

end if

10)

end if

算法2 當(dāng)前出發(fā)機(jī)場(chǎng)是常住地，本文認(rèn)為他即將開始的出行要么去以前去過(guò)的歷史城市，要么探索新航線。

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

(6)

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

(7)

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

如果是返回歷史航線，乘客的特征向量由歷史航線的長(zhǎng)度、不同航線的數(shù)量、兩者間百分比，及其探索新航線的數(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ù)，閾值δ，當(dāng)前出發(fā)機(jī)場(chǎng)r。 輸出：到達(dá)機(jī)場(chǎng)d。

1)

對(duì)每個(gè)機(jī)場(chǎng)計(jì)算T_short

2)

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

3)

P1←旅客選擇歷史航線的概率，P2←旅客選擇新機(jī)場(chǎng)的概率

4)

ifP1>P2then

5)

對(duì)每個(gè)歷史機(jī)場(chǎng)利用式(8)計(jì)算選擇概率

6)

else then

7)

對(duì)每個(gè)新機(jī)場(chǎng)利用式(7)計(jì)算選擇概率

8)

end if

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

4.2 預(yù)測(cè)精度分析

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

Accuracy=accurate_n/total_n

(12)

Recall_return=accurate_return/total_return

(13)

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

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

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

圖5 預(yù)測(cè)精度實(shí)驗(yàn)結(jié)果

圖6 出行返回的召回率

圖7 探索新航線召回率

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

5 結(jié)語(yǔ)

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

圖8 預(yù)測(cè)長(zhǎng)度對(duì)預(yù)測(cè)精度的影響

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

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] 孫永雄,申晨,黃麗平,等.基于二階馬爾可夫模型的模糊時(shí)間序列預(yù)測(cè)[J].計(jì)算機(jī)工程與應(yīng)用,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í)驗(yàn)數(shù)據(jù)序列分類模型[J].計(jì)算機(jī)系統(tǒng)應(yī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] 王巖韜,李蕊,盧飛,等.基于運(yùn)行數(shù)據(jù)的航班運(yùn)行關(guān)鍵風(fēng)險(xiǎn)因素推斷[J].交通運(yùn)輸系統(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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(U333113)；四川省科技支撐計(jì)劃項(xiàng)目(2014GZ0111)。

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

1001- 9081(2017)07- 2124- 05

10.11772/j.issn.1001- 9081.2017.07.2124