融合社交关系与地理信息的兴趣点推荐模型

张 进，孙福振，王绍卿，王 帅，鹿祥志

山东理工大学 计算机科学与技术学院，山东 淄博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]相结合，期待进一步提高兴趣点推荐性能。