融合社交關系與地理信息的興趣點推薦模型

張 進，孫福振，王紹卿，王 帥，鹿祥志

山東理工大學 計算機科學與技術學院，山東 淄博255049

1 引言

近年來，工業界與學術界對于基于位置的社交網絡LBSN的應用探索逐年遞增，例如Foursquare、Facebook、Yelp 等。與傳統的電影、音樂以及書籍推薦不同，基于LBSN 的興趣點推薦面臨更多的問題和挑戰。選擇適合的上下文信息以及合理的融合策略是提高精度的一個主要途徑。基于矩陣分解的推薦算法因在Netflix Prize 取得了突出效果而受到學術界和工業界的關注。其中，經典矩陣分解算法包括SVD++[1]、NMF[2]、PMF[3]等取得較好效果，然而稀疏的簽到矩陣導致經典的矩陣分解算法性能偏低。另外，矩陣分解不能很好地挖掘長尾物品且解釋性差。為緩解這些問題，Ma等人[4]提出了基于概率矩陣分解的SoRec算法，集成了用戶的評分信息和用戶的社交網絡信息，并通過用戶評分信息和社交網絡信息共享用戶隱藏特征矩陣來融合兩種信息源。Zhuang 等人[5]提出了一種集成局部特征學習的LREAP算法，選取局部評分矩陣子模型，融合相似度優化子模型，提出一種新的損失函數擬合誤差與參數約束。Jamali 等人[6]提出了SocialMF 算法，在矩陣分解的過程中集成了信任的傳遞機制，可以有效解決冷啟動問題。Li 等人[7]使用LDA 模型挖掘用戶興趣潛在分布融入相似度的計算，使用動態方法填充用戶簽到數據并計算興趣點概率。Yu 等人[8]使用泊松分布替代傳統的高斯分布擬合用戶簽到行為，使用BPR標準挖掘興趣點推薦中的隱式反饋，融入地理影響作為矩陣分解的正則化因子，但并未考慮社交關系的影響。

上述算法雖然在一定程度上緩解了興趣點推薦領域存在的問題，但仍然存在一定局限性：影響因素選取單一，未能充分挖掘社會關系信息，或沒有考慮現實社會人際關系親疏[9-10]。

為挖掘興趣點推薦的隱式反饋行為，傳統的BPR偏序對生成過程將簽到過的POI 作為正例，未簽到過的POI 作為負例，單純地考慮簽到與未簽到的POI 之間的關系，忽略了簽到的POI之間存在偏序關系。本文增加簽到頻率高低作為正負例的偏序對生成方式，進而更充分地挖掘用戶對POI的偏好。

為挖掘和利用興趣點推薦中包含的上下文信息，例如社交關系與地理位置，大量的研究工作探究融合各種上下文信息對推薦結果的影響，Zhang 等人[11]使用核密度估計的方法計算地理因素對興趣點推薦的影響，Chen等人[12]通過探究社交網絡中的信任與相似來提高推薦精度。為進一步提升推薦精度，本文將用戶在興趣點的簽到頻率作為量化社交關系的基礎，進而得到更準確的社交影響矩陣，并融入推薦模型。

2 基于BPR標準的矩陣分解

BPR模型是基于排序的模型，相對于傳統的矩陣分解，BPR 模型本身關注的是興趣點之間的偏序對關系，并不關注興趣點的評分或者簽到頻率高低，更容易發掘用戶的隱式反饋，在預測用戶真正不喜歡的物品和缺失用戶對某物品的偏好信息的情況下能夠更好地預測，同時矩陣分解需要首先計算評分再進行排序，BPR模型減少了計算過程。模型假設每個用戶的偏好行為相互獨立和同一物品對不同物品的偏序關系相互獨立，首先，對數據進行預處理。即，將評分行為中的顯示反饋物品i 與隱式反饋物品j 處理為一個對級表示形式(u,i,j)的集合。本文重新定義偏序關系對的概念。假設用戶u對興趣點i 的簽到頻率fi高于興趣點j 的簽到頻率，則(u,i,j)表示用戶u 對興趣點i 的偏好程度高于興趣點j。L 表示興趣點集合，U 表示用戶集合。數據集處理為三元組：

?u表示偏序關系，使用最大后驗概率估計的方法學習兩個特征矩陣U 和V，U 和V 作為模型的參數θ，由于前提條件假設用戶偏好獨立，將公式（1）改寫為公式（2）：

對于p(?u|θ)，因為假設條件興趣點i 和j 的偏序關系與其他興趣點無關，則所有用戶在所有興趣點類別上的偏序關系的似然函數為公式（3）：

δ(x)是指示函數，如果x 為真，則函數值為1，如果x 為假，則函數值為0。根據排序關系的完整性和反對稱性，公式（3）可以簡化為公式（4）：

其中P(i ?uj|θ)可以用sigmoid函數來代替，如公式（5）：

假設P(θ)的先驗概率服從高斯分布，均值為0，協方差是矩陣λθI ，依據BPR 標準，最大化對數后驗概率如公式（6）所示：

對于公式（6），可通過隨機梯度下降算法求導數得到公式（7）：

由于公式（8）計算得到梯度下降迭代公式（9）：

最終通過迭代后得到w，h 兩個矩陣計算BPR 模型對于興趣點的偏好分數，如公式（10）所示。其中，w表示迭代后的用戶潛在特征矩陣，h 表示物品潛在特征矩陣。

3 融合社會關系與地理信息的推薦模型

3.1 基于社交關系推薦

不同于傳統的推薦中上下文信息是不完整或模糊的，而基于LBSN的興趣點推薦中包含了豐富且清晰的上下文信息，例如社交關系與地理位置。相比于陌生人，具有社交關系的朋友之間更頻繁地分享對于興趣點的偏好，在興趣點的選擇上也容易被朋友的偏好影響，因此具有社交關系的用戶在興趣點的偏好上有一定的相似性。模型通過用戶的社交網絡信息探究相似與信任兩個概念對推薦結果的影響。用戶相似度源自傳統的基于用戶的協同過濾推薦，但由于評分數據集極其稀疏，使得相似度的計算存在不確定性，導致相似用戶集合不夠準確，所以本文加入信任概念，通過具有社交關系的用戶的簽到信息計算信任度，最終將信任與相似融合作為社交因素的偏好。

3.1.1 相似度計算

首先采用皮爾森相關系數計算用戶之間的相似度，如公式（11）所示：

sim(u1,u2)表示用戶u1，u2的相似度，I(u1)和I(u2)表示用戶u1和用戶u2的簽到的興趣點集合，Ru1,p和Ru2,p分別表示用戶u1和用戶u2對興趣點p 的簽到頻率，和分別表示u1和u2對興趣點的平均簽到頻率。

3.1.2 信任度計算

在傳統的社交關系矩陣Ru1,u2，用戶u1與用戶u2存在社會關系，則對應元素值為1，反之為0。社交關系集合為U{u1,u2|Ru1,u2=1}。

傳統的社交關系矩陣中的0/1方式不能很好地表示用戶之間的遠近關系。基于社交關系集合，本文提出計算用戶之間的信任度來進一步量化用戶之間社交關系差異。信任度是由兩個方面決定：一是具有社交關系用戶之間共同簽到的興趣點數量。取共同簽到數量與最大簽到數量的比值作為信任度計算的第一部分，如公式（12）。二是用戶簽到質量。簽到質量是具有社交關系用戶對于興趣點的頻率與其他用戶對于此興趣點的簽到頻率之差是否小于一個閾值δ，閾值由實驗得出，計算小于此閾值的數量與所有共同簽到過的興趣點的數量之比表示用戶之間的信任程度，作為信任度計算的第二部分。計算公式如公式（13）和公式（14）。

Nu1u2表示用戶u1與用戶u2之間的共同的興趣點數量。

Qu1,j表示用戶u1對興趣點j 的簽到頻率，δ 表示閾值，詳細分析見4.3.3小節。

用戶之間信任度T 計算，如公式（15）所示：

3.1.3 偏好分數計算

基于社交關系的推薦計算，如公式（16）：

3.2 基于地理因素的推薦

Tobler 地理學法則表明，任何事物都具有相關性，且相比于距離遠的事物，距離近的事物之間相關性更大。興趣點之間同樣適合此法則，從節省時間的角度，用戶更傾向于訪問距離較近的興趣點，從用戶的興趣愛好角度，用戶往往存在以某個興趣點地理位置為中心的興趣點群。所以，本文提出融合地理因素影響作為影響因子。具體地，假設地理因素概率分布符合冪律分布，如公式（17）：

D(lm,ln）代表興趣點lm和興趣點ln之間的距離，本文a，b 均為常數。地理因素影響由給定用戶的簽到興趣點集合決定，給定用戶u 訪問過的興趣點集合Li，根據貝葉斯原理推得對于每個興趣點lj的計算公式，如公式（18）：

3.3 模型融合

模型性能差距較大時宜使用加權法，同時為提高推薦精度，不增加算法時間復雜度并且易于實現起見，將兩種模型進行線性加權，用戶的最終偏好分數計算由三種元素加權得到。融合了BPR模型偏序關系、用戶之間社交關系、地理位置遠近三者的綜合影響，如公式（19）：

選取偏好分數較高的top-k 個物品推薦給用戶。其中α 和β 為實驗取得參數，(α=0.5,β=0.25)時取得最優。基于TGMF模型的推薦算法步驟如下所示：

步驟1 根據偏序關系定義處理用戶簽到數據集，生成偏序關系對集合，作為矩陣分解的輸入。

步驟2 梯度下降迭代計算得到兩個隱藏特征矩陣，并使用兩矩陣乘積表示BPR模型的偏好分數，見公式（10）。

步驟3 采用皮爾森相關系數即公式（11）計算用戶相似度，得到用戶-用戶相似度矩陣。

步驟4 定義社交關系矩陣，通過公式（12）和公式（14）即共同簽到興趣點數量和簽到質量計算用戶-用戶信任度。

步驟5 將信任度作為調節相似度的因子，通過公式（16）即信任度矩陣與相似度矩陣相乘得到調節后的相似度矩陣，并與用戶-興趣點簽到矩陣點乘后得到社交關系的影響分數。

步驟6 定義地理因素的冪律分布公式（17），計算興趣點之間的距離，最終根據推導的貝葉斯公式（18）計算地理因素的偏好分數。

步驟7 使用線性加權方式定義模型的總偏好分數，即公式（19），并由高到低排序，選取前top-k 個興趣點推薦給用戶。

TGMF模型改進了傳統的BPR矩陣分解模型，融入用戶社交關系和地理位置信息，充分挖掘和利用具有社交關系的用戶選擇的興趣點和訪問頻率，能更好地擬合用戶之間的關系遠近，有效地提升了推薦質量，詳細分析見4.3.1小節。

4 實驗設計及分析

4.1 實驗數據集

實驗所用的數據集分別為Foursquare 數據集和Gowalla 數據集。Foursquare 是基于地理位置信息的手機服務網站。實驗所用的數據集過濾掉少于10個興趣點評分的用戶和少于10個用戶簽到的興趣點。最終的實驗數據集包含24 941 個用戶對28 593 個興趣點的評分，該數據集將80%作為訓練集，剩余20%作為測試集，訓練集共有491 100條記錄，測試集有157 903條記錄。

Gowalla是提供地理位置服務的社交應用。本數據集為2009 年2 月至2010 年10 月的簽到數據，數據集過濾掉少于15個簽到興趣點的用戶和少于10個用戶簽到的興趣點，過濾后數據集包含18 737個用戶對32 510個興趣點的簽到記錄，訓練集測試集劃分為80%和20%，訓練集共計566 791條記錄，測試集共計175 116條記錄。

4.2 評價標準

采用的推薦質量的評價標準分別是準確度（Precision）和召回率（Recall）[13]。

4.3 實驗結果

實驗比較了本文提出的TGMF（Trust-Geo Matrix Factorization）模 型 和LRT 模 型[14]、BPR-MF 模 型、MGMPFM（Multicenter Gaussian Model and Probabilistic Fator Model）模型在兩個真實數據集推薦精度上的差異。

4.3.1 TGMF模型與其他模型對比

（1）為探究社交關系對推薦精度的影響，選擇TGMF算法潛在特征向量長度為25，TGMF 模型α 、β 值取0.1。四種不同的模型在Gowalla 數據集下選取的top-k值下的準確度與召回率對比結果，如圖1和圖2所示。

圖1 是選取當所有算法準確度取得最優時的top-k值(k=5)作為準確度的度量標準。可以觀察到TGMF模型明顯優于LRT 與MGMPFM 模型，相對于BPR-MF模型也有一定程度提升。圖2 是選取所有算法召回率取得最優時的top-k 值(k=10)作為召回率的度量標準，可以觀察到，TGMF 算法相對于LRT 模型有明顯的提高，相對于MGMPFM 和BPR-MF 算法分別提高了29.6%和11%。結果表明在興趣點推薦中，社交關系是影響推薦精度的重要因素。

（2）BPR標準在挖掘用戶隱式反饋層面具有良好效果，本文采用BPR標準優化矩陣分解模型。由兩個數據集下TGMF和BPR-MF兩種算法與LRT和MGMPFM兩種算法比較結果，如圖1～圖4，可以得出采用BPR 標準的矩陣分解方法優于傳統的點級排序方式。在Gowalla數據集下，取準確度最高top-k 值(k=5)，BPR-MF算法在準確率指標下比MGMPFM 算法分別提高了40%，比LRT 算法提高了160%，可見BPR 模型能更為準確地建模用戶偏好，更好地挖掘興趣點推薦過程中的隱式反饋。

圖2 Gowalla-Recall

圖1 Gowalla-Precision

圖3 Foursquare-Precision

圖4 Foursquare-Recall

（3）LRT算法相比于其他三種算法準確率和召回率最低且在Gowalla 數據集上與其他算法差距較大，其原因是在基于LBSN 的興趣點推薦中用戶簽到的時間影響并不是影響推薦準確度的主要因素，所以將時間影響融入到矩陣分解過程中不能大幅度地提高推薦質量，在k=5 時，MGMPFM算法相比于LRT算法在準確度和召回率分別提高了108%和106%。圖1和圖2表明地理因素是影響興趣點推薦質量的一個重要因素。

（4）在Gowalla數據集中，TGMF算法相比于BPR-MF算法在準確率(k=5)和召回率(k=10)上分別提高了14%和13.8%。在Foursquare 數據集上，TGMF 算法相比于BPR-MF在準確率(k=5)和召回率(k=20)上分別提高了25%和9.3%，結果表明擬合社交因素和改進偏序關系的定義方式對提高興趣點推薦質量有明顯的意義。

（5）由圖1～圖4 可以得出，TGMF 算法在所有的評價標準下相對于其他三種算法都有不同程度的提高，驗證了TGMF算法的有效性。

4.3.2 參數K對TGMF模型的影響

在本文提出的興趣點推薦算法中，矩陣分解過程中隱藏向量的維度同樣是影響推薦精度的一個重要因素。取不同的K 值，分別為5，10，15，20，25，30，35。固定top-k 的值為10，選取不同K 值在Gowalla 數據集下的準確度。如圖5所示，K 值在5到25時準確度不斷提高，在K=25 時達到最優值，隨后開始下降。結果表明增大隱藏特征數量可以提高矩陣的表達能力，同時也帶來了噪聲等問題，適當的控制參數的數量且優先選取較為重要的影響因素是提高推薦精度的重要方式。

圖5 參數K對推薦準確度的影響

4.3.3 閾值δ 對TGMF模型的影響

實驗設置閾值決定兩用戶在某一興趣點上是否具有影響力。實驗首先統計Foursquare 數據集上所有的閾值分布，得出閾值為0、1、2、3、4、5、6 的比例分別為50%，22.9%，13.2%，6%，3.8%，2.2%，1.5%。圖6 顯示，隨著閾值增大，兩種評價標準先升后降，在閾值為1 時取得最優。

圖6 參數δ 對推薦性能的影響

5 結論

本文提出一種融合地理與社交關系的矩陣分解推薦算法，采用BPR標準優化矩陣分解過程，改變偏序關系的定義方式同時將信任加入到相似度的計算過程中，得到更為準確的社交關系影響，進而將地理因素與社交關系融入到興趣點推薦中。在真實數據集上的實驗表明，算法優于部分傳統的推薦算法。該模型具有一定的通用性，適用于微博轉發、新聞點擊預測、在線商務等用戶興趣隱性反饋領域，例如騰訊、百度地圖、微博、美團等對地理位置和社交關系的信息的開發與利用，將地點簽到、地理定位、社交關系等信息作為其推薦系統的影響因素。

未來將嘗試對多種上下文的信息融合方式做進一步探究，而不是簡單的線性融合方式。另外，探索將本文提出的模型和深度學習[15]相結合，期待進一步提高興趣點推薦性能。