结合用户社区和评分矩阵联合社区的推荐算法研究

文 凯,朱传亮,何少元

1(重庆邮电大学 通信与信息工程学院,重庆 400065) 2(重庆邮电大学 通信新技术应用研究中心,重庆 400065) 3(重庆信科设计有限公司,重庆 401121)E-mail:cquptzcl@yeah.net

1 引 言

随着Web2.0的发展,用户间的社交网络扮演着越来越重要的地位,用户之间可以建立不同程度的信任关系,用户的购买行为也不仅仅是依靠用户自身的兴趣爱好了,更多地会考虑到用户所信任的其他用户的意见,社交网络分析表明,用户和所信任的朋友在很大程度上有着相似的偏好,因此一些基于社交网络的算法被提出[1,2],用来改善推荐精度,其中传统的基于社交网络的推荐算法采取一种信任评估的模型,考虑用户间的直接信任关系.文献[3]介绍了一种SocialMF算法,该算法是在社交推荐中比较常用的算法,将信任传播机制融合进概率矩阵分解框架中;文献[4]提出将用户信任和张量分解技术结合起来.文献[5]提出了一种基于用户信任的矩阵分解技术Trust SVD,在SVD++算法的基础上进一步结合显示及隐式用户信任对推荐的影响.

随着社交网络的不断发展,社交网络越来越庞大,社交数据越来越稀疏,导致了推荐结果准确度的下降.同时,随着数据量的越来越大,传统的推荐算法在可扩展性上已经不足以支撑现有的数据量,因此一些基于社区的算法被提出用来改善推荐的可扩展性[6,7].有的挖掘用户社区,有的挖掘项目社区,比如文献[8]首先利用基于密度的聚类算法将物品进行聚类,然后在物品聚类簇中利用加权Slope one算法进行评分预测;文献[9]提出一种基于用户属性的聚类算法,定义了用户之间的偏好距离,根据偏好距离进行聚类;文献[10]提出一种结合SVD的推荐方法,推荐时在目标用户的社区内利用随机游走算法为用户做出推荐;文献[11]提出一种融合拓扑势的层次化聚类算法,综合考虑网络拓扑结构和社交网络属性信息,利用协同过滤预测评分.

同时也有一些学者提出同时将用户和物品进行聚类,这样的聚类方式称为联合聚类(co-clustering),文献[12]通过联合聚类将用户和项目同时划分到社区中,用户或项目只属于一个社区;文献[13]提出了一种混合推荐算法,将用户和物品同时进行聚类并学习用户和物品的属性,去解决冷启动问题;文献[14]提出一种多类联合聚类,通过迭代方式获取用户和产品的联合聚类结果,然后通过统一的框架利用传统的协同过滤算法进行推荐.

然而以上提出的这些聚类方法虽然提高了推荐的效率,但都只考虑了单一社区结构,所以推荐精度不高.针对上述问题,本文综合考虑用户社区结构和联合社区结构,首先基于社交信息和评分信息提出了一种新的用户间相似度度量方法,利用该度量方法对用户进行聚类从而发现用户社区;之后从用户和物品两个维度进行联合聚类,得到一个用户-物品的联合社区.最后结合这两个社区结构,将用户社区结构融入到面向联合社区的矩阵分解模型中从而进行推荐.

2 结合用户社区结构和评分联合社区的推荐模型

2.1 符号表示与框架描述

设U={u1,u2,…um}和V={v1,v2,…vn}分别表示用户和物品的集合,其中m和n分别表示用户和物品的数量,设R∈Rm×n表示用户-项目评分矩阵,设T∈Rm×m表示用户之间的社交关系矩阵,在矩阵T中,当T(a,b)=1时表示用户ua信任用户ub.

图1是本文联合推荐模型的一个整体的框架图,从图中可以看到,整个框架的输入为用户-项目评分数据和用户社交网络数据,整个过程可以分为以下4步:

图1 矩阵分解推荐模型图Fig.1 Matrix decomposition recommendation model

Step 1.分别利用用户的评分数据和社交网络数据挖掘出用户间的评分相似性和用户间的信任关系;

Step 2.融合用户间的评分相似性和信任关系,得到一种新的用户间相似度,基于这种新的用户间关系度量方法进行聚类得到用户社区结构.

Step 3.利用用户的评分模式从用户和物品两个方面对评分矩阵进行联合聚类,将原来稀疏的评分矩阵划分为一个个子矩阵.

Step 4.将用户社区结构融入到面向联合社区的矩阵分解模型中进行推荐.

2.2 用户社区挖掘

由于传统的用户聚类算法只是利用用户间的评分相似性进行聚类,而评分矩阵是十分稀疏的,得到的聚类效果往往不好.因此本文通过融合用户社交信息和评分信息定义一种新的相似性度量方法,然后基于这种新的混合度量方法对用户进行聚类.

2.2.1 获取用户间的信任关系

在社交网络中,人与人之间存在着一种相互信任的关系,通常系统无法直接给出十分精确的数值用来反映两个用户之间的信任程度,系统给出的往往是二元的,同时由于信任网络是十分稀疏的,所以需要对信任网络进行扩展.本文定义用户间的信任关系值度量公式如下:

(1)

式中,t(u,v)∈(0,1],d(u,v)是用户u和用户v之间的最短距离,可以宽度优先搜索算法进行搜索,两个用户之间的距离越短则说明两个用户之间的信任值越大.根据小世界理论,每个用户和陌生人之间间隔不能超过六个人,因此我们限制两个用户之间的最远距离为6,即d(u,v)≤6.

2.2.2 获取用户的评分相似性

传统的相似度计算方法是根据不同用户对项目评分的差别来进行计算的,但是在实际的评分中有些用户对项目的评分普遍都很高,而有的评分普遍都很低,这种单一的评分偏好会影响传统相似度计算方法的准确性,为了减轻这种影响,文献[15]提出一种基于用户评分偏好的相似度计算方法,其计算公式如下:

(2)

2.2.3 融合信任关系和相似性

把用户间的信任关系和评分相似性融合在一起,扬长避短,得到一种新的计算用户间相似度的方法.下面用线性关系来融合这两种关系,如式(3)所示:

(3)

式中,Trust(u,v)表示通过公式(1)计算的用户之间的信任关系,SimRat(u,v)表示通过公式(2)计算的用户间的相似关系.

2.2.4 利用K-means进行用户社区挖掘

社区挖掘就是将相似的用户或项目划分到相同的社区结构中.在进行用户社区挖掘时选择经典的K-means聚类算法,但考虑到经典的K-means聚类算法对初始点的选择比较敏感,如果初始的聚类中心选择不恰当对最后的聚类结果将产生很大影响.因此考虑对初始点的选择进行改进,社会心理学的研究表明,人们在选择推荐的产品的时候往往更加重视专家的意见,由于专家用户对推荐的影响,因此本文考虑将专家用户作为K-means算法的初始聚类中心,结合用户的社交关系和评分信息从可信度,权威性以及评分多样性三个指标出发,对用户成为专家的可能性进行评估.

定义1.可信度.可信度反映的是用户被其他用户信任的程度,可以通过在信任网络中用户的入度来衡量.

(4)

式(4)中,du表示在信任网络中信任用户u的用户数,dmax表示信任网络中入度的最大值.

定义2.权威性.权威性表示用户在整个系统中的活跃度,可以利用用户的评分数量Nu来衡量,用户的评分数量越多,说明用户越活跃.

(5)

定义3.评分多样性.评分多样性表示用户对物品进行评分时所表现出来的评分差异性,如果一个用户对所有物品的评分都相同,这样就不能反映出用户对物品的喜好程度,因此专家对不同物品的评分一定要呈现出一定的差异,因此使用评分的方差vu来衡量用户评分多样性.

(6)

由于k-means算法需要初始的聚类中心,因此根据用户的专家值进行排序,取专家值最大的k个用户作为初始的聚类中心,记作U={expert(u1),expert(u1),…，expert(uk)},那么整个用户聚类的算法步骤描述如下:

输入:用户项目-评分矩阵R,信任矩阵T,聚类簇个数K

输出:K个用户聚类簇

步骤1.将集合U中的K个用户作为初始聚类中心,聚类中心集合记为Center={ce1,ce2,…,cek} 并初始化k个聚类簇,记作C={C1,C2,…,Ck};

步骤2.对用户集合中的每个用户,利用公式(3)计算其与所有聚类中心的混合相似度,找到其中相似度最大的用户Max(Sim(u,cei)),将用户u加入聚类中心cei所在的聚类簇Ci;

步骤3.更新所有的聚类中心,计算每个聚类簇中用户混合相似度均值最大的用户作为新的聚类中心;

步骤5.直到L的值收敛即聚类中心不发生变化时整个迭代就停止,否则返回步骤2继续执行.

经过以上的迭代过程,可以得到K个用户聚类簇,其

中,K值是未知的,过大或过小都将对后面的推荐产生很大的影响,因此本文在后面的实验中来获取其最优值.

2.3 评分矩阵联合社区挖掘

由于在大规模的稀疏评分矩阵中,联合聚类(co-clustering)不仅能有效地降低矩阵的稀疏度,同时可以降低计算的复杂度[14].因此在本小节中,我们利用用户的历史评分信息同时对用户和项目进行聚类,采用这样的方式进行聚类有利于发现矩阵中隐藏的聚类结构.经过联合聚类后,一个较大规模的评分矩阵可以转化为W个规模较小且内部相对稠密的子矩阵,每个子矩阵的内部评分都有较高的相似度,从而可以进行有效的降维,在后面的计算中可以有更小的计算复杂度.

基于评分模式的聚类方法[16]是一种软联合聚类算法,用户和项目可以归属多个不同的类.它首先扫描已有的用户-项目评分矩阵,将用户、项目和评分按照概率分别划分类别,整合这三个概率得到用户-项目评分属于每个类别的概率.迭代的时候要重新计算用户、项目、评分属于某个子矩阵的概率直到收敛.每个聚类簇内部的用户、项目以及评分会重新组成矩阵.计算评分属于某个类别的计算公式如下所示:

p(k|ui,vj,r=

(7)

式(7)中,对每个概率加上α,β,γ是为了防止分母为0,在实验中均设置为0.00000001,p(k|ui),p(k|vj),p(r|k)分别表示用户和项目属于该类别的概率以及评分出现在该类别中的概率,其计算公式分别如下:

(8)

(9)

(10)

式中,V(ui)表示用户ui评价过的物品集合,U(vj)表示对商品vj有过评价的用户集合,r′表示评分矩阵中的不同评分(从1～5,间隔为0.5的数).运行时首先随机初始化每个评分属于某个类别的概率,再不断进行迭代直至收敛,得到最后的结果.整个算法的详细描述如下:

输入:用户-项目评分矩阵R,类别个数W,概率阈值δ

输出:每个类别所含的用户、项目的集合

步骤1.开始时随机初始化每个评分属于某个类别的概率p(k|ui,vj,r),满足∑k′∈Kp(k′|ui,vj,r)=1.

步骤2.对评分矩阵中的每一个用户和项目,分别根据公式(8)和公式(9)分别计算该用户属于各个类别的概率以及该项目属于某个类别的概率.

步骤3.根据公式(10)计算某个类别中存在某个评分的概率.

步骤4.根据公式(7)重新计算p(k|ui,vj,r),并选取所属概率大于δ的类别作为该评分的类别.

步骤5.跳转到步骤2,直到概率值收敛,否则结束程序.

在实验中为了简化起见,本文规定用户所属类别的概率阈值δ=0.5,整个过程迭代完成后,原本稀疏的矩阵转变成W个内部相对稠密的子矩阵,其中W值的大小将对整体的推荐产生影响,其最优值可以通过实验获取.联合聚类示意图如图2所示.

2.4 结合社区结构和联合聚类的矩阵分解推荐

2.4.1 基本的矩阵分解模型

矩阵分解是在推荐系统中运用最为广泛的方法之一,本文以矩阵分解作为基本的模型.在2.3节中得到了聚类后的子矩阵,子矩阵相比原始矩阵而言,矩阵规模小,稀疏性低,因此本文在含有目标用户的子矩阵中进行推荐.设Rw∈RMw×Nw表示评分子矩阵,w∈{1,2,…w},Mw和Nw分别表示评分子矩阵内的用户个数和项目个数,设Uw和Vw分别表示评分子矩阵的用户隐特征向量和项目隐特征向量,在子矩阵内采用矩阵分解技术,和传统矩阵分解技术类似,其误差计算公式如下:

(11)

图2 评分矩阵联合聚类Fig.2 Score matrix co-clustering

2.4.2 融合社区结构和评分联合社区的矩阵分解

在现实生活中,我们做的很多决定往往会受到好友的影响,在2.2节中获取了用户社区结构,将相互影响的用户聚集在一起,用户与同一社区中用户的偏好相似性要高于不在同一个社区中的用户,根据目标用户所在的子矩阵和用户社区,就可以构造如下的正则项公式,其表达式如下:

(12)

因此,融合矩阵分解的框架可以得到一种结合用户社区和评分矩阵联合社区的矩阵分解模型,其目标函数如下所示:

(13)

(14)

(15)

2.4.3 评分预测

当模型训练完成后,每个子矩阵的隐特征向量Uw和Vw可以求得,对于一个给定的用户-项目对(ui,vj),用户对未评分物品的评分预测如公式(16)所示:

(16)

3 实验与分析

在本小节中,我们将在Epinions数据集上进行算法验证和对比,为了简单起见,在后文中用UCCC(user community and co-clustering)来表示本文所提的算法.

3.1 实验数据和评价标准

Epinions是一个消费者评价网站,用户可以通过评分对项目进行评价,数据集中包含用户的评分信息以及用户间的社交信息,其中含有40163个用户对139738个商品的664823条评分记录,除了评分信息以外,还含有487182条用户间的信任关系.

从以上数据集中随机选择80%的用户-商品评分数据作为训练集,剩下的20%作为测试集,本文采用五折交叉验证的方法,即重复五次这一过程,取五次实验结果的平均值作为本实验的结果,本文采用平均绝对误差(mean absolute error,MAE)和均方根误差(root mean square error,RMSE)作为本次实验的评估标准.

(17)

(18)

3.2 对比算法介绍

为了检验本文的算法与其他推荐算法的区别,我们选择了5种其他算法作为对比.

1)BaseMF:文献[17]提出的结合矩阵分解的基本推荐模型,没有融合其他信息.

2)SoReg:文献[2]在矩阵分解的模型中加入了社交关作为正则化项,使得用户的偏好与其好友偏好的均值相似,但是没有考虑任何社区信息.

3)MFCC:文献[16]提出的基于联合聚类的矩阵分解算法,在PMF算法的基础上,将评分矩阵划分为子矩阵并行的进行评分预测.

4)UCCC-U:利用本文中的社区挖掘算法,只利用了用户的社区结构,然后执行矩阵分解算法,没有考虑联合社区结构.

5)UCCC-UI:利用本文中的联合社区挖掘算法,利用子矩阵进行矩阵分解的推荐.

3.3 实验结果及分析

3.3.1 实验参数分析

1)用户社区数目K的确定

首先,针对用户社区的挖掘过程中,要确定用户的聚类数目K,本实验在取不同K值的情况下,观察MAE值的变化情况,得到最合适的用户社区数目.同时,为了验证本文提出的利用专家用户作为初始聚类中心的K-means算法的有效性,同时选择了原始的K-means算法作为对比.对于原始K-means算法而言,由于其初始中心不一样,因此对原始的K-means算法取5次结果的平均值.本次实验的其他参数设置如下:联合社区个数W=20,社区正则化参数α=0.01,矩阵分解正则化参数λ=0.01,矩阵分解的特征向量维度设置为10,实验中K的取值从2开始,间隔为2,实验结果如图3所示.

从图3可以看出,开始时随着聚类簇数目的增加,MAE值呈减小的趋势,在聚类数等于12的时候平均绝对误差达到最小,之后又快速增加.分析其原因可能是:如果用户社区的数量过少,导致用户过度集中,可能有不同偏好的用户也会在一个社区中,导致社区内的平均偏好不准确,影响推荐效果;如果用户社区过多,则会使用户十分分散,不能充分利用相似用户之间的关系,也会导致社区内平均偏好不准确.所以在下面的实验中选择用户社区结构数目为12.同时可以看到采用改进初始聚类中心的K-means算法相比原始的K-means算法效果有明显的改善,也验证了本文所用聚类算法的有效性.

图3 不同K值下的MAE变化情况Fig.3 Changes of MAE under different K value

图4 不同联合聚类簇下的RMSE和MAE值变化Fig.4 Changes of RMSE and MAE under different K value

图5 不同α值情况下RMSE和MAE值变化Fig.5 Change of RMSE and MAE under different α value

2)联合聚类簇数目W的确定

为了找到最优的联合社区情况,本文分别在不同联合社区数目W的情况下(W=10,20,30,40,50,60)计算其RMSE和MAE值,其中用户社区数取12,其他实验参数同 1)中一样,实验结果如图4所示.

从图4中可以看出RMSE与MAE的值刚开始时随着联合聚类簇的数目增加而减小,达到最小值后又开始增加.分析其可能原因是:如果联合社区的数量过少,对于每一个子矩阵而言,其稀疏性仍然很大,因此在推荐时也依然受数据稀疏性的影响很大;如果联合社区数量过多,那么整个评分矩阵显得十分分散,在进行矩阵分解推荐时可以利用的评分数据就十分少,这样同样影响着推荐的精度.因此评分矩阵的联合聚类簇的数目为40的时候可以得到最好的效果.

3)正则化参数α的确定

正则化参数α表示的是用户的社区结构在矩阵分解模型中参与的比重,当α=0时模型相当于基本的矩阵分解模型,本文将α取值分别为{0.0001,0.001,0.01,0.1,1,10}进行实验,其他实验参数设置如下:用户社区数目K=12,评分联合社区数W=40,λ=0.01,记录MAE值和RMSE随着不同的α值得变化情况,实验结果如图5所示.

从图5中可以看到,RMSE和MAE的值先减小后增大,当α=0.01时RMSE和MAE的值达到最小值,分析其可能原因是当α的取值过小时,算法引入的信息对结果影响不大,最后效果不明显;当α取值过大时,引入的信息权重过大造成过拟合的现象,因此效果也不明显.

3.3.2 不同推荐算法整体用户上的效果对比

通过之前实验的分析,可知当用户社区数目K=12,联合社区数目W=40,正则化参数α=0.01时,本文提出的UCCC模型能获得最佳的推荐结果.为了更加进一步验证本文所提算法的有效性,将本文的算法与3.2节中提到的算法进行了对比实验,用户和项目的特征向量维度均设为10,在SoReg中将社交正则化系数α设置为0.01,MFCC中正则化参数λ设置为10,实验结果如表1所示.

从表1中可以看出,本文提出的结合用户社区和评分联合社区的协同过滤算法和其他算法相比,推荐精度更高,分析其可能的原因是,BaseMF算法没有考虑评分信息以外的信息,所以其推荐效果最差;SoReg考虑到了用户间的社交关系信息,推荐精度有一定的提升,但社交关系是十分稀疏的;UCCC-U考虑了用户的社区结构作为正则项,相对于SoReg来说对用户进行了聚类操作,更加有效利用了用户的社交关系信息,因此效果有所提升;MFCC算法和UCCC-UI算法利用了评分矩阵的联合社区结构,效果相比传统的BaseMF算法有所提升.本文提出的UCCC算法一方面使用用户的社区结构,一定程度上缓解用户间的社交稀疏问题;另一方面,针对评分矩阵进行了联合聚类操作,缓解了评分矩阵稀疏的问题,因此整体推荐效果可以得到提升.

表1 不同推荐方法在整体情况下的对比Table 1 Comparison of different methods on all users

3.3.3 不同推荐算法在时间性能上的对比

本章所提的基于用户社区和评分联合社区的推荐算法可以被应用到大规模的数据集中,图6描述的是BaseMF算法、MFCC算法、UCCC算法以及其变体算法在进行评分预测时的运行时间对比.

图6 不同算法的运行时间对比图Fig.6 Comparison of runtime with different algorithms

从图6中可以看出,UCCC-U算法的运行时间最长,这是因为单独地以正则化地方式引入用户的社区结构并不能降低数据的规模,虽然在推荐误差上有所下降,但耗时较长;MFCC、UCCC-UI算法因为进行了联合聚类,所以模型的训练时间显著降低,这也证明了联合聚类确实可以提高运行的效率;同时可以看到UCCC算法相对MFCC和UCCC-U的计算时间是有所增加的,这是由于其在进行矩阵分解时需要搜寻邻居用户的偏好,但从表1可以知道其推荐误差较小,因此其综合性能较优.总体来说本文提出的算法可以在保证一定推荐精度的同时,提高推荐的效率.

4 结 语

本文在传统的基于社区结构的推荐算法的基础上,融合用户的社区结构和评分矩阵联合社区结构,通过利用聚类算法来挖掘用户社区,通过概率的方法来挖掘评分矩阵联合社区,然后在面向联合社区的矩阵中结合用户社区进行矩阵分解.在当前研究中,我们考虑的都是静态兴趣偏好与社交关系,但是随着时间的推移,用户的兴趣和社交关系都是不断在变化的,因此考虑在动态场景下的协同过滤推荐算法是未来研究的重要工作之一.