喬巖磊，杜永萍，趙東玥

(北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,北京 100124)

0 引 言

隨著當(dāng)今互聯(lián)網(wǎng)移動(dòng)化的潮流推進(jìn)，類似導(dǎo)航、交通管理等基于位置的服務(wù)發(fā)展迅速。為了提高位置服務(wù)體驗(yàn)，很多基于位置服務(wù)的應(yīng)用需要預(yù)先知道用戶的位置信息，如路徑推薦、興趣點(diǎn)推薦、廣告推薦等等。假設(shè)用戶A在下午3點(diǎn)經(jīng)過位置1，如果可以比較精準(zhǔn)地預(yù)測(cè)到用戶A在5點(diǎn)的位置2，就可以在3點(diǎn)鐘，針對(duì)性地給A發(fā)送位置2相關(guān)的廣告信息，引導(dǎo)A在對(duì)位置2的訪問過程中訪問廣告內(nèi)容。借助其他信息，如果可以知道用戶A在5點(diǎn)左右進(jìn)行進(jìn)餐，那么就可以在廣告中投放位置2周邊的餐廳信息。因此，對(duì)于用戶在某一真實(shí)時(shí)間區(qū)域內(nèi)的位置預(yù)測(cè)，就變得非常重要。

在軌跡數(shù)據(jù)挖掘方面，鄭宇[1]從多方面闡述了軌跡數(shù)據(jù)挖掘的相關(guān)工作，其中包括軌跡數(shù)據(jù)預(yù)處理，模式挖掘、分類等。Zheng等[2]提出了一種發(fā)現(xiàn)不確定軌跡中top-k個(gè)可能路徑的方法，基于歷史記錄的路徑推斷系統(tǒng)，利用歷史數(shù)據(jù)進(jìn)行出行模式推斷，用于降低用戶軌跡不確定性。

在位置預(yù)測(cè)方面，Xue等[3]提出了SubSyn算法，將用戶的歷史軌跡分解為子軌跡，利用子軌跡合成新軌跡，從而增加軌跡數(shù)目，擴(kuò)大了訓(xùn)練集規(guī)模，提高了預(yù)測(cè)目的地點(diǎn)的準(zhǔn)確率。目前在軌跡預(yù)測(cè)方面，基于馬爾可夫模型的方法[4-5]使用比較廣泛，其核心思想是構(gòu)建一個(gè)馬爾可夫鏈，通過前k步來推測(cè)第k+1步。Yu等[6]提出了SMLP算法，該算法在馬爾可夫模型的基礎(chǔ)上，利用網(wǎng)絡(luò)內(nèi)用戶的相關(guān)性，對(duì)位置進(jìn)行預(yù)測(cè)。Lian等[7]提出了CEPR算法，該算法利用協(xié)同過濾和用戶歷史行為對(duì)用戶未來位置進(jìn)行推薦與預(yù)測(cè)，另外他們還在Jiepang和Gowalla兩個(gè)數(shù)據(jù)集上進(jìn)行了用戶統(tǒng)計(jì)信息和位置可預(yù)測(cè)性的相關(guān)性分析[8]。Zhang等[9]利用前綴樹和啟發(fā)式搜索策略進(jìn)行個(gè)性化路徑推薦。Li等[10]利用用戶社交網(wǎng)絡(luò)關(guān)系和流動(dòng)性特點(diǎn)相關(guān)性分析對(duì)用戶建立多層友誼模型，提高了位置相關(guān)預(yù)測(cè)的性能。

另外，其他研究還包括基于關(guān)聯(lián)規(guī)則的方法[11]、基于近期活動(dòng)序列與歷史活動(dòng)匹配的方法[12]、基于多層感知機(jī)的方法[13]等。

傳統(tǒng)方法在利用馬爾可夫模型進(jìn)行位置預(yù)測(cè)時(shí)，往往要將時(shí)間劃分為若干個(gè)時(shí)間片段，然后在離散的時(shí)間段上進(jìn)行建模和預(yù)測(cè)。這就導(dǎo)致時(shí)間片段長(zhǎng)短的取值對(duì)預(yù)測(cè)結(jié)果會(huì)產(chǎn)生較大影響。若時(shí)間片段取得過長(zhǎng)，則導(dǎo)致預(yù)測(cè)結(jié)果粗糙，應(yīng)用價(jià)值變低；若時(shí)間片段取得過短，則導(dǎo)致模型序列過長(zhǎng)，影響算法效率。為了解決上述問題，文中提出了基于高斯分析的馬爾可夫模型(Markov model based on Gaussian analysis，GA-MM)。該模型通過對(duì)位置轉(zhuǎn)移時(shí)間進(jìn)行高斯混合分析，確定馬爾可夫過程中的狀態(tài)轉(zhuǎn)移節(jié)點(diǎn)，并且不需要對(duì)時(shí)間片段進(jìn)行劃分，從而解決了上述問題。

1 基于高斯分析的馬爾可夫模型

1.1 GA-MM預(yù)測(cè)算法

已知用戶在tstart時(shí)刻對(duì)Lstart進(jìn)行了訪問，要預(yù)測(cè)在tend時(shí)用戶的位置Lend。該問題可轉(zhuǎn)化為對(duì)式(1)進(jìn)行求解，其中X(t)表示t時(shí)刻用戶的位置。

(1)

為了求解式(1)，建立的模型如圖1所示。

圖1 GA-MM示意圖

其中，?節(jié)點(diǎn)是概率流出節(jié)點(diǎn)，表示用戶在該時(shí)間點(diǎn)轉(zhuǎn)移出該位置;⊕節(jié)點(diǎn)是概率流入節(jié)點(diǎn)，表示用戶在該時(shí)間點(diǎn)從其他位置轉(zhuǎn)移至該位置。這兩種節(jié)點(diǎn)相當(dāng)于馬爾可夫模型中的狀態(tài)轉(zhuǎn)移節(jié)點(diǎn)。

假設(shè)用戶的行為符合馬爾可夫過程，即用戶下一個(gè)位置出現(xiàn)在Lβ的概率P(Lβ)只與其位于前一個(gè)位置Lα的概率P(Lα)和在t時(shí)刻的轉(zhuǎn)移概率P(t|Lα→Lβ)有關(guān)。故?節(jié)點(diǎn)的概率可由式(2)計(jì)算得出：

P(Lα→Lβ,t)=P(X(t)=Lα)×P(t|Lα→Lβ)

(2)

⊕節(jié)點(diǎn)的概率計(jì)算由馬爾可夫隨機(jī)性可知：用戶會(huì)按照不同的轉(zhuǎn)移概率從若干個(gè)位置Lα轉(zhuǎn)移至位置Lβ，故用戶在t時(shí)刻位于Lβ的概率P(X(t)=Lβ)為用戶從所有可能位置Lα轉(zhuǎn)移概率之和。

(3)

其中，初始概率P(X(tstart)=Lstart)=1。

1.2 基于高斯混合模型的轉(zhuǎn)移點(diǎn)發(fā)現(xiàn)

利用馬爾可夫模型進(jìn)行位置預(yù)測(cè)時(shí)，往往都采用等間隔的時(shí)間劃分作為一個(gè)狀態(tài)的轉(zhuǎn)移點(diǎn)。例如以小時(shí)為單位進(jìn)行序列建模，每個(gè)狀態(tài)轉(zhuǎn)移點(diǎn)則相距1個(gè)小時(shí)，預(yù)測(cè)過程中則也采用小時(shí)為單位進(jìn)行預(yù)測(cè)。然而，用戶位于不同地點(diǎn)的行為不同，停留時(shí)間也不盡相同，統(tǒng)一的時(shí)間劃分必然導(dǎo)致預(yù)測(cè)結(jié)果的不準(zhǔn)確。為了解決這個(gè)問題，采用高斯混合模型對(duì)馬爾可夫模型中的狀態(tài)轉(zhuǎn)移點(diǎn)進(jìn)行發(fā)現(xiàn)。

由于用戶在每個(gè)位置可能發(fā)生轉(zhuǎn)移的時(shí)間都不相同，所以首先提取用戶從每一個(gè)位置Lα轉(zhuǎn)移至Lβ的時(shí)間點(diǎn)ti，然后學(xué)習(xí)一個(gè)高斯混合模型，如圖2所示。

圖2 高斯混合分布

圖2為一個(gè)由3個(gè)高斯分布混合而成的概率分布，從中可以看出高斯混合模型可以較好地?cái)M合轉(zhuǎn)移時(shí)間點(diǎn)的分布。

故在t時(shí)刻，用戶從位置Lα轉(zhuǎn)移至位置Lβ的概率P(t|Lα→Lβ)可由高斯混合模型計(jì)算得出：

(4)

其中，P(t|Lα→Lβ)為關(guān)于時(shí)間t的函數(shù)，由若干個(gè)帶權(quán)重的高斯分布Nαβ(t|μi,σi)疊加而成；μi為第i個(gè)高斯分布的期望，對(duì)應(yīng)于第i個(gè)高斯分布的概率最大值。這表明用戶在該時(shí)間點(diǎn)從位置Lα轉(zhuǎn)移至位置Lβ的概率最大，于是用該值作為位置的一個(gè)轉(zhuǎn)移時(shí)間點(diǎn)t。

至此，所有相關(guān)概率值已經(jīng)求得，可用式(1)進(jìn)行迭代求解，迭代結(jié)束條件為當(dāng)前時(shí)刻t大于等于結(jié)束時(shí)刻tend。

1.3 位置預(yù)測(cè)算法實(shí)現(xiàn)

基于時(shí)間序列的位置預(yù)測(cè)算法采用遞歸形式進(jìn)行求解，過程中通過數(shù)組R記錄每個(gè)地點(diǎn)的預(yù)測(cè)概率，具體算法描述如下：

算法：GA-MM預(yù)測(cè)算法。

全局變量：R=(RL0,RL1,…,RLm) //初值為0

輸入：

Lcur：當(dāng)前位置，初值為L(zhǎng)start

tnow：當(dāng)前時(shí)間，初值為tstart

tend：結(jié)束時(shí)間

Pcur：當(dāng)前概率值，初值為1

Start:

For 0≤i≤m：

RLi=RLi+Pcur

continue

Else:

End

算法運(yùn)行結(jié)束后，全局變量R中保存著在時(shí)間tend時(shí)，用戶位于各個(gè)位置的概率。將其中概率最大值對(duì)應(yīng)的地點(diǎn)作為最終用戶的位置。

2 實(shí) 驗(yàn)

2.1 數(shù)據(jù)集

GeoLife是由微軟亞洲研究院提供的一份中國(guó)用戶戶外活動(dòng)數(shù)據(jù)集，其中包含了182名用戶的出行記錄，共有17 621條軌跡，總里程超過 1292 951 km。

考慮到絕大多數(shù)軌跡點(diǎn)位于北京，故實(shí)驗(yàn)中只針對(duì)北京的軌跡點(diǎn)進(jìn)行預(yù)測(cè)與分析。經(jīng)過數(shù)據(jù)預(yù)處理工作，包括數(shù)據(jù)過濾與聚類，得到如圖3所示的地點(diǎn)統(tǒng)計(jì)數(shù)據(jù)分布，其中DBSCAN參數(shù)設(shè)置為：類簇內(nèi)點(diǎn)數(shù)量最小閾值=20,最大密度=0.000 5。

圖3展示了每個(gè)地點(diǎn)的用戶平均停留時(shí)間，可以發(fā)現(xiàn)對(duì)于81%以上的地點(diǎn)，用戶的平均停留時(shí)間不超過5 min。

圖3 位置平均停留時(shí)間分布

從以上的統(tǒng)計(jì)信息可以看出，該數(shù)據(jù)集中軌跡點(diǎn)分布相對(duì)分散，用戶移動(dòng)頻率相對(duì)較快，這將會(huì)給實(shí)驗(yàn)結(jié)果帶來一定的影響。

2.2 實(shí)驗(yàn)結(jié)果

選取160名用戶相鄰20天的軌跡數(shù)據(jù)作為訓(xùn)練集，與其時(shí)間相鄰5天的軌跡數(shù)據(jù)作為測(cè)試集(對(duì)于軌跡天數(shù)低于25天的用戶按其所有軌跡數(shù)據(jù)4∶1進(jìn)行劃分，其中有22個(gè)用戶由于軌跡數(shù)量過少被過濾掉)，分別對(duì)不同時(shí)間段以及不同用戶的預(yù)測(cè)性能進(jìn)行了評(píng)價(jià)。

采用準(zhǔn)確率(Precision)對(duì)預(yù)測(cè)結(jié)果進(jìn)行評(píng)價(jià)。

(5)

2.2.1 不同時(shí)間間隔△t對(duì)預(yù)測(cè)性能的影響

為了探究算法性能，將GA-MM算法與同樣不需要序列等值劃分的GMM算法進(jìn)行了對(duì)比。對(duì)用戶在不同時(shí)刻t，經(jīng)過不同時(shí)間間隔△t(min)之后的位置預(yù)測(cè)性能進(jìn)行了評(píng)價(jià)，如圖4所示。

觀察圖4可以發(fā)現(xiàn)，在不同時(shí)段利用不同模型，預(yù)測(cè)準(zhǔn)確率都有所不同?？傮w來說，夜晚和下午的準(zhǔn)確率相對(duì)較高，上午的準(zhǔn)確率則相對(duì)較低。這可能是由于用戶在上午進(jìn)行活動(dòng)的多樣性和不確定性較高，導(dǎo)致了很難對(duì)用戶的習(xí)慣進(jìn)行建模；而在下午和夜間，用戶的行動(dòng)較為固定，預(yù)測(cè)的準(zhǔn)確率也較高。另一方面，不同的預(yù)測(cè)時(shí)間間隔△t對(duì)算法性能的影響也較大。當(dāng)△t∈(0,60)時(shí)，GA-MM算法相比GMM算法具有一定的優(yōu)勢(shì)；當(dāng)△t大于一小時(shí)后，GA-MM算法出現(xiàn)較大性能的下降。

2.2.2 不同用戶的位置預(yù)測(cè)性能

此外，還對(duì)不同用戶進(jìn)行了預(yù)測(cè)實(shí)驗(yàn)并進(jìn)行對(duì)比，以此來估計(jì)準(zhǔn)確率波動(dòng)的幅度，具體數(shù)據(jù)如圖5所示。

圖4 GA-MM與GMM的預(yù)測(cè)準(zhǔn)確率對(duì)比

圖5 用戶平均預(yù)測(cè)準(zhǔn)確率分布

從圖5可見，在不同時(shí)間間隔△t下，對(duì)于不同用戶的預(yù)測(cè)準(zhǔn)確率距離平均準(zhǔn)確率約在±15%以內(nèi)，性能較為穩(wěn)定。對(duì)△t小于30 min的用戶進(jìn)行預(yù)測(cè)時(shí)，實(shí)驗(yàn)結(jié)果顯示GA-MM相比于GMM，預(yù)測(cè)準(zhǔn)確率提高了約12%。

將文中算法與馬爾可夫模型和PST模型[14]進(jìn)行了準(zhǔn)確率對(duì)比，從表1所示?？梢?，相比于其他算法，GA-MM的預(yù)測(cè)準(zhǔn)確率較高。

表1 不同算法的Precision比較

3 結(jié)束語

提出了基于高斯分析的馬爾可夫地理位置預(yù)測(cè)模型。該模型通過高斯混合模型擬合連續(xù)時(shí)間下地點(diǎn)軌跡的轉(zhuǎn)移概率，發(fā)現(xiàn)位置轉(zhuǎn)移節(jié)點(diǎn)，然后對(duì)馬爾可夫過程求取最終的位置預(yù)測(cè)概率，預(yù)測(cè)準(zhǔn)確率在42%左右，相比傳統(tǒng)算法平均準(zhǔn)確率提高了10%左右。在今后的工作中，為了進(jìn)一步提高預(yù)測(cè)準(zhǔn)確率并降低時(shí)間復(fù)雜度，將考慮用其他模型結(jié)合貝葉斯定理對(duì)位置的后驗(yàn)概率進(jìn)行建模，并將結(jié)合簽到數(shù)據(jù)、用戶數(shù)據(jù)等其他信息對(duì)位置預(yù)測(cè)進(jìn)行輔助工作，以進(jìn)一步提高預(yù)測(cè)性能。

[1] ZHENG Y.Trajectory data mining:an overview[J].ACM Transactions on Intelligent Systems & Technology,2015,6(3):1-41.

[2] ZHENG Kai，ZHENG Yu，XIE Xing，et al．Reducing uncertainty of low-sampling-rate trajectories[C]//International conference on data engineering.Arlington,Virginia,USA：IEEE,2012:1144-1155.

[3] XUE A Y,ZHANG R,ZHENG Y,et al.Destination prediction by sub-trajectory synthesis and privacy protection against such prediction[C]//International conference on data engineering.Brisbane,Australia:IEEE,2013:254-265.

[4] 彭 曲,丁治明,郭黎敏.基于馬爾可夫鏈的軌跡預(yù)測(cè)[J].計(jì)算機(jī)科學(xué),2010,37(8):189-193.

[5] SONG C,QU Z,BLUMM N,et al.Limits of predictability in human mobility[J].Science,2010,327(5968):1018-1021.

[6] 于瑞云,夏興有,李 婕,等.參與式感知系統(tǒng)中基于社會(huì)關(guān)系的移動(dòng)用戶位置預(yù)測(cè)算法[J].計(jì)算機(jī)學(xué)報(bào),2015,38(2):374-385.

[7] LIAN D,XIE X,ZHENG V W,et al.CEPR:a collaborative exploration and periodically returning model for location prediction[J].ACM Transactions on Intelligent Systems & Technology,2015,6(1):1-27.

[8] LIAN D,ZHU Y,XIE X,et al.Analyzing location predictability on location-based social networks[C]//Pacific-Asia conference on knowledge discovery and data mining.[s.l.]:[s.n.],2014:102-113.

[9] ZHANG C, LIANG H, WANG K, et al. Personalized trip

recommendation with POI availability and uncertain traveling time[C]//24th ACM international on conference on information and knowledge management.New York,NY,USA:ACM,2015:911-920.

[10] LI N,CHEN G.Multi-layered friendship modeling for location-based mobile social networks[C]//International conference on mobile and ubiquitous systems:networking and services.Toronto,Canada:IEEE,2009:1-10.

[11] MORZY M.Mining frequent trajectories of moving objects for location prediction[C]//International conference on machine learning and data mining in pattern recognition.Berlin:Springer,2007:667-680.

[12] BURBEY I.Predicting future locations and arrival times of individuals[D].Virginia:Virginia University,2011.

[13] KOSKELA T,LEHTOKANGAS M,SAARINEN J,et al.Time series prediction with multilayer perceptron,FIR and Elman neural networks[C]//Proceedings of the world congress on neural networks.[s.l.]:IEEE,1996:491-496.

[14] 王 興,蔣新華,林 劼,等.基于概率后綴樹的移動(dòng)對(duì)象軌跡預(yù)測(cè)[J].計(jì)算機(jī)應(yīng)用,2013,33(11):3119-3122.