基于簽到序列模式的隱式位置訪問推演技術(shù)

夏秀峰,葉鎮(zhèn)搏,劉向宇,周大海,安云哲(沈陽航空航天大學 計算機學院，沈陽 110136)

隨著社交網(wǎng)絡(luò)的蓬勃發(fā)展，多種社交應(yīng)用為數(shù)億用戶提供著各種功能強大的社交服務(wù)。其中，位置簽到服務(wù)是社交應(yīng)用的一項主流服務(wù)。在簽到服務(wù)中，用戶使用帶有定位功能的移動設(shè)備向服務(wù)器發(fā)送自己所處地理位置進行位置簽到?；谖恢煤灥綌?shù)據(jù)服務(wù)商可以進行位置推演、用戶移動模式分析等移動計算任務(wù)，從而實現(xiàn)提高服務(wù)質(zhì)量、促進移動營銷、旅行規(guī)劃、災(zāi)難救援等實際應(yīng)用[1-5]。

目前，F(xiàn)oursquare的簽到數(shù)據(jù)已達5億多條。國內(nèi)的切客、街旁等簽到服務(wù)也有近億條的位置簽到數(shù)據(jù)。但是，社交應(yīng)用中的位置簽到數(shù)據(jù)具有稀疏性和不完整性[4,7]，主要原因是：(1)大規(guī)模的位置簽到數(shù)據(jù)反映了用戶某些行為模式和特性，從而為他人進行個人隱私推演提供了可能[5-9]，導(dǎo)致移動用戶在使用社交應(yīng)用時極為謹慎，在某些敏感地點有意關(guān)閉位置簽到服務(wù)；(2)用戶的位置簽到行為具有一定的隨機性，更加增強了位置簽到數(shù)據(jù)的稀疏性和不完整性。因此，導(dǎo)致了上述基于位置簽到數(shù)據(jù)的各項移動計算任務(wù)的準確率、服務(wù)質(zhì)量的降低。

(1)對于不存在于歷史軌跡數(shù)據(jù)的地點的訪問概率推演結(jié)果為0；

(2)對于不同類別的地點的訪問概率推演結(jié)果可能相同，無法進行更加精確的推演。

表1 歷史軌跡數(shù)據(jù)

圖1 用戶u的歷史軌跡數(shù)據(jù)

產(chǎn)生上述問題的原因在于，當前研究主要基于歷史數(shù)據(jù)中的訪問地點進行推演，而忽略了訪問地點類別所導(dǎo)致的推演結(jié)果差異。針對此問題，本文提出了一種基于用戶簽到序列模式的隱式位置訪問推演技術(shù)，其基本思想是利用用戶的歷史軌跡數(shù)據(jù)來生成簽到序列模式，基于生成的簽到序列模式對可能包含隱式地點訪問的軌跡數(shù)據(jù)進行擴展，從而降低了軌跡數(shù)據(jù)的稀疏性問題，提高了隱式位置訪問概率計算的精度。為了設(shè)計并實現(xiàn)本文的基于簽到序列模式的隱式位置訪問推演算法，需要解決如下挑戰(zhàn)問題和難點：

(1)生成用戶簽到序列模式是一個挑戰(zhàn)性問題。當采用頻繁規(guī)則挖掘算法會丟失簽到地點之間的時空關(guān)聯(lián)特性，而采用時間關(guān)聯(lián)規(guī)則挖掘算法則會忽略簽到地點之間的空間連續(xù)性，設(shè)計一種適合的用戶簽到序列模式挖掘算法，在獲得簽到序列模式的同時保證簽到地點之間的空間連續(xù)性和時空關(guān)聯(lián)特性不發(fā)生改變是一個難點問題；

(2)當推演新地點訪問時，需要采用降低數(shù)據(jù)稀疏性、增加候選隱式訪問地點的方法解決，但有效地降低數(shù)據(jù)稀疏性、并在降低稀疏性的同時保持用戶原有的簽到序列模式不發(fā)生改變是另一個挑戰(zhàn)性問題；

(3)現(xiàn)有的基于貝葉斯的地點訪問推演模型沒有考慮地點類別對于地點訪問推演的影響，如何基于移動軌跡中地點類別設(shè)計地點訪問推演模型是一個較復(fù)雜問題。

本文主要工作和貢獻如下：

(1)提出一種用戶簽到序列模式的度量和挖掘方法，在保持簽到地點時空關(guān)聯(lián)特性的基礎(chǔ)上，保證了鄰近簽到點間的空間連續(xù)性；

(2)提出了一種基于用戶簽到序列模式的隱式位置訪問推演算法，基于用戶的簽到序列模式，通過對可能包含隱式地點訪問的歷史軌跡數(shù)據(jù)進行擴展，在降低軌跡數(shù)據(jù)的稀疏性同時提高了隱式位置訪問概率計算的精度；

(3)基于真實大規(guī)模數(shù)據(jù)集進行實驗測試，驗證了所提出算法能有效抵制簽到數(shù)據(jù)的稀疏性問題，高精度地對隱式位置訪問進行推演和概率計算，同時驗證了該算法的高執(zhí)行效率。

1 相關(guān)工作

位置推演是簽到服務(wù)中一種基于用戶歷史數(shù)據(jù)的推測服務(wù)。它是指使用用戶的背景知識(在移動社交網(wǎng)絡(luò)中指用戶的社會關(guān)系及歷史簽到數(shù)據(jù))推導(dǎo)用戶在某時刻的位置。截至目前，國內(nèi)外研究人員不斷對其進行深入研究，提出了多類推演算法。

第一種采用貝葉斯模型[1,3-4,7,9,17-18]，該方法使用用戶的歷史數(shù)據(jù)建立一個貝葉斯模型，通過計算用戶訪問推演點的后驗概率推演用戶是否會訪問該點，該模型存在著對于新地點的推演效果不佳問題。文獻[5]、[11]、[19]中提出了一種在移動社交網(wǎng)絡(luò)中推演用戶位置的方法。該方法通過用戶n個朋友在t時刻的位置以及時刻t的屬性(具體包括t是工作日或周末，上下班時間段或其它時間段等)判斷該用戶在t時刻的位置。作者采用動態(tài)貝葉斯網(wǎng)絡(luò)作為推演模型，并用真實的簽到數(shù)據(jù)訓練該模型但此方法需要進行訓練學習，時間及空間代價較大。

第二種采用協(xié)同過濾推演模型[1,17-18]，通過協(xié)同過濾找到與用戶相似的用戶，再推演這些相似用戶訪問該位置的概率來推演用戶訪問該地點的概率。2013年Z.Huo等[1]在文獻中提出了一種協(xié)同過濾推演方法，雖然解決了無法推演新地點的問題，但是推演結(jié)果精度較低僅有42%。Cheng等[17]融合地域影響力和社交信息建立矩陣分解模型，從而進行個性化位置推薦。Jia等[18]提出SeqRWR方法動態(tài)選擇在每個時間片對目標用戶最有影響力的N個朋友，然后利用所提的TSB模型對朋友影響力的特征建模，推演用戶在每個時間片的位置并進行推薦。

第三種采用隱馬爾科夫模型。主要思想是應(yīng)用馬爾可夫過程推演用戶位置。根據(jù)馬爾可夫過程得知，用戶下一個訪問地點僅僅與用戶前一個訪問地點有關(guān)，精確度可達80%。2013年Andy Yuan Xue等[3]在文獻提出了SubSyn算法。該算法主要減少了數(shù)據(jù)稀疏性對推演工作帶來的困難，通過將用戶活動空間劃分為網(wǎng)格將推演位置轉(zhuǎn)化為推演位置所處的網(wǎng)格，通過計算從一個網(wǎng)格到另一個網(wǎng)格的轉(zhuǎn)移概率推演用戶訪問該點的概率。

綜上所述，當前位置推演技術(shù)主要存在以下缺點：過于依賴歷史數(shù)據(jù)，對于新訪問地點推演的精度不理想，不同類別點的推演結(jié)果無法差異化；當位置簽到數(shù)據(jù)具有較大稀疏性時，推演結(jié)果較差。產(chǎn)生上述問題的根本原因在于當前位置推演計算技術(shù)忽略了位置訪問地點具有不同的類別，而訪問地點類別對于位置推演和推演結(jié)果具有較大影響。針對此問題，本文提出了一種基于用戶簽到模式的位置隱私推演算法。

2 預(yù)備知識和問題定義

定義1 簽到序列：位置簽到數(shù)據(jù)以(li,ti)形式來表示，其中l(wèi)i表示簽到地點，ti表示位置簽到時間；將用戶uk的簽到數(shù)據(jù)按時間排序組成其簽到序列sk=[(l1,t1),…,(li,ti),…,(ln,tn)]，sk[(l1,t1),…,(li,ti),…,(ln,tn)]，sk[i]代表用戶uk第i個位置簽到數(shù)據(jù)。

定義2 連續(xù)子序列：簽到序列s=l1→…→li→…→ln，若存在序列t=li→li+1→…→li+k-1且由簽到序列s中連續(xù)的k個點組成，k≤n，則將序列t定義為序列s的一個連續(xù)子序列，記為t?s。

定義3 非連續(xù)子序列：簽到序列s=l1→…→li→…→ln，若存在序列c=lp→lq→…→ld且由簽到序列s中非連續(xù)的m個點組成，m

定義4 地點類別：每一個地點li均對應(yīng)一個地點類別，記作c(li)；將地點類別集合表示為C={c1,…,ci,…,cn}，用戶uk的所有簽到地點的地點類別集合表示為Ck。

例如圖1中，地點l3、l4、l6的地點類別為“餐廳”，l5的類別為“藥店”，用戶u的簽到地點類別集合為Cu={“公司”,“餐廳”,“藥店”,“家”}。

定義5 簽到序列模式：簽到序列模式可以用P=c1→c2→…→cn的形式來表示，對于用戶u的某個簽到序列s=lp→lm→…→ln→lq，s的簽到序列模式可記作P(s)=c(lp)→c(lm)→…→c(ln)→c(lq)。在本文中，s的簽到序列模式亦簡稱為s的模式。

定義6 簽到序列模式支持度數(shù)：已知用戶uk的簽到序列集合為Sk，對于模式P=c1→c2→…→cn，將支持P的簽到序列集合表示為SUPP(Sk,P)={s|s∈Sk:P(s)=P}，該簽到序列模式支持度數(shù)為sup(Sk,P)=|SUPP(Sk,P)|。

定義7 隱式地點：已知用戶在ti和tj時刻分別訪問地點li和lj并簽到，如果在此過程中用戶訪問地點lm但未簽到，則稱地點lm為用戶的隱式地點。

問題1 隱式地點訪問概率推演：已知用戶uk的歷史簽到序列集合Sk，對于位于路徑li→lj上的隱式地點lm，推演和計算用戶uk在從地點li移動至地點lj過程中訪問lm的概率。

如圖1所示，本文解決的主要問題是當用戶在t1時刻經(jīng)過地點l1并在t2時刻到達地點l2的過程中，基于用戶的歷史軌跡數(shù)據(jù)推演該用戶訪問l3、l4、l5、l6各地點的概率。

3 隱式地點訪問概率推演

本節(jié)提出一種基于簽到序列模式的隱式位置推演算法(Pattern based Hidden Location Inference，簡稱PI)，具體過程如算法1所示。算法1基本思想是：首先基于用戶的歷史簽到序列數(shù)據(jù)通過計算得到該用戶的簽到序列模式及其對應(yīng)概率；然后根據(jù)得到的簽到序列模式對用戶的簽到序列集合進行隱式位置推演和簽到序列擴展；最后基于擴展后的簽到序列集合采用貝葉斯后驗概率來計算和推演用戶訪問隱式地點lm的概率。

算法1.隱式地點訪問概率推演算法(Pattern based Hidden Location Inference)

輸入: 簽到序列集合Sk, 地點類別集合Ck, 地圖map, 地點li、lm、li+1.

輸出: 隱式地點lm訪問概率.

(1)PSPL=Pattern_Seq_Pro(Sk,Ck,li,li+1); /* 獲得簽到序列模式及對應(yīng)概率 */

(2)Extend_Seq(li,li+1,Sk,Ck, map,PSPL);/* 隱式位置推演和簽到序列擴展 */

(3)num1=0, num2=0;

(4)For eachsiinSkDo

(5) Ifli→lm→li+1?siThen

(6) num1++;

(7) Ifli→li+1?siThen

(8) num2++;

(10)Return Pro;

在算法1中，輸入為簽到序列集合Sk、地點類別集合Ck、地點li、lm和li+1，輸出為用戶uk從li移動至li+1過程中訪問地點lm的概率。算法1首先調(diào)用子算法Pattern_Seq_Pro，Pattern_Seq_Pro算法輸入為用戶歷史序列Sk、地點類別集合Ck、地點li和li+1，輸出用戶所有符合c(li)→c(lm)→c(li+1)形式的簽到序列模式以及對應(yīng)的訪問概率，并存入列表PSPL。然后，算法1調(diào)用子算法Extend_Seq，Extend_Seq算法以簽到序列集合Sk和PSPL作為輸入，實現(xiàn)對用戶簽到序列集合Sk中某些軌跡的擴展。算法1基于擴展后的簽到序列集合Sk、采用公式(1)來計算從li移動至li+1過程中訪問地點lm的概率。在公式(1)中，∑Sli→lm→li+1表示簽到序列集合中l(wèi)i→lm→li+1的數(shù)量，∑Sli→li+1表示簽到序列集合中l(wèi)i→li+1的數(shù)量。公式(1)采用貝葉斯后驗概率計算用戶從li出發(fā)到達li+1途中訪問lm的概率。

(1)

例如，針對表1中的歷史簽到序列數(shù)據(jù)，基于簽到序列模式進行擴展后得到如表3所示的新簽到序列Sk，此時采用公式(1)可得用戶從l1出發(fā)到達l2途中訪問各地點的概率分別為：Pr(l1→l3→l2|l1→l2)=0.075，Pr(l1→l4→l2|l1→l2)=0.275，Pr(l1→l5→l2|l1→l2)=0.2，Pr(l1→l6→l2|l1→l2)=0.4，Pr(l1→?→l2|l1→l2)=0.04；特殊地，Pr(l1→?→l2|l1→l2)表示用戶從l1出發(fā)直達l2途中沒有在任意點停留的概率。

算法2給出了簽到序列模式概率計算(Pattern_Seq_Pro算法)的具體描述，以用戶簽到序列集合Sk、地點類別集合Ck、地點li和li+1作為輸入，輸出模式序列概率列表PSPL，該列表包含了用戶所有符合c(li)→c(lm)→c(li+1)形式的簽到序列模式以及對應(yīng)的訪問概率。

Pattern_Seq_Pro算法基本思想是：先基于用戶地點類別集合Ck找到地點li和li+1對應(yīng)的地點類別建立對應(yīng)的簽到序列模式；再基于得到的簽到序列模式對用戶的簽到序列集合進行遍歷并記錄與之一致的數(shù)量；同時，根據(jù)輸入地點類別得到對應(yīng)的所有簽到序列模式并統(tǒng)計數(shù)量；最后，基于以上兩個統(tǒng)計數(shù)量采用貝葉斯后驗概率來計算用戶某一簽到序列模式的概率。

算法2.模式序列概率(Pattern_Seq_Pro)

輸入:簽到序列集合Sk,地點類別集合Ck,地點li、li+1.

輸出:模式序列概率列表PSPL.

(1)num1=0;

(2)For eachsiiinSkDo

(3)If c(li)→c(li+1)?P(si) Then

(4) num1++;

(5)For each c(lm) inc(li)→c(li+1)?P(si) Do

(6)num(c(li) →c(lm) →c(li+1))++;

(7)Ifc(lm)?LThen

(8)L←L∪{c(lm)};

(9)For each c(lm) inLThen

(11)Return PSPL。

算法2的時間復(fù)雜度為O(|Sk|+num1)。

例如，當輸入地點l1和l2、表1中簽到序列集合Sk、地點類別集合Ck時，算法2可得簽到序列的模式：P(l1→l6→l2)=P(l1→l4→l2)=“公司”→“餐廳”→“家”，其中3個簽到序列符合模式“公司”→“餐廳”→“家”，其對應(yīng)概率為Pr(“公司”→“餐廳”→“家”)=0.6；相似地，可得P(l1→l5→l2)=“公司”→“藥店”→“家”，該模式對應(yīng)概率為Pr(“公司”→“藥店”→“家”)=0.2；P(l1→?→l2)=“公司”→?→“家”=1，該模式對應(yīng)的概率為Pr(“公司”→?→“家”)=0.2。表2給出了算法2得到的簽到序列模式及其對應(yīng)概率。

表2 簽到序列模式概率

由于用戶的簽到序列具有地點稀疏性等特點，采用算法2中獲得的簽到序列模式及其概率通過算法3對某些序列進行擴展，從而降低簽到序列數(shù)據(jù)稀疏度、實現(xiàn)隱式位置訪問推演。

算法3給出了擴展簽到序列(Extend_Seq算法)的具體描述，以用戶簽到序列集合Sk，地點類別集合Ck、地圖數(shù)據(jù)map、簽到序列模式列表PSPL、地點li和li+1作為輸入，對Sk中符合特定規(guī)則的簽到序列進行擴展。Extend_Seq算法的基本思想是在歷史簽到序列集合Sk中找到可擴展序列se=li→li+1，基于該序列中訪問地點li、li+1及其時間差?t=ti+1-ti(地點li的訪問時間記作ti)來獲得此路徑過程中可能經(jīng)過的隱式地點，并基于PSPL中的簽到序列模式來計算每個隱式地點的訪問概率，具體過程如算法3所示。

輸入:地點li、li+1,簽到序列集合Sk,地點類別集合Ck,地圖數(shù)據(jù)map,模式序列概率列表PSPL.

(1)D=?,L=?, times=0; /* D存儲擴展后的簽到序列 */

(2)For eachsiinSkDo

(3)Ifli→li+1?siThen

(4)Δt←ti+1-ti;

(5)L←Hidden locations with respect toli,li+1, map and Δt;

(6) For each categorycm∈C(L) Do

(8)For each locationlmin L of categorycmDo

(9) Add (li→lm→li+1, times) toD;

(10)NormalizeD; /* 對列表D中的訪問概率進行歸一化 */

(11)Sk=Sk∪D;

Extend_Seq算法首先遍歷用戶簽到序列集合Sk，判斷序列si中是否存在li至li+1的連續(xù)子序列，若存在則計算在ti時刻從li出發(fā)、ti+1時刻到達li+1的時間差Δt=ti+1-ti。基于li、li+1和時間差Δt在地圖map中篩選出所有從li至li+1途中能在Δt時間內(nèi)經(jīng)過的地點并存入集合L。對于集合L中的任意地點lm與li、li+1組成的簽到序列采用公式(2) 計算其訪問次數(shù)。在公式(2)中，|cm(L)|表示集合L中地點類別為cm的地點數(shù)量，PSPL(c(li)→cm→c(li+1))表示簽到序列模式c(li)→cm→c(li+1)的訪問概率，得到的times表示擴展序列l(wèi)i→li+1后簽到序列l(wèi)i→lm→li+1的訪問次數(shù)。

(2)

對于L中的每一個地點lm與li和li+1組成簽到序列sj=li→lm→li+1，連同其對應(yīng)的訪問次數(shù)times以二元組形式存入列表D。需要對D中所有簽到序列的訪問次數(shù)按照公式(3)進行歸一化。在公式(3)中，times(sj)表示D中未歸一化時簽到序列sj的訪問次數(shù)，time(sj)表示歸一化后簽到序列sj訪問次數(shù)。

(3)

通過將集合D與集合Sk合并，得到擴展后的簽到序列集合Sk。算法3的時間復(fù)雜度為O(|Sk|+|L|)。

表3 擴展后軌跡數(shù)據(jù)

4 實驗

本文對提出的隱式位置推演算法的有效性進行評估。在實驗過程中，選取兩個真實數(shù)據(jù)集Brightkite和Gowalla進行實驗和分析。

4.1 實驗設(shè)置

Brightkite和Gowalla是基于位置的社交網(wǎng)絡(luò)服務(wù)提供商，其中用戶可以通過簽到服務(wù)來分享他們的位置。本文對Brightkite和Gowalla數(shù)據(jù)集進行預(yù)處理，篩選出美國加州地區(qū)的簽到數(shù)據(jù)，預(yù)處理后Brightkite數(shù)據(jù)集包含9192名用戶，簽到時間從2008年4月到2010年10月，簽到記錄為52萬條；在Gowalla數(shù)據(jù)集中共有14852名用戶，時間從2009年2月至2010年10月，簽到記錄為65萬條。對用戶簽到序列以天為單位分割為若干子簽到序列；提取出兩個數(shù)據(jù)集中簽到地點并對其進行編號，通過開源API獲得簽到地點的地點名稱和地點類別；表4顯示實驗數(shù)據(jù)集的統(tǒng)計信息。

實驗軟硬件環(huán)境如下：(1)硬件環(huán)境:Intel Core i5 3.20GHz,4GB DRAM內(nèi)存；(2)操作系統(tǒng)平臺:Microsoft Windows 7；(3)編程環(huán)境:Python2.7.11,Pycharm。

4.2 實驗結(jié)果分析

為了進行對比，本文將文獻[1]中的推演算法進行了實現(xiàn)，記作BI。實驗中隨機抽取1 000名用戶歷史簽到記錄。隨機向每個用戶的歷史簽到記錄中去掉5、10、15、20個點，將去掉點后的歷史簽到記錄作為集合1。在用戶的歷史簽到記錄集合中隨機添加5、10、15、20個用戶未曾簽到過的地點作為干擾點，將添加點后的歷史簽到數(shù)據(jù)作為集合2。其中，去掉點與增加點被視為用戶的隱式位置。

表4 實驗數(shù)據(jù)集統(tǒng)計信息

本文采用以下四個標準衡量推演結(jié)果。

(2)預(yù)測率1：推演算法計算用戶訪問集合1中去掉點的訪問概率。

(4)預(yù)測率2：推演算法計算用戶訪問集合2中增加點的訪問概率。

正確率結(jié)果如圖2所示，在兩個數(shù)據(jù)集上，PI算法的正確率都要高于BI算法。由于Gowalla數(shù)據(jù)集密集度高于Brightkite數(shù)據(jù)集，所以PI算法在Gowalla數(shù)據(jù)集上正確率達到81.75%高于在Brightkite數(shù)據(jù)集的61.5%。去掉的地點皆為用戶曾經(jīng)訪問過的地點，雖然去掉了地點，但仍有可能從其余的歷史記錄中推測出對應(yīng)的簽到模式。所以PI算法在正確率上要高于BI算法。

錯誤率如圖3所示，PI算法在Brightkite數(shù)據(jù)集上的錯誤率不到10%。隨著增加點數(shù)不斷增多兩個算法在錯誤率上呈上升趨勢。增加的點有三種類型，第一類為用戶曾經(jīng)訪問過的地點；第二類為用戶未曾訪問過的地點，但與起點和終點組成的簽到序列對應(yīng)的模式符合用戶的簽到模式；第三類為用戶未曾訪問過的地點，且與起點和終點形成的簽到序列對應(yīng)的模式不符該用戶的簽到模式；由于PI算法基于歷史記錄以及用戶簽到模式，所以當增加地點為第三類型地點時，PI算法的錯誤率會下降。而當為第二類地點時，錯誤率就會上升，如圖3(a)中，當增加點數(shù)為15時PI算法的錯誤率為13%，而當增加點數(shù)為20時，錯誤率為12%。

圖2 正確率

圖3 錯誤率

預(yù)測率1、預(yù)測率2的結(jié)果如圖4、5所示。預(yù)測率1證明了算法的有效性和可用性，預(yù)測率2則代表算法的無效性。結(jié)合圖4和圖5，可以得到預(yù)測率1在兩個數(shù)據(jù)集上的平均值為50.8%，預(yù)測率2在兩個數(shù)據(jù)集上的平均值為22.3%，預(yù)測率1高于預(yù)測率2，說明了BI和PI算法對用戶訪問地點推演皆有效。PI算法在兩個數(shù)據(jù)集上的預(yù)測率1的平均值為65.6%，BI算法在兩個數(shù)據(jù)集上的預(yù)測率1的平均值為40.6%，PI算法結(jié)果高于BI算法。原因是PI算法對數(shù)據(jù)集進行了擴充增加了可選序列數(shù)目。PI算法的預(yù)測率2在兩個數(shù)據(jù)集分別為15%和20%，低于BI算法在兩個數(shù)據(jù)集上的預(yù)測率2。由于添加點的隨機性，當添加點為第二類地點時PI算法的預(yù)測率2要明顯低于BI算法。

圖4 預(yù)測率1

圖5 預(yù)測率2

算法運行時間結(jié)果如圖6所示，由于Gowalla數(shù)據(jù)集中地點密度高于Brightkite數(shù)據(jù)集，所以無論是增加點還是去掉點，兩種算法在Brightkite數(shù)據(jù)集上的運行時間都要小于在Gowalla數(shù)據(jù)集上的運行時間。PI算法在兩個數(shù)據(jù)集上的平均運行時間為13.77 ms，BI算法在兩個數(shù)據(jù)集上的平均運行時間為7.25 ms，PI算法運行時間要大于BI算法，這是由于PI算法需要比BI算法進行更多的計算導(dǎo)致的，例如PI算法中包含了模式序列概率計算與簽到序列擴展計算。由于去掉、增加點數(shù)目有限，候選集中地點數(shù)目總體上變化不大，導(dǎo)致兩種算法的時間變化不明顯趨于穩(wěn)定。

5 總結(jié)

本文針對基于時空特性的隱式位置推演問題展開研究，提出了一種基于用戶簽到序列模式的隱式位置訪問推演算法PI算法實現(xiàn)對用戶隱式位置訪問的概率計算。PI算法通過歷史軌跡數(shù)據(jù)生成簽到序列模式，基于簽到序列模式對可能包含隱式地點訪問的軌跡數(shù)據(jù)進行擴展，從而降低了軌跡數(shù)據(jù)的稀疏性，提高了隱式位置訪問概率的計算精度。通過真實的簽到數(shù)據(jù)集進行實驗表明PI算法能有效抵制簽到數(shù)據(jù)的稀疏性問題，并能高精度地對隱式位置訪問進行推演和概率計算，同時還驗證了PI算法的高執(zhí)行效率。

圖6 算法運行時間對比

參考文獻(References)：

[1] HUO Z,MENG X,ZHANG R.Feel free to check-in:privacy alert against hidden location inference attacks in GeoSNs[C]//International Conference on Database Systems for Advanced Applications.Springer,Berlin,Heidelberg,2013:377-391.

[2] WANG H,WANG H,YI F,et al.Context-aware personalized path inference from large-scale GPS snippets[J].Expert Systems with Applications,2018,91:78-88.

[3] XUE A Y,ZHANG R,ZHENG Y,et al.Destination prediction by sub-trajectory synthesis and privacy protection against such prediction[C]//Data Engineering(ICDE),2013 IEEE 29th International Conference,Brisbane,2013:254-265.

[4] 李媛.基于位置的社交網(wǎng)絡(luò)推薦算法的研究與應(yīng)用[D].沈陽：中國科學院沈陽計算技術(shù)研究所,2015.

[5] 霍崢,孟小峰,黃毅.PrivateCheckIn:一種移動社交網(wǎng)絡(luò)中的軌跡隱私保護方法[J].計算機學報,2013,36(4):716-726.

[6] WICKER SB.The loss of location privacy in the cellular age[J].Communications of the ACM,2012,55(8):60-68.

[7] BAO JIE,HE TIANFU,RUAN SIJIE,et al.Planning bike lanes based on sharing-bike’s trajectories[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Halifax,2017:1377-1386.

[8] SADILEK A,KAUTZ H,BIGHAM J P.Finding your friends and following them to where you are[C]//Proceedings of the Fifth ACM International Conference on Web Search and Data Mining.Washington D.C,2012:723-732.

[9] 孫瑞.基于軌跡和POI數(shù)據(jù)的熱點區(qū)域?qū)崟r預(yù)測[D].長春：吉林大學,2017.

[10]陳勐,劉洋,王月,等.基于時序特征的移動模式挖掘[J].中國科學:信息科學,2016,46(9):1288-1297.

[12]WERNKE M,SKVORTSOV P,DüRR F,et al.A classification of location privacy attacks and approaches[J].Personal and Ubiquitous Computing,2014,18(1):163-175.

[13]ZHANG L,FANG C,LI Y,et al.Optimal strategies for defending location inference attack in database-driven CRNs[C]//Communications(ICC),2015 IEEE International Conference.London,2015:7640-7645.

[14]SONG Y,HU Z,LIU H,et al.A novel group recommendation algorithm with collaborative filtering[C]//Social Computing(SocialCom),2013 International Conference.Washington,DC,2013:901-904.

[15]YAP G E,LI X L,YU P.Effective next-items recommendation via personalized sequential pattern mining[C]//Database Systems for Advanced Applications.Springer Berlin/Heidelberg,2012:48-64.

[16]HUO Z,MENG X,HU H,et al.You can walk alone:trajectory privacy-preserving through significant stays protection[C]//International Conference on Database Systems for Advanced Applications.Springer,Berlin,Heidelberg,2012:351-366.

[17]YUAN Q,CONG G,MA Z,et al.Time-aware point-of-interest recommendation[C]//Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval,New York 2013:363-372.

[18]CHENG CHEN,YANG HAIQIN,KING I,et al.Fused matrix factorization with geographical and social influence in location-based social networks[C]//Proceedings of the 26th AAAI Conference on Artificial Intelligence,Toronto,2012:17-23.

[19]JIA YANTAO,WANG YUANZHUO,JIN XIAOLONG,et al.Location prediction:a temporal-spatial bayesian model[J].ACM Transactions on Intelligent Systems and Technology,2016,7(3):31.

[20]DASH M,KOO K K,GOMES J B,et al.Next place prediction by understanding mobility patterns[C]//Pervasive Computing and Communication Workshops(PerCom Workshops),2015 IEEE International Conference.St.Louis,2015:469-474.