基于社交和地理信息的興趣點推薦

郭晨睿，李 平，2

1.長沙理工大學 計算機與通信工程學院，長沙 410114

2.智能交通大數據處理湖南省重點實驗室，長沙 410114

1 概述

隨著移動智能設備等技術的快速發展，基于位置的社交網絡[1-7]（Location Based Social Networks，LBSNs）應運而生，如Foursquare、Gowall和微信等。LBSNs連接了現實世界和虛擬世界，用戶通過線下訪問現實生活中他們感興趣的地理位置，并在線上以簽到的方式發表評論等信息，與其他用戶分享自己在該興趣點（Points-of-Interests，POIs）的簽到體驗。LBSNs不僅受到了廣大用戶喜愛，而且受到學術界和工業界的廣泛關注。LBSNs的廣泛應用推動了興趣點推薦系統的發展。在興趣點推薦系統中融合多種影響因素可以有效提高興趣點推薦系統的質量。因此，融合多種影響因素構建興趣點推薦系統是廣大學者的主要研究方向。

傳統的基于用戶的協同過濾算法將兩個用戶之間的相互影響當作對稱的影響，即對于LBSNs中任意的兩個用戶，彼此的影響是相同的。然而，在現實生活中這種情況并不一定如此，例如：專家可能會對新用戶產生影響，但是新用戶根本不會影響專家。此外，興趣點是現實生活中真實存在的地點，用戶在興趣點的簽到行為必然會受到用戶與興趣點之間地理位置的影響，即地理影響。文獻[4，7]中計算同一用戶在一天內簽到的兩個相鄰興趣點之間的距離，并匯總所有用戶簽到的結果，獲得如圖1所示的距離函數。其中，概率值越大表明用戶更愿意在該距離處的興趣點簽到。由圖1可以看出，隨著兩個興趣點之間距離的增加，用戶愿意簽到訪問的概率隨之減少。

圖1 地理影響簽到概率分布本文

針對上述問題，本文提出了一種融合用戶、社交和地理信息（Fuse Users、Social and Geographic，FUSG）的興趣點推薦模型。首先，使用一種改進的基于用戶的協同過濾算法：非對稱用戶影響模型計算兩個用戶間的定向影響，并通過PageRank算法生成用戶的全局影響因子來改進非對稱用戶影響模型；其次，提出了一種融合社交用戶之間的居住距離和他們的共同好友的方法來計算用戶相似度；然后，利用地理信息挖掘用戶的簽到特征，生成地理模型；最后，將改進的用戶影響、社交影響和地理影響融合成FUSG興趣點推薦模型。

本文的主要貢獻點由以下三個方面：（1）采用非對稱用戶影響模型和PageRank算法生成用戶的全局影響因子來改進基于用戶的協同過濾算法進行興趣點推薦；（2）提出了一種新的計算用戶相似度的方法：通過社交用戶的居住距離與用戶的朋友集合計算用戶之間的相似度；（3）融合用戶偏好、社交信息和地理信息三種影響因素生成的FUSG模型在真實數據上的精確率和召回率都有所提高。

2 相關工作

主要展示一些與本文相關的最新研究工作，這些工作主要圍繞地理影響和社交關系進行興趣點推薦。

地理影響[4-12]，地理影響是區分興趣點推薦與傳統項目推薦的重要因素，用戶在興趣點的簽到行為取決于用戶和興趣點的地理特征。文獻[4]中Cheng等人提出了一種多中心的高斯模型（Multi-center Gaussian Model，MGM）來挖掘用戶的簽到歷史的多個中心的位置，從而使用地理影響來增強興趣點推薦的質量，但是由于用戶簽到數據的稀疏性，難以確定用戶簽到中心，且很難使用相同的分布對不同的用戶進行建模；文獻[7]中Zhang等人使用核密度估計將地理影響模型轉化為用戶的個性化距離分布，實驗結果表明，該方法優于MGM，但是在很多真實推薦場景中并不適用，計算復雜度相對較高，且距離分布估計難度較高；因此本文模型采用文獻[11]中Ye等人提出的冪函數分布，從距離上擬合用戶的空間分布，假設用戶簽到的地點之間的距離符合冪函數分布。

社交影響[11，13-17]，基于LBSNs中的朋友比非朋友會擁有更多的共同興趣的假設來提高興趣點推薦的質量。文獻[11，14]中Ye等人提出了一種基于朋友的協同過濾（Friend-based Collaborative Filtering，FCF），該方法融合了用戶的朋友集合及用戶簽到的興趣點集合，但是未考慮用戶現實生活中居住距離對興趣點推薦的影響；文獻[15]中在計算社交用戶相似度時僅僅考慮了用戶的朋友集合，未考慮到用戶之間居住距離對用戶相似度的影響；文獻[17]中Zhang等人提出了基于用戶現實生活居住距離的方法計算用戶相似度，但是未考慮用戶社交關系對興趣點推薦的影響。因此，本文模型為充分考慮了用戶現實居住距離及用戶朋友集合對興趣點簽到的影響，提出了一種新的基于社交關系的相似度計算方法。

3 FUSG模型

3.1 非對稱用戶影響

R=[cul]m×n表示用戶u在興趣點l的簽到矩陣，其中m表示用戶的數量，n表示興趣點的數量，矩陣中第i行和第 j列的cul表示用戶u在興趣點l的簽到次數。簽到次數越多，表明用戶u越喜歡趣點l，若用戶u未在興趣點l簽到過，則cul=0。

首先，需要計算用戶u對其所有簽到過的趣點l的平均簽到次數 cˉu，如公式（1）所示：

其中，nu表示用戶u簽到過的興趣點的總數目。使用用戶的平均簽到次數cˉu來構建布爾矩陣其中由公式（2）計算獲得：

根據矩陣R′構建非對稱用戶影響矩陣W=[wuv]m×m,其中wuv表示用戶u對用戶v的影響因子，wuv的計算方式如公式（3）所示：

不同于傳統的基于用戶的協同過濾算法中使用的對稱用戶關系矩陣，該用戶關系矩陣是不對稱矩陣。

假設：（1）用戶可以影響的用戶越多，則該用戶在興趣點推薦系統中用戶全局重要性越高；（2）如果有多個用戶可以對目標用戶產生影響，則目標用戶更容易受到全局重要性較高用戶的影響[18]。

基于上述假設，可以得出結論：除了非對稱用戶影響矩陣之外，全局用戶重要性值在提高推薦的準確性方面也起著關鍵作用。因此，本文使用PageRank算法計算用戶的重要性值。直觀地說，如果一個用戶可以影響的用戶越多，該用戶的全局影響值越高。目標用戶的in-degree表示能夠影響他的用戶數量，out-degree表示目標用戶能夠影響的其他用戶數量。如果用戶u和用戶v之間的影響值wuv大于等于平均影響值wˉ，則影響因子等于1，表示用戶u可以對用戶v產生影響；否則的值為0，用戶u不會對用戶v產生影響。平均影響值wˉ和影響因子分別由公式（4）、（5）計算得到：

其中，δ(x)是指示函數，當x?0時δ(x)=1，否則δ(x)=0。

用戶u可以影響的用戶數目du通過公式（6）計算得到：

隨機初始化用戶的PageRank值，并使用下面的迭代模型得到用戶最終的PageRank值。在每次迭代t中，PageRank的值由公式（7）計算：

其中，Ι∈Rm×1是全1向量，α∈[0,1]是阻尼系數，表示其他用戶對目標用戶的貢獻的縮放因子；in(u)表示可以影響目標用戶u的用戶的集合。

在FUSG模型中，具有較低的in-degree和較高的out-degree的用戶更重要。在公式（7）中，影響更多用戶并且受較少用戶影響的用戶具有較小PageRank值，PageRank值越小表明用戶越重要。解決上述問題最簡單的方法是使用單調遞增函數來改進用戶的PageRank值，如公式（8）所示：

但是，該方法生成的用戶重要性值遠大于其影響值，當將用戶的影響值和重要性結合起來進行預測時，后者會在推薦過程中壓制前者，減小前者對推薦質量的影響。非對稱用戶影響值的范圍是[0，1]，因此用戶的PageRank值需要映射到[0，1]，所以上述方法并不適用。本文模型采用邏輯回歸函數將PageRank值映射到[0，1]，如公式（9）所示：

根據非對稱用戶影響值和用戶全局重要性值的乘積來對目標用戶將在某興趣點簽到的概率進行預測。給定用戶u，用戶u將在興趣點l簽到的預測概率c?ul根據公式（10）得到：

其中，wvu表示用戶v對用戶u的影響值。

3.2 基于社交的影響

現實生活中，朋友之間具有較多的共同興趣，例如：朋友經常一起去看電影等。為了充分利用社交影響，設計了一種融合社交關系和用戶居住距離來計算用戶間的社交影響[11，19]。一方面居住距離較近的朋友比距離較遠的朋友分享更多的興趣點；另一方面兩個用戶擁有的共同朋友越多，他們之間的共同興趣也就可能越多。通過sigmoid函數將擁有社交關系的用戶的居住距離轉換為規范的相似性，同時，使用Jaccard相似度計算LBSNs中用戶之間的相似性。使用超參數β來平衡上述兩種相似性，則用戶u和用戶v之間的相似度sim(u,v)如公式（11）所示：

其中，Fu表示用戶u的社交朋友集，v∈Fu，dis(u,v)表示用戶u和用戶v居住距離，超參數β∈[0,1]。用戶u在興趣點簽到的預測概率r?ul如公式（12）所示：

rvl表示用戶v在興趣點l簽到的頻率。

3.3 基于地理的影響

由圖1可知用戶在興趣點簽到的意愿與興趣點之間的距離成冪律分布。使用冪律分布模擬用戶從一個興趣點移動到另外一個興趣點的距離函數作為用戶可能簽到概率，如公式（13）所示：

其中，disl表示兩個興趣點之間的距離，wi(disl)表示用戶訪問距離disl遠的興趣點的概率，a和k是冪律函數的參數。

使用最大似然估計計算參數a和k，在公式（13）的兩邊取對數，得到公式（14）：

通過最小二乘法獲得公式（13）中的參數a和k。假設：用戶在興趣點li，他將要簽到的興趣點是lj，興趣點li和興趣點lj之間的距離為disl(li,lj)。用戶將在興趣點lj簽到的概率與用戶在距離disl(li,lj)處興趣點簽到的意愿wi(disl) 成比例。如公式（15）所示：

給定用戶u和他簽到歷史的興趣點集合Lu，基于貝葉斯公式預測用戶在每個候選興趣點的簽到概率，然后向用戶推薦概率較高的興趣點。由公式（16）計算得到：

其中，P(l)是數據集中所有用戶在興趣點簽到先驗概率表示訪問過興趣點l的用戶數目。

3.4 FUSG模型

融合用戶偏好、社交信息和地理信息進行興趣點推薦，提高興趣點推薦系統的質量。用分別表示用戶ui基于用戶偏好、社交信息和地理信息模型下在興趣點lj的簽到概率，計算如公式（17）、（18）和（19）所示：

用Sij表示用戶ui最終在興趣點lj的簽到的概率得分，即用戶ui在興趣點lj簽到的可能性越大，則Sij越大。設、和分別表示用戶基于用戶偏好、社交信息和地理信息模型下的簽到的概率得分，則Sij計算如公式（20）所示：

其中，、和分別由公式（21）、（22）和（23）計算獲得：

其中，L表示所有興趣點集合，Lu表示用戶u簽到過的興趣點集合。

4 實驗結果及分析

4.1 實驗數據集

本文實驗使用Gowalla公開的實際數據集[17]。數據集統計數據如表1所示，數據集包含196 591位用戶、1 280 969個興趣點、6 442 890次簽到、950 327個社交關系鏈接、用戶簽到矩陣稀疏度為2.9×10－5、平均位用戶簽到37.18個興趣點以及平均每個興趣點有3.11次簽到。在實驗中，隨機選取數據集中的20%作為測試數據集，剩余80%的數據集作為訓練數據集。

表1 Gowalla實驗數據集

4.2 評價指標

在性能對比實驗中，采用兩種Top-N指標評估推薦的質量，精確率Precision@N和召回率Recall@N。衡量指標如公式（24）、（25）所示：

其中，N是推薦給用戶的POIs的數量，T(u)是用戶在測試集上的行為列表，R(u)是根據用戶在訓練集上的行為給用戶做出的推薦列表。

4.3 參數分析

本節中，主要分析參數α和β對FUSG模型在數據集上對實驗結果的影響。首先分析參數β，該參數在計算基于社交的相似度時在平衡兩個用戶間居住距離和用戶朋友集合方面起著重要作用。圖2和圖3分別給出了參數β在[0，1]變化時，對推薦結果精確率和召回率的影響，其中Top-N個數為5。由圖2和圖3中可以發現FUSG模型的精確率和召回率隨著參數的增加先增加后減少。當參數β等于0.5時，本文FUSG模型的Precision@5和Recall@5達到最高值，分別為0.13和0.07。當參數β為0.5時，模型推薦效果最佳。因此，本文實驗中將參數β設置為0.5。

圖2 參數β與精確率

圖3 參數β與召回率

下面將分析參數α對FUSG模型性能的影響。參數α用于平衡非對稱用戶影響中用戶的全局影響因子。固定參數β的值為0.5，參數α的值在[0，1]范圍內變化。圖4和圖5分別給出了FUSG模型在參數α改變時的精確率和召回率，從圖中可以看出模型的Precision@5和Recall@5隨著參數α的增加而增加，當參數為1時，Precision@5和Recall@5達到最大值。因此，本章實驗中設置參數α的值為1。

圖4 參數α與精確率

圖5 參數α與召回率

4.4 實驗結果分析

為了驗證本章FUSG模型在興趣點推薦的性能，本節首先根據4.3節參數分析對參數進行設置。將參數α和β的值分別設為1和0.5。本章采用的對比模型如表2所示。下面為四種對比模型的詳細介紹：

US模型：融合用戶偏好和社交信息的興趣點推薦（User preference and Social influence，US）。僅考慮FUSG模型中用戶偏好和社交關系，計算方法為

UG模型：融合用戶偏好和地理信息的興趣點推薦（User preference and Geographical influence，UG）。選用了FUSG模型中的用戶偏好和地理信息作為影響因

SGFM模型[19]：基于社交和地理影響的興趣點推薦。該模型首先將用戶偏好和基于社交的協同過濾融合到一個組合模型中，然后和地理信息影響結合在一起形成SGFM模型。

USG模型[11]：利用地理影響的協同興趣點推薦。該模型將基于用戶的協同過濾、基于社交的協同過濾和地理信息影響進行線性擬合，形成了USG模型。

表2 本文模型和對比模型

圖6和圖7分別為五種模型的精確率和召回率的實驗對比結果。隨著推薦Top-N數量的增加，模型的精確率整體呈下降趨勢，召回率則呈現不斷上升趨勢。從圖6和圖7可知，本文所提出的模型在精確率和召回率上都明顯優于其他四種對比模型。FUSG模型取得的顯著進步表明融合多種因素興趣點推薦的有效性。由于US僅僅考慮了用戶偏好和社交信息的影響，而忽略了對興趣點推薦影響最重要的地理信息，因此，在對比模型中該模型的精確率和召回率相對較低。在UG模型中使用地理信息代替了社交信息，充分利用用戶的地理信息，雖然比US模型在精確率和召回率上有了一定的提高，但是優于使用的影響因素相對較少，沒有使用到用戶的社交信息。因此，在提高興趣點質量上有一定的限制。SGFM模型中雖然使用了用戶偏好、社交信息和地理信息三種影響因素，但是由于在考慮用戶偏好時，認為兩個用戶之間的影響是對稱的；在社交信息中計算用戶相似度時僅考慮了用戶的朋友集合，沒有考慮用戶之間的居住距離等信息，并且計算地理影響是存在一定的不足。USG模型在計算用戶偏好時存在與SGFM模型相同的不足，但是在社交關系中計算用戶相似度時，不僅考慮了用戶的朋友集合，而且還將用戶簽到的興趣點集合融入到相似度中，在一定程度上提高了社交關系的影響，在挖掘地理信息影響時使用冪律分布來挖掘地理信息對興趣點推薦系統的影響，該方法優于SGFM模型中的地理信息影響。根據圖6和圖7可以看出，UG模型明顯優于US模型，該實驗結果表明，用戶更喜歡訪問他歷史簽到興趣點附近的興趣點，而不是他的社交朋友們喜歡簽到的興趣點，即地理信息在提高興趣點推薦性能上優于社交關系的影響。

圖6 五種模型精確率對比

圖7 五種模型召回率對比

5 結論與展望

本文提出的FUSG模型，能夠充分地利用用戶的簽到歷史、社交信息和地理信息。同時，提出了利用朋友間的居住距離和朋友集合來求解社交關系中的用戶相似度；最后融合地理信息得到推薦結果。通過在真實的Gowalla數據集上的實驗結果，表明本文的FUSG模型在提高興趣點推薦型性能上有了一定的提高，能夠為用戶提供更準確的參考。

在現實生活中時間信息對人們的簽到行為有著重要的影響，一方面是由于用戶在時間維度上具有一定的規律性和周期性；另一方面興趣點在提供服務時有一定的時間限制，如：飯店和博物館的營業時間等。如果在FUSG模型中能夠融入時間影響將會獲得更好的推薦效果。