DMM+C:一個(gè)融合多源數(shù)據(jù)的位置預(yù)測方法

盧 菁,安 吉,劉 叢

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093)

1 引 言

隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的發(fā)展,位置服務(wù)越來越受到人們的關(guān)注.為了提供更好的個(gè)性化推薦[1]、基于位置的廣告[2]等服務(wù),許多系統(tǒng)需要預(yù)測用戶的位置.已有很多研究結(jié)合用戶簽到歷史軌跡的地理信息和語義信息來進(jìn)行預(yù)測.因?yàn)橐胛恢谜Z義信息后,將會(huì)發(fā)現(xiàn)某個(gè)用戶Ui與用戶Uj雖然居住在不同的城市,若共享某共同語義位置,且日常生活習(xí)慣和愛好相似,則兩個(gè)用戶的語義行為是相似的[3].

大多數(shù)研究都對(duì)位置預(yù)測中的頻繁模式進(jìn)行有效挖掘.文獻(xiàn)[3]通過挖掘用戶語義軌跡的共同點(diǎn)進(jìn)行聚類,確定同一聚類中用戶的頻繁活動(dòng),完成對(duì)用戶的位置預(yù)測.文獻(xiàn)[4]提出了TransPredict方法,不僅根據(jù)語義軌跡考慮相似用戶,還結(jié)合交通工具進(jìn)行位置預(yù)測.以上模型都使用PrefixSpan算法進(jìn)行軌跡模式挖掘.然而,PrefixSpan旨在挖掘所有數(shù)據(jù),與過去的頻繁模式相比,最近的頻繁模式具有更高的影響和價(jià)值[5].簽到軌跡數(shù)據(jù)是與時(shí)間高度相關(guān)的位置序列,本文將PrefixSpan和滑動(dòng)時(shí)間窗口技術(shù)相結(jié)合,通過挖掘最近一系列塊中的活動(dòng)模式來不斷更新用戶的軌跡模式.

Markov模型在位置預(yù)測領(lǐng)域有著廣泛的應(yīng)用[6],其依賴于一個(gè)大矩陣[7],導(dǎo)致了高空間復(fù)雜性和數(shù)據(jù)稀疏問題.多階Markov模型更適合于用戶軌跡的建模和預(yù)測,然而,在實(shí)際應(yīng)用中的其階數(shù)很難確定.若階數(shù)太低,歷史信息不能得到充分利用;若階數(shù)太高,而用戶的歷史軌跡沒有滿足高階Markov模型所需要的路徑時(shí),則不能給出預(yù)測結(jié)果.另一方面訓(xùn)練高階Markov模型對(duì)用戶的歷史軌跡數(shù)據(jù)要求過高,預(yù)測性能常常會(huì)下降[8].

針對(duì)此問題,許多研究成功地將動(dòng)態(tài)Markov模型應(yīng)用于位置預(yù)測.文獻(xiàn)[8]采用自適應(yīng)方法確定模型階數(shù)k,根據(jù)各階模型的重要性,通過Adaboost算法給出1～k階模型的權(quán)系數(shù).文獻(xiàn)[9]利用群體出行模式來提高個(gè)人用戶位置預(yù)測精度.首先對(duì)軌跡點(diǎn)進(jìn)行空間聚類,構(gòu)造聚類鏈接,再利用聚類鏈和Fano不等式估計(jì)下一個(gè)位置的可預(yù)測性,最后采用部分匹配預(yù)測的方法,對(duì)活動(dòng)頻繁的用戶進(jìn)行個(gè)體軌跡的聚類鏈路預(yù)測.文獻(xiàn)[10]使用具有時(shí)間戳和用戶時(shí)空規(guī)則的動(dòng)態(tài)Markov模型進(jìn)行位置預(yù)測.然而,上述工作只考慮了GSP數(shù)據(jù)和移動(dòng)用戶的運(yùn)動(dòng)軌跡,忽略了語義信息對(duì)用戶行為的影響.文獻(xiàn)[11]利用軌跡模式樹基于Markov模型進(jìn)行預(yù)測,一定程度上減小了預(yù)測稀疏性.然而該模型在用戶軌跡序列與軌跡樹匹配失敗時(shí)將自動(dòng)降低階數(shù),存在路徑匹配量過少等問題.文獻(xiàn)[12]利用新停留點(diǎn)的比例判定數(shù)據(jù)時(shí)效性,并提出使用高階Markov模型對(duì)位置進(jìn)行預(yù)測.該模型在用戶軌跡序列與軌跡樹不能匹配時(shí),直接轉(zhuǎn)為考慮時(shí)間特性或移動(dòng)模式進(jìn)行預(yù)測,對(duì)歷史軌跡數(shù)據(jù)的使用有限.

雖然上述一些研究在位置預(yù)測中也考慮了各種因素,目前研究很少結(jié)合與興趣點(diǎn)相關(guān)用戶評(píng)論.眾所周知,一些用戶在他們簽到的位置上會(huì)留下評(píng)論,其中包含大量個(gè)人在興趣點(diǎn)的體會(huì)[13].當(dāng)用戶根據(jù)自身行為偏好在興趣點(diǎn)之間進(jìn)行轉(zhuǎn)移時(shí),往往會(huì)考慮其他用戶對(duì)興趣點(diǎn)的評(píng)價(jià).另外,用戶并不是對(duì)自己訪問過的所有地方都留下正面評(píng)價(jià),因此存在這樣可能性:很多用戶都到過一個(gè)地方,但是同樣都留下了負(fù)面的評(píng)價(jià).因此,用戶評(píng)論也會(huì)影響用戶的行為規(guī)律,對(duì)位置預(yù)測具有重要影響.

綜上,本文通過用戶歷史軌跡信息將多階Markov模型與軌跡前綴樹(TPtree)相結(jié)合來動(dòng)態(tài)確定模型的階數(shù),捕獲用戶行為序列模式隨時(shí)間的變化規(guī)律,再利用評(píng)論的概率分布進(jìn)一步提高預(yù)測的精確度.本文的主要貢獻(xiàn)如下:

1)本文采用基于滑動(dòng)時(shí)間窗口的PrefixSpan算法實(shí)現(xiàn)的動(dòng)態(tài)Markov模型多源數(shù)據(jù)挖掘位置預(yù)測方法(DMM+C).通過PrefixSpan算法與滑動(dòng)時(shí)間窗口的技術(shù)相結(jié)合,提出了改進(jìn)算法STW-P,通過挖掘最近一系列塊中的移動(dòng)模式,不斷地更新用戶的軌跡模式,捕獲用戶移動(dòng)序列模式隨時(shí)間變化的規(guī)律;

2)在Markov模型的基礎(chǔ)上,結(jié)合地理,語義位置信息以及用戶相似行為提出利用動(dòng)態(tài)Markov模型的位置預(yù)測方法(DMM),將多階Markov模型與TPtree相結(jié)合,根據(jù)用戶的歷史軌跡信息和行為相似性,自動(dòng)地選擇Markov模型中最合適的階數(shù)進(jìn)行預(yù)測,獲取位置預(yù)測集合;

3)結(jié)合用戶在興趣點(diǎn)的評(píng)論分析獲得位置預(yù)測集合中的正面評(píng)價(jià)概率分布,提出了DMM+C方法,將正面評(píng)價(jià)的概率最高的位置預(yù)測為用戶下一個(gè)位置;

4)在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了該方法的有效性.

2 問題描述與框架

2.1 基本定義

定義4.簽到記錄:對(duì)于每個(gè)用戶u,在位置v1,v2,…,vn-1至?xí)r間tn-1的歷史簽到記錄可以定義為一組使用時(shí)間戳排序的簽到,表示為Cu=(,,…,).

問題定義.用戶未來位置預(yù)測:給定用戶ui,該用戶的歷史簽到記錄為Cui,主要任務(wù)是預(yù)測用戶ui在時(shí)間tn下一個(gè)訪問的位置Lnext,表示為如式(1)所示:

(1)

2.2 基于動(dòng)態(tài)Markov模型DMM的構(gòu)建框架

本文總框架如圖1所示.框架由4部分組成:Ⅰ)預(yù)處理模塊:將用戶的簽到軌跡數(shù)據(jù)轉(zhuǎn)換為簽到位置序列；Ⅱ)模式挖掘模塊:從單個(gè)用戶的軌跡中挖掘頻繁的語義軌跡模式,構(gòu)建語義軌跡前綴模式樹(STPtree).對(duì)基于語義軌跡模式和簽到頻率的移動(dòng)用戶進(jìn)行聚類.對(duì)于每個(gè)聚類,提取頻繁的地理位置軌跡模式,并構(gòu)建位置軌跡前綴模式樹(LTPtree)；Ⅲ)階數(shù)確定模塊(DMM):根據(jù)用戶的歷史軌跡信息動(dòng)態(tài)地選擇Markov模型的正確階數(shù),計(jì)算出用戶的位置預(yù)測集合；Ⅳ)結(jié)合評(píng)論的(DMM+C)位置預(yù)測模塊:通過LDA對(duì)位置預(yù)測集合文本進(jìn)行建模并且計(jì)算文本當(dāng)中詞的概率分布,根據(jù)位置的主題詞的概率分布和正面評(píng)價(jià)以及負(fù)面評(píng)價(jià)的概率分布進(jìn)行位置預(yù)測.

圖1 DMM+C的總框架圖

3 算法設(shè)計(jì)與實(shí)現(xiàn)

3.1 數(shù)據(jù)預(yù)處理

用戶簽到數(shù)據(jù)集的包含位置標(biāo)識(shí)、語義位置名稱、緯度,經(jīng)度、地理地址、城市和州、簽到用戶、簽到活動(dòng)、類別和類別標(biāo)識(shí).在預(yù)處理步驟中,將每個(gè)用戶的簽到位置數(shù)據(jù)轉(zhuǎn)換為簽到位置序列.再通過調(diào)用Openstreet API為地理簽到位置分配語義標(biāo)記,獲得位置語義軌跡和興趣點(diǎn)語義信息集.

3.2 頻繁模式挖掘

首先需要從簽到軌跡中分別挖掘用戶的語義和地理頻繁模式,構(gòu)建與所發(fā)現(xiàn)的模式相對(duì)應(yīng)的TPtree,獲得用戶頻繁移動(dòng)模式,然后基于歐氏距離計(jì)算相似度,并采用AP聚類算法[14]進(jìn)行用戶相似度聚類.

3.2.1 基于語義地理軌跡的模式挖掘

本文提出了一種改進(jìn)的STW-P算法來挖掘語義軌跡集(SD)和地理軌跡集(GD),獲得用戶的頻繁地理移動(dòng)模式和頻繁語義移動(dòng)模式.通常將一周的軌跡作為基本窗口大小[11],若系統(tǒng)中接收到了下一個(gè)基本窗口,則窗口進(jìn)行滑動(dòng)并且更新用戶軌跡信息.給定數(shù)據(jù)SD和PrefixSpan算法的最小支持度閾值(λ),其中0<λ≤1,STW-P模式挖掘的全過程概述如算法1所示.其中λ的選值將在實(shí)驗(yàn)中探討.

算法1.頻繁模式挖掘

輸入:語義軌跡數(shù)據(jù)集:SD,候選集:C·,最小支持度:λ,基本窗口:g.

2.fori=1 to|C·|do

3.forj=1 to|SD|do

4.if(tcurrent≤tbase)then

7.if(tcurrent>tbasethen

10.postfixDic=genNewpostfixDic();

12. k+=1

表1顯示了用戶U的軌跡歷史被轉(zhuǎn)換成語義軌跡集的例子.如果將PrefixSpan算法的支持度閾值λ設(shè)為0.6,則語義軌跡模式如表2所示.

表1 語義軌跡集示例

表2 語義軌跡模式示例

3.2.2 軌跡前綴樹(TPtree)構(gòu)建

為了便于預(yù)測,挖掘出的語義軌跡模式需要構(gòu)造成一個(gè)語義軌跡前綴樹(STPtree).本文采用了文獻(xiàn)[3]中描述的方法來構(gòu)建STPtree,其根節(jié)點(diǎn)將所有頻繁模式集成到一棵樹中,樹的每條路徑表示一個(gè)決策規(guī)則,包含語義軌跡模式集,支持度和子節(jié)點(diǎn)值.若節(jié)點(diǎn)支持度小于頻繁序列的支持度,則更新節(jié)點(diǎn)支持度.

3.2.3 用戶相似性度量和聚類

本文采用基于信息傳遞AP聚類算法[14],因?yàn)锳P算法將所有對(duì)象作為潛在的聚類中心,隨著算法的迭代找到最合適的中心,無需事先知道分類數(shù)量.

(2)

其中,uin和ujn是用戶訪問第n個(gè)語義位置的次數(shù),而uit和ujt是用戶訪問所有位的總次數(shù).

3.3 融合多源數(shù)據(jù)的位置預(yù)測方法(DMM+C)

給定表1中用戶的歷史軌跡,假設(shè)使用三階Markov模型來建模數(shù)據(jù),若用戶前綴軌跡序列為<商場,咖啡館,公園>,采用該TPtree來匹配狀態(tài)轉(zhuǎn)移矩陣進(jìn)行預(yù)測.若系統(tǒng)中沒有對(duì)應(yīng)<商場,咖啡館,公園>的匹配項(xiàng),使用三階Markov模型無法給出預(yù)測結(jié)果.在這種情況下,文獻(xiàn)[8,11,12]將自動(dòng)降低Markov模型的階數(shù),直到匹配成功.模型階數(shù)降低后,即便在用戶歷史TPtree中找到該用戶的前綴序列,依然可能存在匹配量過少,導(dǎo)致預(yù)測效果不佳.因此,我們提出結(jié)合相鄰簇中的相似用戶信息盡可能避免降低階數(shù),并結(jié)合用戶在興趣點(diǎn)的評(píng)論來提高位置預(yù)測精度.

3.3.1 模型階數(shù)確定

假設(shè)P(Li)表示移動(dòng)用戶到達(dá)位置l的概率.給定移動(dòng)用戶u的下一個(gè)位置Li概率分布P(Li)與u到達(dá)的前k個(gè)位置之外的位置無關(guān),表示為如式(3)所示:

(3)

(4)

DMM根據(jù)用戶歷史軌跡模式、當(dāng)前前綴軌跡序列和相鄰簇中用戶的軌跡序列自動(dòng)進(jìn)行Markov模型階數(shù)的確定.算法2顯示了用DMM方法確定Markov模型階數(shù)過程,通過3個(gè)步驟決定模型的階數(shù):

算法2.Markov模型階數(shù)確定算法

輸出:Markov模型階數(shù)

1.Sequence=getSubSequence(),k=[];;

3.if(i?=Seq‖fu>

(包含跟i相同的sequence_id的序列統(tǒng)計(jì)))then

4.P(l|)=P(Li);

6.returnTRUE→k

7.else

10.break;

11.for(i=0;

12.Seq=Sequence.get(i);

14.k=n;

15.if(fu=TPtree→treeSequence_count)then

16.TPtreeNode

17.returnFalse

19.while(false=DFS(TPtree,Sequence))do

21.if(j=Sequence.size()-1)then

22.K=Sequence.size();

25.returnk

26.if(k==1)then

27.return1;

28.else

29.return=k*Sequence(k-1);

3.3.2 位置得分計(jì)算

(5)

Li=α(Lgeo-Lsem)+Lsem

(6)

根據(jù)地理位置候選集中元素與語義位置候選集中元素的對(duì)應(yīng)關(guān)系概率分布,匹配目標(biāo)軌跡取訪問概率最大的位置如式(7)所示:

P(Li)=arg(max{P(l|maxsup(ln,…,ln-k+1>))})

(7)

(8)

3.3.3 評(píng)論挖掘與分析(DMM+C)

(9)

3.3.4 位置預(yù)測

Lnext=arg(max {L=L(t)set|Supmax(P(vw|dm),Li)

(10)

4 實(shí)驗(yàn)評(píng)估

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

本文使用了文獻(xiàn)[13,15]中提供的Foursquare全球移動(dòng)通信網(wǎng)絡(luò)數(shù)據(jù)集來評(píng)估DMM+C方法性能.首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,以確保每個(gè)用戶在一個(gè)城市中至少有20個(gè)簽到和10條評(píng)論,并且每個(gè)位置至少被5個(gè)用戶訪問過.表3給出了預(yù)處理后數(shù)據(jù)集的統(tǒng)計(jì)細(xì)節(jié).

表3 數(shù)據(jù)集統(tǒng)計(jì)

4.2 評(píng)估指標(biāo)

本文采用了精確度,準(zhǔn)確率,召回率,F-Measure以及平均改善率來評(píng)估DMM和DMM+C方法的有效性和功效.Accuracy:A=CP+÷TP,Precision:P=CP+÷(CP++CP-),Recall:R=(CP++CP-)÷|TT|,F-Measure:FM=2(P×R)÷(P+R)),平均改善率定義為:AIR=(Mours-Mbaseline)÷Mbaseline,其中,CP+和CP-分別代表正確預(yù)測和錯(cuò)誤預(yù)測的數(shù)量,TT代表軌跡總數(shù),TP代表預(yù)測總數(shù),Mours是DMM+C的平均預(yù)測精度,Mbaseline是相應(yīng)模型的平均預(yù)測精度.

4.3 參數(shù)估計(jì)

在進(jìn)行位置概率計(jì)算和預(yù)測時(shí),式(6)修正系數(shù)α的取值會(huì)影響預(yù)測結(jié)果的精度.在本實(shí)驗(yàn)中,令從0到1增量步長為0.1依次取值,觀察預(yù)測精度的變化.進(jìn)行50次測試,結(jié)果如圖2所示.

圖2 修正系數(shù)對(duì)DMM預(yù)測精度的影響

在圖2中可以觀察到當(dāng)α=7時(shí),DMM預(yù)測精度最高.可以看出,參數(shù)α的值對(duì)預(yù)測的精度有一定的影響.當(dāng)α的值比較小時(shí),語義位置信息對(duì)預(yù)測結(jié)果影響比較大,DMM對(duì)于用戶位置改變不頻繁的情況更加準(zhǔn)確.當(dāng)α的值比較大時(shí),地理位置信息對(duì)預(yù)測結(jié)果產(chǎn)生比較大的影響,因此DMM對(duì)位置改變較頻繁的移動(dòng)用戶預(yù)測更加準(zhǔn)確.

4.4 Markov模型階數(shù)對(duì)預(yù)測的影響

為了評(píng)估DMM+C方法的性能,將數(shù)據(jù)集分為兩部分:第1部分選擇90%作為訓(xùn)練集,第2部分選擇10%作為測試集.實(shí)驗(yàn)中,訓(xùn)練集用于訓(xùn)練兩種DMM模型:標(biāo)準(zhǔn)DMM模型(1-DMM)和2階DMM模型(2-DMM).然后利用測試集對(duì)1-DMM～4-DMM和1-DMM+C～4-DMM+C進(jìn)行驗(yàn)證.

圖3顯示了DMM和DMM+C各4種模型預(yù)測方法的準(zhǔn)確率,召回率及F-meausre.從圖3(a)中可以看出,預(yù)測準(zhǔn)確率隨著階數(shù)K增加(從1至3)而上升,隨后平衡.3-DMM+C的預(yù)測準(zhǔn)確率明顯高于3-DMM和4-DMM.DMM根據(jù)用戶當(dāng)前的軌跡序列和用戶的歷史軌跡模式將多階Markov模型與TPtree相結(jié)合自動(dòng)地選擇適當(dāng)?shù)碾A數(shù)來進(jìn)行預(yù)測,從而改善普通Markov模型的階數(shù)過低導(dǎo)致的不確定性和階數(shù)過高導(dǎo)致的預(yù)測準(zhǔn)確率和覆蓋率低的缺陷.DMM+C結(jié)合DMM性能和用戶評(píng)論的概率分布進(jìn)一步提高預(yù)測準(zhǔn)確率.從圖3(b)和圖3(c)中同樣可以看出,兩個(gè)模型的2階和3階的召回率以及F-meausre高于對(duì)應(yīng)的標(biāo)準(zhǔn)模型.此外,兩個(gè)模型的4階準(zhǔn)確率,召回率,和F-meausre最高,但跟3階對(duì)比并沒有明顯的提高.另外,3-DMM+C的預(yù)測性能最為明顯高,因此,在后續(xù)對(duì)比實(shí)驗(yàn)中把K設(shè)為3,然后用DMM+C進(jìn)行比較.

圖3 階數(shù)對(duì)DMM和DSMM+C預(yù)測的影響

4.5 DMM+C與其他模型性能比較

4.5.1 Top-N的預(yù)測精度比較

首先,本文通過不同Top-N的值從1～10比較了DMM+C與AMM[8]和VOMM[7]的預(yù)測精度.如圖4所示,模型的預(yù)測精度隨著N的增加而上升,而且DMM+C預(yù)測精度最好.DMM+C結(jié)合了位置中包含的語義信息,這有助于更好地選擇模型的階數(shù),從而提高了預(yù)測精度.另外,DMM+C利用戶評(píng)論的概率分布進(jìn)一步提高預(yù)測精度.DMM+C預(yù)測方法與AMM和VOMM方法相比的平均改善率,預(yù)測精度分別提高了7.33%和10.91%.

圖4 不同Top-N上不同模型的預(yù)測精度

4.5.2 閾值λ的影響

在基于頻繁模式挖掘模型中,PrefixSpan最小支持度閾值的大小將會(huì)對(duì)預(yù)測算法的精度和準(zhǔn)確度產(chǎn)生一定的影響.為了測試在不同最小支持度閾值下的算法性能,本文通過調(diào)整閾值的大小來驗(yàn)證不同預(yù)測方法在不同條件下的預(yù)測精度.

如圖5所示,隨著λ值增加,預(yù)測精度反而下降.λ值太高導(dǎo)致挖掘不太頻繁的用戶模式,這將導(dǎo)致更多不匹配的情況,從而降低預(yù)測精度.如圖所示,DMM+C受λ值因素影響是3種方法當(dāng)中最小的.DMM+C通過基于滑動(dòng)時(shí)間窗口的PrefixSpan算法,不斷更新用戶的軌跡模式,捕捉用戶移動(dòng)序列模式隨時(shí)間的變化.在對(duì)不同用戶進(jìn)行聚類時(shí),DMM+C方法考慮了用戶訪問位置的頻率,這一因素在預(yù)測過程中發(fā)揮了巨大優(yōu)勢.通過該用戶所在簇距離最近的相鄰簇,將相鄰簇中具有相似用戶信息的用戶軌跡序列用于確定模型的階數(shù),盡可能避免了階數(shù)直接降低,從而提高了用戶序列匹配度,因此下降趨勢比較平緩.

圖5 λ值數(shù)對(duì)模型預(yù)測精度的影響

5 結(jié) 論

針對(duì)簡單的Markov模型和傳統(tǒng)高階 Markov模型在移動(dòng)預(yù)測領(lǐng)域存在預(yù)測精確度不足以及預(yù)測穩(wěn)定性較差的問題,本文提出了一種融合多源數(shù)據(jù)的位置預(yù)測方法(DMM+C).通過移動(dòng)用戶的歷史軌跡、目標(biāo)位置語義信息、用戶在興趣點(diǎn)簽到頻率以及相鄰簇中相似用戶的關(guān)系建立Markov模型,選擇合適的階數(shù)進(jìn)行位置預(yù)測.另外,結(jié)合用戶評(píng)論分析提高位置預(yù)測的精度.在Foursquare數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)來評(píng)估DMM+C性能,結(jié)果證明了本方法的有效性.

未來可通過用戶評(píng)論全面挖掘用戶的移動(dòng)意圖,結(jié)合動(dòng)態(tài)DMM模型進(jìn)行用戶位置預(yù)測以及個(gè)性化序列推薦.