印桂生，程偉杰，董宇欣，董紅斌，張萬松

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

?

使用軌跡指紋和地點相似性的地點推薦

印桂生，程偉杰，董宇欣，董紅斌，張萬松

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

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

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

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

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

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

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

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

1軌跡建模

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

1.1軌跡歷史表示

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

1.2停留點提取

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

1.3停留點聚類分析

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

2相似度計算

2.1用戶軌跡相似度

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

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

(1)

(2)

(3)

(4)

(5)

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

(6)

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

(7)

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

(8)

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

(9)

2.2地點相似度

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

(10)

(11)

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

(12)

(13)

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

3混合軌跡和地點相似性的推薦算法

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

(14)

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

(15)

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

4對比試驗和結(jié)果分析

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

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

4.2實驗評價指標

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

(16)

(17)

式中：Ru表示向用戶u推薦的地點集合,Tu表示在測試集中用戶u真實訪問過的地點集合。

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

(18)

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

4.3實驗參數(shù)的設(shè)定

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

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

4.4實驗結(jié)果及分析

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

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

圖2　DPPLS、PPLS和CS的準確率對比Fig. 2　Comparison of precision for DPPLS, PPLS and CS

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

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

從圖2可以看到,當K<6時,CS算法和PPLS算法比DPPLS算法在準確率低,當K≥6時,三者準確率趨于同一個值。

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

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

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

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

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

圖5　ULCF、UserCF和LocationCF的準確率對比Fig. 5　Comparison of precision for ULCF, UserCF and LocationCF

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

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

5結(jié)論

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

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

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

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

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

參考文獻：

[1]馬宇馳, 楊寧, 謝琳, 等, 基于軌跡時空關(guān)聯(lián)語義和時態(tài)熵的移動對象社會角色發(fā)現(xiàn)[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的用戶時空行為興趣相似性計算方法[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é)同過濾推薦算法[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

中圖分類號：TP391

文獻標志碼：A

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

doi:10.11990/jheu.201506035

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

基金項目：國家自然科學(xué)基金資助項目(61272186，61472095);黑龍江省自然科學(xué)基金資助項目(F201110);中央高?；A(chǔ)研究基金資助項目(HEUCF100604)；黑龍江博士后基金資助項目(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.