融合用户隐含偏好的社会化推荐算法

杨 鹏,邵 堃,霍 星,张阳洋,景永俊,3

1(合肥工业大学 计算机与信息学院,合肥 230009) 2(合肥工业大学 数学学院,合肥 230009) 3(北方民族大学 计算机科学与工程学院,银川 750021)E-mail:huoxing@hfut.edu.cn

1 引 言

当今是一个信息爆炸的时代,各种各样的信息充斥着人们的眼球,其中大量的信息对于某一用户来说是无效的.如何对冗余信息进行过滤,对用户关注进行可靠而有效的推荐,满足用户个性化的需求,是当今研究的热点与难点.

目前,主流推荐系统可以分为3类:基于内容的推荐[1]、协同过滤推荐[2]和组合推荐[3].其中,协同过滤推荐算法因其对推荐对象没有要求,能够处理非结构化的复杂对象而受到工业界和学术界的共同关注.协同过滤算法是通过对用户的历史评价进行分析,找到与目标用户兴趣相似的用户群,综合这些用户对于某一产品或服务的评价,对目标用户感兴趣的产品或服务进行预测.这符合人类的正常思维,并且通过共享他人的经验,往往能发现用户潜在的而本人尚未发现的兴趣爱好.

传统的协同过滤算法从用户的显式偏好入手,将用户对商品的评分或购买记录作为依据,来对相似用户进行分析,利用具有相似偏好的用户进行推荐[4,5].但是推荐系统中用户数量和产品数量都是十分庞大的,单个用户的评分记录或是购物记录相对于整个推荐系统来说是极小的一部分,这就造成了稀疏和维度灾难问题.基于矩阵分解的算法[6-9]由于其对高维数据的处理优势脱颖而出.该类算法以矩阵的形式表示用户对产品的评分信息,之后将评分矩阵分解为用户和产品的潜在特征向量,进而用用户和产品向量间的内积来描述两者之间的关联性.这个潜在特征向量通过描述物品和用户在各个属性上的偏好来解释评分值,而这些属性是从用户反馈自动推断的,如质量、价格、送货时间等等.现在社会,同质化的产品越来越多,用户需要的不仅仅是评分高的产品,更需要符合自己偏好的产品.本文将用户潜在向量中所包含的偏好信息定义为用户的隐含属性偏好,它提供了用户偏好的额外信息.利用相似度度量算法计算出用户间隐含属性偏好的相似度,将其融入矩阵分解模型,可以优化矩阵分解的过程,增加预测准确度.

矩阵分解算法有效解决了数据的稀疏和高维问题,但是由于其依赖评分信息,对于评分数量极少的用户,也就是常说的冷启动用户,推荐效果较差.为了解决这一问题,研究人员开始将社交信息融入矩阵分解模型[10],提出了社会化推荐算法[11,12].这是建立在一种观察之上:相较于根据相似匿名用户在线系统的推荐,人们更倾向于依赖他们信任用户的推荐.当前主要使用的社交信息有两种[13]——信任关系和好友关系.其两者的主要差别为,信任关系一定程度建立在相似的偏好与品味上,而好友关系则是建立在社交圈之上,可能不存在相似偏好的基础.在社交生活中,用户的推荐来源远不止来自好友的推荐,基于口味相似而互相信任的用户推荐也很大程度上影响着用户的选择.通过对直接信任关系的分析,基于信任总体的RSTE[14]、基于信任传播的SocialMF[15]等一系列社会化算法被提出,并取得了一定的成效.随后,研究人员开始挖掘间接的信任关系.Fang 等人[16]将信任信息Sik分解成:善意(benevolence)、正直(integrity)、能力(competence)、可预测性(predictability)4个维度进行衡量.Yao[17]和Pan[18]等人将信任信息分解为信任主体和信任客体进行分析.但是以上算法将用户信任的每一个其他用户都视为同等的存在,割裂了信任关系与评分的联系,没有考虑到建立起这种信任关系背后所包含的用户偏好.本文将信任关系与用户的评分记录相联系,利用评分记录为信任关系加权,建立了用户的隐含信任偏好,代替了原本单纯的要么信任要么不信任的0-1信任关系,充分挖掘了隐含在信任关系中的用户偏好.

另外,不同的用户有不同的评分偏好[19].有的用户偏好给自己非常满意的产品打出高分,对于在自己期望值左右的产品使用默认评价或是不予置评;有的用户无论什么产品都会给出自己认为合适的评分.这两者相比,前者的评分均值更高.而产品方面,有些产品的整体评分较高,即使出现单个产品的低分也不会影响其全局评分,反之亦然.同时,在不同的平台上有不同的产品类型,用户所给出的评分根据产品类型的不同会偏向保守或是偏向开放.所以,需要引入偏置来减小这种由用户的评分偏好所带来的影响.在Netflix Prize比赛中,将偏置加入到传统矩阵分解模型中去也已被证明是有效的[20].

基于以上论述,本文通过引入用户隐含属性偏好、隐含信任偏好、评分偏好,提出了一种融合用户隐含偏好的社会化推荐算法SocialIP(Social recommendation integrating Implicit Preferences).该算法的主要贡献如下:

利用用户隐含属性偏好的相似度拓展和优化了矩阵分解模型,对于提供显式偏好不足的用户更加有效.同时将用户评分的相似度降至低维进行评估,有效地防止了由于用户评分过少而出现的用户间过于相似的情况发生;考虑到用户评分记录和信任之间关系而引入了用户隐含信任偏好,深度挖掘了评分信息与信任信息的联系,使得推荐来源更为可靠.

2 相关工作

本节主要介绍社会化推荐的一般场景,并对概率矩阵分解算法PMF[21]和基于社交网络中信任传播机制的推荐算法SocialMF进行概述,本文在以上两个算法的基础上进行了改进与创新.

2.1 问题描述

社会化推荐系统是在社会化网络分析理论的基础上,将用户社会属性信息加权融合到传统推荐系统中,以提取更优的潜在特征向量.在缓解传统推荐系统中数据稀疏性及冷启动问题的同时,还提高了推荐系统的性能.其问题所处的一般场景如下:

假设有N个用户组成的用户集为U={u1,u2,…,un},M个产品组成的产品集I={i1,i2,…,im},用户与产品之间构成一个评分矩阵R=[Ru,i]N×M,用户u与产品i若有历史交互并进行评价,则评分矩阵中的元素Ru,i表示用户u对产品i的评分,若无评价信息,则Ru,i为空值.在社会网络中,用户与用户之间的信任关系常用信任矩阵T=[Tu,v]N×N表示,其中的元素由0和1组成,若用户u与用户v为直接好友则Tu,v为1,否则为0.用户u拥有的直接好友的集合为Nu.

社会化推荐算法需要解决的问题为:给出一个用户u和产品i,其评分Ru,i是未知的,利用已有的评分矩阵R和信任矩阵T来推断u对i的评分.

2.2 概率矩阵分解(PMF)算法

传统的协同过滤算法难以处理海量数据,并且在用户评分极少的情况下,无法给出精确的预测值,于是Salakhutdinov等人提出了概率矩阵分解模型.该模型假设存在潜在用户特征矩阵UK×N和产品潜在特征矩阵VK×M,将评分矩阵的条件分布定义为:

(1)

(2)

结合公式(1),用户和产品特征的后验概率可由贝叶斯公式推导为:

(3)

与公式(3)对应的图模型如图1所示.

图1 概率矩阵分解(PMF)图模型Fig.1 Graphical model for Probabilistic Matrix Factorization(PMF)

最后通过梯度下降的方法更新Uu和Vi中的元素值,对原矩阵中未知的元素进行预测.在同一个推荐系统中,无论是评分信息还是信任信息,其用户是相同的,即共享同一个用户空间.那么概率矩阵分解算法将用户矩阵分离出来,则可以将其他与用户相关的附加信息加入到推荐模型中去以提高推荐精度.本文基于这一点,引入用户隐含偏好,利用用户间的偏好相似度优化用户空间,符合协同过滤的基本思想,拓展了传统的矩阵分解模型.

2.3 SocialMF推荐算法

Ma等人提出了SocialMF模型,利用用户的社交信息,将信任传播与矩阵分解相结合,从社交关系角度拓展了概率矩阵分解的模型.文中提出,由于社交关系的影响,用户u所拥有的直接好友Nu会影响用户的行为.也就是说,用户的潜在向量是依赖于其所有的直接好友的,公式(4)表示了这个影响:

(4)

(5)

考虑到社交网络并不会改变观测到的评分的条件分布.它只影响用户潜在特征向量.评分的条件概率与公式(1)中的条件概率相同.但是对于用户潜在矩阵,则变为两个影响因素:零均值的高斯分布以及其直接好友的潜在特征的条件分布,表示如公式(6)所示:

(6)

根据评分和社会关系矩阵,利用贝叶斯推断可以得到隐含特征的后验概率:

(7)

同样,最后对在Uu和Vi上对所有用户u和所有产品i进行梯度下降来找到目标函数的局部最小值.

SocialMF算法在概率矩阵分解的框架下加入了信任关系,在一定程度上缓解了冷启动问题.但是其对信任关系的挖掘并不充分,仅利用信任传播为用户进行信任的加权,没有考虑到隐含在用户信任背后的偏好关系.用户不可能在所有产品上都与其信任的用户相一致,信任关系建立的背后所包含的用户偏好是不同的.本文在其基础上构建了用户隐含信任偏好,让评分不仅依赖于用户和产品的潜在特征向量的交互,也受用户的相似信任用户的影响.

3 融合用户隐含偏好的社会化推荐算法

本节对用户隐含属性偏好进行描述,并将信任信息与评分信息联系起来,构建了用户隐含信任偏好,最后综合用户的评分偏好,正式定义融合用户隐含偏好的社会化推荐算法.

3.1 用户隐含属性偏好

正如前文所述,用户评分的背后隐含着对各个属性的偏好程度.所以在分析用户相似度时,除了通过对用户已评分产品进行分析而获得用户的显式偏好,还应该对用户隐含的偏好进行分析.评分矩阵R经过分解,可以获得用户潜在矩阵UK×N和产品潜在矩阵VK×M..用户矩阵中的元素显示的是用户对于某一属性的偏好程度;产品矩阵中的元素显示的是产品的拥有某一属性的程度.为了进一步描述隐含偏好,图2给出了一个直观的例子.

图2 用户隐含属性偏好图例Fig.2 Illustrative example for users′ implicit preferences

在本例中,假设获得了5个用户(如“Alice”、“Bob”、“Carol”、“David”和“Elva”)对于5项产品A,B,C,D,E的评分.根据此评分信息建立一个5×5的评分矩阵R,如果用户对于某项产品没有评分,则令Ru,i=“？”,如图2(a)所示.设置属性数量K=2,可以通过矩阵分解从评分矩阵中得到两个5×2的矩阵U和VT(进行转置方便观察),分别如图2(b)和图2(c)所示.用户矩阵U的每一列对应用户,每一行代表产品的一个特定属性(如“交付时间”,“产品价格”等等).

从图2(b)中可以看出,Alice对于“交付时间”和“产品价格”都较为重视;Bob和Carol则更加重视交付时间,而David和Elva更关心产品的价格.分解出的用户潜在矩阵U中包含了用户对于不同属性的偏好程度,本文将其定义为用户的隐含属性偏好.用户隐含属性偏好可以更加全面地评价用户之间的相似度.同时,因为这种隐含属性的偏好是低维度的,在进行相似度评估时,有效地防止了由于用户整体的评分较为稀疏,评分矩阵中充斥着大量的”0”和未知元素而带来的用户相似度过高的问题.本文利用修正的余弦相似度函数对用户的相似度进行量化:

Su,v=sim(u,v)=

(8)

3.2 用户隐含信任偏好

用户的信任关系一定程度上建立在拥有相似偏好的基础上,反过来说,隐含在用户信任信息里的偏好可以推断出用户的信任强度.本文虽然同SocialMF一样引入了信任关系,但是通过分析评分记录和信任关系的联系,建立了用户的隐含信任偏好.正如前文所说,以SocialMF为代表的一系列算法仅仅因为共享同一个用户空间而使用了信任信息,割裂了评分和信任之间的关系.而信任是具有条件性的,在某些时候即使推荐直接好友或是好友的好友所喜好的产品也是不可信的.例如A信任B会组装电脑,B相信C会组装电脑,那么对于电脑配件的相关产品来说,C推荐的产品在一定程度上是可以信任的.但是,假如A信任B会修电脑,B相信C会修自行车,就不代表A信任C能修好电脑.而从信任关系上来说,这两种情况都是A信任B,B信任C.所以对于朋友的推荐来说,除了信任度之外,所推荐的产品是否符合用户的偏好也是需要考虑的.而这种偏好可以使用用户间的信任关系加以相同的评分记录来衡量.所以,本文利用信任关系和评分信息建立了加权的用户信任关系图,如图3所示.

图3 加权的用户信任关系图Fig.3 Weighted user trust graph

在图3关系图G={U,E,W}中,U为用户的集合,E为边的集合,W表示边的权重.用户u若信任用户v,则用户u与用户v间可以构成边Eu,v.这时,如果在设定的消费记录数量内,u和v先后消费了同一个产品,则其边Eu,v的权重Wu,v增加1.遍历所有的其他用户,符合这样的产品数目即是u到v的有向边权重Wu,v.根据此网络图,公式(9)定义包含了用户信任偏好的信任关系Tu,v:

(9)

其中,f(Uu,Uv)为用户Uu和Uv消费产品的并集,Wu,v为从u至v的有向边权重,d为用户Uu和Uv在关系图中的距离.例如在图3中,用户A和用户B消费产品的并集数目为100,那么A对B的信任度为TA,B=10/100*e0=0.1.而A对D的信任度TA,D=25/100*e-1≈0.09.值得注意的有两点,一是两个用户之间的影响是有向的,这与现有的无向计算方法相比更具合理性;二是信任的权重会随着用户距离的增大而持续衰减,这保持了信任的传播特性.本文将这种考虑了用户偏好的信任值代替原本通过简单归一化处理的信任值融入到矩阵分解模型中.

3.3 用户评分偏好

不同用户间评分偏好的差异会给不同系统、不同产品的评分带来很大差异,可以引入全局偏置、用户偏置、产品偏置来对这种现象进行处理.

全局偏置代表了不同系统的平均信任水平.用户倾向于在一些互惠环境(如电子商务)中乐观地评价,而在另一些环境(如与安全相关的应用程序)中则更为保守.所以将全局偏置作为一个标量μ加入模型对于适应不同的系统是有效的.

用户偏置则是基于观察到一些用户比其他用户更慷慨地给予更高的评分这种现象而得出的.这种偏置反映了用户对物品的评分倾向,不同的用户对于同一产品的满意程度可能大致相同,但是评分却可能有很大差异,这与用户本身的评分习惯有关.因此,本文将用户偏置建模为向量P,用Pu表示第u个用户的评分倾向.

而产品偏置旨在描述这样一个事实,即某些物品在被评分时可能比其他物品有更高的信任等级.有些产品可能受益于公司口碑等多种因素,在达到用户的期待程度时,用户会非常慷慨地给予高分;即使未达到用户的期待值,用户也可能给予其高于均值的评分.所以,考虑到这种信任等级带来的影响,与用户偏置一样,本文将这种类型的偏置建模为向量Q,其中Qi表示第i个物品相对于平均值的被信任能力.

最后,将以上三种偏置融入矩阵分解模型中.假设用户偏置、物品偏置以及整体评分相互独立,用户和物品偏置服从均值为0,方差分别为σP,σQ的高斯分布:

(10)

最终,用户u对产品i的预测评分可以表示为:

(11)

3.4 算法总述

在以上的分析基础上,本文提出一种融合了用户隐含偏好的社会化推荐算法:

1)本文采用概率矩阵分解模型对评分进行建模,并在模型中加入偏置以考虑用户的评分偏好对模型的影响,如公式(11)所示.

2)利用权重矩阵W来衡量用户相似度和信任度对用户潜在特征向量的影响.在实际情况下,用户评分多而好友少和用户评分少而好友多这两种情况都有出现,将用户隐含属性偏好或是隐含信任偏好作为唯一的影响因素都是不可取的.权重矩阵W中的元素Wu,v由权重系数α加以平衡,本文使用用户的共同评分数量来决定权重系数α:

(12)

其中NRu,v为用户u和用户v的共同评分数,NRu是用户u的总评分数,Su,v为用户属性偏好的相似度,Tu,v为带有用户偏好的信任值.同时本文假设用户偏好与他的相似用户或是相似好友的偏好相似,即:

(13)

3)根据公式(3),公式(7),则可以将用户和产品特征的后验概率定义,并取log对数:

(14)

最大化对数后验概率分布相当于最小化式(15)的损失函数:

(15)

4)最后采用梯度下降法求解得到公式(15)的局部最优解,各变量的梯度计算如公式(16)-公式(19)所示:

(16)

(17)

(18)

(19)

本文算法的对应图模型如图4所示.

图4 融合用户隐含偏好相似度的推荐算法图模型(SocialIP)Fig.4 Graphical model for SocialIP

4 实验结果与分析

4.1 数据集

本文在FilmTrust1和Epinions2这两个含有用户评分信息和社交关系的公开测试集上进行了测试.这两个数据集的统计特征如表1所示.

表1 数据集的统计特征Table 1 Statistics of datasets

FilmTrust数据集由Guo等人[22]从FilmTrust网站爬取所得.FilmTrust是一个基于信任关系的电影推荐网站,用户能够依据自身偏好对电影做出评分,同时构建单向信任关系.Epinions数据集是由Massa等人[23]于2003年11月-12月从评价网站Epinions上收集所得.Epinions提供了各种商品的比较信息以供用户评分,同时,用户能够添加信任用户以构建有向社交网络.

4.2 实验结果与分析

本文采用两种常用的精确度指标平均绝对误差MAE、均方根误差RMSE来衡量系统的推荐性能.并与以下几种推荐算法进行了横向对比:

PMF:Salakhutdinov等人提出的概率矩阵分解算法,该算法从概率的角度对评分矩阵的分解进行解释;

SoRec:Ma等人[24]首先提出的一种基于概率矩阵分解的社会化推荐算法,该算法加入了用户社交关系矩阵,同时将其分解为用户特征矩阵与社交特征矩阵;

RSTE:Ma等人提出的另一种基于社交网络的推荐算法,该算法在不仅利用用户的偏好信息对评分进行预测,还将用户好友的偏好加入到该算法之中;

SocialMF:Jamali和Ester提出的一种基于信任传播的经典推荐算法,利用了用户的社交信息,假定用户的偏好与其直

1https://www.librec.net/datasets.html2http://www.trustlet.org/epinions.html

接好友类似,将信任传播与矩阵分解相结合,拓展了概率矩阵分解的模型.

实验参数是影响算法性能的重要因素.为了能够全面地评价这些算法,取维度K=5,10分别测量本文及以上算法的MAE和RMSE.同时,实验中将所有算法的学习率均设为0.001,变量的初始化均采用文献中所提供的初始化方法.最终测试结果如表2所示.

表2 不同推荐方法在FilmTrust和Epinions上的性能对比Table 2 Comparison of different recommendation algorithm on FilmTrust and Epinions

表中标有“*”号的为进行对比的算法中表现最好的,而本文提出的算法在MAE上相对于其他表现最好的算法提高了1至3个百分点,而在RMSE上最高有提升6个百分点,仅在K=10的Epinions稍有不足,但是其差距是极小的.从结果中可以看出:相对于仅依靠评分信息的PMF算法,其他算法由于结合了社交信息,推荐精度均有了较为明显的提升.本文算法SocialIP在结合社交信息的基础上,还深度分析了用户隐含的偏好,相比于从评分本身分析用户信息的算法在MAE和RMSE这两个评价指标上更优.同时,本文算法在Epinions数据集和FilmTrust上均有不错的表现,这是因为本文加入了偏置信息,能够适应不同的推荐环境.随着用户评分数量和信任数量的增加,SocialIP算法虽然在MAE上与其他算法的差距变小,但是RMSE上仍有一定的优势.SocialIP算法虽然整体优于其他算法,但是在Epinions中的提高程度相比FilmTrust有所下降,这说明在候选项目数量非常大、冷启动用户较多的情况下,对于算法质量的提高有一定的影响,但是通过挖掘偏好和信任关系,也能够一定程度上提高推荐质量.因此,本算法更为适合于候选数量较小的情况.

4.3 参数的影响

本文还针对不同的维度K,不同的迭代次数对SocialIP算法进行了实验.如图5所示,从维度上看,维度过小时,由于数据量的庞大,无法较好地拟合原矩阵的评分.在维度为5时取得最优,但随着维度的增多,算法的性能有一定的退化.这是因为虽然维度的增多可以表现用户对更多属性的偏好,但是过拟合的风险也是随之增加的.

本文还将维数K设置为5,通过不断增大迭代次数来观察其带来的影响.其影响由图6所示.刚开始,随着训练次数增加,推荐误差减少,之后逐渐趋于收敛.且在不同数据集上,达到最小误差时所需的迭代次数是不同的.当迭代次数为30和60时,FilmTrust和Epinions上SocialIP的推荐准确度分别达到最高.

图5 维数K对于SocialIP的影响Fig.5 Effect of dimensions K on SocialIP

图6 迭代次数对于SocialIP的影响Fig.6 Effect of epoches on SocialIP

5 结束语

本文在现有社会化推荐系统的基础上,提出了一种融合用户隐含偏好的社会化推荐算法.该算法提出了用户隐含属性偏好,利用用户的潜在向量衡量用户间偏好的相似度;将用户的信任信息与评分记录相融合,构建了带有用户信任偏好的信任关系;并考虑到用户的评分偏好.文章将这三者融入了矩阵分解模型,取得了一定的成效.但是,用户隐含偏好的分析仍是基于评分记录的,所以对于新用户的出现仍存在一定的问题.所以,本算法仍有提升的空间,未来会针对冷启动问题以及社会关系的有效挖掘等多个角度加以改进.