郭晨睿，李 平，2

1.長(zhǎng)沙理工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院，長(zhǎng)沙 410114

2.智能交通大數(shù)據(jù)處理湖南省重點(diǎn)實(shí)驗(yàn)室，長(zhǎng)沙 410114

1 概述

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

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

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

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

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

2 相關(guān)工作

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

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

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

3 FUSG模型

3.1 非對(duì)稱用戶影響

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

首先，需要計(jì)算用戶u對(duì)其所有簽到過(guò)的趣點(diǎn)l的平均簽到次數(shù) cˉu，如公式（1）所示：

其中，nu表示用戶u簽到過(guò)的興趣點(diǎn)的總數(shù)目。使用用戶的平均簽到次數(shù)cˉu來(lái)構(gòu)建布爾矩陣其中由公式（2）計(jì)算獲得：

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

不同于傳統(tǒng)的基于用戶的協(xié)同過(guò)濾算法中使用的對(duì)稱用戶關(guān)系矩陣，該用戶關(guān)系矩陣是不對(duì)稱矩陣。

假設(shè)：（1）用戶可以影響的用戶越多，則該用戶在興趣點(diǎn)推薦系統(tǒng)中用戶全局重要性越高；（2）如果有多個(gè)用戶可以對(duì)目標(biāo)用戶產(chǎn)生影響，則目標(biāo)用戶更容易受到全局重要性較高用戶的影響[18]。

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

其中，δ(x)是指示函數(shù)，當(dāng)x?0時(shí)δ(x)=1，否則δ(x)=0。

用戶u可以影響的用戶數(shù)目du通過(guò)公式（6）計(jì)算得到：

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

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

在FUSG模型中，具有較低的in-degree和較高的out-degree的用戶更重要。在公式（7）中，影響更多用戶并且受較少用戶影響的用戶具有較小PageRank值，PageRank值越小表明用戶越重要。解決上述問(wèn)題最簡(jiǎn)單的方法是使用單調(diào)遞增函數(shù)來(lái)改進(jìn)用戶的PageRank值，如公式（8）所示：

但是，該方法生成的用戶重要性值遠(yuǎn)大于其影響值，當(dāng)將用戶的影響值和重要性結(jié)合起來(lái)進(jìn)行預(yù)測(cè)時(shí)，后者會(huì)在推薦過(guò)程中壓制前者，減小前者對(duì)推薦質(zhì)量的影響。非對(duì)稱用戶影響值的范圍是[0，1]，因此用戶的PageRank值需要映射到[0，1]，所以上述方法并不適用。本文模型采用邏輯回歸函數(shù)將PageRank值映射到[0，1]，如公式（9）所示：

根據(jù)非對(duì)稱用戶影響值和用戶全局重要性值的乘積來(lái)對(duì)目標(biāo)用戶將在某興趣點(diǎn)簽到的概率進(jìn)行預(yù)測(cè)。給定用戶u，用戶u將在興趣點(diǎn)l簽到的預(yù)測(cè)概率c?ul根據(jù)公式（10）得到：

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

3.2 基于社交的影響

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

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

rvl表示用戶v在興趣點(diǎn)l簽到的頻率。

3.3 基于地理的影響

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

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

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

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

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

其中，P(l)是數(shù)據(jù)集中所有用戶在興趣點(diǎn)簽到先驗(yàn)概率表示訪問(wèn)過(guò)興趣點(diǎn)l的用戶數(shù)目。

3.4 FUSG模型

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

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

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

其中，L表示所有興趣點(diǎn)集合，Lu表示用戶u簽到過(guò)的興趣點(diǎn)集合。

4 實(shí)驗(yàn)結(jié)果及分析

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

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

表1 Gowalla實(shí)驗(yàn)數(shù)據(jù)集

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

在性能對(duì)比實(shí)驗(yàn)中，采用兩種Top-N指標(biāo)評(píng)估推薦的質(zhì)量，精確率Precision@N和召回率Recall@N。衡量指標(biāo)如公式（24）、（25）所示：

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

4.3 參數(shù)分析

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

圖2 參數(shù)β與精確率

圖3 參數(shù)β與召回率

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

圖4 參數(shù)α與精確率

圖5 參數(shù)α與召回率

4.4 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本章FUSG模型在興趣點(diǎn)推薦的性能，本節(jié)首先根據(jù)4.3節(jié)參數(shù)分析對(duì)參數(shù)進(jìn)行設(shè)置。將參數(shù)α和β的值分別設(shè)為1和0.5。本章采用的對(duì)比模型如表2所示。下面為四種對(duì)比模型的詳細(xì)介紹：

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

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

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

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

表2 本文模型和對(duì)比模型

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

圖6 五種模型精確率對(duì)比

圖7 五種模型召回率對(duì)比

5 結(jié)論與展望

本文提出的FUSG模型，能夠充分地利用用戶的簽到歷史、社交信息和地理信息。同時(shí)，提出了利用朋友間的居住距離和朋友集合來(lái)求解社交關(guān)系中的用戶相似度；最后融合地理信息得到推薦結(jié)果。通過(guò)在真實(shí)的Gowalla數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，表明本文的FUSG模型在提高興趣點(diǎn)推薦型性能上有了一定的提高，能夠?yàn)橛脩籼峁└鼫?zhǔn)確的參考。

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