移動用戶下一地點預(yù)測新方法

馬春來, 單 洪, 李 志, 朱立新

(解放軍電子工程學(xué)院,安徽 合肥 230037)

?

移動用戶下一地點預(yù)測新方法

馬春來, 單 洪, 李 志, 朱立新

(解放軍電子工程學(xué)院,安徽 合肥 230037)

針對目前移動用戶地點預(yù)測方法對時間的依賴性較強且在小數(shù)據(jù)集上表現(xiàn)差的問題,提出一種基于皮特曼-尤爾及移動馬爾可夫鏈(PY-MMC)模型的下一步地點預(yù)測方法.該方法綜合考慮目標用戶軌跡的短時效應(yīng)及冪律分布特征.以用戶的時間位置熵為參考,計算可預(yù)測性因子.依據(jù)該因子對皮特曼-尤爾模型及移動馬爾可夫鏈模型輸出的概率線性加權(quán),建立PY-MMC模型.利用新模型計算每個下一步候選地點的概率,并取最大者輸出,完成下一步地點的預(yù)測.以“Geolife”及“Foursquare”數(shù)據(jù)集為例,采用一步準確率、一步候選準確率及平均準確率3個評估指標進行實驗.結(jié)果表明：新方法能夠有效克服基于MMC模型的預(yù)測方法準確率隨時間波動較大的不足.同時,該方法解決了基于PY模型的預(yù)測方法對子序列長度過度依賴的問題.

移動馬爾可夫鏈(MMC); 皮特曼-尤爾過程; 位置熵；移動用戶；下一地點預(yù)測

基于位置的服務(wù)(location based services,LBS)的普及與機器學(xué)習(xí)、數(shù)據(jù)挖掘等技術(shù)的發(fā)展,使得位置大數(shù)據(jù)(location big data, LBD)的價值提取成為一個新興、熱點問題[1].研究表明,在獲取移動用戶歷史位置信息的情況下,通過時空挖掘技術(shù),不僅能夠有效推斷用戶的家庭住址、工作地點[2],還能夠?qū)τ脩舻奈恢眠M行預(yù)測[3].在商業(yè)層面,位置預(yù)測可以用于基于位置的推薦系統(tǒng)[4],如根據(jù)用戶可能到達的地方,推薦用戶所需的服務(wù)、新的朋友、多媒體信息等；在公共安全層面,位置預(yù)測可以用于對目標用戶進行跟蹤定位,掌握其預(yù)定軌跡[5],有效防范危害公共安全事件的發(fā)生[6-7].由此可見,研究位置預(yù)測對于LBS中的隱私保護及位置大數(shù)據(jù)的價值提取具有重要意義.

目前,位置預(yù)測的方法主要分為3類.1)以用戶個體移動的特征或?qū)傩詾橐罁?jù)進行建模并預(yù)測,如利用用戶簽到的冪律分布屬性,建立HPY(hierarchical Pitman-Yor)模型進行預(yù)測[8].利用用戶活動規(guī)律的周期性,建立周期移動模型進行預(yù)測[9].利用用戶軌跡的短時效應(yīng),建立n-MMC模型進行預(yù)測[10-11]等.2)利用機器學(xué)習(xí)方法進行預(yù)測,如動態(tài)貝葉斯網(wǎng)絡(luò)[12]、人工神經(jīng)網(wǎng)絡(luò)[6]等方法.但這些方法需要進行訓(xùn)練學(xué)習(xí),時間及空間代價較大.3)以第三方信息(如：社會關(guān)系、地點類別、移動距離、人員類型、軌跡相似性)為輔助進行預(yù)測[13].這類方法需要額外的先驗知識作輸入,部分數(shù)據(jù)集無法滿足該要求.

基于用戶個體移動特征建模的方法,能夠從目標個體的移動本質(zhì)出發(fā),預(yù)測用戶的軌跡,具有較高的預(yù)測效率和準確率.然而,以上方法所用模型僅基于用戶軌跡的某一屬性,并未將多種屬性綜合考慮.鑒于此,本文將以目標個體軌跡的短時效應(yīng)和冪律分布特征為依據(jù),將移動馬爾可夫鏈(mobility Markov chain， MMC)和Pitman-Yor過程結(jié)合起來,提出一種基于PY-MMC模型的位置預(yù)測方法,完成對目標用戶下一步地點的預(yù)測.

1 問題描述

設(shè)數(shù)據(jù)集

D={d1,d2, …,dW}.

式中：di=(ui,ti,φi),i=1,2,…,W,ui為用戶ID,ti為用戶到訪時間,φi為用戶到訪地點的經(jīng)緯度.選取某一用戶為研究對象.首先進行預(yù)處理(剪枝、聚類)[14]及興趣點(points of interest,POI)識別[15].然后提取出軌跡集Τ={(ti,li)|i=1,2,…,X}、時間序列t=(t1,t2,…,tX)、位置序列L=(l1,l2, …,lX).其中,X為用戶軌跡總長度,li∈Q.Q={qj|j=1,2 …,RL}為用戶ui到訪過的POI或簇標號集合,RL為用戶曾到過的地點的集合大小.地點流程圖反映了各數(shù)據(jù)集與變量的關(guān)系,如圖1所示.

圖1 移動用戶地點預(yù)測流程圖Fig.1 Flow chart of next place prediction of mobile users

結(jié)合圖1,地點預(yù)測問題可描述如下：設(shè)ui為目標用戶,已知T為該用戶的軌跡集(長度為X),給出該用戶下一步地點lX+1的條件概率分布P(lX+1|T).

2 短時效應(yīng)與MMC模型

2.1 短時效應(yīng)

用戶個體具有一定移動轉(zhuǎn)移性,這種轉(zhuǎn)移性建立了用戶當(dāng)前位置與此前一個時間段τ內(nèi)的軌跡關(guān)聯(lián)關(guān)系.設(shè)該軌跡序列為L′,其中,L′=(l1,l2,…,lY).下一步地點為qi的概率可表示為序列(L′,qi)在序列L中出現(xiàn)的比例,如下式所示：

(1)

(2)

2.2 MMC模型

傳統(tǒng)的馬爾可夫鏈雖然在一定程度上能夠描述用戶活動的短時效應(yīng),但并未考慮周視圖及日視圖下用戶活動規(guī)律的差異性.例如：一天之中不同時間段用戶的移動規(guī)律不同,一周之中每一天用戶的移動規(guī)律也不盡相同.傳統(tǒng)馬爾可夫鏈忽視了這種差異性,降低了其地點預(yù)測的精度.MMC模型將某一時間段w作為窗口,首先在局部考察時間窗口內(nèi)部的狀態(tài)轉(zhuǎn)移情況,然后在全局考察不同窗口之間的狀態(tài)轉(zhuǎn)移情況.MMC生成算法如下所示.

輸入：數(shù)據(jù)集D、時間段數(shù)目m、穩(wěn)態(tài)分布初始值λ0

輸出：Mw、Mg、Iw、Ig

1) 將地點或簇標注為不同的POI_ID，并生成軌跡序列Τ(若數(shù)據(jù)集D為GPS數(shù)據(jù)等連續(xù)軌跡則需要進行剪枝、聚類等預(yù)處理).

4) 計算時間窗口之間的狀態(tài)轉(zhuǎn)移矩陣Mg、穩(wěn)態(tài)分布的特征向量λg及行號索引矩陣Ig并輸出.

Iw及Ig分別為Mw及Mg的行號索引矩陣,存放L′與轉(zhuǎn)移矩陣的對應(yīng)關(guān)系.在利用訓(xùn)練數(shù)據(jù)生成MMC模型后,根據(jù)已知軌跡進行預(yù)測,算法如下所示.

輸入：Mw、Mg、Iw、Ig

輸出：Next_ID、PMMC

1) 根據(jù)L′及Iw、Ig,按行搜索Mw、Mg的行號.

2) 根據(jù)獲取的行號,搜索本行最大值MaxValue.

3) 若有且僅有一個非零最大值,將MaxValue輸出為PMMC,該MaxValue對應(yīng)的列號輸出為Next_ID.

4) 若該行有多個MaxValue,則隨機選擇1個,將其輸出為PMMC,將其對應(yīng)的列號輸出為Next_ID.

5) 若該行均為0,則Next_ID及PMMC輸出均為0.

MMC模型雖然能夠較好地考慮到不同時間窗口用戶行為的差異性,但并未從統(tǒng)計意義上對用戶概率分布進行分析，因此，MMC模型在分析較長位置序列時具有一定局限性.

3 冪律分布與Pitman-Yor過程

3.1 冪律分布

文獻[3]指出,在一段時間內(nèi),用戶到訪地點的頻次與該頻次的概率密度呈冪律分布[16].將用戶到訪地點頻次的概率降序排列后,頻次概率密度pf的對數(shù)與頻次f的對數(shù)呈線性關(guān)系,如下式所示：

lnpf=-αlnf+c.

(3)

式中：α及c均為常數(shù).對式(3)兩側(cè)同時作指數(shù)運算可得

pf=Cf-α.

(4)

式中：C=exp (c)亦為常數(shù).

下式為其累積分布可表示為用戶到訪頻次大于或等于f的點集所占比例：

(5)

由式(5)可推得

(6)

為驗證用戶歷史軌跡的冪律分布屬性,以“Geolife”數(shù)據(jù)集為例進行實驗.采用速度剪枝及基于密度的聚類算法(本文采用CFSFDP(clustering by fast search and find of density peaks)算法[17])將無關(guān)噪聲點剔除,分別統(tǒng)計85名用戶到訪各簇的頻次,給出對數(shù)坐標軸下用戶到訪頻次的累積分布如圖2所示.由圖2可以看出,在對數(shù)坐標軸視圖下,用戶的到訪頻次概率分布與到訪頻次均呈線性關(guān)系.這也驗證了用戶到訪頻次基本服從冪律分布的特征.

圖2 用戶到訪頻次與累積分布的關(guān)系Fig.2 Correlation between user’s check-in frequency and cumulative distribution function

3.2 Pitman-Yor過程

冪律分布有多種描述方法,其中自然語言處理中的詞分布服從冪律分布,其層次結(jié)構(gòu)又與用戶到訪地點結(jié)構(gòu)極為相似.鑒于該相似性,可通過類比思想將自然語言處理中的方法應(yīng)用到對用戶移動規(guī)律的描述上來.目前較為經(jīng)典的語言模型為Pitman-Yor過程[18].該過程能夠準確描述Power-law分布：

G～ζ(d,γ,G0).

(7)

用該過程類比描述軌跡模型,則G可表示下一次目標用戶到訪地點的分布,ζ表示Pitman-Yor過程,γ及d∈[0,1)為控制Power-law屬性的參數(shù),若d=0則Pitman-Yor過程退化為Dirichlet過程.初始分布G0(l)=1/RL表示目標用戶簽到的先驗概率.

考慮到L為用戶數(shù)據(jù)規(guī)模,若其時間跨度較長,則在此期間用戶的活動區(qū)域及移動規(guī)律有可能發(fā)生遷移,從而影響對用戶移動模式的預(yù)測.因此,從序列L中選擇最近一段子序列L″作為位置預(yù)測的參考數(shù)據(jù).若L數(shù)據(jù)的時間跨度較小或其規(guī)模不大,則L″默認取整段L.在已知序列L″的條件下,用戶下一步出現(xiàn)的位置坐標φZ+1可能以現(xiàn)有分布隸屬于已有POI集Q,也可能是以一個新的分布形式包含于某一地點qi.用戶下一次到訪地點概率可分為兩部分.若到訪地點為qi,則其概率可表示為

(8)

式中：Pexit為到訪新地點的概率，Pnew為到訪已存在地點的概率,Ni表示用戶到訪第i個POIqi的總數(shù)目,

為簽到序列的長度,RL″表示序列L″中用戶到訪過的不同POI的數(shù)目.

在確定模型參數(shù)后,即可通過Pitman-Yor模型計算每一個可能到訪的地點的概率,選取最大值及對應(yīng)的POI標號,完成用戶位置預(yù)測.

4 PY-MMC模型

4.1 模型定義

MMC模型在進行位置預(yù)測時,考慮了最近一段軌跡的序列關(guān)系,能夠較好地描述短時效應(yīng),但存在以下缺點.1)僅根據(jù)局部軌跡信息進行預(yù)測,無法從統(tǒng)計意義上描述用戶到訪地點的分布.2)僅根據(jù)曾出現(xiàn)的序列生成轉(zhuǎn)移矩陣,遇到未出現(xiàn)過的序列時,無法進行預(yù)測.3)在用戶活動頻繁但又到訪地點較多的區(qū)域,預(yù)測準確度較差.Pitman-Yor過程采用非參數(shù)貝葉斯進行估計,使模型能夠較好地適應(yīng)數(shù)據(jù)集的變化,從而較好地描述用戶移動的冪律分布特性,但該方法忽略了地點之間的前后繼承關(guān)系.

鑒于此,本文將Pitman-Yor過程及MMC模型結(jié)合,提出一種PY-MMC模型.該模型同時考慮了用戶個體在移動過程中呈現(xiàn)的短時效應(yīng)及冪律分布特性.MMC考慮的僅為時間窗口w內(nèi)用戶到訪過的地點序列,但用戶在每個窗口w內(nèi)的活動規(guī)律不盡相同.研究表明,用戶在夜間的移動性更差,在工作日的移動性更具規(guī)律性,而在休息日的移動性則更加隨機.用戶移動的隨機性越強,可預(yù)測性就越差,MMC模型預(yù)測的準確率就越差,這就意味著在時間窗口w中,MMC模型預(yù)測的可信度與用戶的不確定性負相關(guān).因此,PY-MMC模型采用可預(yù)測性因子作為MMC輸出可信度的權(quán)值,定義如下式所示：

(9)

式中：η為可預(yù)測性因子,μ為調(diào)節(jié)因子,用于調(diào)節(jié)η的影響程度,使權(quán)值的變化在[(1-μ)/2, (1+μ)/2 ].由此可以看出,已知位置序列L預(yù)測下一步地點在qi的概率由PMMC及PPY加權(quán)計算而得.在計算P(qi|L)之后,選擇最大概率輸出,并得到用戶在已知軌跡Τ條件下的下一步地點.具體算法如下所示.

輸入：Τ、m、μ、w

輸出：Next_ID、PPY-MMC

1) 根據(jù)前述第一個算法,生成MMC,得到相應(yīng)的Mw、Mg、Iw、Ig.

2) 根據(jù)Mw、Mg、Iw、Ig,計算用戶j下一步可能到達的每一個地點qi的概率PMMC.

3) 根據(jù)式(8),計算用戶j下一步可能到達的每一個地點qi的概率PPY.

4) 根據(jù)式(9),計算用戶j下一步可能到達的每一個地點qi的概率PPY-MMC.

5) 若有且僅有一個非零最大值,將最大值MaxValue輸出為PPY-MMC,該MaxValue對應(yīng)的列號輸出為Next_ID.

6) 若該行有多個MaxValue,則隨機選擇1個,將其輸出為PPY-MMC,并將其對應(yīng)的列號輸出為Next_ID.

7) 若該行均為0,則Next_ID及PPY-MMC輸出均為0.

由此可見,PY-MMC模型并不是PY模型和MMC模型輸出概率的簡單相加,而是根據(jù)可預(yù)測性因子作為權(quán)重分布的重要參考,下面將給出該權(quán)值的度量方法.

4.2 可預(yù)測性因子定義

由于熵能夠?qū)κ录l(fā)生的不確定性進行量化,從空間及時間的角度,都可以對時空信息的不確定性進行描述.將位置熵分為空間位置熵和時間位置熵,空間位置熵表征的是不同用戶到訪某一地點的不確定性,反映了該地點的多樣性,用于區(qū)分地點的屬性(公共場所、居住區(qū)域).時間位置熵能夠表示用戶在某一時段移動的不確定性,用于描述用戶的活躍性和可預(yù)測性.參照文獻[19]定義用戶在某一時間窗口內(nèi)的時間位置熵(簡稱時位置熵)：

(10)

圖3 不同時間窗口下用戶時位置熵與時間關(guān)系Fig.3 Correlation between user’s location entropy and time with different time windows

不同時間窗口用戶平均時位置熵的明顯差異性說明了不同時間段用戶具有不同的可預(yù)測性,故本文采用時位置熵表征可預(yù)測性因子：

(11)

5 實驗與結(jié)果分析

5.1 實驗準備

為檢驗所提出模型的有效性,本文選取了連續(xù)更新的GPS軌跡和偶發(fā)更新的LBSN(location based social network)用戶Check-in數(shù)據(jù)中的具有代表性的公開數(shù)據(jù)集：Geolife數(shù)據(jù)集[20]和Foursquare數(shù)據(jù)集[8].

Geolife為微軟亞洲研究院的公開項目,該項目采用GPS接收機每5 s跟蹤并采集了182個用戶的自2007年4月至2012年8月的移動軌跡.該數(shù)據(jù)集共分兩個版本,具體參數(shù)如表1所示,其中,NU為用戶數(shù)量,NT為軌跡數(shù)量,NL為位置數(shù)量，Dt為用戶總的移動距離.

表1 “Geolife”數(shù)據(jù)集的基本屬性

Foursquare是于2009年誕生的基于位置服務(wù)的社交網(wǎng)站,截至目前,約有4 500萬用戶.如表2所示為通過公開應(yīng)用程序接口(application program interface,API)爬取到的用戶簽到數(shù)據(jù).其中,NF為用戶之間相互關(guān)注的數(shù)量.

表2 “Foursquare”數(shù)據(jù)集基本屬性

分別從Geolife及Foursquare數(shù)據(jù)集中提取85名、70名用戶的軌跡,進行如下實驗.1)研究PY-MMC模型的階數(shù)對下一步地點預(yù)測準確率的影響,在驗證模型的有效性的同時,給出合適的N的參考值.2)研究序列L″的長度Z對模型預(yù)測方法的準確率的影響,進一步驗證該預(yù)測方法的有效性.3)分別采用MMC模型、PY模型及PY-MMC模型進行對比實驗,考察3種方法準確率與數(shù)據(jù)集序列長度X之間的關(guān)系.4)采用多個用戶的多條軌跡進行實驗,統(tǒng)計并對比新模型與MMC、PY模型的預(yù)測準確率.5)在周視圖下,考察3種方法在不同的時間窗口中的位置預(yù)測準確率.

實驗共分為3個步驟：1)對目標用戶的數(shù)據(jù)集進行速度剪枝處理,并剔除噪聲點；2)采用基于密度的聚類方法對處理過的數(shù)據(jù)集進行聚類,并對每個簇標號,生成用戶軌跡數(shù)據(jù)集T；3)根據(jù)不同模型的初始參數(shù)值,從T中選取序列L、L′、L″進行預(yù)測,并以L后的地點作為參考,統(tǒng)計預(yù)測準確率.

本文采用以下3種評估指標對預(yù)測準確率進行度量：

1)一步準確率：用戶下一步地點預(yù)測正確的次數(shù)Nstep與該用戶軌跡總數(shù)目Ntraj之比：

(12)

2)一步候選準確率：用戶下一步地點在候選列表Lk中的次數(shù)Ncand與該用戶軌跡總數(shù)目Ntraj之比：

(13)

式中：Ncand為用戶下一步地點預(yù)測正確的次數(shù),Ntraj為參與預(yù)測的軌跡總數(shù)目.本次實驗中候選列表Lk長度k=3.

3)平均準確率：多名用戶下一步地點預(yù)測正確的次數(shù)之和與軌跡總數(shù)目之比：

(14)

5.2 實驗結(jié)果分析

1)模型預(yù)測準確率與PY-MMC階數(shù)Y之間關(guān)系實驗.

取數(shù)據(jù)集長度X=260,時間段數(shù)目m=3,子序列長度Z=260,強度參數(shù)γ=5,減損參數(shù)d=0.5,調(diào)節(jié)因子μ=0.6選取不同的MMC階數(shù)(Y=1, 2, 3, 4),考察PY-MMC預(yù)測準確率σ如圖4所示.

圖4 皮特曼尤爾-移動馬爾可夫鏈模型-階數(shù)與準確率的關(guān)系Fig.4 Correlation between accuracy and order of PY-MMC model

由圖4(a)、4(b)可看出,隨著階數(shù)Y的增加,模型一步準確率和候選準確率先升高后降低,在Y=2時,PY-MMC預(yù)測準確率最高.這說明了目標用戶下一步地點與包括當(dāng)前地點在內(nèi)的前2個地點密切相關(guān).分析原因如下：當(dāng)Y<2時,下一個狀態(tài)僅與當(dāng)前狀態(tài)有關(guān),在進行預(yù)測時沒有考慮到序列關(guān)系,從而使生成的轉(zhuǎn)移矩陣過于單一,導(dǎo)致預(yù)測準確率降低；當(dāng)Y>2時,較早的狀態(tài)參與了對下一個狀態(tài)的預(yù)測,而這些狀態(tài)往往過于冗余,形成的轉(zhuǎn)移矩陣也較為龐大,降低了馬爾可夫鏈的泛化能力,增加了預(yù)測誤差.

2)模型預(yù)測準確率與PY-MMC模型子序列長度Z之間關(guān)系實驗.

圖5 皮特曼尤爾-移動馬爾可夫鏈模型中子序列長度與準確率的關(guān)系Fig.5 Correlation between accuracy and length of sub-sequences of PY-MMC model

分別選取不同的子序列L″,采用PY-MMC模型進行預(yù)測,考察預(yù)測準確率(見圖5).由圖5(a)、5(b)可以看出,隨著子序列長度Z的增加,模型預(yù)測準確率呈上升趨勢.當(dāng)Z≥270時,預(yù)測精度基本不再變化.這是由于PY-MMC模型中的子模型依據(jù)Pitman-Yor過程,而這一過程及冪律分布需要較多的點來表征.在子序列長度Z增加時,更多的位置點參與了對該分布的描述,從而使模型的預(yù)測準確率逐漸增加.

3)三種模型預(yù)測準確率與數(shù)據(jù)集大小X之間關(guān)系實驗.

圖6 不同數(shù)據(jù)集大小條件下PY, MMC and PY-MMC模型準確率Fig.6 Accuracies of PY, MMC and PY-MMC model with different dataset sizes

通過分段選取130個不同長度的軌跡集,其長度X=50n(n=1,2,…,10),考察X取不同值時模型準確率的變化情況.由圖6(a)、6(b)可以看出,隨著數(shù)據(jù)集長度增加,三種模型的預(yù)測準確率均先逐漸增加后趨于平緩.這說明了無論何種模型,都需要充足的訓(xùn)練集來訓(xùn)練,才能保證有較穩(wěn)定的預(yù)測準確率.另外,在X較大時,PY-MMC模型準確率略高,而PY與MMC的準確率基本一致.在X較小時,MMC及PY-MMC模型的準確率均明顯高于PY模型的準確率.這說明了PY模型由于無法用較少的數(shù)據(jù)得到更為精確的分布,從而難以應(yīng)用于長度較短的數(shù)據(jù)集中.

4)三種模型預(yù)測準確率與時間窗口w關(guān)系實驗.

圖7 不同時間窗口條件下PY、MMC、PY-MMC模型的準確率對比Fig.7 Accuracy comparison of PY, MMC and PY-MMC model with different time windows

以w=8為時間窗口,將一周分為21個時間窗,統(tǒng)計每一個窗口內(nèi)3種模型的預(yù)測準確率,如圖7所示.由圖7(a)、7(b)可看出,相比于PY及PY-MMC模型,MMC模型的預(yù)測誤差波動較為明顯.在每一天的第1、3個窗口MMC均具有較高的準確率,而在第2個時間窗口MMC的預(yù)測誤差較大.這主要是由于MMC模型僅根據(jù)較短的序列進行預(yù)測,其預(yù)測準確率受時間窗內(nèi)的不確定性影響較大,而用戶在不同的時間窗口移動的不確定性不同,這就導(dǎo)致了MMC的不穩(wěn)定.相比于MMC及PY-MMC模型,PY模型的預(yù)測誤差較為平穩(wěn),基本與時間無關(guān).尤其在第16～21個時間窗口(周六、周日)內(nèi),這種差別更為明顯.這主要是由于PY模型僅描述的是子序列內(nèi)各數(shù)據(jù)點的分布過程,不包含時間標簽,在不同的時間窗口表現(xiàn)都是一致的.

5)三種模型平均準確率統(tǒng)計對比.

為綜合考察3種模型的表現(xiàn),對85名用戶不同長度的軌跡進行預(yù)測,統(tǒng)計其預(yù)測準確率均值.如表3所示.

表3 PY、MMC、PY-MMC模型預(yù)測平均準確率

Tab.3 Average accuracies of PY, MMC and PY-MMC model for prediction

%

由圖4～7及表3可以看出,相比于Geolife,Foursquare數(shù)據(jù)集準確率較低.這主要是由于偶發(fā)更新的軌跡數(shù)據(jù)與LBSN用戶簽到習(xí)慣有關(guān),稀疏的數(shù)據(jù)造成了較多細節(jié)信息的缺失,從而導(dǎo)致無法獲得更高的準確率.無論是對于Geolife數(shù)據(jù)集是Foursquare數(shù)據(jù)集,相比于PY及MMC模型,PY-MMC模型在不同的數(shù)據(jù)集長度、不同的時間窗口、不同的用戶的條件下均具有較高準確率.這主要是由于PY-MMC模型同時考慮了PY模型及MMC模型的優(yōu)點,兼顧了用戶軌跡的短時效應(yīng)和冪律分布特征.該模型既能解決PY模型因數(shù)據(jù)量不足而難以描述冪律分布的問題,又能彌補MMC模型的預(yù)測準確率隨時間變化較大的缺點.

綜上所述,得出以下結(jié)論：1)MMC預(yù)測準確率與階數(shù)Y有關(guān),Y過大或過小均會降低MMC預(yù)測準確率.2)PY預(yù)測準確率依賴子序列長度Z,較長的Z可以得到更穩(wěn)定的預(yù)測.3)足夠的數(shù)據(jù)集能夠保證3種模型得到更準確的預(yù)測.4)MMC在不同的時間窗口,預(yù)測準確率誤差波動較大.5)PY-MMC模型比MMC及PY模型更加穩(wěn)定.6)數(shù)據(jù)更新越頻繁,軌跡在時間尺度上越“緊密”,用戶位置可預(yù)測性越強,準確率越高.

6 結(jié) 語

該模型從時間的角度將用戶軌跡視為馬爾可夫過程,從空間的角度將用戶軌跡視為Pitman-Yor過程,從而克服了單一模型各自的缺點.實驗考察了MMC階數(shù)、子序列長度、數(shù)據(jù)集大小及不同時間窗口與模型準確率之間的關(guān)系.結(jié)果表明,相比于PY和MMC模型,PY-MMC模型在不同的數(shù)據(jù)集長度及的時間窗口條件下具有較高的預(yù)測準確率,對LBS用戶的位置預(yù)測具有一定參考意義.今后將在此基礎(chǔ)上進一步研究第三方信息(如：社會關(guān)系、POI類型)輔助下的移動用戶地點預(yù)測方法.

[1] 郭遲,劉經(jīng)南,方媛,等.位置大數(shù)據(jù)的價值提取與協(xié)同挖掘方法[J].軟件學(xué)報,2014,25(4): 713-730. GUO Chi, LIU Jing-nan, FANG Yuan, et al. Value extraction and collaborative mining methods for location big data [J]. Ruan Jian Xue Bao/Journal of Software, 2014, 25(4):713-730.

[2] KRUMM J. Inference attacks on location tracks [J]. IEEE Pervasive Computing, 2007,4480: 127-143.

[3] LU X, WETTER E, BHARTI N, et al. Approaching the limit of predictability in human mobility [J]. Scientific Reports, 2013, 3(10): 1-9.

[4] BAO J, ZHENG Y, WILKIE D, et al. Recommendations in location-based social networks: a survey [J]. GeoInformatica, 2015, 19(3): 525-565.

[5] MIGUEL P C, FRIGNAL J. Geo-location inference attacks: from modeling to privacy risk assessment [C]∥ 2014 Tenth European Dependable Computing Conference (EDCC). Tyne: IEEE, 2014: 222-225.

[6] GUNDUZ S, YAVANOGLU U, SAGIROGLU S. Predicting next location of twitter users for surveillance [C]∥ 2013 12th International Conference on Machine Learning and Applications (ICMLA). Miami: IEEE, 2013: 267-273.

[7] BOGOMOLOV A, LEPRI B, STAIANO J, et al. Once upon a crime: towards crime prediction from demographics and mobile data [C]∥ Proceedings of the 16th International Conference on Multimodal Interaction. Istanbul: ACM, 2014: 1-10.

[8] GAO H, TANG J, LIU H. Exploring social-historical ties on location-based social networks [C] ∥ The 6th International AAAI Conference on Weblogs and Social Media. Dublin: AAAI, 2012: 1-8.

[9] CHO E, MYERS S A, LESKOVEC J. Friendship and mobility: user movement in location-based social networks [C] ∥ Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego: ACM, 2011: 1-9.

[10] CHEN M, YU X, LIU Y. Mining moving patterns for predicting next location[J]. Information Systems, 2015, 54: 156-168.

[11] GAMBS S, KILLIJIAN M, MIGUEL P C. De-anonymization attack on geolocated data [J]. Journal of Computer and System Sciences, 2014, 80(8): 1597-1614.

[12] DASH M, KEE K K, GOMES J B, et al. Next place prediction by understanding mobility patterns [C]∥ 2015 IEEE International Conference on Pervasive Computing and Communication Workshops. St.Louis: IEEE,2015: 469-474.

[13] BAUMANN P, KLEIMINGER W, SANTINI S. The influence of temporal and spatial features on the performance of next-place prediction algorithms [C]∥ Proceedings of the 2013 ACM International Joint Conference On Pervasive And Ubiquitous Computing.Zurich: ACM, 2013: 1-10.

[14] 豐江帆,熊雨虹.一種基于個人位置信息的重要地點識別方法[J].小型微型計算機系統(tǒng),2013,34(3): 503-507. FENG Jiang-fan, XIONG Yu-hong. An important place identification algorithm based on personal GPS location [J]. Journal of Chinese Computer Systems, 2013, 34(3): 503-507.

[15] 王明,胡慶武,李清泉,等.基于位置簽到數(shù)據(jù)的城市分層地標提取[J].計算機學(xué)報.2016,39(2): 405-413. WANG Ming, HU Qing-wu, LI Qing-quan, et al. Extracting hierarchical landmark from check-in data [J]. Chinese Journal of Computers, 2016, 39(2):405-413.

[16] CLAUSET A, SHALIZI C R, NEWMAN M E. Power-law distributions in empirical data [J]. SIAM Review, 2009, 51(4): 661-703.

[17] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks [J]. Science, 2014, 344(6191): 1492-1496.

[18] TEH Y W. A hierarchical Bayesian language model based on Pitman-Yor processes [C]∥ Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics. Stroudsburg: ACM, 2006: 985-992.

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

[20] ZHENG Y, CHEN Y, XIE X, et al. Geolife2.0: A location-based social networking service [C] ∥ 2009 Tenth International Conference on Mobile Data Management: Systems, Services and Middleware. Taipei: IEEE, 2009: 357-358.

New next place prediction method for mobile users

MA Chun-lai, SHAN Hong, LI Zhi, ZHU Li-xin

(ElectronicEngineeringInstituteofPLA,Hefei230037,China)

A next place prediction method based on Pitman-Yor model and mobility Markov chain(PY-MMC) model was proposed to solve the problems that mobile users’ next place prediction method depended on time heavily and the performance was poor on small dataset. The method considered both short effect and power-law distribution features of users’ trajectories. The predictability factor was calculated with temporal location entropy of users. A PY-MMC model was constructed depending on the predictability factor, which was used to weight the output probability from PY-MMC model. The maximum probability of each candidate next place was calculated with the new model. Geolife and Foursquare dataset were used in experiment, which was evaluated with one-step accuracy, one-step accuracy of candidate places and average accuracy. Experimental results show that the new method can improve stability of MMC model, and solve the problem that accuracy rate of PY model based method excessively relied on the length of sub-sequence.

mobility Markov chain (MMC); Pitman-Yor process; location entropy; mobile users; next place prediction

2015-12-15.

馬春來(1989—)，男，博士生，從事網(wǎng)絡(luò)安全、情報挖掘研究. ORCID: 0000-0002-8432-2052. E-mail: eviiive@163.com 通信聯(lián)系人：單洪，男，教授，博導(dǎo). ORCID: 0000-0002-9669-0215. E-mail: hshan222@sina.com

10.3785/j.issn.1008-973X.2016.12.018

TP 309

A

1008-973X(2016)12-2371-09