喬巖磊，杜永萍，趙東玥

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

0 引 言

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

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

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

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

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

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

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

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

(1)

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

圖1 GA-MM示意圖

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

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

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

(2)

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

(3)

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

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

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

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

圖2 高斯混合分布

圖2為一個由3個高斯分布混合而成的概率分布，從中可以看出高斯混合模型可以較好地擬合轉(zhuǎn)移時間點的分布。

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

(4)

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

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

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

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

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

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

輸入：

Lcur：當(dāng)前位置，初值為Lstart

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

tend：結(jié)束時間

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

Start:

For 0≤i≤m：

RLi=RLi+Pcur

continue

Else:

End

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

2 實 驗

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

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

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

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

圖3 位置平均停留時間分布

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

2.2 實驗結(jié)果

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

采用準(zhǔn)確率(Precision)對預(yù)測結(jié)果進(jìn)行評價。

(5)

2.2.1 不同時間間隔△t對預(yù)測性能的影響

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

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

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

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

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

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

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

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

表1 不同算法的Precision比較

3 結(jié)束語

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

[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ù)測[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)中基于社會關(guān)系的移動用戶位置預(yù)測算法[J].計算機(jī)學(xué)報,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] 王 興,蔣新華,林 劼,等.基于概率后綴樹的移動對象軌跡預(yù)測[J].計算機(jī)應(yīng)用,2013,33(11):3119-3122.