融合相对评分的个性化兴趣点推荐算法

单硕堂 陈廷伟 贾梦威

(辽宁大学信息学院 辽宁 沈阳 110036)

0 引 言

随着人们对网络社交需求的提高，诞生了一种新的基于位置的社交网络[1](LBSN)。基于位置的社交网络不仅指的是社会关系用户，而且还包括兴趣点(POI)签到以及签到时间戳和对地点的相关评论、描述。与其他社交网络相比，LBSN不仅能够反映用户真实生活中所在的地理位置，而且将现实生活和虚拟世界进行有效地结合，为研究者提供了机会和挑战。

个性化推荐主要以用户、信息以及用户和信息之间的关系为研究对象，经过对用户的行为方式，独特偏好等信息进行剖析和学习，挖掘出用户的兴趣和特点，从而形成模型。如今的个性化推荐方法已经应用在生活中的各个领域，如日常所知的电影推荐、音乐推荐等。

经过对目前个性化推荐的研究发现，在所涉及数据的维度方面可以分为同构社交网络的推荐和异构社交网络的推荐。同构社交网络下主流的个性化推荐方法有三种：协同过滤方法、基于上下文感知的方法和链路分析法[2]。目前应用最广泛的协同过滤算法以寻找与用户相似度高的项目为原理，间接推断目标用户的兴趣，投其所好进行推荐，亚马逊的书籍推荐使用的就是协同过滤算法。协同过滤算法主要由三个阶段构成：首先根据相关历史数据，计算出用户之间的偏好相似度，其次以用户所在位置为参照选择top-n个用户可能去的地点，最后对推荐的结果进行评估。张俊等[3]提出了融合兴趣和评分的协同过滤推荐算法，将用户相似性和用户评分相似性进行两次融合，通过专家信任度的概念对用户未评分项目进行评分预测填充，降低了数据的稀疏性。链路分析是将社交网络抽象成拓扑结构，从中挖掘数据之间的关联性，从而形成推荐。Cheng等[4]通过将用户签到信息抽象成马尔科夫模型，通过区域的过滤推荐用户附近的兴趣点。上下文感知的推荐方法主要通过用户的个人信息及位置属性构建推荐模型。Meng等[5]将LBSN和上下文推荐方法进行结合，从而提高推荐精度。LBSN在同构信息网络下的个性化推荐已经被许多学者进行了广泛的研究。近年来，LBSN异构的特性也被发掘出来，只是研究还处在新兴阶段，其中曹玖新等[6]就从LBSN数据的异构特性展开研究，用元路径的方法进行个性化推荐，在一定程度上对数据存在的稀疏性有了缓解，并提升了推荐的准确性，但仍然有一定的不足。

本文首先对评分信息体现个性化问题进行了描述，接着对用户的评分行为进行研究，以效用模型和比较模型为依据提出用户相对评分概念。通过相对评分来学习用户个性化偏好，并将相对评分信息转化为元路径的权值进而提出融合相对评分的个性化兴趣点推荐算法MpgbCount(Bidirectional Meta-Path Grade Count)，最终形成一个效果理想的个性化兴趣点推荐系统。该算法利用LBSN中的异构性信息和相对评分信息，充分挖掘用户的个性化，并在一定程度上缓解了数据的稀疏性，进一步提升了推荐系统的准确性和个性化程度。

1 相关理论基础

1.1 基于双向元路径诱导的相似度度量算法

根据双向路径诱导模型，设计元路径下两个节点之间相似度的度量方法(MpgbSim算法)：

MpgbSim(A1,An|L)=

(1)

式中：元路径L=A1A2…An，A为对象类型节点集合。MpgbSim(A1,An|L,Ai)表示按照正向诱导元路径L从A1节点到Ai节点的抵达率和按照逆向诱导元路径L-1从An节点到Ai节点的抵达率的乘积。ξ表示迭代计算节点的每个出度到目标节点的概率累加和与出度数量相除的函数。

1.2 用户专家的引入

定义1用户专家[11]：用户u评论过的兴趣点大于阈值φ且对某类兴趣点有过评论，称用户u为这类兴趣点的专家。用函数表示:

(2)

(3)

式(2)中:rui表示用户u对兴趣点i的评分；g(rui)表示对某类兴趣点是否评论过。式(3)中：m为系统中用户的数量；n为系统中兴趣点的数量。

1.3 各种兴趣点推荐算法比较

(1) 基于内容的推荐 系统在不用获得用户对兴趣点评价意见的情况下，通过学习用户对选择过偏好地点的内容信息，来完成对新的兴趣点喜好程度预测。如今基于内容的推荐系统对用户的历史信息建立配置文件，通过对配置文件相似性的比较进行推荐。基于内容的推荐优点为不需要考虑用户-项目评价矩阵的稀疏性问题，对冷启动的问题也有一定缓解作用，并且有一套完善的理论体系进行支撑。但缺点是由于基于内容的推荐仅可以向用户推荐与其历史信息有关的项目，推荐结果易出现针对特定数据产生特定结果的问题，算法的扩展性不好，缺乏潜在挖掘能力。

(2) 基于协同过滤的推荐 基于协同过滤的兴趣点推荐技术是根据使用者对兴趣点的打分来预测兴趣点对使用者的相关程度。其优点有[7]：避免了基于内容推荐时，项目关键词提取准确度不够的问题，可以发现用户潜在兴趣偏好；自适应性好，能够获得用户充分的隐式反馈。如今将协同过滤算法主要分为基于内存和基于模型两类。基于内存的推荐核心思想是通过将使用者对项目的打分形成的矩阵进行分析，确定与用户相似度最高的最相关集合，进而通过最相关集合内用户对某个项目的评分，来预测被推荐人对那些没有评过分项目的评分。基于模型的推荐算法，通过训练用户-兴趣点的评分矩阵形成决策模型，将贝叶斯网络、聚类、降维等技术与基于模型的推荐进行融合，从而对高维矩阵数据稀疏性问题进行处理[8]。

1.4 推荐系统评价指标

定义2准确率：准确率为在所有推荐结果中用户会感兴趣的概率。推荐系统所推荐的兴趣点会产生四种情况：用N1表示系统测算后推荐的兴趣点用户正好喜欢；N2表示系统测算后推荐的兴趣点用户不喜欢；N3表示用户喜欢的推荐系统没有进行推荐；N4用户不喜欢的兴趣点并且系统没有推荐。按照分数高低的推荐数N=N1+N2，用M代表用户喜欢的兴趣点数，则M=N1+N3，则计算方法为：

(4)

定义3召回率：召回率表示为系统最终推荐给用户喜欢的兴趣点占全部兴趣点的比例，则计算公式为：

(5)

2 融合相对评分的个性化兴趣点推荐

2.1 评分描述个性化问题

传统的异构社交网络只考虑了节点类型和关系类型，而个性化推荐算法不仅仅要在用户与兴趣点的相似度度量准确性上努力，还需要充分体现个性化程度[9]。目前大部分研究异构信息网络的个性化推荐中，都忽略了元路径上的属性值或者权重信息，然而在实际生活中，元路径中带有相关属性信息的异构社交网络是非常普遍的[10]。我们在Yelp数据集中通过用户专家对商家的喜好不同，打出1～5分的评分来反映用户本身的个性化信息。

当出现相同的兴趣点相似度时，传统的相似度算法只能并行推荐，不能按照优先顺序进行推荐。如果将用户专家的评分作为权值引入到原路径中去，通过权值大小为好友推荐，即使兴趣点相似，也能通过权值更精确地推荐。为了能够更精确地反映用户的个性化信息，引入了带权异构社交网络和带权元路径的概念。

2.2 概念扩展

定义4带权值的异构社交网络[11](WHSN)：已知由G=(V,E,A,W,S,φ，ψ)组成的社交网络，其中：V是对象的集合，V={v1，v2，…,vn}，vi(1≤i≤n)代表网络中的节点，n是节点的数量;E是链接的集合;A是对象类型的集合且φ:V→A是对象类型集合之间的映射函数，其中每个对象类型v∈V属于一个特定的对象类型φ(v)∈A；W表示节点间属性值的集合[11]。当对象类型的数量|A|>1或者链接类型数|S|>1且|W|>0时，这个社交网络为带权值的异构社交网络；当对象类型的数量|A|>1或者链接类型数|S|>1且|W|=0时为非带权值的异构社交网络。

定义5带权元路径：带权元路径是节点间路径上存在属性值的一种元路径，其符号表示：

其中：αi(si)表示元路径关系S上的属性值，若元路径上属性值取值为空，则这条路径为非带权元路径，反之，这条元路径为带权元路径。

2.3 用户评分行为分析

如果用户专家U1在带权路径下，同时对不同类型的商家A和商家B都打了4分，从直观上无法确定U1更喜欢哪一个商家，这就需要从相对的角度去判断，比如历史的评分，同类商家的评分等发现用户的偏好。为了提高对用户兴趣点推荐的准确性，针对用户在带权异构社交网络下评分差异的问题，我们从以下三个性质对用户评分行为进行剖析[12]：

(1) 相对性 从用户专家对兴趣点的评分，仅能很局限地预测用户的偏好，因为评分具有相对性，所以预测结果会产生一定的差异。例如，用户专家U1对兴趣点A的评分是4分，而他的历史评分平均值在4.3分，我们可以分析出相对其他兴趣点而言，U1不太喜欢兴趣点A。由于评分存在相对性，为了更好地获取用户的偏好，不能仅仅使用单一绝对的评分值。为了更好地进行个性化推荐，我们必须从相对的角度看待用户的评分行为，用用户评分的相对顺序代替原来的具体数值，尽可能地学习用户的偏好。

(2) 比较性 用户对兴趣点评分的过程，其实是一个比较的过程，与历史评分进行比较，与去过的兴趣点进行比较。所以用户的评分并不是随心所欲，互不影响的，是由心情、时间、回忆等多种因素影响的过程。为此本文通过对比筛选的过程来模拟。

(3) 时限性 根据心理学中的短期记忆效应，考虑历史评分要有一定的时间限制，不能把用户所有的历史签到行为都考虑进来。所以在比较模型中引入时间阈值的思想将用户比较的历史评分记录限定在一定范围内。

通过上面对用户评分行为的分析，本文提出了一种新的模型来学习以用户评分来预测用户的兴趣偏好的问题，这个模型是以效用理论作为基础的选择模型当作参考而引出的。在时间阈值范围内，收集一个用户专家的所有对兴趣点的签到评分记录并形成一个评分矩阵，所有用户专家评分矩阵形成一个数据集，每个集合中全部的兴趣点都会有相应的评分，并且将兴趣点按照评分大小进行排序后形成偏序关系集。用户专家对某个兴趣点评分高，可以推出他可能对这一类兴趣点都感兴趣。为了更好地预测用户个性化偏好，可以在偏序关系的基础上对于用户的评分行为进行学习。

2.4 相对评分问题定义

我们在Yelp数据集获取了N个用户专家和M个兴趣点，定义U={u1，u2，…，un}为用户集合，P={p1，p2，…，pn}为兴趣点集合，U和P形成了一个用户-兴趣点的评分矩阵R，一个用户ui会对一个兴趣点pj进行签到评分rij。针对基于位置的异构社交网络进行研究，要求用户专家的评分记录在设定的时间戳内，按照先后顺序进行排序，并将评分集合形成的属性集称为时限签到集合。

定义6时限签到集合：时限签到集合记录了用户专家在时间阈值T内，在相应的时间对相应的兴趣点的评分信息，于是有：

(6)

式中：t(i，pj)表示ui对pj的签到时间，是指用户i所有的签到评分记录中以兴趣点j为起点以时间阈值T为约束的所有签到评分的集合，其中pk、pj代表兴趣点，rik是用户i对兴趣点k的评分。

为了更好地解决数据稀疏性问题，找到合适的时间阈值，我们用用户专家评分的前K次记录来模拟时间阈值。按照时间顺序，将用户-兴趣点评分矩阵中的每一行用户评分信息进行排列，在时间阈值的范围内形成一个集合，也可根据用户专家对兴趣点信息打分的分值由高到低进行排列，从而构成一个偏序关系，用符号表示为：

(7)

2.5 用户评分行为建模

pj▷phIIFZ(ui,pj)≥Z(ui,ph)

(8)

式中：Zij表示Z(ui，pj)的简化形式。兴趣点j的效用值比h的效用值高时，证明用户相对于h来说更喜欢j。

根据随机效用模型RUM(Random Utility Model)[14]，效用由以下两部分构成，其公式化表示为：

Z(ui,pj)=Q(ui，pj)+εij

(9)

式中：Q(ui，pj)=rij表示显示效用，即可以通过某种方式观察到的，例如对兴趣点的相对评分；而εij代表隐式效用，例如一些偶然事件。为了方便研究，本文用矩阵分解中常用的隐式因子来表示评分rij。由于用户在对兴趣点评分时会受到一定的隐性因素影响，而一部分对评分产生影响的隐因子可以成为用户对兴趣点的兴趣维度。

基于效用的用户兴趣偏好度表示为：

Pro(pj▷ph)=Pro(Z(ui,pj)≥Z(ui,ph))

(10)

将式(10)代入式(11)得：

Pro(pj▷ph)=Pro(Q(ui，pj)+εij≥Q(ui，ph)+εih)=

Pro(Q(ui，pj)-Q(ui，ph)+εij≥εih)

(11)

根据Logit模型，按照双重指数表示更为准确，于是推导出用户对两个兴趣点的偏好度形式化为：

(12)

(2) 用户评分选择模型 在Yelp数据集中，存在大量的评分数据和近期签到集合，集合的整体兴趣偏好度公式可表示为：

(13)

式中：Q(u)代表用户专家u所有的兴趣点签到集合。和前面一样使用隐性因子Z、Q来表示效用，为了避免过拟合现象，对Z和Q进行先验，即一个球形多变量的高斯先验：

Pro(Z,Q|Θ)=N(Z,Q|0,σ2I)

(14)

图1是基于比较的用户评分行为对应图模型。其中:≥T表示观测变量，即为有时间阈值约束的兴趣点签到集合，Zi和Qj表示需要学习的未知变量。根据矩阵分解理论，当Zi和Qj获得后，用户对兴趣点的效用值可以被近似地算出，两个参数σZ和σQ是先验超参，M和N分别代表兴趣点数目和用户的数目。

图1 用户比较模型图

根据贝叶斯原理，求得后验概率为：

Pro(Z,Q|▷T)∝Pro(▷T|Z,Q)Pro(Z|Θ)Pro(Q|Θ)

(15)

同样，我们将目标函数化成对数形式：

{Z,Q}= arg min-[logPro(▷T|Z,Q)+

logPro(Z,Q|Θ)]

(16)

式中:第二项可以看作是消除过拟合问题的正则化项，并且{Z，Q}服从高斯先验。根据随机梯度下降原理[16]每次优化时随机选取一个用户专家对兴趣点的评分，只针对于该评分相关的用户和兴趣点的隐式因子进行优化，由于使用ZQT来度量rij,则对Z和Q的推导公式为：

(17)

(18)

最终基于比较的用户相对评分预测值为：

(19)

2.6 融合相对评分的个性化推荐

通过前面的学习，形成了用户-兴趣点的相对评分矩阵β∈RN×M，其中相对评分矩阵β中的每个元素β(u,p)代表用户专家u对特定兴趣点p的相对评分。把基于位置的社交网络模型中元路径的权值用用户u对兴趣点p的相对评分来表示，从而提出MpgbCount推荐算法，用公式表示为：

(20)

式中：pro(i,j)表示特定元路径L下节点i到达节点j的概率；βij为节点i到节点j的路径权值，即用户专家i对兴趣点j的相对评分。

3 实验及结果分析

本节将MpgbCount算法与其他个性化推荐算法进行对比，验证本文所提方法的优越性。实验环境为联想笔记本，Intel i5，内存为8 GB，采用Java语言编写。

3.1 实验数据及方法

本文通过Yelp数据集、FoursquareAll全球数据集和FoursquareNY纽约数据集对MpgbCount算法进行评估。Foursquare数据集是通过公开的API抓取的，如表1所示。

表1 Foursquare数据集整理

用户可以在Yelp网站对自己感兴趣的地点进行签到，分享给好友，对商家进行打分或者添加评论信息，所以可通过Yelp数据集对MpgbCount算法进行评估。由于存在低频用户，使得数据存在稀疏性，为了不影响个性化推荐的结果，我们对数据进行了一定的预处理，筛选出符合用户专家标准的用户数据进行测验。经过筛选，得到20 166个用户和39 104个兴趣点信息，总计评分数为152 721个。为了方便进行实验，将数据分成训练集和测试集两部分，并将整体数据的90%最为训练集，剩余的10%作为测试集。表2为Yelp数据集整理。

表2 Yelp数据集整理

通过图2所展示的用户对兴趣点评分的分类，我们发现大部分用户对自己喜欢的兴趣点都打了4～5分，而且很多用户在对兴趣点签到时就会对兴趣点进行评分。

图2 用户评分直方图

在实验方面，将MpgbCount推荐算法与其他经典的算法进行对比，通过准确率和召回率的高低来衡量个性化推荐系统的好坏。

3.2 实验数据结果及分析

在基于元路径的个性化兴趣点推荐方面，目前只有曹玖新等[6]发表了一篇文章，但其并没有考虑到元路径的权值信息和元路径节点间相遇的问题。本文采用双向元路径诱导相似度的方式，将用户评分信息作为元路径的权值，解决了文献[6]的M算法中存在的元路径相遇和权值信息的问题。在Yelp数据集所组成的带权异构社交网络下，将本文所提出的MpgbCount算法与文献[6]的M算法以及文献[17]中所提到的常见的算法进行对比。

由于评分具有时效性，需要分析时间阈值对算法产生的影响。我们用所记评分之前k次来代替时间阈值T，代表用户通过短期记忆能够将多少个以前的评分进行综合考虑。图3显示了时间阈值k的取值对Recall的影响。可以看出，当用户专家在评分时考虑相对较少的历史评分时，短期记忆占了主导地位，这时算法随k的升高而有所下降，所以时间阈值T的选取需要具体衡量。在与其他算法进行比较时，需根据实验结果的具体情况选择相对应的k值进行计算。

图3 时间阈值对Recall的影响

本文在同等情况下对表3中的算法进行对比，并通过准确率和召回率来度量算法的优劣。由于MpgbCount算法综合考虑了用户与用户之间、兴趣点与兴趣点之间、用户与兴趣点之间的各种关联情况，进而对各节点之间潜在的相关性进行挖掘，该算法相较于其他未充分考虑节点关系及单纯考虑用户评分分值的算法推荐效果提升明显。

表3 各种算法简单描述

各算法的准确率如图4所示，召回率如图5所示。不难发现，本文所提到的MpgbCount算法在准确率和召回率两个方面都有很好的表现，本文算法相比M算法在推荐方面具有一定的优势，相比其他算法优势更加明显。所以在带权值的异构社交网络的研究中，本文所提出的MpgbCount的算法对兴趣点的个性化推荐有着很好的效果。

图4 Yelp数据集中各算法推荐结果的准确率

图5 Yelp数据集中各算法推荐结果的召回率

针对LBSN常见的数据稀疏性问题，将MpgbCount算法和表3中的各种算法在Foursquare两种稀疏性不同的数据集上进行准确性测试，结果如表4所示。本文所提出的MpgbCount算法在准确性上降低的范围在10%～15%之间，而其他算法的降低范围都在15%以上，甚至有很多在20%以上。由此可以证明本文所提出的MpgbCount算法对数据的稀疏性有一定程度的缓解。

表4 各算法在Foursquare不同数据集准确率对比

4 结 语

本文针对LBSN中基于双向元路径的兴趣点推荐问题，在完成异构社交网络下对不同类型节点间进行相似度测量的前提下，提出了融合相对评分的个性化推荐算法。对兴趣点推荐系统中以用户对兴趣点评分的形式描述个性化的问题，并就单纯的评分分值在一定程度上存在用户偏好误差的问题进行深入研究。从评分的时效性和相对性角度出发，对用户的评分行为进行分析，基于比较模型和效用理论提出相对评分概念，构建用户相对评分选择模型。将相对评分转化为元路径的权值，构成带权元路径，可以更好地度量用户与兴趣点间的相似度，最后通过个性化推荐算法生成推荐列表。实验显示，本文算法相比其他推荐算法推荐效果更佳，并且对数据稀疏性由一定的缓解作用。