盧 菁,安 吉,劉 叢

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

1 引 言

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

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

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

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

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

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

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

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

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

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

2 問題描述與框架

2.1 基本定義

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

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

(1)

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

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

圖1 DMM+C的總框架圖

3 算法設計與實現(xiàn)

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

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

3.2 頻繁模式挖掘

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

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

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

算法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算法的支持度閾值λ設為0.6,則語義軌跡模式如表2所示.

表1 語義軌跡集示例

表2 語義軌跡模式示例

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

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

3.2.3 用戶相似性度量和聚類

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

(2)

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

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

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

3.3.1 模型階數(shù)確定

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

(3)

(4)

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

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

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

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

3.if(i?=Seq‖fu>

(包含跟i相同的sequence_id的序列統(tǒng)計))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 位置得分計算

(5)

Li=α(Lgeo-Lsem)+Lsem

(6)

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

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

(7)

(8)

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

(9)

3.3.4 位置預測

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

(10)

4 實驗評估

4.1 實驗數(shù)據(jù)集描述

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

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

4.2 評估指標

本文采用了精確度,準確率,召回率,F-Measure以及平均改善率來評估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-分別代表正確預測和錯誤預測的數(shù)量,TT代表軌跡總數(shù),TP代表預測總數(shù),Mours是DMM+C的平均預測精度,Mbaseline是相應模型的平均預測精度.

4.3 參數(shù)估計

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

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

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

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

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

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

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

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

4.5.1 Top-N的預測精度比較

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

圖4 不同Top-N上不同模型的預測精度

4.5.2 閾值λ的影響

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

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

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

5 結(jié) 論

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

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