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

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

1 引言

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

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

為挖掘興趣點推薦的隱式反饋行為，傳統(tǒng)的BPR偏序?qū)ι蛇^程將簽到過的POI 作為正例，未簽到過的POI 作為負例，單純地考慮簽到與未簽到的POI 之間的關(guān)系，忽略了簽到的POI之間存在偏序關(guān)系。本文增加簽到頻率高低作為正負例的偏序?qū)ι煞绞?，進而更充分地挖掘用戶對POI的偏好。

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

2 基于BPR標準的矩陣分解

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

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

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

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

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

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

對于公式（6），可通過隨機梯度下降算法求導(dǎo)數(shù)得到公式（7）：

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

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

3 融合社會關(guān)系與地理信息的推薦模型

3.1 基于社交關(guān)系推薦

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

3.1.1 相似度計算

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

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

3.1.2 信任度計算

在傳統(tǒng)的社交關(guān)系矩陣Ru1,u2，用戶u1與用戶u2存在社會關(guān)系，則對應(yīng)元素值為1，反之為0。社交關(guān)系集合為U{u1,u2|Ru1,u2=1}。

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

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

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

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

3.1.3 偏好分數(shù)計算

基于社交關(guān)系的推薦計算，如公式（16）：

3.2 基于地理因素的推薦

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

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

3.3 模型融合

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

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

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

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

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

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

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

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

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

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

4 實驗設(shè)計及分析

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

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

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

4.2 評價標準

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

4.3 實驗結(jié)果

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

4.3.1 TGMF模型與其他模型對比

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

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

（2）BPR標準在挖掘用戶隱式反饋層面具有良好效果，本文采用BPR標準優(yōu)化矩陣分解模型。由兩個數(shù)據(jù)集下TGMF和BPR-MF兩種算法與LRT和MGMPFM兩種算法比較結(jié)果，如圖1～圖4，可以得出采用BPR 標準的矩陣分解方法優(yōu)于傳統(tǒng)的點級排序方式。在Gowalla數(shù)據(jù)集下，取準確度最高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 數(shù)據(jù)集上與其他算法差距較大，其原因是在基于LBSN 的興趣點推薦中用戶簽到的時間影響并不是影響推薦準確度的主要因素，所以將時間影響融入到矩陣分解過程中不能大幅度地提高推薦質(zhì)量，在k=5 時，MGMPFM算法相比于LRT算法在準確度和召回率分別提高了108%和106%。圖1和圖2表明地理因素是影響興趣點推薦質(zhì)量的一個重要因素。

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

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

4.3.2 參數(shù)K對TGMF模型的影響

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

圖5 參數(shù)K對推薦準確度的影響

4.3.3 閾值δ 對TGMF模型的影響

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

圖6 參數(shù)δ 對推薦性能的影響

5 結(jié)論

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

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