融合社区结构和社交影响力的矩阵分解推荐

熊丽荣,沈树茂,范 菁

(浙江工业大学 计算机科学与技术学院,杭州 310023)

1 引 言

推荐系统作为一种信息过滤工具,可以有效地缓解信息过载问题.帮助人们从大量繁杂的信息中找到自己感兴趣的内容.协同过滤技术是现在最流行的推荐方法,其中的矩阵分解方法[1]受到了很多人的关注.

在社交网络中,用户的行为不仅会被自己的兴趣爱好影响,也会被其他用户影响.研究表明,拥有一定社交关系的用户之间会在一些方面存在相似性[2].在矩阵分解推荐算法中引入用户的社交关系可以增强推荐准确度[3,4].可是社交网络中往往存在长尾效应[5],即只有少数的用户拥有大量的社交关系,而大多数的用户拥有很少的社交关系.在社交网络中,拥有某些相似的特征和爱好的用户会相互聚集成为社区,同一个社区内的用户会对彼此的选择产生影响.同时,在社区内与用户拥有间接关系的用户很多,增加间接社交关系的使用而不只是仅仅使用直接社交关系可以有效地缓解用户好友稀疏问题.

本文提出一种融合社区结构和社交影响力的矩阵分解推荐算法SoInf.同时使用用户评分信息和社会网络结构信息来计算用户之间的影响力,且将用户之间的相互影响和用户个人影响力相结合,更精确刻画用户间的相互影响.将社区结构和用户间社交影响力结合到矩阵分解中,来增加推荐的准确度.

这篇论文的主要贡献如下:

1)考虑社区内的其他用户对用户的影响,而不仅仅是用户的直接邻居的影响.基于社交网络结构进行社区发现,将社区结构用于用户之间的影响力计算和模型构建.

2)同时使用用户评分信息和社会网络结构信息来计算用户之间的影响力.结合社区信息,计算用户个人影响力.融合用户之间的影响力和用户个人影响力,得到非对称的用户之间的影响力.

3)用户社区结构信息和用户社交影响力结合到矩阵分解中,提出一种融合社区结构和社交影响力的矩阵分解推荐算法SoInf,缓解用户评分的稀疏问题,同时提升推荐准确度.

2 相关工作

在社交网络中,拥有较强的社交关系的用户之间存在一定的相似性,彼此之间会相互影响.因此在矩阵分解推荐算法中引入社交关系可以增强推荐效果[6,7].引入社交关系的矩阵分解推荐算法可以分成两类:

1)以用户特征矩阵为纽带,同时分解用户评分矩阵和用户社交关系矩阵[8,10-12].

2)优化用户特征向量[13-23],通过与用户之间拥有社交关系的用户来优化用户的特征矩阵.

同时分解用户评分矩阵和用户社交关系矩阵的推荐算法认为通过同步分解评分矩阵和社交矩阵可以获取更准确的用户隐式特征向量.在概率矩阵分解推荐模型[9]基础上,Ma等人[8]提出了同时分解用户评分矩阵和用户社交关系矩阵的SoRec模型.而对信任与被信任行为的不同进行考虑,Yang等人[10]提出了TrustMF模型,分别刻画了用户受其信任用户的影响与对信任他的用户的影响.同时考虑局部社交信息和全局社交信息,Tang等人[11]提出了LOCABAL模型,引入不同视角的社交关系以提升推荐效果.

优化用户特征向量的矩阵分解方法,用户特征向量受到社交网络中关联用户的影响.引入用户社交关系,可以优化当前用户的隐式特征向量.引入用户好友的偏好信息,Ma等人[13]提出了一种融合社交信息的推荐模型RSTE,在一定程度上利用了社交信息.考虑社交网络中的用户的偏好信息会随着用户之间的相互交流而传播,Jamali等人[14]提出了一种社交推荐模型SocialMF,利用信任传播机制增强推荐效果.SoReg是Ma 等人[15]提出的一种社交正则化推荐模型,使用社交信息对推荐模型进行增强,考虑用户的行为受到用户好友的影响,且用户之间社交关系越强两个用户的兴趣爱好越相似.Guo等人[16]提出TrustSVD模型,将用户显式信任关系与评分信息都看作隐式反馈信息,使用隐式社交反馈信息对用户特征矩阵进约束.把用户之间的相似和各个用户的重要性相结合,Davoudi等人[17]提出了一个社会信任模型,其中包含了偏好相似性、用户的中心地位和社会关系,并使用矩阵分解来对项目进行评分预测.王等人[18]利用用户评分过程中潜在存在的信任关系,提出一种基于信任机制的推荐算法TM-PMF.

虽然在上述优化用户特征的推荐算法中,也有一些算法[14,17]使用了间接社交关系来计算用户间相似度,但是在构建矩阵分解模型时只利用了用户的直接相连用户,即只利用了直接社交关系.直接社交关系存在用户好友数据稀疏问题.社交网络中存在社区结构,将社区结合到推荐模型中可以有效地缓解用户好友稀疏问题.Yang等人[19]提出了CircleCon模型,考虑用户在不同领域会拥有不同的信任用户集合,根据评分信息和社交网络数据推断出特定分类的社交信任圈,提出基于圈子的推荐模型.Ma等人[20]在SR+模型中认为用户的隐式特征向量同时依赖于用户的朋友和与用户非常相似的其他用户.然而SR+需要通过预先设定一个相似阈值来过滤与用户相似的其他用户.Li等人[21]在社交化推荐算法MFC中引入了重叠社区发现算法,通过计算用户与社区的相关度和用户与其他用户的相似度,来获取各个用户间兴趣的差异,并对目标函数中的正则项进行约束,使用间接社交关系来增强推荐效果.考虑社交关系中具有同构关系,将兴趣爱好相似的用户分配到同一个社区,在此基础上Tang 等人[22]构建了推荐模型SoDimRec.Ahmadian等人[23]提出了一种基于自适应邻居选择机制的社会推荐算法SRANS.为用户选择合适的邻居,可以提高推荐过程中评分预测的准确性.

本文也是增加了间接社交关系的使用,考虑社区内用户间的相互影响,来增加推荐准确度.与上述工作不同的是,我们将社区结构和社交影响力融合到矩阵分解推荐模型中.同时使用用户评分信息和社交网络结构信息来计算用户之间的影响力,且将用户之间的影响力和用户个人影响力相结合,更精确刻画用户间的相互影响,从而提升推荐效果.

3 推荐算法SoInf

3.1 相关定义

U={u1,u2,…,um}表示推荐系统中用户的集合,V={v1,v2,…,vn}表示推荐系统中项目的集合.将用户对项目的评分矩阵表示为R=(Rij)m×n,其中Rij∈{1,2,3,4,5}表示用户ui对项目vj的评分.T=(Tij)m×m表示用户的社交关系矩阵,Tij=1表示用户ui和用户vj之间存在好友关系,否则Tij=0,与用户ui的直接相连的好友集合为Ni.假设有x个社区,g={g1,…,gx}是社区集合.对于用户ui,设ui∈gi，C(i)∈(gi∪Ni)表示用户好友和其所属社区的其他用户的集合.矩阵分解推荐算法将用户评分矩阵R近似地分解成低阶的用户特征矩阵U∈Rl×m和低阶的项目特征矩阵V∈Rl×n,其中l是隐特征向量的维数.

3.2 社区发现

用户的偏好受到社区内其他用户的影响.采用社区发现算法将用户集合根据其社交网络结构进行划分,属于同一社区内的用户存在相同的特性或爱好.简单随机块模型[24]假设生成链接的概率只与两个端点的社区相关,社区选择各节点的概率相同.而实际的链接生成过程与很多因素有关,如有些节点是权威的节点,其被社区选择的概率相对要大.

Karrer和Newman[25]提出度纠正随机块模型DCBM.DCBM使用了Kernighan-Lin算法[26],这是一种基于贪婪原理的启发式算法.首先将网络随机地划分为x个社区的初始集合.然后重复地将一个顶点从一个集合移动到另一个集合,在每一次移动中选择目标函数增加最大的移动结果,或者目标函数减少最小的移动,且每个顶点只能移动一次.当所有顶点都被移动后,检查移动过程中从开始到结束所经过的状态,选择目标分数最高的那个移动状态,并使用这个状态作为相同过程的新迭代的起点.当目标函数没有增加时,一个完整的迭代过程结束,并得到最终的网络的社区划分结果.

相比于简单随机块模型,DCBM在发现社区的过程中考虑节点度的影响,可以更好地识别网络中的非重叠广义社区.本文使用DCBM对用户网络进行社区发现,将每个用户被划分到各个社区中.

3.3 影响力计算

本文的影响力计算从两个方面进行考虑.一方面,通过用户评分信息和社交网络结构信息来计算用户之间的影响力.另一方面,通过社交网络拓扑结构分析用户在社交网络中的个人影响力.用户个人影响力,即用户影响其他用户的能力[27],类似于可信度.研究表明在社交网络中,越重要的人越能快速扩散和放大舆论[28].本文将用户之间的影响力和用户的个人影响力相结合,计算非对称的用户之间的影响力.

3.3.1 使用用户评分信息计算用户之间的影响力

用户之间的影响力是指任意两个用户之间的相互影响的大小,在计算的时候我们同时使用用户历史评分信息和社交网络结构信息.通过用户历史评分信息,我们可以分析得到用户之间的相似性,本文采用皮尔逊相似性来计算相似度.与其他同样使用用户评分计算相似度的方法相比较,皮尔逊相关系数中对用户评分做了处理.在实际情况中,每个用户的打分习惯和对评分档位的理解存在差异,导致有些用户打分整体偏高,而有些整体偏低的情况.而皮尔逊相关系数可以很好的去除这种差异,更准确的衡量用户之间的相似性.其公式如下:

(1)

3.3.2 使用社交网络结构信息计算用户间影响力

但是通过用户评分计算出的相似度只利用了评分信息,没有充分利用用户之间的信息,所以本文同时使用社交网络结构信息来计算用户之间的影响力.

使用社交网络结构数据,通过SimRank算法[29]计算用户间的影响力.定义两个用户i和k之间的SimRank相似度infs(i,k).SimRank基于相似的用户则邻居也相似的思想来计算用户间的相似度,计算方法如下:

1)infs(i,k)=0,当I(i)=φ或I(k)=φ;

2)在其他情况下,

(2)

其中,I(i)表示所有指向用户a的用户集合,d∈(0,1)是一个阻尼系数.

在社交网络中,用户寻求建议时更容易受到个人影响力大的其他用户的影响.而且用户在选择其他用户进行交流时,会更倾向于选择与其同一个社区的用户,而不是社区外的用户.

定义社区中各个用户的局部影响力为si，S为由社区中所有用户的局部影响力组成的个性化向量.在每个社区中,使用PageRank[30]求出社区中各个用户的局部影响力si.

定义用户个人影响力fi，F为网络中用户影响力得分向量,fi∈F.

本文通过社区信息计算出的个性化向量S结合到Personalized PageRank[31],计算得到的用户个人影响力,见公式(3):

F=aPTF+(1-a)S

(3)

P为网络图的转移矩阵,a为跳转因子.在整个社交网络中使用Personalized PageRank算法,可以计算出每个用户的全局个人影响力fi.然后对用户的全局个人影响力进行数据标准化将影响力映射到[0,1]区间上.

计算出来的用户之间的影响力基本都呈对称性,直接用来描述用户之间的影响会有一定偏差.在实际情况中,用户i对用户k的影响力可能与用户k对用户i的影响力不同.个人影响力大的用户更容易影响其他用户.将用户的个人影响力与用户之间的影响力相结合,得到使用社交网络结构信息计算的非对称的用户i与用户k之间的影响力:

(4)

3.3.3 计算综合的用户之间的影响力

把使用用户历史评分信息计算的用户之间的影响力sim(i,k)和使用社交网络结构信息计算的用户之间的影响力inf(i,k)相结合,得到综合的用户i对k的影响力:

(5)

3.4 融合社区结构和用户影响力的推荐算法

本文在Ma等人[15]提出的SoReg的基础上提出一种融合社区结构和社交影响力的矩阵分解推荐算法SoInf,利用用户之间的影响力信息和用户评分信息进行推荐,其模型如图1所示.

图1 SoInf模型图Fig.1 Graphical model of SoInf

我们使用用户在社区中的间接社交关系来增强我们的模型,根据社区内其他用户和用户好友的偏好来获得用户的偏好信息.与SoReg中用户ui只受到用户好友的影响不同,在SoInf中,用户ui的隐式特征向量受到用户的好友Ni和其所属社区gi中其他用户的影响.在SoReg中,用户与好友之间的相互影响关系受到通过用户历史评分信息计算的相似度的影响.而在SoInf中,同时使用用户评分信息和社交网络结构信息来计算用户之间的影响力f(i,k),并融合用户之间的影响力和结合社区信息计算的用户个人影响力.用户ui的隐式特征向量Ui和用户uk的隐式特征Uk受到用户之间的影响力f(i,k)的约束:

(6)

假设Ui，Vj先验概率服从高斯分布且相互独立,则有:

(7)

(8)

给定用户的同社区内的其他用户和用户的直接邻居的隐式特征,在用户隐式特征空间执行优化任务,得到用户隐式特征的条件分布:

(9)

预测评分值的条件分布如下:

(10)

利用贝叶斯规则,特征矩阵U和V的后验分布可通过如下方法计算:

(11)

对后验分布取对数,可得:

(12)

其中Con是常量.最大化上述对数后验概率,等价于最小化如下目标函数:

(13)

(14)

(15)

本文给出我们的算法,如下所示:

Algorithm1:learningSoInfInput:RatingsintrainingsetR,usersocialmatrixT,Learningrateγ,α,λU,λVOutput:userlatentprofilematrixUanditemlatentprofilematrixV1 InitializeUandV;2 repeat3 forrij∈Rdo4 updateUi←Ui—α∂E∂UibasedonEq.(14);5 updateUj←Uj—α∂E∂VjbasedonEq.(15);6 untilconvergence;7 returnUandV;

4 复杂性分析

5 实 验

5.1 数据集

豆瓣1https://www.douban.com是一个中国社交网络平台,主要是对图书、电影和音乐进行评论和推荐.每个人可以根据自己的喜好对图书、电影和音乐进行评分,评分从1到5.我们使用Zhong等人[32]分享的数据集,仅仅使用其中电影相关的数据,并且移除评分为零的数据.实验中使用的豆瓣数据集共包含6164个至少评分过一次的用户,28781部电影,715204条评分和8728条好友关系.

CiaoDVD是Guo等人[33]爬取的一个英国DVD社交网站Ciao2http://dvd.ciao.co.uk的公开数据集.评分从1到5,共包含17615个用户,16121部电影,72665条评分和22484条信任关系.

5.2 对比算法

为了比较本文提出的算法SoInf与其他算法在推荐结果准确度上的差别,我们选择6种算法作为对比算法进行实验.

PMF[9]:仅仅使用了评分信息,没有加入用户的社交关系信息.

SoRec[8]:属于同步分解评分矩阵和社交关系矩阵的方法,同时将其分解为用户特征矩阵与社交特征矩阵.

TrustMF[10]:属于同步分解评分矩阵和社交关系矩阵的方法,将每一个用户映射为信任者特征向量和被信任者特征向量.

SocialMF[14]:属于利用直接社交关系对用户特征矩阵进行优化的方法,使用用户好友信息和信任传播机制来增强推荐效果.

SoReg[15]:属于利用直接社交关系对用户特征矩阵进行优化的方法,通过加入社交正则项使得用户的偏好与其好友的偏好相似.

MFC[21]:属于利用间接社交关系对用户特征矩阵优化的方法.在矩阵分解模型中引入了重叠社区发现算法,区分用户所在社区不同的差异.

为了说明我们的SoInf模型的效果,我们分别进行以下三组实验比较:

1)使用社区中间接社交关系,对推荐的增强效果.把我们的仅仅添加社区信息的模型命名为SoInfc.将它与上述其他算法进行比较.

2)同时使用用户评分信息和社交网络结构信息来计算用户之间的影响力,对推荐的增强效果.把在SoInfc模型基础上,同时使用用户评分信息和社交网络结构信息来计算用户之间的影响力的模型命名为SoInfs.将它和SoInfc以及其他算法进行比较.

3)结合用户个人影响力,对推荐的增强效果.在SoInfs模型基础上,结合用户个人影响力来计算用户之间的影响力的模型就是本文提出的SoInf.将它与SoInfs以及其他算法相比较.

5.3 评价指标

本文的实验采用五重交叉验证方法,即随机把数据集分成5份,每次选择其中的4份作为训练集,选择剩下的1份作为测试集,对5次的评估结果取平均值得到最终的评估结果.为了分析本文提出的算法对推荐结果的精确度,采用平均绝对误差(Mean Absolute Error,MAE)和均方根绝对误差(Root Mean Square Error,RMSE)作为实验结果的评估方法.MAE值和RMSE值越小表示预测评分和真实评分的差距越小,推荐结果越准确.

(16)

(17)

5.4 参数选择和分析

实验参数的设置影响着算法的最终准确度.根据文献[8,9,10,14,15,21]中的参数设定规则,将所有算法的隐特征向量个数l设为10,迭代计算的步长(学习率)γ设为0.0001,迭代的终止条件设为前后两次迭代误差小于0.00001,将λu和λv设置为0.001.在我们的算法中,正则项系数α表示用户社交网络社区信息以及用户之间的影响力信息在矩阵分解模型中参与的比重,将α的值分别取值为{0.01,0.1,1,10,50,100}进行实验.记录我们的算法SoInf的推荐结果的MAE值和RMSE值随不同α值的变化情况,如图2和图3所示.

图2 SoInf算法的 MAE值随α值的变化Fig.2 MAE of the SoInf algorithm varies with parameter α

由图2和图3可知,对于Douban数据集,当α为10时MAE和RMSE最小, 也就是推荐准确度最高, 所以在我们的算法中设α为10.而对于ciaoDVD数据集,当α为50时MAE和RMSE最小.依据文献[8,9,10,14,15,21]对于其他算法的参数进行设定,见表1.

图3 SoInf算法的RMSE值随α值的变化Fig.3 RMSE of the SoInf algorithm varies with parameter α

表1 不同社交推荐方法参数设定
Table 1 Parameters for different social recommendation methods

方法参数设定PMFλu=0.001,λv=0.001,SoRecλu=0.001,λv=0.001,α=1TrustMFλu=0.001,λv=0.001,α=1SoRegλu=0.001,λv=0.001,α=0.001SocialMFλu=0.001,λv=0.001,α=1MFCλu=0.001,λv=0.001,α=0.001SoInfλu=0.001,λv=0.001,α=10

5.5 实验结果比较和分析

在为每个算法选择最优的参数以后,通过实验我们可以比较各个矩阵分解的预测效果.表2里显示的是在Douban和CiaoDVD数据集中各个算法的MAE和RMSE.在图4和图5中分别显示了各个算法的MAE和RMSE的对比.

表2 SoInf算法与其他推荐算法的实验结果对比
Table 2 Comparison ofMAEandRSMEfor SoInf algorithm and other recommendation algorithms

算法DoubanCiaoDVDMAERMSEMAERMSEPMF0.63970.83170.79541.0930SoRec0.60350.76700.76341.0311TrustMF0.60120.76170.76311.0303SocialMF0.61490.77570.76381.0337SoReg0.60360.76180.76321.0321MFC0.59960.76080.75941.0299SoInfc0.59930.75990.75791.0295SoInfs0.59840.75960.75591.0286SoInf0.59810.75950.75531.0268

通过观察和分析,我们可以得到以下几个结论:

1)使用社区中间接社交关系,对推荐效果的分析.相对于利用直接社交信息进行用户特征矩阵优化的模型(SoReg,SocialMF)和同步分解评分矩阵和社交关系矩阵的模型(SoRec,TrsutMF),基于社区的社交推荐模型(MFC,SoInfc,SoInfs,SoInf)准确度更高.这表明社区信息的引入可以缓解用户好友稀疏的问题,提升推荐效果.

图4 各个算法的MAE指标比较Fig.4 Comparison of MAE for different algorithms

2)同时使用用户评分信息和社交网络结构信息来计算用户之间的影响力,对推荐效果的分析.和仅仅使用用户评分信息来计算用户之间的影响力的SoInfc算法相比较,同时使用评分信息和社交网络结构信息来计算用户之间的影响力的SoInfs准确度更高,说明同时使用评分信息和社交网络结构信息来计算用户之间的影响力可以更加准确地刻画用户间的相互影响,更加有效地使用用户评分信息与社交信息.

3)结合用户个人影响力来计算有差异的用户之间的影响力效果分析.结合用户个人影响力来计算非对称的用户之间的影响力的模型SoInf相比没有结合用户的个人影响力的SoInfs推荐准确度更高.说明使用结合用户个人影响力得到的非对称的用户之间的影响力,可以获得更好的推荐结果.

与PMF相比较,我们提出的推荐模型SoInf在Douban数据集上对于MAE和RMSE分别提升了6.50%和8.68%,在ciaoDVD上数据集分别提升了5.04%和6.06%.对比其他算法,我们的模型SoInf在准确度方面有一定的提升.与MFC通过重叠社区来增强基于社区的推荐的效果不同,我们考虑通过更精确地刻画用户之间的关系,得到用户之间的影响力来对基于社区的推荐进行增强.SoInf与MFC相比准确度更高,说明将社区结构和社交影响力相融合到矩阵分解模型中,同时使用用户的评分信息和社交网络结构信息,可以更加充分合理的利用推荐数据,达到更好的推荐效果.

图5 各个算法的RMSE指标比较Fig.5 Comparison of RMSE for different algorithms

6 总 结

本文提出了一种融合社区结构和社交影响力的矩阵分解推荐算法SoInf.为了减少好友的稀疏,我们采用间接社交关系来代替直接社交关系.进行社区发现,然后结合社区信息进行用户个人影响力计算.考虑社区内其他用户对用户的影响,来提高推荐的准确度.使用社区内用户之间的影响力和用户的个人影响力,得到非对称的用户之间的影响力.通过在Douban和ciaoDVD数据集上的实验结果表明,算法在推荐准确度上比一些已有的基于矩阵分解的算法更好.未来,我们将研究使用社交影响力和评分信息来构建用户画像,使用用户画像来提升推荐效果.