李 琰,劉嘉勇

0 引言

隨著移動(dòng)設(shè)備的廣泛應(yīng)用以及定位技術(shù)的發(fā)展,基于位置的服務(wù)(Location Based Service, LBS)越來(lái)越受到社會(huì)各界的關(guān)注[1]。目前,LBS獲得的位置信息僅限于移動(dòng)用戶的當(dāng)前位置,這使得為用戶提供的服務(wù)缺乏可預(yù)見性。為了提高LBS的服務(wù)質(zhì)量,對(duì)用戶未來(lái)位置的預(yù)測(cè)已成為近年來(lái)的研究熱點(diǎn)。事實(shí)上,良好準(zhǔn)確的位置預(yù)測(cè)算法不僅可以讓LBS中的商家根據(jù)預(yù)測(cè)結(jié)果挖掘潛在的客戶進(jìn)行商品推送,而且能幫助用戶利用商家的精準(zhǔn)推送從海量商品中進(jìn)行高效選擇,從而獲得更好的用戶體驗(yàn)[2]。

文獻(xiàn)[3]研究了一種基于變階的Markov位置預(yù)測(cè)模型,該模型預(yù)測(cè)能力高于標(biāo)準(zhǔn)Markov模型;但此類算法通常存在數(shù)據(jù)稀疏問(wèn)題,因此憑借單個(gè)用戶的歷史軌跡數(shù)據(jù)構(gòu)建狀態(tài)轉(zhuǎn)移矩陣的Markov位置預(yù)測(cè)模型準(zhǔn)確率不高。文獻(xiàn)[4]用已有的先驗(yàn)知識(shí),為用戶建立個(gè)性化的位置推理模型,一定程度上解決了數(shù)據(jù)稀疏的問(wèn)題;但該方法實(shí)現(xiàn)過(guò)程復(fù)雜,適用范圍狹窄。文獻(xiàn)[5]中提出了在空間維度上基于輻射模型的位置預(yù)測(cè)方法,提高了預(yù)測(cè)的準(zhǔn)確率;但該方法對(duì)地點(diǎn)的吸引力定義不準(zhǔn)確,并且在時(shí)間維度上只考慮了單個(gè)用戶的行為規(guī)律,限制了模型的預(yù)測(cè)能力。

針對(duì)上述問(wèn)題,本文提出在時(shí)間維度上利用作者主題模型(Author Topic Model, ATM)[6]自動(dòng)地發(fā)現(xiàn)與目標(biāo)用戶移動(dòng)行為相似的用戶群,根據(jù)用戶群的行為規(guī)律來(lái)優(yōu)化個(gè)人的行為規(guī)律模型,以解決數(shù)據(jù)稀疏的問(wèn)題,并擴(kuò)大預(yù)測(cè)模型的適用范圍;在空間維度上對(duì)基于輻射模型的空間預(yù)測(cè)方法[5]進(jìn)行了改進(jìn)和優(yōu)化,最后通過(guò)大量實(shí)驗(yàn)和實(shí)際數(shù)據(jù)集測(cè)試,驗(yàn)證了該預(yù)測(cè)模型的有效性。

1 本文模型

本文提出的位置預(yù)測(cè)模型基于人類移動(dòng)具有強(qiáng)規(guī)律性,文獻(xiàn)[7-8]指出可以將人類有強(qiáng)周期性的移動(dòng)看作往返于“家庭”和“工作”位置狀態(tài)之間。如圖1所示:圖1(a)展示用戶在一天時(shí)間內(nèi)處于家庭/工作位置狀態(tài)的概率分布；圖1(b)描述在家庭/工作位置狀態(tài)下用戶簽到數(shù)據(jù)在地理空間上的分布情況。其中,圈和叉分別表示在家庭位置狀態(tài)和工作位置狀態(tài)下用戶的簽到數(shù)據(jù),圖1(b)中圈圍成區(qū)域是工作位置狀態(tài)區(qū)域,而叉圍成的則是家庭位置狀態(tài)區(qū)域。

圖1 用戶周期性移動(dòng)規(guī)律展示圖

本文模型操作流程如圖2所示:

圖2 模型預(yù)測(cè)流程

1)在時(shí)間維度上,先依據(jù)作者主題模型自動(dòng)地發(fā)現(xiàn)用戶在移動(dòng)行為規(guī)律上相似的群體,然后計(jì)算在時(shí)刻t相似用戶群在位置狀態(tài)(家庭H/工作W)的概率,即用戶的概率p(H|t)和p(W|t)。

2)在空間維度上,對(duì)文獻(xiàn)[5]中提出的基于輻射模型的空間預(yù)測(cè)進(jìn)行改進(jìn),對(duì)用戶的家庭和工作位置狀態(tài)區(qū)域進(jìn)行單獨(dú)的輻射模型訓(xùn)練,并計(jì)算在t時(shí)刻,用戶的候選簽到地點(diǎn)集Venues分別在H和W位置狀態(tài)區(qū)域成為簽到地點(diǎn)x的概率p(x|H)和p(x|W),其中Venues指在所有用戶位置數(shù)據(jù)中出現(xiàn)過(guò)的地點(diǎn)。

3)綜合以上結(jié)果,根據(jù)式(1)計(jì)算得到Venues成為簽到地點(diǎn)x的概率p(x|t),比較候選地點(diǎn)的概率大小,取概率值最大的地點(diǎn)作為預(yù)測(cè)的簽到地點(diǎn)x,如式(2)所示:

p(x|t)=p(x|H)·p(H|t)+p(x|W)·p(W|t)

(1)

x=arg max{p(x|t),x∈Venues}

(2)

2 基于作者主題模型的時(shí)間-位置狀態(tài)預(yù)測(cè)

作者主題模型是一個(gè)級(jí)聯(lián)生成模型[9],它是隱含狄利克雷分布(Latent Dirichlet Allocation, LDA)[10]結(jié)合元數(shù)據(jù)作者的衍生模型,可以解決計(jì)算作者間的相似度問(wèn)題。

基于作者主題模型(ATM)的時(shí)間-位置狀態(tài)預(yù)測(cè)模型憑借用戶歷史簽到數(shù)據(jù)訓(xùn)練ATM后自動(dòng)發(fā)現(xiàn)用戶在移動(dòng)行為規(guī)律上相似的群體,然后用ATM訓(xùn)練結(jié)果中權(quán)重排名前N的表示用戶位置狀態(tài)轉(zhuǎn)移的詞去描述該群體的移動(dòng)行為規(guī)律,最后依據(jù)群體的行為規(guī)律以及本文提出的時(shí)間-用戶位置狀態(tài)概率算法得到在時(shí)間t用戶處于位置狀態(tài)(H/W)的概率。模型實(shí)現(xiàn)流程如圖3所示。

圖3 時(shí)間-位置狀態(tài)預(yù)測(cè)模型實(shí)現(xiàn)流程

2.1 位置數(shù)據(jù)預(yù)處理

位置數(shù)據(jù)預(yù)處理主要是將用戶每天的原始簽到數(shù)據(jù)表示為由48個(gè)位置詞按照時(shí)間先后順序構(gòu)成的位置詞轉(zhuǎn)移序列[11]。位置詞用來(lái)表示用戶在某時(shí)段的位置狀態(tài)轉(zhuǎn)移過(guò)程,包含3個(gè)連續(xù)位置標(biāo)簽和1個(gè)時(shí)間段標(biāo)簽,位置標(biāo)簽標(biāo)記簽到位置所處的位置狀態(tài)區(qū)域,時(shí)間段標(biāo)簽用簽到時(shí)間對(duì)應(yīng)的時(shí)段標(biāo)記,例如:位置詞HHH1,其位置標(biāo)簽是HHH,時(shí)間段標(biāo)簽是1,它表示用戶在時(shí)間段1的位置轉(zhuǎn)移是HHH,即在時(shí)段1該用戶一直在家庭位置狀態(tài)區(qū)域活動(dòng)。本節(jié)的位置數(shù)據(jù)表示可分為以下三個(gè)步驟:

1)確定簽到位置數(shù)據(jù)集中每個(gè)位置的標(biāo)簽,即根據(jù)用戶在訪問(wèn)位置的時(shí)間空間分布規(guī)律,確定該位置所處的位置狀態(tài)區(qū)域(H:家,W:工作,O:其他,N:缺失數(shù)據(jù))。

2)確定用戶每天的位置標(biāo)簽轉(zhuǎn)移序列。位置標(biāo)簽轉(zhuǎn)移序列的定義與位置詞轉(zhuǎn)移序列的類似,它是由48個(gè)位置標(biāo)簽按照時(shí)間先后順序構(gòu)成的轉(zhuǎn)移序列。本文以30 min作為劃分時(shí)間單位,將一天劃分為48個(gè)時(shí)間塊,對(duì)于每個(gè)時(shí)間塊,選擇用戶停留時(shí)間最長(zhǎng)的位置作為用戶在該時(shí)間塊的停留位置,從而確定該時(shí)間塊的位置標(biāo)簽,以此便形成用戶每天的位置標(biāo)簽轉(zhuǎn)移序列。

3)確定用戶每天的位置詞轉(zhuǎn)移序列,即先從用戶每天的位置標(biāo)簽轉(zhuǎn)移序列中從頭依次取3個(gè)連續(xù)位置標(biāo)簽,然后由步驟2)可知,3個(gè)位置標(biāo)簽跨越1.5 h,通過(guò)時(shí)間累加的計(jì)算可得到它們對(duì)應(yīng)的時(shí)段,取包含位置標(biāo)簽多的時(shí)段為位置詞的時(shí)段標(biāo)簽,進(jìn)而結(jié)合3個(gè)連續(xù)位置標(biāo)簽和對(duì)應(yīng)的時(shí)段標(biāo)簽得到一個(gè)完整的位置詞。以此類推,可獲得48個(gè)位置詞,并按照時(shí)間先后順序構(gòu)成位置詞轉(zhuǎn)移序列。本文將人的一天分為8個(gè)時(shí)間段:1)00:00—07:00;2)07:00—09:00;3)09:00—11:00;4)11:00—14:00;5)14:00—17:00;6)17:00—19:00;7)19:00—21:00;8)21:00—24:00。

2.2 用戶-用戶群模型的生成

用戶-用戶群模型是作者主題模型在本文的應(yīng)用,本文憑借該模型來(lái)自動(dòng)發(fā)現(xiàn)與目標(biāo)用戶在移動(dòng)行為規(guī)律上相似的用戶群體。

在用戶-用戶群模型中，每個(gè)位置詞w和兩個(gè)潛在變量(用戶u和用戶群g)相聯(lián)系。如圖4所示,該模型的生成過(guò)程包括兩個(gè)步驟:1)挑選一個(gè)用戶u和一個(gè)用戶群g;2)根據(jù)用戶-用戶群概率分布Θ和用戶群-位置詞概率分布Φ生成位置詞w。其中α和β是模型的先驗(yàn)參數(shù)[9]。

圖4 用戶-用戶群模型的概率圖模型

憑借所有用戶的位置詞轉(zhuǎn)移序列數(shù)據(jù)訓(xùn)練用戶-用戶群模型,得到參數(shù)Θ和Φ。從圖4中用戶-用戶群的概率圖模型易知,有以下條件概率:

P(w|A,α,β)=?P(w|A,Θ,Φ)P(Θ,Φ|α,β)dΘdΦ

(3)

其中:Θ表示用戶-用戶群概率分布;Φ表示用戶群-位置詞概率分布;A表示位置數(shù)據(jù)集中的用戶。當(dāng)Θ和Φ被看作隨機(jī)變量時(shí),位置數(shù)據(jù)集的邊緣概率可以通過(guò)對(duì)它們進(jìn)行積分得到。一些估計(jì)推斷方法可用來(lái)估計(jì)級(jí)聯(lián)貝葉斯模型的后驗(yàn)分布,本節(jié)采用吉布斯采樣[10]來(lái)進(jìn)行推斷,從而獲得參數(shù)Θ和Φ的值。其推導(dǎo)過(guò)程如下:

在用戶群G數(shù)量固定時(shí),θ和φ的條件下w的概率可以表示為:

(4)

同時(shí),可以得到每個(gè)位置詞轉(zhuǎn)移序列中的位置詞wd的概率:

(5)

根據(jù)式(4)和(5),式(3)可表示為:

P(w|A,α,β)=

考慮到這里采用離散隨機(jī)變量和多項(xiàng)式分布,位置詞集的分布可以進(jìn)一步轉(zhuǎn)換為向量u、g的所有可能組合的和形式,因此,式(4)可以轉(zhuǎn)換為如下形式:

P(w|A,α,β,G)=

其中:

P(u,g,w,Θ,Φ|A,α,β)=

(9)

對(duì)式(8)中的Θ和Φ進(jìn)行積分可得:

P(u,g,w|A,α,β)=

(10)

根據(jù)吉布斯采樣,需要估計(jì)P(u,g|Dtrain,α,β)。其中,Dtrain為訓(xùn)練數(shù)據(jù)中的用戶和位置詞集合。根據(jù)貝葉斯準(zhǔn)則,吉布斯采樣可以使用如下條件分布:

P(ui=a,gi=t|wi=w,u-i,g-i,w-i,A,α,β)=

(11)

可以得到:

P(ui=a,gi=t|wi=w,u-i,g-i,w-i,A,α,β)∝

(12)

在第s次采樣中,在用戶群gN+1=G條件下位置詞wN+1=W的概率為:

(13)

同樣,在用戶uN+1=a條件下用戶群gN+1=t的位置詞概率為:

(14)

通過(guò)上述的吉布斯采樣過(guò)程可以對(duì)參數(shù)Θ和Φ的值進(jìn)行估計(jì)。

2.3 相似用戶群體的發(fā)現(xiàn)

本文用100名用戶的位置數(shù)據(jù)訓(xùn)練用戶-用戶群模型,并將用戶群數(shù)設(shè)定為50,然后根據(jù)模型估計(jì)的參數(shù)Θ和Φ,選擇用戶群5、20和28按指定概率排序,得到的結(jié)果如表1～2所示。本文使用2.2節(jié)生成的模型自動(dòng)地發(fā)現(xiàn)相似用戶群以及他們的特征路徑。在表1中,如用戶群5所示,排名靠前的位置詞大多都包含工作標(biāo)簽W,這說(shuō)明與用戶群5移動(dòng)行為相似的用戶(如:用戶10)工作時(shí)間較長(zhǎng),且工作時(shí)間集中在4～6時(shí)間段。如表2所示,用戶16和19與用戶群20相似,從表1中可知,他們2、7、8時(shí)間段在家,并在4和5時(shí)間段處于工作狀態(tài)。以此類推,可以發(fā)現(xiàn)用戶11和8在1和8時(shí)間段處于家庭位置狀態(tài),4～6時(shí)間段在工作并且在時(shí)間段8回家。再者,用戶群20的工作時(shí)間比用戶群5和28的工作時(shí)間短,可推測(cè)對(duì)于與用戶群5相似度高的用戶(如:用戶10和5),他們的工作量比與用戶群20相似度高的用戶(如:用戶16和19)大。

表1 不同用戶群中按 P(w|g)排序排名前9的位置詞

表2 不同用戶群中按 P(g|u)排序排名前4的用戶

如圖5所示,用戶10的移動(dòng)行為規(guī)律主要與用戶群30相似,而用戶13與多個(gè)用戶群相似。由此可知,用戶10在行為移動(dòng)方面的生活方式是幾乎不變,而用戶13可能具有高度變化的生活方式。此外,還可以發(fā)現(xiàn),圖6中所有用戶排名前三相似用戶群的概率之和都大于0.5，并且大約有1/3用戶的概率接近1,這說(shuō)明用戶的行為移動(dòng)模式可以憑借其排名前三的相似用戶群行為規(guī)律共同去描述。

圖5 不同用戶的相似用戶群概率分布

圖6 所有用戶排名Top3用戶群的概率和分布

2.4 時(shí)間-用戶位置狀態(tài)概率算法

時(shí)間-用戶位置狀態(tài)概率算法是用來(lái)計(jì)算在指定時(shí)間t用戶處于位置狀態(tài)(H/W)概率的算法,該算法的實(shí)現(xiàn)步驟如下:

1)根據(jù)2.2節(jié)訓(xùn)練模型得到的參數(shù)Θ定位到與用戶相似排名前N的用戶群以及相應(yīng)的概率user_sim_ug。

2)通過(guò)參數(shù)Φ和user_sim_ug可獲得目標(biāo)用戶相似用戶群分別在8個(gè)時(shí)段中概率最大的位置詞以及計(jì)算相應(yīng)概率p_i。

3)最后計(jì)算出目標(biāo)用戶在時(shí)間t所處的位置狀態(tài)的概率p(S|i)。

概率p_i和p(S|i)的計(jì)算公式如下：

p_i=p_g·p_l;i∈[1,8]

(15)

S∈{H,W},i∈[1,8] (16)

其中:p_i為i時(shí)段概率最大位置詞的概率;p_g是目標(biāo)用戶屬于用戶群g的概率;p_l是i時(shí)段概率最大位置詞在Φ中的概率;p(S|i)是目標(biāo)用戶在i時(shí)段時(shí)位置狀態(tài)為S的概率;count_S是i時(shí)段用戶位置詞中包含S的數(shù)值;l_word是位置詞的長(zhǎng)度。另外,根據(jù)圖6的結(jié)果,說(shuō)明用戶的行為移動(dòng)模式可以用其排名前三的相似用戶群行為模式共同去描述,所以,本文將排名前N位設(shè)定為前3位。

3 基于輻射模型的位置狀態(tài)-候選地點(diǎn)預(yù)測(cè)

3.1 基于輻射模型的空間預(yù)測(cè)模型

輻射模型最初用于對(duì)移動(dòng)性和遷移模式的建模[12],該模型用于計(jì)算彼此距離r處的位置i和j之間的流動(dòng)強(qiáng)度Tij(位置i、j分別具有群體m和n)，如式(17)[13]所示:

(17)

其中:Ti是離開位置i的用戶總數(shù);sij是以i為中心、半徑為rij的圓中的用戶總數(shù)(該數(shù)不包括在位置i和j上停留的用戶數(shù))。

文獻(xiàn)[5]中提出在空間預(yù)測(cè)建模上對(duì)家庭H和工作W位置狀態(tài)區(qū)域進(jìn)行單獨(dú)的輻射模型訓(xùn)練,他們假設(shè)在每個(gè)位置狀態(tài)區(qū)域中有一個(gè)中心地點(diǎn),即用戶經(jīng)常簽到的地點(diǎn)并且用戶通常從該地點(diǎn)移動(dòng)到同一區(qū)域內(nèi)的不同候選地點(diǎn),其中候選地點(diǎn)指在所有用戶位置數(shù)據(jù)中出現(xiàn)過(guò)的地點(diǎn)。例如,用戶工作地點(diǎn)即可視為W區(qū)域的中心地。在他們的研究中,假設(shè)移動(dòng)僅在中心地點(diǎn)與其他地點(diǎn)之間發(fā)生,對(duì)于給定的區(qū)域,在j簽到的概率等于用戶從中心地i移動(dòng)到地點(diǎn)j的概率,如式(18)所示:

(18)

其中:n代表地點(diǎn)j的吸引力。文獻(xiàn)[5]將它定義為在所有用戶位置數(shù)據(jù)集中在該地點(diǎn)進(jìn)行簽到的總次數(shù)。m與n的定義相同,但m僅用于代表家庭或工作中心地點(diǎn)i的吸引力。然而,地點(diǎn)的吸引力越大,其成為用戶簽到地點(diǎn)的概率也就越大。

3.2 基于輻射模型的位置狀態(tài)-候選地點(diǎn)預(yù)測(cè)模型

位置狀態(tài)-候選地點(diǎn)預(yù)測(cè)模型是在文獻(xiàn)[5]中提出的空間預(yù)測(cè)模型上進(jìn)行改進(jìn)得到,具體模型實(shí)現(xiàn)流程如圖7所示。

圖7 位置狀態(tài)-候選地點(diǎn)預(yù)測(cè)模型流程

文獻(xiàn)[5]將地點(diǎn)的吸引力n定義為所有用戶在該地點(diǎn)進(jìn)行簽到的總次數(shù),本文作者認(rèn)為該定義存在不合理性。假設(shè)研究對(duì)象是在學(xué)校區(qū)域內(nèi)活動(dòng)的用戶群體并在此基礎(chǔ)上計(jì)算學(xué)校食堂的吸引力n值,眾所周知,目標(biāo)群體在學(xué)校食堂簽到的總次數(shù)較多,按文獻(xiàn)[5]對(duì)n的定義來(lái)計(jì)算食堂的吸引力n,必然得到的結(jié)論是:無(wú)論何時(shí),食堂的n值大。實(shí)際上,在非就餐時(shí)間食堂處于關(guān)閉狀態(tài),它的吸引力n大大降低,這與根據(jù)n的原定義得出的結(jié)論矛盾。因此,本文加入時(shí)間因素更準(zhǔn)確地定義n為:在指定時(shí)間所屬時(shí)段所有用戶在該地點(diǎn)進(jìn)行簽到的總次數(shù)。最后通過(guò)實(shí)驗(yàn)驗(yàn)證了這種改進(jìn)方法的有效性。具體確定地點(diǎn)n值的改進(jìn)算法偽代碼如算法1。

算法1get_N():獲得地點(diǎn)的n值。

輸入 指定時(shí)間t,check_in_dataset(用戶位置數(shù)據(jù)集)。

輸出n。

確定時(shí)刻t所處的時(shí)段i(i∈[1,8]);

從check_in_dataset中篩選出屬于i時(shí)段的簽到數(shù)據(jù),并存入check_in_period中;

fordataincheck_in_perioddo

從data中找到不同的簽到地點(diǎn)venues;

forvenueinvenusdo

對(duì)venue進(jìn)行計(jì)數(shù),再將相應(yīng)的值存入n[venue]中;

endfor

endfor

returnn;

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

4.1 數(shù)據(jù)及評(píng)價(jià)標(biāo)準(zhǔn)

本文采用美國(guó)著名LBS網(wǎng)站Gowalla的簽到數(shù)據(jù)集來(lái)進(jìn)行用戶位置預(yù)測(cè)。其中,本文選取的實(shí)驗(yàn)數(shù)據(jù)集包含2009年8月3日—11月10日90天共1萬(wàn)多用戶的60多萬(wàn)條位置數(shù)據(jù)。從數(shù)據(jù)集中抽取較活躍的100名用戶進(jìn)行實(shí)驗(yàn)。每條簽到數(shù)據(jù)包括用戶移動(dòng)設(shè)備串號(hào)、簽到id、簽到時(shí)間、簽到點(diǎn)經(jīng)度以及簽到點(diǎn)緯度。

對(duì)于每個(gè)用戶的位置數(shù)據(jù),將其80%數(shù)據(jù)設(shè)定為訓(xùn)練集,剩余20%設(shè)定為測(cè)試集,并采用準(zhǔn)確率來(lái)評(píng)判位置預(yù)測(cè)算法的有效性。

驗(yàn)證步驟如圖8所示。

圖8 算法驗(yàn)證步驟流程

本文采用準(zhǔn)確率作為評(píng)價(jià)標(biāo)準(zhǔn)。

準(zhǔn)確率是指預(yù)測(cè)正例與預(yù)測(cè)樣本的比例,是廣泛用于信息檢索和統(tǒng)計(jì)學(xué)領(lǐng)域的度量值,用來(lái)評(píng)價(jià)結(jié)果的質(zhì)量。其計(jì)算公式如下:

(19)

表3是兩分類器混淆矩陣(confusion matrix)。

表3 兩分類混淆矩陣

其中:TP表示實(shí)際為正類,實(shí)驗(yàn)結(jié)果也為正類的樣本數(shù)量;FN表示實(shí)際為正類,實(shí)驗(yàn)結(jié)果為反類的樣本數(shù)量;FP表示實(shí)際為反類,結(jié)果為正類的樣本數(shù)量;TN表示實(shí)際為反類,結(jié)果也為反類的樣本數(shù)量。

4.2 結(jié)果與分析

與本文模型對(duì)比的是文獻(xiàn)[3,5]模型。對(duì)比模型介紹如下:

模型A:文獻(xiàn)[3]中提出的基于變階的Markov模型,利用訓(xùn)練好的變階Markov模型,根據(jù)文獻(xiàn)[3]已定義的公式結(jié)合該用戶當(dāng)前所處的位置,來(lái)計(jì)算其出現(xiàn)在每一可能位置的概率,然后將概率最大的那個(gè)位置選作預(yù)測(cè)結(jié)果。

模型B:文獻(xiàn)[5]中提出的輻射模型(Radiation Model, RM),在空間維度上采用輻射模型,在時(shí)間維度上采用一維混合高斯模型,并綜合以上兩個(gè)維度來(lái)預(yù)測(cè)用戶位置。

模型C:本文提出的預(yù)測(cè)模型,在模型B的基礎(chǔ)上進(jìn)行改進(jìn),在時(shí)間維度上改用基于ATM的時(shí)間-位置狀態(tài)預(yù)測(cè)模型。

模型D:本文提出的預(yù)測(cè)模型,在模型C的基礎(chǔ)上進(jìn)行改進(jìn),在空間維度上采用本文改進(jìn)的基于輻射模型的位置狀態(tài)-候選地點(diǎn)預(yù)測(cè)模型。

各個(gè)模型所有實(shí)驗(yàn)用戶周一至周日預(yù)測(cè)準(zhǔn)確率均值的對(duì)比結(jié)果如表4所示。

從表4可看出：1)本文模型C和D的平均預(yù)測(cè)準(zhǔn)確率均優(yōu)于對(duì)比模型；模型D的預(yù)測(cè)準(zhǔn)確率高于C,這說(shuō)明在空間維度上對(duì)模型C改進(jìn)是有效的。本文提出的模型D的平均預(yù)測(cè)準(zhǔn)確率比基于Markov的預(yù)測(cè)模型A[3]提高了近28個(gè)百分點(diǎn),比同類型預(yù)測(cè)模型B[5]提高了近31個(gè)百分點(diǎn)。2)與模型A[3]相比,由于模型B、C、D的預(yù)測(cè)準(zhǔn)確率受用戶移動(dòng)規(guī)律性的影響且一般用戶在工作日的移動(dòng)規(guī)律性強(qiáng)于周末,因而本文提出的模型更適用于預(yù)測(cè)在工作日中用戶的位置。

表4 各種模型的平均預(yù)測(cè)準(zhǔn)確率 %

5 結(jié)語(yǔ)

本文從用戶歷史位置數(shù)據(jù)中研究了預(yù)測(cè)用戶位置的算法,提出一種基于作者主題模型和輻射模型的用戶位置預(yù)測(cè)模型。該模型在時(shí)間維度上,采用了作者主題模型訓(xùn)練出用戶的兩個(gè)概率分布矩陣,依據(jù)矩陣可得到用戶在某時(shí)刻下的狀態(tài)(“家”或“工作”);在空間維度上,依據(jù)輻射模型得到在用戶所處狀態(tài)下最可能出現(xiàn)的地點(diǎn),將此地點(diǎn)作為預(yù)測(cè)地點(diǎn)。通過(guò)大量實(shí)驗(yàn)結(jié)果驗(yàn)證了本文模型在預(yù)測(cè)用戶位置上的有效性。然而,預(yù)測(cè)用戶下一時(shí)刻的位置,不僅與用戶自身的行為習(xí)慣有關(guān),還受朋友關(guān)系等其他因素影響,下一步將致力于進(jìn)行基于社交關(guān)系和用戶行為習(xí)慣的位置預(yù)測(cè)。

參考文獻(xiàn)(References)

[1] BAO J, ZHENG Y, MOKBEL M F. Location-based and preference-aware recommendation using sparse geo-social networking data[C]// Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York: ACM, 2012: 199-208.

[2] NOULAS A, SCELLATO S, LATHIA N, et al. Mining user mobility features for next place prediction in location-based services[C]// ICDM 2012: Proceedings of the 2012 IEEE 12th International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2012: 1038-1043.

[3] Yang j, J X, M Xu, et al. Predicting next location using a variable order Markov model[C]// IWGS 2014: Proceedings of the 5th ACM SIGSPATIAL International Workshop on GeoStreaming. New York: ACM, 2014: 37-42.

[4] 薛迪, 吳禮發(fā), 李華波, 等.TraDR: 一種基于軌跡分解重構(gòu)的移動(dòng)社交網(wǎng)絡(luò)位置預(yù)測(cè)方法[J]. 計(jì)算機(jī)科學(xué), 2016, 43(3): 93-98.(XUE D, WU L F, LI H B, et al. TraDR: a destination prediction method based on trajectory decomposition and reconstruction in geo-social networks[J]. Computer Science, 2016, 43(3): 93-98.)

[5] TARASOV A, KLING F, POZDNOUKHOV A. Prediction of user location using the radiation model and social check-ins[C]// UrbComp 2013: Proceedings of the 2nd ACM SIGKDD International Workshop on Urban Computing. New York: ACM, 2013: Article No. 8.

[6] ROSEN-ZVI M, GRIFFITHS T, STEYVERS M, et al. The author-topic model for authors and documents[C]// UAI 2004: Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence. Arlington, Virginia, USA: AUAI Press, 2004: 487-494.

[7] EAGLE N, PENTLAND A. Eigenbehaviors: identifying structure in routine[J]. Behavioral Ecology and Sociobiology, 2009, 63(7): 1057-1066.

[8] LI Z, DING B, HAN J, et al. Mining periodic behaviors for moving objects [C]// KDD 2010: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2010: 1099-1108.

[9] 李杰, 王小偉.基于作者主題模型的遙感圖像自動(dòng)類別標(biāo)注方法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2013, 30(10): 263-265.(LI J, WANG X W. Automatic category tagging of remote sensing images using author topic model[J]. Computer Applications and Software, 2013, 30(10): 263-265.)

[10] 徐戈, 王厚峰.自然語(yǔ)言處理中主題模型的發(fā)展[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(8): 1423-1436.(XU G, WANG H F. The development of topic models in natural language processing[J]. Chinese Journal of Computers, 2011, 34(8): 1423-1436.)

[11] FARRAHI K, GATICA-PEREZ D. What did you do today? Discovering daily routines from large-scale mobile data[C]// MM 2008: Proceedings of the 16th ACM International Conference on Multimedia. New York: ACM, 2008: 849-852.

[12] SIMINI F, GONZLEZ M C, MARITAN A, et al. A universal model for mobility and migration patterns[J]. Nature, 2012, 484(7392): 96-100.

[13] McARDLE G, LAWLOR A, LLXREY E, et al. City-scale traffic simulation from digital footprints[C]// UrbComp 2012: Proceedings of the 2012 ACM SIGKDD International Workshop on Urban Computing. New York: ACM, 2012: 47-54.

[14] ZHENG J, NI L M. An unsupervised framework for sensing individual and cluster behavior patterns from human mobile data[C]// UbiComp 2012: Proceedings of the 2012 ACM Conference on Ubiquitous Computing. New York: ACM, 2012: 153-162.

[15] 張瑩, 李智, 張省.基于位置的社交網(wǎng)絡(luò)用戶軌跡相似性算法[J]. 四川大學(xué)學(xué)報(bào)(工程科學(xué)版), 2013, 45(增刊2): 140-144.(ZHANG Y, LI Z, ZHANG S. Users trajectory similarity algorithmic research on location-based social network[J]. Journal of Sichuan University (Engineering Science Edition), 2013, 45(S2): 140-144.)