融合社交關(guān)系與地理信息的興趣點(diǎn)推薦模型

張 進(jìn)，孫福振，王紹卿，王 帥，鹿祥志

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

1 引言

近年來，工業(yè)界與學(xué)術(shù)界對于基于位置的社交網(wǎng)絡(luò)LBSN的應(yīng)用探索逐年遞增，例如Foursquare、Facebook、Yelp 等。與傳統(tǒng)的電影、音樂以及書籍推薦不同，基于LBSN 的興趣點(diǎn)推薦面臨更多的問題和挑戰(zhàn)。選擇適合的上下文信息以及合理的融合策略是提高精度的一個(gè)主要途徑?；诰仃嚪纸獾耐扑]算法因在Netflix Prize 取得了突出效果而受到學(xué)術(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]提出了一種集成局部特征學(xué)習(xí)的LREAP算法，選取局部評分矩陣子模型，融合相似度優(yōu)化子模型，提出一種新的損失函數(shù)擬合誤差與參數(shù)約束。Jamali 等人[6]提出了SocialMF 算法，在矩陣分解的過程中集成了信任的傳遞機(jī)制，可以有效解決冷啟動(dòng)問題。Li 等人[7]使用LDA 模型挖掘用戶興趣潛在分布融入相似度的計(jì)算，使用動(dòng)態(tài)方法填充用戶簽到數(shù)據(jù)并計(jì)算興趣點(diǎn)概率。Yu 等人[8]使用泊松分布替代傳統(tǒng)的高斯分布擬合用戶簽到行為，使用BPR標(biāo)準(zhǔn)挖掘興趣點(diǎn)推薦中的隱式反饋，融入地理影響作為矩陣分解的正則化因子，但并未考慮社交關(guān)系的影響。

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

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

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

2 基于BPR標(biāo)準(zhǔn)的矩陣分解

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

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

對于p(?u|θ)，因?yàn)榧僭O(shè)條件興趣點(diǎn)i 和j 的偏序關(guān)系與其他興趣點(diǎn)無關(guān)，則所有用戶在所有興趣點(diǎ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(θ)的先驗(yàn)概率服從高斯分布，均值為0，協(xié)方差是矩陣λθI ，依據(jù)BPR 標(biāo)準(zhǔn)，最大化對數(shù)后驗(yàn)概率如公式（6）所示：

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

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

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

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

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

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

3.1.1 相似度計(jì)算

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

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

3.1.2 信任度計(jì)算

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

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

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

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

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

3.1.3 偏好分?jǐn)?shù)計(jì)算

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

3.2 基于地理因素的推薦

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

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

3.3 模型融合

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

選取偏好分?jǐn)?shù)較高的top-k 個(gè)物品推薦給用戶。其中α 和β 為實(shí)驗(yàn)取得參數(shù)，(α=0.5,β=0.25)時(shí)取得最優(yōu)?；赥GMF模型的推薦算法步驟如下所示：

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)設(shè)計(jì)及分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

4.2 評價(jià)標(biāo)準(zhǔn)

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

4.3 實(shí)驗(yàn)結(jié)果

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

4.3.1 TGMF模型與其他模型對比

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

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

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

圖2 Gowalla-Recall

圖1 Gowalla-Precision

圖3 Foursquare-Precision

圖4 Foursquare-Recall

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

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

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

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

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

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

4.3.3 閾值δ 對TGMF模型的影響

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

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

5 結(jié)論

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

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