融合地點(diǎn)影響力的興趣點(diǎn)推薦算法

許朝 孟凡榮 袁冠 李月娥 劉肖

摘 要：為解決興趣點(diǎn)（POI）推薦不準(zhǔn)確和效率低的問題，深入分析社交因素和地理位置因素的影響，提出了一種融合地點(diǎn)影響力的POI推薦算法。首先，為了解決簽到數(shù)據(jù)稀疏的問題，將2度好友引入?yún)f(xié)同過濾算法中構(gòu)建了社交影響模型，通過計(jì)算經(jīng)歷和好友相似度獲取2度好友對(duì)用戶的社交影響;其次，深入考慮地理位置因素對(duì)POI推薦影響，在對(duì)社交網(wǎng)絡(luò)分析的基礎(chǔ)上構(gòu)造了地點(diǎn)影響力模型，通過PageRank算法發(fā)現(xiàn)用戶影響力，結(jié)合POI被簽到次數(shù)計(jì)算地點(diǎn)影響力，獲取準(zhǔn)確的整體位置偏好，并使用核密度估計(jì)方法對(duì)用戶簽到行為建模和獲取個(gè)性化地理位置特征;最后，融合社交模型和地理位置模型提高推薦準(zhǔn)確性，并通過構(gòu)造POI推薦候選集來提高推薦效率。在Gowalla和Yelp簽到數(shù)據(jù)集上實(shí)驗(yàn)，結(jié)果表明所提算法能夠快速完成POI推薦，在準(zhǔn)確率和召回率指標(biāo)上明顯優(yōu)于融合時(shí)間因素的位置推薦（LRT）和融合地理社交因素的個(gè)性化位置推薦（iGSLR）算法。

關(guān)鍵詞：興趣點(diǎn)推薦;基于位置的社交網(wǎng)絡(luò);協(xié)同過濾算法;地點(diǎn)影響力;核密度估計(jì)

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

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

PointofInterest recommendation algorithm combining location influence

XU Chao1，2， MENG Fanrong1， YUAN Guan1*， LI Yuee2， LIU Xiao1

1.College of Computer Science and Technology， China University of Mining and Technology， Xuzhou Jiangsu 221116， China;

2.Archives， China University of Mining and Technology， Xuzhou Jiangsu 221116， China

Abstract：

Focused on the issue that PointOfInterest （POI） recommendation has low recommendation accuracy and efficiency， with deep analysis of the influence of social factors and geographical factors in POI recommendation， a POI recommendation algorithm combining location influence was presented. Firstly， in order to solve the sparseness of signin data， the 2degree friends were introduced into the collaborative filtering algorithm to construct a social influence model， and the social influence of the 2degree friends on the users were obtained by calculating experience and friend similarity. Secondly， by deep consideration of the influence of geographical factors on POI， a location influence model was constructed based on the analysis of social networks. The users influences were discovered through the PageRank algorithm， and the location influences were calculated by the POI signin frequency， obtaining overall geographical preference. Moreover， kernel density estimation method was used to model the users signin behaviors and obtain the personalized geographical features. Finally， the social model and the geographic model were combined to improve the recommendation accuracy， and the recommendation efficiency was improved by constructing the candidate POI recommendation set. Experiments on Gowalla and Yelp signin datasets show that the proposed algorithm can quickly recommend POIs for users， and has high accuracy and recall rate than Location Recommendation with Temporal effects （LRT） algorithm and iGSLR （Personalized GeoSocial Location Recommendation） algorithm.

Key words：

pointofinterest recommendation; locationbased social network; collaborative filtering algorithm; location influence; kernel density estimation

0?引言

隨著網(wǎng)絡(luò)技術(shù)和移動(dòng)對(duì)象定位技術(shù)的進(jìn)步，基于位置的社交網(wǎng)絡(luò)（LocationBased Social Network， LBSN）得到了快速的發(fā)展，為人們提供了極其便利的位置服務(wù)。典型的LBSN應(yīng)用有Foursquare、Gowalla和大眾點(diǎn)評(píng)等，這些應(yīng)用主要包括位置推薦、位置簽到、位置評(píng)論和位置共享等功能[1-2]。在LBSN中，為用戶推薦可能感興趣的地理位置的服務(wù)被稱為興趣點(diǎn)（PointOfInterest， POI）推薦。POI推薦對(duì)促進(jìn)旅游、商家營銷推薦、研究用戶的活動(dòng)模式和生活規(guī)律具有重要意義。

協(xié)同過濾算法被廣泛應(yīng)用于軌跡聚類[3]和位置預(yù)測(cè)算法中，大量的興趣點(diǎn)推薦算法[4-6]在協(xié)同過濾算法的基礎(chǔ)上，通過考慮社交和地理位置等諸多因素的影響來提升推薦效果， 然而，這些算法普遍存在以下兩個(gè)問題：

1）推薦不準(zhǔn)確。LBSN中興趣點(diǎn)總數(shù)異常龐大，用戶訪問的興趣點(diǎn)只占極少一部分，這導(dǎo)致用戶興趣點(diǎn)簽到矩陣極為稀疏，使得挖掘用戶的偏好具有難度，且由于各算法在考慮社交和地理位置等因素的影響時(shí)不夠深入全面，進(jìn)一步造成推薦的不準(zhǔn)確。

2）推薦缺乏個(gè)性化、推薦效率低。協(xié)同過濾算法的基礎(chǔ)是相似度計(jì)算，算法缺乏個(gè)性化的表示方法，導(dǎo)致難以獲取用戶的個(gè)性化偏好。由于算法缺乏簡(jiǎn)單有效的召回機(jī)制，需要針對(duì)所有興趣點(diǎn)計(jì)算推薦得分，因此造成大量的時(shí)間消耗，導(dǎo)致推薦效率低。

對(duì)于問題1），本文探索用戶好友及2hop好友的社交影響，緩解數(shù)據(jù)的稀疏問題。融入從整體簽到數(shù)據(jù)和個(gè)人簽到數(shù)據(jù)中深入挖掘的地理位置特征，提升推薦的準(zhǔn)確性。對(duì)于問題2），本文利用核密度估計(jì)方法對(duì)用戶的個(gè)人簽到數(shù)據(jù)進(jìn)行建模，用以獲取用戶個(gè)性化的地理位置偏好，提高推薦的個(gè)性化程度。同時(shí)，構(gòu)造推薦候選集以提高算法的推薦效率。

針對(duì)上述問題，本文綜合應(yīng)用協(xié)同過濾技術(shù)和社交網(wǎng)絡(luò)分析技術(shù)，從理論上研究LBSN中POI推薦問題，從應(yīng)用上解決數(shù)據(jù)稀疏和推薦效率低的問題。

1?相關(guān)工作

目前大多數(shù)興趣點(diǎn)推薦算法由協(xié)同過濾算法發(fā)展而來，主要分析社交因素、地理位置因素和時(shí)間因素的影響，并將這些影響因素加入模型中進(jìn)而改善推薦的效果。

1）基于社交因素的推薦。

根據(jù)社會(huì)同質(zhì)理論和影響理論，好友間會(huì)表現(xiàn)出共同的興趣愛好和相似行為，用戶傾向于接受朋友的推薦。大量的研究利用社交因素來提高興趣點(diǎn)推薦的質(zhì)量。其中：文獻(xiàn)[1]在協(xié)同過濾算法的基礎(chǔ)上，綜合考慮社交因素和地理位置因素，提出了融合地理社交因素的個(gè)性化位置推薦（Personalized GeoSocial Location Recommendation，iGSLR）算法;文獻(xiàn)[4]利用矩陣分解（Matrix Factorization，MF）模型，融合用戶的社交影響力對(duì)模型進(jìn)行增強(qiáng);文獻(xiàn)[5]將好友類型劃分為社交好友、位置好友和鄰近好友，系統(tǒng)地考慮了不同好友的社交影響; 文獻(xiàn)[6-7]通過對(duì)社交因素、地理位置因素和興趣點(diǎn)類別因素之間相關(guān)性的研究，提升推薦效果。

2）融合地理位置因素的推薦。

與音樂、電影等項(xiàng)目推薦不同，地理位置因素是興趣點(diǎn)推薦的一個(gè)獨(dú)特因素，大量的研究利用興趣點(diǎn)在空間上的聚集現(xiàn)象來提高推薦的準(zhǔn)確性[8-11]。主流的地理位置建模方法有以下三類：冪律分布、高斯分布和核密度估計(jì)方法。其中：文獻(xiàn)[8-9]認(rèn)為用戶簽到的分布符合冪律分布，通過冪律分布獲取用戶簽到的距離偏好; Liu等[10]將用戶簽到分布抽象為高斯分布，結(jié)合泊松因子模型進(jìn)行協(xié)同過濾推薦; 與以上方法不同，文獻(xiàn)[1，11]利用核密度估計(jì)方法從二維角度對(duì)用戶簽到記錄進(jìn)行建模，避免了對(duì)所有用戶設(shè)置公共距離函數(shù)的局限性，因此可以獲取個(gè)性化的地理位置偏好。

3）綜合其他因素的推薦。

除了社交因素和地理位置因素，時(shí)間、興趣點(diǎn)流行度等因素也會(huì)對(duì)用戶的簽到行為產(chǎn)生影響。其中，Gao等[12]提出的融合時(shí)間因素的位置推薦（Location Recommendation with Temporal effects， LRT）算法，按時(shí)間（T=24h）將用戶興趣點(diǎn)簽到矩陣進(jìn)行劃分，使用矩陣分解方法獲取用戶簽到的時(shí)間偏好。文獻(xiàn)[13-14]認(rèn)為興趣點(diǎn)的流行度體現(xiàn)了興趣點(diǎn)的服務(wù)質(zhì)量，因此將流行度融入?yún)f(xié)同過濾算法中，結(jié)合社交因素和地理位置因素能夠更好地完成推薦。

然而，之前的研究很少考慮用戶好友影響力的傳播屬性，用戶的2hop好友也會(huì)影響用戶行為;同時(shí)，在挖掘地理位置特征時(shí)不夠深入全面，如地點(diǎn)影響力的計(jì)算僅考慮興趣點(diǎn)被簽到頻率。在推薦效率方面，算法缺乏簡(jiǎn)單有效的召回機(jī)制，推薦效率低。

本文在之前的研究基礎(chǔ)上作出以下改進(jìn)：首先，通過實(shí)驗(yàn)驗(yàn)證了用戶2hop好友對(duì)用戶簽到行為的影響，并將用戶2hop好友加入?yún)f(xié)同過濾算法的計(jì)算中，從而緩解數(shù)據(jù)稀疏問題，提高推薦的準(zhǔn)確性;其次，在對(duì)社交網(wǎng)絡(luò)分析的基礎(chǔ)上，構(gòu)造了地點(diǎn)影響力模型，通過隨機(jī)游走（PageRank）算法獲取用戶影響力，并結(jié)合地點(diǎn)被簽到的頻率進(jìn)一步挖掘地點(diǎn)影響力，深入全面地獲取整體地理位置偏好;然后，使用核密度估計(jì)方法對(duì)個(gè)人簽到記錄進(jìn)行建模，獲取用戶個(gè)性化的地理位置偏好;最后，綜合社交因素和地理位置因素，提高推薦的準(zhǔn)確性和個(gè)性化程度，并根據(jù)地點(diǎn)影響力排名和好友訪問興趣點(diǎn)集合生成推薦候選集，提升推薦效率。

2?問題描述和相關(guān)分析

2.1?問題描述

在LBSN中，數(shù)據(jù)集主要分為用戶集U={u1， u2， …， um}， 興趣點(diǎn)集L={ l1， l2， …， ln }和訪問時(shí)間集T={ t1， t2， …， tk }。

興趣點(diǎn)推薦問題的示意圖如圖1所示，當(dāng)用戶ui在地理層lj和時(shí)間層tk完成簽到時(shí)，其簽到記錄可以用三元組表示為C=〈ui， lj，tk〉。

本文的研究框架如圖2所示。

為方便后續(xù)討論，對(duì)興趣點(diǎn)及2度好友進(jìn)行如下相關(guān)定義：

定義1?POI。POI是指在空間中能夠唯一標(biāo)識(shí)的地點(diǎn)（如某個(gè)餐廳或影院等）。興趣點(diǎn)可以表示為〈id， （longitude， latitude）〉，其中id為唯一標(biāo)識(shí)符，（longitude， latitude）為POI的經(jīng)緯度。

定義2?2度好友。在LBSN中，用戶之間的好友關(guān)系可以用網(wǎng)絡(luò)圖來表示，用戶的直接好友和2hop好友構(gòu)成了2度好友。

在圖3的社交關(guān)系圖，用戶u2的直接好友集合{u1，u4，u7}，2hop好友集合為{u3，u8}，則用戶u2的2度好友集合為F2={u1，u3，u4，u7，u8}。

社交關(guān)系的一個(gè)實(shí)例如圖3所示。

在符號(hào)描述的基礎(chǔ)上，本文給出興趣點(diǎn)推薦的問題描述。

問題1?POI推薦。給定一個(gè)用戶ui，其簽到記錄Ci，興趣點(diǎn)推薦的目的是為該用戶推薦N個(gè)可能訪問但暫未訪問的興趣點(diǎn)。

2.2?好友影響分析

為驗(yàn)證好友具有相似的訪問行為以及好友的影響力，通過實(shí)驗(yàn)分析用戶好友及2度好友對(duì)用戶簽到行為的真實(shí)影響。以Gowalla數(shù)據(jù)集為例，按照4.1節(jié)描述劃分訓(xùn)練集和測(cè)試集，根據(jù)式（1）計(jì)算用戶簽到行為的相似性。

p=∑ f∈Fi∑ ui∈UT（ui）∩Train（f）T（ui）（1）

其中：Fi代表用戶ui的2度好友集合，T（ui）代表測(cè)試集中成功推薦的興趣點(diǎn)集合，Train（f）代表訓(xùn)練集中用戶2度好友簽到歷史興趣點(diǎn)集合。探索用戶直接好友影響時(shí)，將公式中Fi的替換為fi，實(shí)驗(yàn)結(jié)果如圖4所示。

實(shí)驗(yàn)結(jié)果表明，在為用戶成功推薦的POI中，有超過20%的POI是其直接好友訪問過的，而超過60%的POI被其2度好友訪問過。由此可以看出，用戶的簽到行為與其2度好友具有更廣泛的相似性，且2度好友的簽到行為會(huì)對(duì)用戶產(chǎn)生傳遞的影響。因此，探索2度好友的社交影響可以緩解數(shù)據(jù)的稀疏問題，提高推薦準(zhǔn)確率。

3?興趣點(diǎn)推薦模型

本章通過構(gòu)建社交影響模型、地點(diǎn)影響力模型和個(gè)性化地理位置模型來對(duì)POI的特征進(jìn)行表示。給出推薦候選集的生成方法。最后，通過模型融合，從候選集中選取適當(dāng)?shù)腜OI對(duì)用戶進(jìn)行推薦。

3.1?社交影響模型

本文改進(jìn)基于好友的協(xié)同過濾算法，分別計(jì)算用戶與其2度好友的經(jīng)歷相似度和好友相似度，并結(jié)合用戶歷史簽到記錄計(jì)算用戶訪問興趣點(diǎn)的概率。

本文擴(kuò)大了基于好友的協(xié)同過濾算法相似度計(jì)算的用戶范圍，針對(duì)2度好友集合Fi，計(jì)算用戶相似度，進(jìn)一步計(jì)算訪問概率，訪問概率如式（2）所示：

ps（i， j）=∑ uk∈FiSIi，k·ck， j∑ uk∈FiSIi，k（2）

其中： Fi為用戶ui的2度好友集合，ck， j為用戶uk訪問興趣點(diǎn)lj 的狀態(tài)，SIi，k代表用戶ui和用戶uk的社交影響因子。SIi，k可通過式（3）表示，其中SIEi，k代表用戶ui和用戶uk的經(jīng)歷相似度，SIFi，k代表用戶ui和用戶uk的好友相似度，參數(shù)α 表示影響權(quán)重。

SIi，k=（1-α）·SIEi，k+α·SIFi，k（3）

當(dāng)α=1時(shí)，社交影響因子完全由好友相似度決定; 當(dāng)α=0時(shí)，社交影響因子完全由經(jīng)歷相似度決定。經(jīng)歷相似度和好友相似度的計(jì)算可由式（4）和式（5）來表達(dá)。

用戶ui和uk的經(jīng)歷相似度SIEi，k基于訪問的共現(xiàn)現(xiàn)象，并根據(jù)余弦相似度進(jìn)行計(jì)算：

SIEi，k=∑ lj∈Lci， j·ck， j∑ lj∈Lc2i， j·∑ lj∈Lc2k， j（4）

其中： ci， j和ck， j分別為ui和uk訪問興趣點(diǎn)lj的狀態(tài)。當(dāng)ui和uj共同訪問的比例越大，它們的經(jīng)歷相似度越高。

好友相似度SIFi，k是基于用戶ui和uk的共同好友比例進(jìn)行計(jì)算：

SIFi，k=|Fi∩Fk||Fi∪Fk|（5）

其中：Fi和Fj分別為用戶ui和用戶uj的2度好友，共同好友比例越大，好友相似度越高。

3.2?地點(diǎn)影響力模型

興趣點(diǎn)的影響力代表興趣點(diǎn)的受歡迎程度，興趣點(diǎn)被簽到的次數(shù)越多影響力越大;然而，LBSN中各用戶的影響力存在差異，不同用戶的簽到行為會(huì)產(chǎn)生不同影響，僅考慮POI被簽到次數(shù)并不準(zhǔn)確， 因此，本文構(gòu)建了地點(diǎn)影響力模型，在獲取用戶影響力的基礎(chǔ)上，全面深入地計(jì)算興趣點(diǎn)的影響力。地點(diǎn)影響力模型的構(gòu)建分為兩步：用戶影響力發(fā)現(xiàn)和地點(diǎn)影響力發(fā)現(xiàn)。

PageRank算法作為一種網(wǎng)頁重要性排序算法，是根據(jù)網(wǎng)頁之間相互鏈接關(guān)系判斷網(wǎng)頁重要性。該算法具有較高的時(shí)間效率，適合大型網(wǎng)絡(luò)中判斷節(jié)點(diǎn)的重要性，同樣適用于社交網(wǎng)絡(luò)中用戶影響力分析[15]，因此，本文使用PageRank算法對(duì)LBSN中各用戶重要性排序并計(jì)算用戶影響力。

用戶ui的PageRank值PR（ui），如式（6）所示：

PR（ui）=β·∑ v∈fiPR（v）|F（v）|+1-βN（6）

其中：β為阻尼系數(shù)， fi表示用戶ui的直接好友，N為L(zhǎng)BSN中的用戶數(shù)。

對(duì)所有用戶的PageRank值排序后可得到用戶ui的PageRank排名m，并使用式（7）計(jì)算用戶ui的影響分?jǐn)?shù)s（ui）：

s（ui）=11+logm（7）

從式（7）中可看出，用戶的排名越靠前，影響分?jǐn)?shù)越高。在得到用戶影響分?jǐn)?shù)后，使用用戶影響得分對(duì)POI被簽到的次數(shù)進(jìn)行加權(quán)，使用式（8）進(jìn)一步計(jì)算地點(diǎn)的影響力：

p（lj）=∑ ui∈Us（ui）Nui，lj∑ ui∈Us（ui）Nui（8）

其中：Nui為用戶ui訪問POI的總次數(shù)，Nui，lj為用戶ui訪問興趣點(diǎn)lj的次數(shù)，s（ui） 表示用戶ui的影響分?jǐn)?shù)，用戶的影響分?jǐn)?shù)越高，其簽到行為對(duì)地點(diǎn)影響力的作用越大。

3.3?個(gè)性化地理位置模型

為提高推薦的個(gè)性化程度，本文使用核密度估計(jì)方法建立個(gè)性化地理位置模型[1，11]，該方法僅從數(shù)據(jù)本身出發(fā)得到用戶簽到分布，具有推薦相對(duì)準(zhǔn)確、富有個(gè)性化的特點(diǎn)。模型的建立分為三個(gè)步驟：距離樣本數(shù)據(jù)的獲取、距離分布的估計(jì)和個(gè)性化地理位置影響力的計(jì)算。

用戶ui的距離樣本數(shù)據(jù)D是通過計(jì)算該用戶簽入的每一對(duì)位置之間的距離來獲取的。距離分布估計(jì)則依靠核函數(shù)和平滑參數(shù)完成。根據(jù)簽到的位置之間的距離樣本D，距離為d的分布：

f^（d）=1|D|h∑ d′∈DKd-d′h （9）

其中：K（·）為核函數(shù);h是平滑參數(shù)，也被稱為帶寬或窗口。核函數(shù)選擇最常用的高斯核函數(shù)K（x）=12πe-x22，根據(jù)經(jīng)驗(yàn)[1，11]，當(dāng)選擇高斯核核函數(shù)時(shí)，通過最小化分布的平均積分誤差，平滑參數(shù)的最佳選擇為h=453n15。

對(duì)于用戶ui，其簽到地點(diǎn)集合為L(zhǎng)i={ l1， l2， …， lk}，對(duì)于一個(gè)新的簽到地點(diǎn)lj，按照式（10）計(jì)算每一對(duì)地點(diǎn)的距離：

dj，k=distance（lj，lk）; lk∈Li（10）

根據(jù)式（10）計(jì)算每一對(duì)興趣點(diǎn)距離為dj，k之后，根據(jù)式（9）分別計(jì)算核密度估計(jì) f^（dj，k），用戶ui訪問新興趣點(diǎn)lj的概率由每一對(duì) f^（dj，k）共同決定：

pg（i， j）=1n∑n1f^（dj，k）（11）

3.4?模型融合

本節(jié)綜合社交影響模型、地點(diǎn)影響力模型和個(gè)性化地理位置模型完成模型融合，并提出推薦候選集構(gòu)造方法。根據(jù)2.2節(jié)的分析，用戶訪問的興趣點(diǎn)大多數(shù)是其2度好友訪問過的，因此利用2度好友訪問記錄可以快速縮小推薦范圍。為增加推薦的范圍和覆蓋度，在構(gòu)造候選集時(shí)加入高影響力的興趣點(diǎn)集合。默認(rèn)選取影響力排名前1%的興趣點(diǎn)構(gòu)造候選集，選取比例可根據(jù)實(shí)際情況調(diào)整，當(dāng)選取比例達(dá)到100%時(shí)，算法對(duì)所有興趣點(diǎn)訪問得分，此時(shí)推薦范圍最大，其推薦時(shí)間也最長(zhǎng)。

對(duì)于用戶ui和推薦候選集P中的興趣點(diǎn)li∈P，最終的推薦分?jǐn)?shù)由社交影響模型、地點(diǎn)影響力模型和個(gè)性化地理位置模型共同決定，其計(jì)算公式為：

Score（i， j）=ps（i， j）·p（j）·pg（i， j）（12）

算法的偽代碼如算法1所示：

算法1?融合地點(diǎn)影響力的興趣點(diǎn)推薦算法。

輸入?用戶集U，用戶簽到地點(diǎn)集L，用戶好友集F;

輸出?包含N個(gè)興趣點(diǎn)組成的推薦列表。

程序前

1）

for li∈L each do

2）

由式（7）計(jì)算所有興趣點(diǎn)的影響力P（lj）;

3）

end for

4）

對(duì)興趣點(diǎn)排序，選取流行度前1%的興趣點(diǎn)作為部分推薦候選集Q;

5）

foreach ui∈U do

6）

獲取其2度好友簽到的興趣點(diǎn)集合W;

7）

構(gòu)造推薦候選集P=Q∪W

8）

end for

9）

for each ui∈U do

10）

for each li∈L do

11）

由式（1）計(jì)算社交影響ps（i， j）;

12）

由式（10）計(jì)算地理位置影響pg（i， j）;

13）

由式（11）計(jì)算最終推薦得分Score（i， j）;

14）

end for

15）

根據(jù)Score（i， j）選取TopN個(gè)POI推薦給用戶

16）

end for

程序后

與同類算法相比，本文提出的算法深入考慮了用戶2度好友的社交影響，能夠更加有效地緩解數(shù)據(jù)稀疏問題。通過融合地點(diǎn)影響力模型和個(gè)性化地理位置模型，深入全面地挖掘地理位置特征;同時(shí)，本算法增加了召回機(jī)制，通過構(gòu)建推薦候選集可以大幅度提高推薦效率。

4?實(shí)驗(yàn)

4.1?數(shù)據(jù)集及實(shí)驗(yàn)環(huán)境描述

本文選擇兩個(gè)典型的LBSN平臺(tái)Gowalla和Yelp上的真實(shí)簽到數(shù)據(jù)集驗(yàn)證算法的有效性，數(shù)據(jù)集的統(tǒng)計(jì)信息如表2所示。

對(duì)于兩個(gè)數(shù)據(jù)集分別按照時(shí)間順序劃分，選取80%作為訓(xùn)練集，剩余20%作為測(cè)試集。

實(shí)驗(yàn)運(yùn)行在服務(wù)器上，硬件環(huán)境為：Intel Xeon CPU E52630 2.5GHz、128GB RAM和1.5TB硬盤。運(yùn)行系統(tǒng)為ubuntu16.04，實(shí)驗(yàn)代碼為python3。

4.2?評(píng)價(jià)指標(biāo)

本文選用常用的準(zhǔn)確率（Pricision）和召回率（Recall）進(jìn)行TopN（N=5，10，20）來檢驗(yàn)算法的有效性，其中N表示為每個(gè)用戶推薦的興趣點(diǎn)數(shù)量。

準(zhǔn)確率和召回率的計(jì)算公式分別如式（13）、（14）所示：

Precision@N=∑ui∈U|R（ui）∩T（ui）|∑ui∈U|R（ui）|（13）

Recall@N=∑ui∈U|R（ui）∩T（ui）|∑ui∈U|T（ui）|（14）

其中： R（ui）表示為用戶ui推薦的興趣點(diǎn)列表;T（ui）表示在測(cè)試集上用戶ui去過的興趣點(diǎn)列表; |R（ui） ∩T（ui）|表示推薦給ui的并且被其真正訪問的區(qū)域，其值越大表明推薦結(jié)果越準(zhǔn)確。同時(shí)推薦準(zhǔn)確率和召回率還受到推薦規(guī)模與實(shí)際訪問規(guī)模的影響。

4.3?參數(shù)選擇

在計(jì)算社交影響因子的式（3）中，參數(shù)α的取值決定了經(jīng)歷相似度和好友相似度的影響權(quán)重。在計(jì)算用戶PageRank值的式（6）中，參數(shù)β的值決定了信息的轉(zhuǎn)移概率和網(wǎng)絡(luò)的收斂速度。在并未考慮地點(diǎn)影響力模型的情況下，在Gowalla數(shù)據(jù)集上選取不同的α的值進(jìn)行Top5推薦，推薦結(jié)果如圖5所示?？梢钥闯?，當(dāng)α=0.1時(shí)，推薦效果最好，因此在之后的實(shí)驗(yàn)中設(shè)置α的值為0.1。

在設(shè)置的α的值為0.1的情況下，選取不同的β值進(jìn)行Top5推薦，分別計(jì)算推薦的準(zhǔn)確率和召回率，推薦結(jié)果如圖6所示。可以看出，當(dāng)β=0.4時(shí)，推薦效果最好，因此在之后的實(shí)驗(yàn)中設(shè)置β的值為0.4。

同樣，在Yelp數(shù)據(jù)集上采用相同的方法確定實(shí)驗(yàn)的參數(shù)，當(dāng)α=0.2和β=0.5時(shí)，推薦效果最好。對(duì)比兩個(gè)數(shù)據(jù)集的參數(shù)可以發(fā)現(xiàn)，相比Gowalla數(shù)據(jù)集，Yelp數(shù)據(jù)集上好友的聯(lián)系更加緊密，因此，用戶的好友相似度對(duì)社交影響因子的作用更大，信息的影響概率也越大。

4.4?算法對(duì)比

為驗(yàn)證本文所提出算法的性能，選取了以下算法驗(yàn)證算法的有效性， 其中：融合地點(diǎn)影響力的興趣點(diǎn)推薦算法（FriendGeo with Location effects，F(xiàn)GL）是本文提出的算法;F1GL是本算法僅考慮直接好友，不考慮2度好友影響的情況。 FGP是本算法在融合地點(diǎn)影響力時(shí)，不考慮用戶影響力差異的情況，僅考慮了興趣點(diǎn)被簽到次數(shù)的情況。iGSLR和LRT算法分別為文獻(xiàn)[11]和文獻(xiàn)[12]所提出的算法，算法的具體描述如表3所示。

本文對(duì)各算法進(jìn)行了實(shí)驗(yàn)對(duì)比，其中圖7（a）和（b）分別表示各算法在Gowalla數(shù)據(jù)集上進(jìn)行TOPN（N=5，10，20）情況下對(duì)應(yīng)的準(zhǔn)確率和召回率，圖8（a）和（b）同樣對(duì)應(yīng)各算法在Yelp數(shù)據(jù)集上推薦的準(zhǔn)確率和召回率。

可以看出，本文算法在兩個(gè)數(shù)據(jù)集上準(zhǔn)確率和召回率都高于其他算法。其中，LRT算法在這兩個(gè)數(shù)據(jù)集上的表現(xiàn)最差，該算法將用戶簽到矩陣按時(shí)間（T=24）劃分成多個(gè)矩陣，盡管有利于時(shí)間感知的POI推薦，但是該方法帶來了數(shù)據(jù)稀疏問題，造成推薦的準(zhǔn)確率低。實(shí)驗(yàn)結(jié)果表明，F(xiàn)GL算法的準(zhǔn)確率和召回率都高于LRT算法和F1GL算法，這說明了融合社交因素可以增強(qiáng)用戶的相似性提升推薦結(jié)果的可信度，同時(shí)考慮2度好友影響，體現(xiàn)了社交影響的傳播屬性，對(duì)推薦結(jié)果產(chǎn)生了積極作用。與iGSLR算法相比，F(xiàn)GP和FGL算法的準(zhǔn)確率和召回率都有所提高，說明了地點(diǎn)影響力對(duì)POI推薦結(jié)果具有正面影響。對(duì)比FGL和FGP算法，也可以發(fā)現(xiàn)，在分析用戶影響力的基礎(chǔ)上進(jìn)一步挖掘地點(diǎn)影響力，相比于僅使用POI被簽到次數(shù)衡量地點(diǎn)影響力，可以更加準(zhǔn)確地把握用戶群體的興趣特征以及訪問規(guī)律。

為衡量算法的推薦效率，本文定義平均推薦時(shí)間為每位用戶進(jìn)行TopN（N=20）推薦的時(shí)間，包括查詢和排序時(shí)間。其中，本文算法的推薦時(shí)間與候選集的構(gòu)造相關(guān)，默認(rèn)選取高影響力興趣點(diǎn)比例為1%時(shí)，算法的平均推薦時(shí)間如表4所示，可以看出，構(gòu)建推薦候選集可以極大地提高算法的推薦效率。

5?結(jié)語

本文提出一種融合地點(diǎn)影響力的興趣點(diǎn)推薦算法，通過構(gòu)造候選集提升推薦效率，并綜合社交好友因素和地理位置因素完成推薦。通過引入2度好友影響解決數(shù)據(jù)稀疏問題，通過對(duì)地點(diǎn)影響力和個(gè)人地理位置建模，分別獲取整體位置偏好和個(gè)人位置偏好，提高推薦的準(zhǔn)確性和個(gè)性化。實(shí)驗(yàn)表明，該方法相對(duì)于其他算法興趣點(diǎn)推薦算法準(zhǔn)確率和召回率均有所提高且推薦效率更高。

參考文獻(xiàn) （References）

[1]YALI S， FUZHI Z， WENYUAN L. An adaptive pointofinterest recommendation method for locationbased social networks based on user activity and spatial features[J]. KnowledgeBased Systems， 2019， 163（1）： 267-282.

[2]袁冠.移動(dòng)對(duì)象軌跡數(shù)據(jù)挖掘方法[D].徐州：中國礦業(yè)大學(xué)，2012：1-7. （YUAN G. Research on the mining methods of trajectory data for moving objects[D]. Xuzhou： China University of Mining and Technology， 2012： 1-7.）

[3]袁冠，夏士雄，張磊，等.基于結(jié)構(gòu)相似度的軌跡聚類算法[J].通信學(xué)報(bào)， 2011， 32（9）：103-110. （YUAN G， XIA S X， ZHANG L， et al. Trajectory clustering algorithm based on structural similarity[J]. Journal on Communications， 2011， 32（9）： 103-110.）

[4]ZHANG Z， LIU Y， ZHANG Z， et al. Fused matrix factorization with multitag， social and geographical influences for POI recommendation[J]. World Wide Web， 2019， 22（3）： 1135-1150.

[15]張琛.社交網(wǎng)絡(luò)用戶影響力的評(píng)估算法研究[D].武漢：武漢郵電科學(xué)研究院， 2018：15-22. （ZHANG C. Research on evaluation algorithms of social network users influence[D]. Wuhan： Wuhan Research Institute of Posts and Telecommunications， 2018： 15-22.）

This work is partially supported by the National Natural Science Foundation of China （71774159）， the China Postdoctoral Fund Project （2018M642358）， the Think Tank of Green Safety Management and Policy Science （2018WHCC03）.

XU Chao， born in 1996， M. S. candidate. His research interests include locationbased social network computing.

MENG Fanrong， born in 1962， Ph. D.， professor. Her research interests include database， data mining.

YUAN Guan， born in 1982， Ph. D.， associate professor. His research interests include spatiotemporal data mining.

LI Yuee， born in 1983， M. S. Her research interests include information management system.

LIU Xiao， born in 1994， M. S. candidate. His research interests include pattern recognition.