一種基于位置和時間信息的興趣點推薦方法

譚 偉,賈朝龍,桑春艷

(重慶郵電大學(xué) 軟件工程學(xué)院,重慶 400065)

在當(dāng)今信息化時代,隨著互聯(lián)網(wǎng)技術(shù)和定位技術(shù)的飛速發(fā)展以及社會經(jīng)濟(jì)的快速發(fā)展,人們選擇出行的方式以出行的地點越來越廣泛。人們的興趣點(POI,point of interest)如:旅游景點、電影院、博物館、餐廳等也不斷增加,然而,面對大量的POIs,人們?nèi)绾胃鶕?jù)個人喜好快速選擇與自己興趣相關(guān)的興趣點成為了用戶的一個難題?；谶@樣的環(huán)境下,基于位置的社交化網(wǎng)絡(luò)(LBSNs,location-based social networks)推薦技術(shù)及其相關(guān)的應(yīng)用服務(wù)應(yīng)運而生,目前比較流行的LBSNs有Foursquare、Gowalla、Geo Life、微信朋友圈等[1]。

在基于位置的社交網(wǎng)絡(luò)(LBSNs)中,鼓勵用戶分享自己每天的信息,如:行程信息、位置信息、POI簽到信息以及其它的相關(guān)信息[2]。用戶訪問過的POIs的相關(guān)信息(如簽到時間、經(jīng)緯度、日期等)可以通過顯示和隱式的方式同時獲得,即用戶到達(dá)一個POI之后的簽到行為和手機(jī)的自動定位功能,而這些信息又可以被其好友(其他用戶)共享[3]。使用用戶以及POIs的相關(guān)信息,就能夠?qū)τ脩敉扑]用戶未曾訪問過的POIs。而協(xié)同過濾是推薦系統(tǒng)比較流行的方法,協(xié)同過濾主要是通過不同的用戶對項目的評分以及用戶或項目之間的相似度來給用戶推薦項目[4]。

筆者提出一種根據(jù)位置和時間信息的POI推薦方法。根據(jù)用戶的歷史出行地點的簽到信息數(shù)據(jù),通過分析地點簽到信息的地理信息,使用出行地點簽到時間及簽到數(shù)量來計算POI的流行度,最后根據(jù)綜合分析POIs地理信息和流行度來向用戶推薦用戶未曾訪問過的POIs。研究得:

1)研究使用POIs的位置信息(經(jīng)度、緯度)計算POIs之間的距離,然后根據(jù)距離信息計算POIs之間的相似度,距離越遠(yuǎn)相似度越低。

2)使用POIs在不同時間被簽到的數(shù)量來計算POIs的流行度,將一天劃分為不同的時間段,分別計算POIs在每個時間段被簽到的數(shù)量,數(shù)量越大表示該POIs在該時間點的流行度越高,最后根據(jù)POIs在各個不同時間點的流行度計算POIs之間的相似度。

3)根據(jù)位置和時間信息融合1)、2)中計算出的POIs之間的相似度,最終計算出不同POIs的整體相似度來向用戶推薦新的POIs,并且分析了不同占比對實驗結(jié)果的影響效果。

1 相關(guān)工作

基于位置信息的推薦方法,基于時間信息的推薦方法和基于位置時間信息的推薦方法。

1)基于位置信息的推薦方法。在LBSNs中,用戶和POIs的位置信息對于興趣點推薦是一個比較重要的因素,因為用戶更加傾向于訪問離自己比較近的POIs。文獻(xiàn)[5-7]使用冪律分布函數(shù)計算用戶從當(dāng)前POI訪問下一POI的概率;文獻(xiàn)[8-10]使用高斯分布函數(shù)計算用戶從當(dāng)前POI訪問下一POI的概率;文獻(xiàn)[11-13]使用核密度估計來建模地理位置影響。

2)基于時間信息的推薦方法。時間信息對于POI推薦來說是一個非常重要的因素,因為用戶出行地點是根據(jù)時間的變化而改變的。文獻(xiàn)[14-16]都是使用時間信息將一天分為24 h或者上午、下午、晚上、傍晚等,然后使用協(xié)同過濾相關(guān)的一些推薦方法產(chǎn)生POIs推薦。文獻(xiàn)[17]從POIs的角度出發(fā),使用時間信息將一天均等分為12份,即12個時間戳,統(tǒng)計所有POIs在不同時間戳的被簽到的次數(shù),然后以向量的方式表示每個POI,使用時間信息以向量的方式計算POIs之間的相似度,最后以Top-N的方式產(chǎn)生推薦。文獻(xiàn)[18]從用戶的角度出發(fā),在基于用戶的協(xié)同過濾(User-based collaborative filtering)的基礎(chǔ)上,使用改進(jìn)后的余弦相似度計算POIs的相似度。首先使用K-means算法將所有用戶分為活躍用戶和不活躍用戶,對于活躍用戶,根據(jù)用戶在一天24 h(均等分為24個時間戳)的簽到情況產(chǎn)生POIs推薦;對于不活躍用戶,根據(jù)用戶在一天中的簽到情況產(chǎn)生POIs推薦。

3)基于位置時間信息的推薦方法。現(xiàn)有的一些方法從用戶的角度出發(fā),使用位置和時間信息綜合分析產(chǎn)生POIs推薦。文獻(xiàn)[6]從用戶的角度出發(fā),在基于用戶的協(xié)同過濾的基礎(chǔ)上進(jìn)行改進(jìn),依次融入POIs在不同時間是否有被簽到記錄以及位置信息后計算興趣點的評分,最后以Top-N的方式向目標(biāo)用戶推薦新的POIs。文獻(xiàn)[19]從用戶的角度出發(fā),根據(jù)用戶的歷史簽到情況采用模糊C均值(Fuzzy C-means)算法將用戶分為活躍用戶和不活躍用戶,對于活躍用戶,根據(jù)用戶在一天中不同時間的簽到記錄,提出二維(POIs的經(jīng)緯度)高斯核密度估計算法計算相似度產(chǎn)生POIs推薦;對于不活躍用戶,使用一維(POIs之間的距離)冪律分布函數(shù)的方式計算相似度產(chǎn)生推薦。

2 基于位置和時間信息的興趣點推薦方法

2.1 問題描述

主要研究的問題是從POIs的角度出發(fā)分為3個步驟,首先,使用POIs的位置信息(經(jīng)度和緯度)計算用戶歷史訪問和未曾訪問過的地點的相似度;然后,使用時間信息統(tǒng)計POIs在一天內(nèi)不同時間段被簽到的次數(shù),以向量的形式表示每個POIs,計算用戶歷史訪問和未曾訪問過的地點的相似度;最后使用位置和時間信息綜合分析計算整體相似度,即估算出目標(biāo)用戶對未曾訪問過的POIs的訪問概率,進(jìn)而對目標(biāo)用戶進(jìn)行POIs推薦。

假設(shè)U={u1,u2,…,un}為用戶集合,L={l1,l2,…,ln}為POIs集合。使用位置和時間信息計算出目標(biāo)用戶u可能訪問所有未曾訪問過的POIs的概率,以Top-N的方式向目標(biāo)用戶u進(jìn)行POIs推薦。

2.2 使用位置信息進(jìn)行相似度建模

在社交網(wǎng)絡(luò)中,地理信息是一個比較重要的因素。在現(xiàn)實生活中,相對于較遠(yuǎn)的興趣點,人們往往會更加傾向于選擇訪問離自己位置更近的興趣點,如圖1所示,圖1展示了Foursquare數(shù)據(jù)集中興趣點的位置信息分布情況,從圖1中可以看出興趣點分布在很多區(qū)域,大部分?jǐn)?shù)據(jù)都集中在分布在幾個比較集中的群集里面,這說明人們更加傾向于訪問距離比較近的興趣點。所以將地理位置信息融入到的興趣點推薦方法中,在單考慮地理位置信息影響時,用戶訪問下一個興趣點的概率與用戶所在興趣點和下一個興趣點之間的距離成反比,即距離越遠(yuǎn)用戶訪問的概率越小,用公式(1)計算用戶訪問下一興趣點的概率。

圖1 Foursquare數(shù)據(jù)集中興趣點分布情況Fig.1 Distribution of interest points in foursquare dataset

2.3 融入時間信息進(jìn)行相似度建模

在現(xiàn)實社會中,人們在不同的時間點會根據(jù)實際的情況訪問不同的地方,如圖2所示,圖2展示了Foursquare數(shù)據(jù)集中2個隨機(jī)POIs在一天24 h各個不同時間地點被用戶簽到的次數(shù),從圖2中可以看出:興趣點L1在8～12 h和13～17 h這2個時間段被簽到頻率比較高,這說明L1可能是某辦公地點,因為在現(xiàn)實生活中這個時間段為上班時間;興趣點L2在10～12 h和18～20 h這2個時間段被簽到的頻率比較高,其中18～20 h這個時間段的頻率最高,這說明L2可能是某娛樂場所。

圖2 Foursquare 2個興趣點簽到分布Fig.2 Foursquare sign in distribution of 2 interest points

通過上述分析以及考慮到在實際中用戶的簽到行為,將用戶的簽到時間按照不同的時間段進(jìn)行分段處理,統(tǒng)計在不同時間段興趣點被用戶簽到的次數(shù)。從圖2可以看出,興趣點在白天的被簽到的次數(shù)往往較多,而在深夜以及凌晨時間段的被簽到的次數(shù)較少,因此將1天24 h進(jìn)行不同時間段的劃分,如表1所示。然后統(tǒng)計每個POI在不同時間段被簽到的次數(shù),以矩陣的形式表示所有POIs在不同時間段被簽到的情況,如表2所示。

表1 時間段劃分Table 1 Time period division

表2 POIs時間矩陣Table 2 POIs time matrix

為了得到更好的推薦效果,將上述矩陣數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)縮放,常用的標(biāo)準(zhǔn)縮放有歸一化和標(biāo)準(zhǔn)化處理,由于考慮到采用的數(shù)據(jù)量比較大(Foursquare數(shù)據(jù)的興趣點簽到記錄有194 108條),而歸一化處理容易受到異常點的影響大,其魯棒性較差,適合傳統(tǒng)精確小數(shù)據(jù)的場景,所以采用標(biāo)準(zhǔn)化的方式處理上述矩陣數(shù)據(jù)。計算公式如下

經(jīng)過標(biāo)準(zhǔn)化之后,以向量的形式表示每個興趣點[17],如公式6,Cv(li)表示興趣點li在每個時間點的被簽到情況。使用時間信息計算興趣點之間的相似度的計算公式如下

綜合考慮興趣點的位置信息和時間信息,以整體的方式計算興趣點之間的相似度,計算公式如公式(7)所示,其中α為參數(shù),取值區(qū)間為(0,1),表示位置信息和時間信息的不同占比。

在向目標(biāo)用戶推薦新的興趣點時,將興趣點劃分為用戶訪問過和用戶未曾訪問過的2個集合,將用戶訪問過的集合作為用戶的特征集合,統(tǒng)計計算特征集合中所有興趣點在一天中被簽到的次數(shù),選取前k個興趣點作為用戶的特征興趣點。計算前k個用戶訪問過的興趣點與所有用戶未曾訪問過的興趣點的相似度,最后以Top-N的方式向目標(biāo)用戶推薦前N個興趣點集合。

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)集

實驗的數(shù)據(jù)采用來自真實世界的數(shù)據(jù)集,這些數(shù)據(jù)來自于Foursquare真實數(shù)據(jù)集[6],Foursquare數(shù)據(jù)集采集的是2010年8月到2011年7月用戶在新加坡的簽到數(shù)據(jù),數(shù)據(jù)中一共包括2 321名用戶,5 596個簽到興趣點以及194 108條簽到記錄。Foursquare數(shù)據(jù)集信息含有用戶ID、興趣點ID、興趣點的經(jīng)度和緯度以及用戶在興趣點的簽到時間。數(shù)據(jù)集的相關(guān)內(nèi)容如表2所示。

表2 實驗數(shù)據(jù)集Table 2 Experimental data set

3.2 評估方法

準(zhǔn)確率(Precision)和召回率(Recall)是TOP-N推薦的重要評價指標(biāo),故采用準(zhǔn)確率和回歸率來評估提出的推薦算法的性能,對目標(biāo)用戶u推薦結(jié)果的準(zhǔn)確率和召回率計算公式如下

其中:Pu@n表示向目標(biāo)用戶u推薦前N個興趣點時的準(zhǔn)確率;Ru@n表示向目標(biāo)用戶u推薦前N個興趣點時的召回率;TPu表示向目標(biāo)用戶u推薦正確的興趣點的數(shù)量;FPu表示向目標(biāo)用戶u推薦錯誤的興趣點的數(shù)量;FNu表示向目標(biāo)用戶u沒有推薦到的興趣點的數(shù)量。

整體的準(zhǔn)確率和召回率計算公式如下

其中:Pall表示最終推薦算法的準(zhǔn)確率;Rall表示最終推薦算法的召回率;表示在訓(xùn)練集和測試集中都存在的用戶的數(shù)量。

3.3 實驗結(jié)果分析

3.3.1 使用位置信息推薦效果

在實驗中,設(shè)置用戶的訪問過的興趣點的特征興趣點數(shù)量k為k={1,2,3,4,5,6,7},產(chǎn)生的興趣點推薦數(shù)量N為N={10,20,30},實驗結(jié)果的準(zhǔn)確率和召回率如圖3和圖4所示。

圖3 不同k值和N值的準(zhǔn)確率Fig.3 Accuracy of different K and N values

圖4 不同k值和N值的召回率Fig.4 Recall rates for different K and N values

從實驗結(jié)果中可以看出,興趣點推薦數(shù)量固定不變時,當(dāng)k取值在1～6時,推薦結(jié)果的準(zhǔn)確率和召回率基本上都是隨著k的增加而增加,但當(dāng)k取值從6調(diào)整到7時,實驗結(jié)果的準(zhǔn)確率和召回率基本都有所下降,k取值為6時,產(chǎn)生的推薦效果比較好;k固定不變時,實驗結(jié)果的準(zhǔn)確率隨著興趣點推薦數(shù)量的增加而下降,實驗結(jié)果的召回率隨著興趣點推薦數(shù)量的增加而增加。

3.3.2 加入時間因素后推薦效果

在實驗中,設(shè)置用戶的訪問過的興趣點的特征興趣點數(shù)量k為6,產(chǎn)生的興趣點推薦數(shù)量N為N={10,20,30},實驗結(jié)果的準(zhǔn)確率和召回率如圖5和圖6所示。

圖5 不同α值的準(zhǔn)確率Fig.5 DifferentαAccuracy of values

圖6 不同α值的召回率Fig.6 DifferentαRecall rate of values

從實驗結(jié)果中可以看出,興趣點推薦數(shù)量為10時,α的取值為0.1時,實驗結(jié)果的準(zhǔn)確率較高;興趣點推薦數(shù)量為20時,α的取值為0.1和0.9時,實驗結(jié)果的準(zhǔn)確率較高;興趣點推薦數(shù)量為30時,α的取值為0.1和0.9時,實驗結(jié)果的準(zhǔn)確率較高。綜合考慮準(zhǔn)確率召回率以及興趣點推薦數(shù)量,當(dāng)α的取值為0.1時實驗結(jié)果的效果比較好。

3.3.3 基于位置信息和融入時間信息后的比較

為了驗證融入時間信息后的效果比未融入時間信息的效果即僅使用位置信息好,綜合考慮了不同情況下的選取用戶不同特征興趣點數(shù)量和進(jìn)行不同數(shù)目的推薦興趣點的準(zhǔn)確率和召回率,采取平均值的方式,即不同情況下的平均準(zhǔn)確率和平均召回率,將兩種方式進(jìn)行了實驗對比。LB表示僅使用位置信息的建模,LTB表示融入時間信息后的建模。實驗對比結(jié)果如圖7和圖8所示:

圖7 是否融入時間信息的準(zhǔn)確率對比Fig.7 Whether to integrate the accuracy comparison of time information

圖8 是否融入時間信息的召回率對比Fig.8 Recall rate comparison whether time information is integrated

從對比實驗結(jié)果中可以看出,無論是準(zhǔn)確率和召回率,在融入時間信息后的效果都要比僅使用位置信息的效果好,這說明在使用位置信息的建模中融入時間信息后進(jìn)行建模效果更佳。在準(zhǔn)確率上,推薦的興趣點為Top-10時,融入時間信息后準(zhǔn)確率提高了0.6%,推薦興趣點為Top-20和Top-30時,融入時間信息后準(zhǔn)確率提高了0.1%;在召回率上,推薦興趣點為Top-10、Top-20和Top-30時,融入時間信息后召回率平均提高了0.1%。從而說明提出的基于位置和時間信息的興趣點推薦方法是有效的。

4 結(jié)束語

基于興趣點的位置和時間信息,提出了一種基于位置和時間信息的興趣點推薦方法。從興趣點的角度出發(fā),綜合分析興趣點的位置信息和興趣點在一天中不同時間段被簽到的情況,使用這些信息計算興趣點之間的相似度,以Top-N的方式向目標(biāo)用戶推薦新的興趣點集合,實驗結(jié)果表明,研究提出的方法是有效的。在未來的工作中,考慮融入更多有關(guān)用戶和興趣點的信息以得到更好的推薦效果,如用戶的朋友和社交關(guān)系以及興趣點的類別和評論信息等。