使用軌跡指紋和地點(diǎn)相似性的地點(diǎn)推薦

印桂生，程偉杰，董宇欣，董紅斌，張萬(wàn)松

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001)

?

使用軌跡指紋和地點(diǎn)相似性的地點(diǎn)推薦

印桂生，程偉杰，董宇欣，董紅斌，張萬(wàn)松

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001)

摘要：針對(duì)傳統(tǒng)的時(shí)空軌跡相似性度量算法中存在的計(jì)算復(fù)雜度高且不適于增量計(jì)算的問(wèn)題,提出了基于相似哈希計(jì)算用戶時(shí)空軌跡相似度的方法,同時(shí)使用逆軌跡頻率(ITF)度量位置流行度對(duì)軌跡相似性的影響,將用戶的歷史軌跡編碼為二進(jìn)制軌跡指紋,并根據(jù)海明距離判斷軌跡指紋之間的相似性,使得相似性計(jì)算可以在線性時(shí)間內(nèi)完成；此外,改進(jìn)了地點(diǎn)相似性算法,并將軌跡相似度和地點(diǎn)相似度相結(jié)合提出了基于地點(diǎn)和軌跡相似性的地點(diǎn)推薦算法。 實(shí)驗(yàn)結(jié)果表明，本文的推薦方法在準(zhǔn)確率、召回率和覆蓋率方面能夠取得較好的推薦效果,驗(yàn)證了所提方法的有效性。

關(guān)鍵詞：時(shí)空軌跡；軌跡相似性；軌跡指紋；地點(diǎn)流行度；地點(diǎn)推薦

隨著位置定位技術(shù)和無(wú)線通訊技術(shù)的發(fā)展,智能聯(lián)網(wǎng)設(shè)備將位置定位技術(shù)與移動(dòng)網(wǎng)絡(luò)技術(shù)相結(jié)合,為用戶提供了便利且無(wú)時(shí)無(wú)刻和無(wú)處不在的移動(dòng)服務(wù),這就使得收集反映用戶行為規(guī)律和興趣習(xí)慣的日常軌跡成為可能。通過(guò)移動(dòng)網(wǎng)絡(luò)技術(shù)收集的時(shí)空軌跡數(shù)據(jù)可以用于分析用戶的移動(dòng)特點(diǎn)和生活規(guī)律,從而深入理解用戶、位置以及兩者之間的相關(guān)關(guān)聯(lián)[1]。從最早的地理信息系統(tǒng)到現(xiàn)在的移動(dòng)網(wǎng)絡(luò)服務(wù),研究人員基于用戶歷史軌跡做了大量分析用戶和地理的研究[2]。在基于歷史軌跡理解用戶和地理空間的研究中,判斷地理軌跡的相似性[3]成為一個(gè)關(guān)鍵的問(wèn)題。因?yàn)?相似用戶更容易具有相似的行為偏好,而基于相似用戶向用戶推薦服務(wù)也是協(xié)同過(guò)濾的主要思想。因此,通過(guò)分析大量用戶的歷史軌跡[4],可以尋找與目標(biāo)用戶的歷史軌跡相似的用戶,從而可以為用戶提供基于位置的推薦服務(wù),例如推薦飯店、推薦旅行線路或者推薦朋友等。

傳統(tǒng)的基于軌跡的相似性計(jì)算都采用最長(zhǎng)公共子串[5-6]計(jì)算用戶歷史軌跡的相似性。該方法是極其費(fèi)時(shí)的,尤其是歷史軌跡較長(zhǎng)時(shí)問(wèn)題會(huì)變得更加嚴(yán)重,此外,軌跡的改變和增加都需要重新計(jì)算相似性,而在基于位置的社會(huì)網(wǎng)絡(luò)中,個(gè)人的時(shí)空軌跡是快速增加并且不斷演化的,這就使得計(jì)算成本急劇增加。在已有的計(jì)算軌跡相似性的方法中,為了節(jié)約時(shí)間和計(jì)算資源,不得不加入公共子串長(zhǎng)度的最大閾值來(lái)停止最大公共子串的檢測(cè)[5]。因此,在分析基于位置的社會(huì)網(wǎng)絡(luò)中的時(shí)空軌跡的時(shí)候迫切需要一種快速且適合海量數(shù)據(jù)和增量計(jì)算的相似度計(jì)算方法。

相似哈希[7-8]是局部敏感哈希的一種,由Moses Charikar[7]在2002年提出,是一種用單個(gè)哈希函數(shù)得到文檔最小哈希簽名,根據(jù)簽名計(jì)算文檔的相似性,去除重復(fù)網(wǎng)頁(yè)的方法。本文根據(jù)人們的地理軌跡的計(jì)算特點(diǎn),考慮地理位置在用戶的地理軌跡中的重要性,將比較歷史軌跡的相似性轉(zhuǎn)換為對(duì)歷史軌跡的簽名的比較,將公共字串計(jì)算轉(zhuǎn)換成二進(jìn)制碼的異或比較。

此外，在給用戶推薦地點(diǎn)的時(shí)候,還考慮了地點(diǎn)之間的相似度,通過(guò)綜合考慮用戶習(xí)慣的相似度和地點(diǎn)之間的相似度,提出了混合軌跡和地點(diǎn)相似性的推薦算法。

綜上,本文的工作主要是從GPS日志中提取用戶的有效停留點(diǎn),然后通過(guò)聚類停留點(diǎn)獲取用戶的一致的可比較的用戶軌跡歷史,進(jìn)而使用相似哈希獲取軌跡的二進(jìn)制指紋,將二進(jìn)制指紋之間的海明距離作為用戶的歷史軌跡之間的相似性。綜合考慮軌跡相似性和地點(diǎn)相似性,為用戶提供地點(diǎn)推薦服務(wù)。

1軌跡建模

一般GPS設(shè)備接收信號(hào)的平均周期比較短,這就造成GPS日志中記錄的GPS點(diǎn)非常密集,如果直接用于計(jì)算,將導(dǎo)致極大的計(jì)算量；此外,由于GPS日志中的GPS點(diǎn)的精度比較高,用戶在同一地點(diǎn)會(huì)產(chǎn)生多個(gè)GPS點(diǎn),如果直接使用GPS點(diǎn)計(jì)算用戶的相似性,就認(rèn)為2個(gè)用戶沒(méi)有訪問(wèn)共同的地點(diǎn),事實(shí)上,2個(gè)用戶訪問(wèn)的是同一個(gè)地點(diǎn)。因此,有必要將GPS日志中的GPS點(diǎn)進(jìn)行處理,提取能夠表示用戶生活習(xí)慣的有效停留點(diǎn),并進(jìn)一步使用基于密度的聚類算法,將所有用戶的停留點(diǎn)聚類形成可比較的停留區(qū)域。停留區(qū)域不僅可以為用戶提供可比較的軌跡數(shù)據(jù),同時(shí)可以獲取更豐富的語(yǔ)義信息。下面將簡(jiǎn)單介紹GPS日志的基本處理,包括停留點(diǎn)提取和停留區(qū)域聚類,具體的方法可以參考文獻(xiàn)[9]。

1.1軌跡歷史表示

GPS日志中的GPS坐標(biāo)一般包含經(jīng)緯度和采集時(shí)間等信息,首先需要從GPS日志中提取GPS坐標(biāo)點(diǎn),形成GPS軌跡歷史。這里只關(guān)注GPS坐標(biāo)點(diǎn)的經(jīng)緯度坐標(biāo)和采集時(shí)間,將包含經(jīng)緯度和采集時(shí)間的數(shù)據(jù)稱為GPS坐標(biāo)點(diǎn)。GPS坐標(biāo)點(diǎn)可以表示成p=(a,o,t),其中a為緯度,o為經(jīng)度,t為采集的時(shí)間。

1.2停留點(diǎn)提取

用戶的軌跡歷史中GPS坐標(biāo)點(diǎn)比較密集,并且包含大量不能反映用戶行為興趣和特點(diǎn)的噪聲數(shù)據(jù),不僅增加了計(jì)算量,而且干擾了對(duì)用戶真實(shí)行為的分析,因此需要從歷史軌跡中提取能真實(shí)反映用戶行為興趣和特點(diǎn)的GPS坐標(biāo)點(diǎn),并使用這些點(diǎn)表示用戶的歷史軌跡。如果用戶在某個(gè)區(qū)域內(nèi)停留超過(guò)了一定時(shí)間,可以認(rèn)為該用戶在該區(qū)域內(nèi)的GPS坐標(biāo)點(diǎn)屬于有效坐標(biāo)點(diǎn),可以使用該區(qū)域內(nèi)所有GPS坐標(biāo)點(diǎn)經(jīng)緯度的平均值作為該區(qū)域的停留點(diǎn)坐標(biāo),進(jìn)入該區(qū)域的時(shí)間戳作為該停留點(diǎn)的開(kāi)始時(shí)間,離開(kāi)該區(qū)域的時(shí)間戳作為該停留點(diǎn)的離開(kāi)時(shí)間。

1.3停留點(diǎn)聚類分析

在完成對(duì)每個(gè)用戶的停留點(diǎn)提取工作后需要對(duì)停留點(diǎn)進(jìn)行聚類分析,因?yàn)橥Ａ酎c(diǎn)是虛擬的坐標(biāo)點(diǎn),與用戶的實(shí)際行為相差很大,如果直接對(duì)停留點(diǎn)分析,則分析的準(zhǔn)確性大大降低。因此需要將所有用戶的停留點(diǎn)進(jìn)行聚類,形成一致的可比較的停留區(qū)域。在停留點(diǎn)聚類過(guò)程中,使用基于密度的聚類算法對(duì)停留點(diǎn)進(jìn)行聚類,之所以使用基于密度的聚類算法,是因?yàn)橄啾绕渌垲愃惴?該方法有助于檢測(cè)不規(guī)則形狀的聚類[5]。經(jīng)過(guò)聚類分析之后,可以將所有用戶的軌跡轉(zhuǎn)換為用停留區(qū)域表示的軌跡,該軌跡中的軌跡點(diǎn)就是聚類后的停留區(qū)域,這樣就可以通過(guò)用戶的軌跡歷史分析用戶之間的相似性了,具體的相似性計(jì)算方法將在下文給出。

2相似度計(jì)算

2.1用戶軌跡相似度

通過(guò)聚類分析得到了用戶的歷史軌跡,用戶經(jīng)歷過(guò)的地點(diǎn)在計(jì)算用戶興趣相似度所占的權(quán)重與它們?cè)跉v史軌跡所出現(xiàn)的次數(shù)成反比,出現(xiàn)次數(shù)越多的地方對(duì)于貢獻(xiàn)用戶興趣相似度所占的權(quán)重越小,反之,出現(xiàn)次數(shù)越少的地方對(duì)于貢獻(xiàn)用戶相似度所占的權(quán)重越大。借鑒IR系統(tǒng)中的逆文檔頻率,定義了逆軌跡頻率,用以反映每個(gè)地點(diǎn)對(duì)于用戶興趣的權(quán)重。

定義1 逆軌跡頻率(ITF)。逆軌跡頻率是軌跡中軌跡點(diǎn)的普遍重要性的度量,可以由總用戶數(shù)除以訪問(wèn)過(guò)該軌跡點(diǎn)的用戶的數(shù)目,再將得到的商取對(duì)數(shù),則軌跡點(diǎn)r的逆軌跡頻率為

(1)

(2)

(3)

(4)

(5)

通過(guò)以上的權(quán)重編碼逆映射規(guī)則,可以將用戶歷史軌跡權(quán)重轉(zhuǎn)換為二進(jìn)制編碼,即用戶u的第i條軌跡的興趣指紋為Fu,i：

(6)

得到用戶的興趣指紋之后,使用海明距離表示用戶之間的差異性。海明距離指興趣指紋的對(duì)應(yīng)比特取值不同的比特?cái)?shù),該值越小表示興趣指紋的差異越小。將海明距離歸一化處理后,可以得到軌跡x和y之間的差異率dx,y：

(7)

式中：H(Fu,x,Fv,y) 表示軌跡的海明距離。通過(guò)差異率,可以計(jì)算軌跡x和y之間的相似性如下：

(8)

用戶歷史軌跡的相似性通過(guò)計(jì)算用戶的所有軌跡之間的相似性獲得。用戶u和用戶v的軌跡相似性為

(9)

2.2地點(diǎn)相似度

在為用戶推薦地點(diǎn)的時(shí)候,不僅要考慮用戶軌跡之間的相似性,還要考慮地點(diǎn)之間的相似性。本文在計(jì)算相似度時(shí),不僅僅考慮用戶興趣相似度,而且也考慮地點(diǎn)之間的相似度。在計(jì)算地點(diǎn)相似度時(shí),本文借鑒基于物品的協(xié)同過(guò)濾的思想對(duì)地點(diǎn)相似度進(jìn)行計(jì)算。常見(jiàn)的計(jì)算物品相似性的方法有余弦相似度[10]和條件概率[11]等。條件概率的計(jì)算公式為

(10)

(11)

式(11)通過(guò)提高λ的值來(lái)緩解熱門物品i對(duì)于相似度計(jì)算的影響。但是該公式存在一定的局限性,其中λ的取值只能取一個(gè)固定值,并不能很好的區(qū)別不同物品的流行度,所以推薦效果有待提高。本文在計(jì)算地點(diǎn)相似度時(shí),充分考慮地點(diǎn)流行度這一因素,并對(duì)相似度進(jìn)行歸一化,以提高推薦的準(zhǔn)確度。λ的取值采用動(dòng)態(tài)的值,該值由2個(gè)地點(diǎn)的流行度決定。λ取值為地點(diǎn)i的流行度與地點(diǎn)i、地點(diǎn)j流行度之和的比值。即動(dòng)態(tài)懲罰地點(diǎn)流行度的相似度(dynamic penalized popular location similarity, DPPLS)計(jì)算方法如下：

(12)

(13)

經(jīng)過(guò)上面的改進(jìn)就可以對(duì)不同地點(diǎn)的流行度進(jìn)行考慮,動(dòng)態(tài)緩解熱門地點(diǎn)對(duì)于地點(diǎn)相似度計(jì)算的影響,相對(duì)于靜態(tài)的緩解熱門地點(diǎn)對(duì)于地點(diǎn)相似度的計(jì)算的影響更加有效,可以更好地提高推薦的準(zhǔn)確度。

3混合軌跡和地點(diǎn)相似性的推薦算法

在傳統(tǒng)的推薦系統(tǒng)中,一般基于用戶對(duì)物品的評(píng)分,向用戶推薦物品。評(píng)分一般分為兩種：顯示評(píng)分和隱式評(píng)分。顯示評(píng)分指用戶對(duì)物品直接給出的喜歡和不喜歡或者具體的分值等評(píng)價(jià),而隱式評(píng)分一般包括評(píng)語(yǔ)、在線瀏覽時(shí)間和購(gòu)買次數(shù)等。基于GPS軌跡無(wú)法獲取用戶對(duì)每個(gè)地點(diǎn)的顯示評(píng)分,因此只能使用隱式評(píng)分評(píng)估用戶對(duì)地點(diǎn)的興趣。在這里使用用戶對(duì)每個(gè)地點(diǎn)的訪問(wèn)次數(shù)作為用戶對(duì)某個(gè)地點(diǎn)的隱式評(píng)分。為了對(duì)不同用戶的訪問(wèn)次數(shù)進(jìn)行統(tǒng)一比較，需要將每個(gè)用戶的訪問(wèn)次數(shù)進(jìn)行歸一化處理。歸一化處理使用如下的公式計(jì)算：

(14)

已有的推薦算法僅僅考慮用戶相似度,或者僅僅考慮物品的相似度。本文將同時(shí)考慮用戶相似度和位置相似度,從而為用戶推薦更可能感興趣的地點(diǎn)。這里需要使用參數(shù)α和β決定2個(gè)相似性對(duì)推薦的影響權(quán)重,要求α+β=1。用戶u對(duì)軌跡點(diǎn)tr的潛在興趣可以表示為

(15)

式中：Tu表示用戶u所有訪問(wèn)過(guò)的地點(diǎn),Ur表示訪問(wèn)過(guò)軌跡點(diǎn)r的用戶的集合。這樣便可以獲得用戶對(duì)未訪問(wèn)過(guò)的地點(diǎn)的潛在興趣,從而可以向用戶推薦潛在興趣較大的Top-N地點(diǎn)，進(jìn)一步可以將推薦地點(diǎn)附近的飯店、商場(chǎng)等信息推薦給用戶。

4對(duì)比試驗(yàn)和結(jié)果分析

4.1數(shù)據(jù)集介紹

使用的數(shù)據(jù)集是微軟亞洲研究院提供的GPS數(shù)據(jù)集[14-15],其中包含用戶在2007年-2012年間的軌跡,在該數(shù)據(jù)集中每條GPS軌跡都是一系列的坐標(biāo)點(diǎn),其中每個(gè)坐標(biāo)點(diǎn)都是由經(jīng)度、維度和時(shí)間3種信息組成。本文將該數(shù)據(jù)集按照時(shí)序順序進(jìn)行了劃分，將前80%的數(shù)據(jù)用作訓(xùn)練集，將余下的20%的數(shù)據(jù)用作測(cè)試集，同時(shí)為了避免過(guò)耦合問(wèn)題，本文進(jìn)行了5次交叉確認(rèn)實(shí)驗(yàn)。

4.2實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)采用召回率和準(zhǔn)確率作為評(píng)價(jià)標(biāo)準(zhǔn)。準(zhǔn)確率和召回率是信息檢索和自然語(yǔ)言處理中經(jīng)常使用的評(píng)價(jià)指標(biāo)，也是評(píng)測(cè)推薦算法精度的常用指標(biāo)。準(zhǔn)確率(precision)和召回率(recall)分別表示推薦產(chǎn)品中用戶真實(shí)購(gòu)買產(chǎn)品的比例和用戶真實(shí)購(gòu)買產(chǎn)品中屬于推薦產(chǎn)品的比例:

(16)

(17)

式中：Ru表示向用戶u推薦的地點(diǎn)集合,Tu表示在測(cè)試集中用戶u真實(shí)訪問(wèn)過(guò)的地點(diǎn)集合。

覆蓋率描述推薦系統(tǒng)發(fā)掘長(zhǎng)尾物品的能力，一般指推薦系統(tǒng)所推薦的地點(diǎn)占系統(tǒng)中所有地點(diǎn)的比例。該比例越高,表明推薦系統(tǒng)的覆蓋率越高,長(zhǎng)尾地點(diǎn)被用戶訪問(wèn)的概率也越大。覆蓋率(coverage)計(jì)算公式如下

(18)

式中：Ru表示向用戶u推薦的地點(diǎn)集合,L表示系統(tǒng)中所有的地點(diǎn)集合。

4.3實(shí)驗(yàn)參數(shù)的設(shè)定

在實(shí)驗(yàn)中，提取停留點(diǎn)算法有2個(gè)重要的參數(shù)：時(shí)間閾值和距離閾值。如果時(shí)間閾值和距離閾值選取的太小,則會(huì)生成很多的停留點(diǎn),這些停留點(diǎn)中存在很多無(wú)意義的噪音數(shù)據(jù)。如果時(shí)間閾值和距離閾值太大,停留點(diǎn)就會(huì)太少,精度就會(huì)減小。

根據(jù)文獻(xiàn)[5]設(shè)定時(shí)間閾值為30 min,停留點(diǎn)距離閾值為200 m,在聚類分析時(shí),DBSCAN算法半徑設(shè)定為500 m,簇內(nèi)最少停留點(diǎn)個(gè)數(shù)設(shè)定為2。

4.4實(shí)驗(yàn)結(jié)果及分析

將本文的動(dòng)態(tài)懲罰地點(diǎn)流行度的相似度方法(DPPLS)與余弦相似度方法(CS)[10]和懲罰地點(diǎn)流行度的相似度方法(PPLS)[12-13]進(jìn)行對(duì)比。該組實(shí)驗(yàn)是為了驗(yàn)證動(dòng)態(tài)懲罰地點(diǎn)流行度的相似度方法在計(jì)算地點(diǎn)的相似上是否比傳統(tǒng)的余弦相似度方法、懲罰地點(diǎn)流行度的相似度方法表現(xiàn)出色。為了對(duì)比3種方法的效果，將相似度用于地點(diǎn)推薦中，根據(jù)推薦算法的召回率、準(zhǔn)確率和覆蓋率進(jìn)行比較。具有較高推薦精確度并且能夠覆蓋較多地點(diǎn)的相似度方法被認(rèn)為是較好的相似度分析算法(具體結(jié)果如圖1～3)。

圖1　DPPLS、PPLS和CS的召回率對(duì)比Fig. 1　Comparison of recall for DPPLS, PPLS and CS

圖2　DPPLS、PPLS和CS的準(zhǔn)確率對(duì)比Fig. 2　Comparison of precision for DPPLS, PPLS and CS

圖3　DPPLS、PPLS和CS的覆蓋率對(duì)比Fig. 3　Comparison of coverage for DPPLS, PPLS and CS

從圖1可以看到,CS算法和PPLS算法比DPPLS算法在召回率方面要低,當(dāng)K≥6時(shí)三者召回率趨于同一個(gè)值。

從圖2可以看到,當(dāng)K<6時(shí),CS算法和PPLS算法比DPPLS算法在準(zhǔn)確率低,當(dāng)K≥6時(shí),三者準(zhǔn)確率趨于同一個(gè)值。

從圖3可以看到,CS算法和PPLS算法的覆蓋率要比DPPLS算法低很多,表明本文提出的DPPLS算法要比CS算法和PPLS算法在推薦長(zhǎng)尾地點(diǎn)的能力強(qiáng)。

以下對(duì)比的是基于用戶的協(xié)同過(guò)濾(UserCF)、基于位置的協(xié)同過(guò)濾(LocationCF)和基于用戶和位置的混合協(xié)同過(guò)濾(ULCF)在召回率和準(zhǔn)確率方面的對(duì)比。

如圖4和5所示,推薦的召回率和準(zhǔn)確率并不和參數(shù)K成線性關(guān)系。UserCF算法、LocationCF算法和ULCF算法都在隨著K值的增大呈現(xiàn)逐漸減小的趨勢(shì)。本文提出的ULCF算法在召回率和準(zhǔn)確率方面都要高出UserCF算法和LocationCF算法。

如圖6所示,LocationCF算法隨著K值的變大覆蓋率先變小后變大。UserCF和ULCF算法都在隨著K值變大覆蓋率先變大后變小,并且ULCF算法的覆蓋率在K大于4后顯著強(qiáng)于UserCF和LocationCF算法。

圖4　ULCF、UserCF和LocationCF的召回率對(duì)比Fig. 4　Comparison of recall for ULCF, UserCF and LocationCF

圖5　ULCF、UserCF和LocationCF的準(zhǔn)確率對(duì)比Fig. 5　Comparison of precision for ULCF, UserCF and LocationCF

圖6　ULCF、UserCF和LocationCF的覆蓋率對(duì)比Fig. 6　Comparison of coverage for ULCF, UserCF and LocationCF

綜上,ULCF算法在K值為3時(shí), 召回率、準(zhǔn)確率和覆蓋率都取得相對(duì)較好的性能。通過(guò)實(shí)驗(yàn)表明,使用相似哈希計(jì)算用戶的軌跡相似性是可行的,并且通過(guò)混合軌跡相似性和地點(diǎn)相似性可以為用戶提供比較好的推薦服務(wù)。

5結(jié)論

本文針對(duì)傳統(tǒng)的基于時(shí)空軌跡數(shù)據(jù)分析用戶的相似性的方法中存在的問(wèn)題，研究了使用相似哈希分析用戶軌跡的相似性的方法，同時(shí)考慮地點(diǎn)流行度對(duì)地點(diǎn)相似性的影響，提出了混合軌跡相似性和動(dòng)態(tài)懲罰流行度的地點(diǎn)相似性的方法，根據(jù)該相似性提供個(gè)性化的地點(diǎn)推薦服務(wù)，得到如下結(jié)論：

1)使用相似哈希的方法能夠加快軌跡數(shù)據(jù)的分析，提高軌跡計(jì)算的效率；

2)考慮地點(diǎn)的流行度動(dòng)態(tài)懲罰熱門地點(diǎn)在地點(diǎn)相似性計(jì)算中的權(quán)重能夠顯著提高地點(diǎn)推薦的準(zhǔn)確度；

3)將軌跡的相似性與地點(diǎn)的相似性相結(jié)合，能夠比單獨(dú)使用軌跡相似性和地點(diǎn)相似性取得更好的推薦效果。

本文進(jìn)一步的研究工作如下:用戶訪問(wèn)某個(gè)地點(diǎn),不只取決于自己的興趣,還受用戶好友的影響,需要分析用戶的好友關(guān)系對(duì)用戶興趣的影響權(quán)重。

參考文獻(xiàn)：

[1]馬宇馳, 楊寧, 謝琳, 等, 基于軌跡時(shí)空關(guān)聯(lián)語(yǔ)義和時(shí)態(tài)熵的移動(dòng)對(duì)象社會(huì)角色發(fā)現(xiàn)[J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 49(10): 2153-2160.

MA Yuchi, YANG Ning, XIE Lin, et al. Social roles discovery of moving objects based on spatial-temporal associated semantics and temporal entropy of trajectories[J]. Journal of computer research and development, 2012, 49(10): 2153-2160.

[2]LI Mu, AHMED A, SMOLA A J. Inferring movement trajectories from GPS snippets[C]//Proceedings of the Eighth ACM International Conference on Web Search and Data Mining. New York, USA, 2015: 325-334.

[3]ZHONG Haidong, ZHANG Shaozhong, WANG Yanling. Mining users' similarity from moving trajectories for mobile e-commerce recommendation[J]. International journal of hybrid information technology, 2014, 7(4): 309-320.

[4]李曉靜, 張曉濱. 基于LCS的用戶時(shí)空行為興趣相似性計(jì)算方法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2013, 49(20): 251-254.

LI Xiaojing, ZHANG Xiaobin. Computing user similarity of spatio-temporal behaviour and interests based on LCS[J]. Computer engineering and applications, 2013, 49(20): 251-254.

[5]LI Quannan, ZHENG Yu, XIE Xing, et al. Mining user similarity based on location history[C]//Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, USA, 2008.

[6]YING J J C, LU E H C, LEE W C, et al. Mining user similarity from semantic trajectories[C]//Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Location Based Social Networks. New York, USA, 2010: 19-26.

[7]CHARIKAR M S. Similarity estimation techniques from rounding algorithms[C]//Proceedings of the thiry-fourth Annual ACM Symposium on Theory of Computing. New York, USA, 2002: 380-388.

[8]SADOWSKI C, LEVIN G. Simhash: Hash-based similarity detection[R]. Technical Report, Google, 2007: 1-10.

[9]ZHENG Yu, ZHOU Xiaofang. Computing with spatial trajectories[M]. New York, USA: Springer, 2011: 243-325.

[10]ADOMAVICIUS G, TUZHILIN A. Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions[J]. IEEE transactions on knowledge and data engineering, 2005, 17(6): 734-749.

[11]KITTS B, FREED D, VRIEZE M. Cross-sell: a fast promotion-tunable customer-item recommendation method based on conditionally independent probabilities[C]//Proceedings of the sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA, 2000: 437-446.

[12]DESHPANDE M, KARYPIS G. Item-based top-N recommendation algorithms[J]. ACM transactions on information systems, 2004, 22(1): 143-177.

[13]邢春曉, 高鳳榮, 戰(zhàn)思南. 適應(yīng)用戶興趣變化的協(xié)同過(guò)濾推薦算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2007, 44(2): 296-301.

XING Chunxiao, GAO Fengrong, ZHAN Si'nan. A collaborative filtering recommendation algorithm incorporated with user interest change[J]. Journal of computer research and development, 2007, 44(2): 296-301.

[14]ZHENG Yu, ZHANG Lizhu, XIE Xing, et al. Mining interesting locations and travel sequences from GPS trajectories[C]//Proceedings of the 18th international conference on World wide web. New York, USA, 2009: 791-800.

[15]ZHEGN Yu, LI Quannan, CHEN Yukun, et al. Understanding mobility based on GPS data[C]//Proceedings of the 10th International Conference on Ubiquitous Computing. New York, USA, 2008: 312-321.

Location recommendation using trajectory fingerprints and location similarity

YIN Guisheng, CHENG Weijie, DONG Yuxin, DONG Hongbin, ZHANG Wansong

(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)

Abstract：In order to solve the problem of the high computational complexity and inapplicability to incremental computing of traditional spatial-temporal trajectory similarity measurements, in this paper we propose a simHash-based method to measure the similarity between different users' spatial-temporal trajectories, which also consider the influence of location popularity on the trajectories' similarities by using the locations' inverse trajectory frequency (ITF). With this method, users' trajectories are initially transformed into binary trajectory fingerprints. We use the Hamming distance to determine the similarity of the users' trajectories, and the similarity calculation can be finished within linear time. In addition, we propose an improved location similarity algorithm and combine the location similarity with the trajectory similarity to generate interesting location recommendations. Compared with the existing method, the experimental results verify the effectiveness of the proposed method and demonstrate that it has better performance with respect to precision, recall, and coverage.

Keywords：spatial-temporal trajectory; trajectory similarity; trajectory fingerprint; location popularity; location recommendation

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1006-7043(2016)03-414-06

doi:10.11990/jheu.201506035

作者簡(jiǎn)介：印桂生(1964-),男,教授,博士生導(dǎo)師.通信作者：印桂生,E-mail: yinguisheng@hrbeu.edu.cn.

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61272186，61472095);黑龍江省自然科學(xué)基金資助項(xiàng)目(F201110);中央高?；A(chǔ)研究基金資助項(xiàng)目(HEUCF100604)；黑龍江博士后基金資助項(xiàng)目(LBH-Z12068).

收稿日期：2015-06-11.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20151218.1051.004.html

網(wǎng)絡(luò)出版日期：2015-12-18.