融合用户影响力和灰关联分析的Slope One推荐算法

陈彩蓉,刘 虹,张岐山

(福州大学 经济与管理学院,福州 350108)

1 引 言

协同过滤是目前使用最为广泛的一种个性化推荐算法,它可以根据用户的历史行为对其进行推荐.Slope One算法作为一种基于项目的协同过滤算法,由 Lemire等人于2005年提出,其计算效率高且易于实现[1],但在应用中仍面临许多挑战:

1)Slope One算法在计算过程中将所有用户等量齐观,没有考虑到用户间的差异对实验结果产生的影响.而且传统的相似度计算方法易受个别异常点的影响而造成数据丢失和信息失真.

2)数据稀疏性.随着用户数量的增加以及物品的爆炸式增长,用户不可能对每一个物品都有过评价,用户-项目矩阵极其稀疏.Slope One算法在密集数据下能够得到良好的推荐效果,但是在面临稀疏矩阵时的推荐质量并不可观.

3)冷启动问题.当一个用户初入系统时,因为系统中有关该用户的信息不足,因此无法为其生成推荐,同样,当出现新项目时,系统也不太可能向用户推荐这些项目,因为没有用户购买这些项目或对这些项目产生评级,从而导致了冷启动问题.

4)灰羊用户问题.灰羊用户指的是与几乎所有用户的相似性都不高的用户群体,导致系统推荐效果不佳.事实上,当用户长时间处于冷启动问题的情况下时,由于其对系统的产品未表现出兴趣,有可能会被误认为是灰羊用户[2].

因此,针对Slope One算法的研究与完善引起了诸多学者的关注和重视.Jiang等人[3]对Slope One算法进行了改进,其在采用可信数据的基础上融合了用户相似度,能够有效提高算法的推荐精度.Song等人[4]提出基于余弦相似度的K-Means++聚类算法,并在不同用户类中考虑个体评分差异,在降低空间复杂度的同时提高了推荐质量.Hu等人[5]在Slope One算法基础上融合Salton系数来衡量景点间的相似度,有效提高旅游景点推荐系统的新颖性和准确性.冯勇等人[6]综合考虑项目类型和项目评分数据来计算项目间的相似性,并在此基础上考虑项目筛选策略,有效提升推荐效率和推荐精度.陈梅梅等人[7]采用调整余弦相似度计算用户间的相似性,同时兼顾了不同活跃度用户的话语权差异对预测结果的影响,在一定程度上缓解了数据稀疏问题,提高了推荐的准确性.Ye等人[8]采用改进的Pearson和Jaccard加权融合方法,并结合K近邻的思想来计算Slope One算法中的偏差项,提高了预测精度,然后引入用户标签信息进一步提高预测精度.

这些算法的仿真结果显示,推荐系统的质量有了一定的提高,但目前有关研究中对于相似度的改进一般都采用传统方法来计算相似性,在数据稀疏的情况下精度不高[9],从而导致推荐结果不理想.且目前研究多是针对数据稀疏以及优化预测精度等角度进行改进,仍然难以完美解决Slope One算法中存在的包括冷启动和灰羊用户等在内的所有问题.综上讨论,本文在上述研究工作基础上提出了一种融合用户影响力和灰关联分析的改进加权 Slope One 推荐算法(GISO),该算法在Slope One算法基础上综合考虑了用户相似性和用户影响力,并融合到评分预测过程中.具体的,本文的创新主要体现在以下两个方面:

1)引入均衡接近度.为了克服传统的相似度计算方法的不足,本文采用均衡接近度灰关联方法来度量用户间的相似性,既考虑了用户间距离的接近性,又考虑了用户整体的无差异性接近,充分捕捉用户间的潜在关联,显著提高算法在少数据、贫信息不确定性系统中的推荐精度,使得算法在数据稀疏、邻域较少的情况下,仍然可以达到较高的推荐准确率和较快的收敛速度.

2)引入用户影响力.Slope One算法在评分预测过程中仅考虑了用户对项目之间的评分差异,忽视了用户间的信任信息,针对这部分信息,本文引入基于图结构的PageRank算法构建用户信任关系网络,将用户节点的权重作为体现用户影响力水平的参数融入到算法评分预测过程中,能够有效缓解冷启动以及灰羊用户等问题对算法的影响.

以下将详细介绍本文的研究工作.

2 相关工作

2.1 Slope One算法简介

2.1.1 Slope One算法

Slope One算法[10]的基本思想来源于一元线性回归模型f(x)=x+b.Slope One算法主要包括两步:1)计算用户在各个项目中的评分差异;2)基于用户的历史评分和项目评分差值估计该用户对目标项目的大致评分.给定项目i和j,它们之间的评分偏差公式见式(1):

(1)

用户u对项目j的预测公式:

(2)

其中,u代表该用户集合中的用户;Sj,i(χ)为评价过项目i、j的用户集合;Rj为用户u的评分项目集合;card()表示Rj中包含的元素总数目;devj,i代表项目i相对于项目j的评分偏差.

2.1.2 Weighted Slope One算法

由于Slope One算法未考虑用户间的可信度差异,故Lemire等人[11]还提出了一种加权Slope One算法:

(3)

其中,Puj为用户u对项目j的预测评分值,Cji为同时对项目i,j有评分的用户总数,devj,i为项目i相对于项目j的平均评分偏差.

Weighted Slope One算法相比原Slope One算法,进一步考虑了对任意两个项目同时有过评分的用户数,其基本思想是,若有1000名用户对项目i和j完成过评价,但仅有10名用户都对i和k完成过评价,那么计算出的devi,j比devi,k更具说服力.但Weighted Slope One算法忽略了不同用户之间的差异性,带来了新的误差.

2.2 均衡接近度灰关联方法

均衡接近度方法是基于传统灰关联系数方法,进一步考虑灰关联因子序列间点的距离接近性及整体的无差异性接近发展而来的方法[12],其在复杂系统及贫信息系统中得以有效应用.

定义1.(灰关联度)设灰关联因子集X=(x1,x2,x3,…,xn),参考列X0={x0(k)|k∈K},比较列Xi={xi(k)|k∈k},i∈I={1,2,3,…,m},K={1,2,3,…,n}.

(4)

(5)

其中,ζ为分辨系数,一般取0.5[13];γ(X0,Xi)表示第i个比较列的灰关联度.

定义2.(均衡度)设第i个比较列的关联系数列为Ri={γ(x0(k),xi(k))|k∈K}.

(6)

(7)

其中,lnn为最大熵;pi(k)为比较列Xi的第k个属性上的灰关联密度值;B(Ri)为第i个比较列的均衡度.

定义3.(均衡接近度)

Ba(X0,Xi)=B(Ri)×γ(X0,Xi)

(8)

其中,Ba(X0,Xi)为参考列X0与比较列Xi的均衡接近度,均衡接近度越大则两序列相关性越大.

均衡接近度方法有效改进了传统的灰关联系数方法[13],进一步解决点关联强倾向和信息稀疏的不足.此外,与传统的相似性度量方法相比,均衡接近度方法极大增加了系统内部各要素之间接近程度的可辨识性.故本文采用均衡接近度来度量用户之间的相关性,计算其相似度.

2.3 PageRank算法

PageRank算法,又称网页排名算法,其核心思想是:根据网页之间相互链接的引用关系计算网页得分,并按分值进行排序,从而得到网页重要度的排名.Google用它来体现网页的相关性和重要性,其在搜索引擎中所展现出的优秀性能引起了广泛关注,并在多个学术领域有所应用,如角色识别[14]、用户评价[15]等.PageRank值(以下简称PR值)的计算公式如下:

(9)

其中,Mpi是所有对pi网页有出链的网页集合,L(pj)是网页pj的出链数目,N是网页总数,α是阻尼系数,常置为0.85[16].

假设用图1所示的输入数据文件运行PageRank算法,根据公式(9)的计算将得到以下输出,见表1.被引用意味着这个页面很重要,由于URL_2被引用的次数最多,因此其拥有最高的页面排名.而URL_3被最重要的URL_2所引用,因此URL_3的排名也随之上升到第2位.在图1中可以看到URL_1被引用的次数最少,这也就是其排名最低的原因.

表1 基于PageRank算法得出的网页排名Table 1 URL ranks based on PageRank algorithm

图1 PageRank算法的输入数据示例Fig.1 Sample input data for PageRank algorithm

本文提出的用户信任关系传播思想是:被多个用户所信任的用户其影响力是高的,被影响力高的用户所信任的用户同样具有高影响力,与PageRank算法思想类似,因此引入PageRank算法,利用图结构来建模用户的优先级,令每个用户作为一个节点,若用户间存在信任关系,则将该信任关系视为有向边,并以此构建一个用户信任关系网络,用以拟合用户之间的信任关系,并使用PageRank算法计算出各个用户节点的权重,作为体现用户影响力水平的参数.

3 改进加权Slope One推荐算法

3.1 融合用户影响力和均衡接近度的Slope One推荐算法

本文基于传统的加权Slope One算法,提出融合用户影响力和灰关联分析的改进加权Slope One算法.用户的PR值越高则表示该用户具有更高的用户影响力,说明其给出的推荐具有更高的公信力和代表性,因此,将公式(9)计算出来的PR值加权到公式(1)中可得公式(10):

(10)

其中,由于所有节点的PR值总和为1,在节点数量很多的情况下,各节点的PR值相应减小,因此,为了放大PR值的效果,在后续实验中将其乘以1000.

在改进后的公式(10)中,用户的预测评分受到其他用户的影响,影响的程度取决于该节点用户的PR值的大小,但并不是所有具有影响力的用户都可以为预测用户带来有效的影响.当用户之间相似性越大时,用户之间兴趣相似的可能性越大,认为该用户对预测用户的影响力相应增强.因此,本文引入均衡接近度衡量用户间的相似性,将公式(8)得到的均衡接近度值加权到公式(3)中,结合(10)式,得到融合用户影响力和灰关联分析的改进加权Slope One 推荐算法(Slope One Algorithm Integrating Grey Association Analysis and User Influence,GISO),见公式(11):

(11)

其中,Simuv为用户u与对项目i,j有过共同评分的前K个相似用户v的均衡接近度值.

例如,现有用户u1,u2,u3,u4对项目i1,i2,i3,i4,i5的评分矩阵R,见表2;参照图1建立用户信任关系矩阵F,用户u1,u2,u3,u4分别对应网页URL_1,URL_2,URL_3,URL_4,见表3.

表2 用户-项目评分矩阵RTable 2 User-item rating matrix R

表3 用户信任关系矩阵FTable 3 Users′ trust relationship matrix F

表3中,fuu′=0表示用户u不信任用户u′,fuu′=1表示用户u信任用户u′.

根据表2和表3,融合用户影响力和灰关联分析的改进加权Slope One算法具体步骤如下.

第1步.计算所有具有共同评分项的用户之间的均衡接近度值.

以计算用户u1和u2的均衡接近度为例,将未评分项看作0,令u1评分数据为参考数据列:{x0}={a11,0,a13,a14,a15},u2评分数据为比较列:{x1}={0,a22,a23,0,a25},i∈I={1,2,3,4},K={1,2,3,4,5}.

此时计算参考列{x0}与比较列{x1}对应元素的绝对差值|x0(k)-x1(k)|,根据公式(4)可得灰关联系数γ(x0(k),x1(k)),由公式(5)进一步得到灰关联度γ(x0,x1),再由公式(6)计算灰关联密度值p(x0(k),x1(k)).本例最大熵lnn=ln5,则由公式(7)可算得均衡度B(R1),最后根据公式(8)得到均衡接近度Ba(X0,X1).同理,可得各用户之间的均衡接近度值.

第2步.计算各用户节点的影响力权重.

由于表3的信任关系参照图1设立,因此反映各用户影响力的PR值可直接参照表1得到.

第3步.将均衡接近度和用户影响力加权至评分预测过程中.

如当计算用户u1对项目i2的预测评分值时,首先将对项目i2有过评分的所有用户筛选出来,即{u2,u4};其次在用户集合{u2,u4}中寻找与用户u1同时进行过评分的所有项目,包括目标项目i2在内,构成项目集合{i1,i2,i3,i5};接着利用公式(10)分别计算i2相对于i1,i3,i5的评分偏差,可得:

最后根据公式(11)可以计算出用户u1对项目i2的评分预测值Puj.

本文所提出的GISO算法在Slope One算法基础上综合考虑了用户相似度和用户影响力.首先,采用均衡接近度方法计算用户间的相似度,有效衡量用户间关系的密切程度;其次,引入PageRank算法,利用图结构来建模用户间的信任关系,将计算出的PR值作为体现用户影响力水平的参数;最后,将均衡接近度和用户影响力作为权重因子加权到Slope One算法的评分预测过程中,从而进一步实现推荐.算法流程图可以用图2来表示.

图2 本文算法流程Fig.2 Procedure of the proposed algorithm

3.2 算法描述

在上述设计思想的基础上,归纳融合用户影响力和灰关联分析的改进加权Slope One推荐算法(GISO)的伪代码如下:

算法1.GISO算法

输入：目标用户u,待评分项目j,评分项目集合I={i1,i2,…,in},用户-项目评分矩阵R,用户信任关系矩阵F,邻居用户数K.

输出：目标用户u对评分项目j的预测评分Puj

1.foruin matrix

2. for each user

3. ifjin user andiin user

4. Algorithm 1-1

5. sortBa

6. Algorithm 1-2

7. end for

8.end for

9.foriinI

10. for each user

11. ifjin user andiin user

14. else

15. pass

16. end for

17.end for

18.returnPuj

其中,GISO算法中涉及到的子代码,均衡接近度算法及PageRank算法的伪代码如下:

算法2.均衡接近度算法

输入：用户项目评分矩阵R.

输出：用户间的均衡接近度值Ba.

6.ifHm(X)==0 orHm(X)==0

Ba=0

7.else

9.Ba(X0,Xi)=B(Ri)×γ(X0,Xi)

10.returnBa

算法3.PageRank算法

输入：用户信任关系矩阵F,阻尼因子a.

输出：用户的影响力权重PRi.

1.i=0

2.PR0=1/N

3.while |PRi(u)-PRi-1(u)|>εdo

4.i=i+1

6.end while

7.returnPRi(u)

4 实验分析

4.1 实验设置

4.1.1 实验环境

实验硬件配置为处理器AMD Ryzen7-5800H,3.20GHz,内存16GB;软件环境为Windows10×64操作系统;运行环境为Python3.7.0.

4.1.2 数据集

本文选取Guo等人[17]发布的公开数据集Ciao作为实验数据,数据集中包含用户间的信任信息及用户对项目的评分信息.对每个用户,随机抽取评分数据中的80%作为训练集,其余的记录作为测试集.本文基础数据集Ciao的详细介绍见表4.

表5 实验对比模型Table 5 Introduction to the Ciao dataset

4.1.3 对比模型

为验证本文提出的GISO算法的推荐性能,对比SO、WSO、PSO、CSO、GBSO[18]算法,从不同近邻数、冷启动条件下、不同稀疏度等多角度探究算法的有效性.

4.2 实验指标

为评估本文所提算法的推荐质量,选取平均绝对误差(MAE)和均方根误差(RMSE)两个指标来验证本文算法的推荐性能.MAE和RMSE值越低表示预测效果越好,计算公式见公式(12)、公式(13):

(12)

(13)

4.3 实验设计

为探究文本提出的改进加权Slope One算法的推荐质量,共设置了3组对照实验.首先,通过在Ciao数据集上分别按不同近邻数及不同的算法进行计算,验证了本文算法的提升效果和收敛速率,进一步探究了该算法在灰羊用户群体中的表现;其次,选取评价记录总数小于等于25条的用户,设置为冷启动用户,探究本文算法对冷启动用户的推荐效果;最后,为了模拟本文算法在不同数据稀疏度状况下的表现,抽取Ciao数据集中一定比例的数据构成新的数据集进一步实验.

4.4 实验结果

实验1.不同推荐算法的性能对比

在Ciao数据集上,分别按6种不同的算法进行计算,同时,不断调整近邻数,观察MAE和RMSE值的变化趋势.假设用户的近邻数K为[2,20],步长为2.由于SO、WSO算法的计算过程中并未将用户间的相似性考虑在内,所以不需要选取近邻数,因而通过这两种算法得到的MAE、RMSE值的结果是线性的,无变化趋势.实验结果见图3、图4.

图3 各推荐算法的MAE比较Fig.3 MAE comparison of recommendation algorithms

图4 各推荐算法的RMSE比较Fig.4 RMSE comparison of recommendation algorithms

观察图3、图4可知,在不同近邻数下,WSO算法对比SO算法的MAE和RMSE值均有所下降,因此,考虑用户评分数量差异性能够在一定程度上提升算法预测准确度.但很显然,在进一步对比改进WSO的PSO和CSO算法后,可以发现它们在Ciao数据集上并没有展现出考虑用户相似度本应出现的优势,甚至拉低了SO和WSO原始模型的效果.这是由于在Ciao数据集高达99.97%的稀疏度条件下,皮尔逊相关系数和余弦相似度无法在贫信息背景下准确测度用户间的密切程度,相反,均衡接近度灰关联方法能够在贫信息系统中有效提高用户相似度计算的精度.当近邻数小于3时,CBSO算法并没有有效提升推荐效果,但总体而言,结合均衡接近度的GBSO和GISO算法对比其他几种算法,包括原始的SO、WSO算法,其推荐效果得到了显著提升.

另外,在近邻数为[2,20]的取值区间内,随着近邻数的增加,根据CSO、PSO、GBSO算法所计算出来的MAE和RMSE值均呈现下降并逐渐收敛的趋势,不同的是,GBSO算法的收敛速度更快,在K值为6时,通过GBSO算法得到的MAE和RMSE值均已趋于平稳.而在GBSO算法基础上进一步考虑用户影响力因素的GISO算法,在不同近邻数条件下表现稳定,在推荐效果上也有显著提升,说明其在相似用户较少,即近邻数较少的灰羊用户群体中,也能够达到优异且稳定的推荐效果.

实验2.算法冷启动对比分析

为了验证本文提出的GISO算法对冷启动问题的优化作用,本次实验中将评分数量小于25的用户设定为冷启动用户,并在实验1的基础上更换冷启动数据集.其中,近邻数K取[2,20],步长为2.实验结果见图5、图6.

图5 冷启动下各算法MAE对比Fig.5 MAE Comparison of Algorithms under Cold Start

图6 冷启动下各算法RMSE对比Fig.6 RMSE Comparison of Algorithms under Cold Start

同样,由于SO、WSO算法不用选取近邻数,故由这两种算法计算得到的关于冷启动用户的MAE、RMSE值无变化趋势.

从图5、图6可以观察到,由SO、WSO算法得到的预测效果较差,因此这两种算法受到冷启动问题影响较大.当然,CSO、PSO算法在相似信息更为稀疏的冷启动用户实验中,并没有发挥出更好的性能.不同的是,基于均衡接近度灰关联衡量用户相似度的GBSO和GISO算法在冷启动实验中则表现得更为优异且稳定,充分证明了均衡相似度灰关联相比于其它算法,在稀疏数据集下具有更好的推荐精度.此外,在GBSO算法基础上进一步融合了用户影响力因素的GISO算法,无论在何近邻值下,对于冷启动用户都能达到更好的推荐效果,这是因为在本实验设置中的冷启动用户当中存在一定的灰羊用户,其在和其他用户相似度都非常低,从而造成推荐性能下降的情况下,融合用户影响力的GISO算法能够在一定程度上为用户给出更具有公信力和影响力的推荐,从而提升推荐性能.本实验充分证实了GISO算法面对用户冷启动问题的有效性,同时也进一步证明了其能够有效降低灰羊用户对推荐性能的影响.

实验3.不同稀疏度下算法的性能对比

为探究GISO算法在不同稀疏度条件下的推荐性能,将原Ciao数据集按一定比例对每个用户的评分记录进行抽取,抽取原则为按四舍五入随机抽取.就此,分别构成了抽取比例为10%,20%,…,100%的10个数据集,表6列出了这10个数据集的相关信息,并给出了各个数据集的稀疏度排序(由大到小).

表6 实验数据集Table 6 Datasets in experiments

在上述两个实验中可以看到,6种不同算法在近邻数K为20时均已收敛或达到平衡,因此本实验中的K值固定为20,分别令6种算法在10种不同稀疏度的数据集中进行计算.图7、图8展示了在K值为20时,不同评分稀疏度数据集下各种算法的性能,其中横轴表示数据集稀疏度排序,纵轴表示MAE和RMSE.这6种算法在不同稀疏度数据集上表现不同,但性能曲线有相似的趋势.此外,GISO算法在不同评分稀疏度下的推荐准确率均优于其他算法,表明在不同稀疏度条件下,该方法均可以有效地挖掘社交数据中隐含的交互信息,从而缓解数据稀疏问题,进一步提高算法的预测精度.

图7 不同稀疏度下各算法MAE对比Fig.7 MAE comparison of algorithms under different sparsity

图8 不同稀疏度下各算法RMSE对比Fig.8 RMSE comparison of algorithms under different sparsity

以上3组实验结果充分验证了均衡接近度灰关联分析方法衡量用户相似度的优势,证明了本文提出的GISO算法在不同K值下的表现稳定,收敛速度快,在推荐性能上均优于SO、WSO、CSO、PSO以及GBSO算法,预测评分效果也较其他对比算法更加准确,能够有效缓解推荐系统中的数据稀疏、冷启动、以及灰羊用户等问题.

5 结束语

本文提出了融合用户影响力和灰关联分析的改进加权Slope One推荐算法,采用均衡接近度方法计算用户间的相似度,引入PageRank算法计算用户影响力,并将均衡接近度和用户影响力融入到Slope One算法的评分预测过程中.实验结果显示,该算法相比于传统的推荐算法,能够有效缓解数据稀疏、冷启动以及灰羊用户等问题对推荐效果产生的影响,并且在邻域较少的情况下,仍然可以达到较高的推荐准确率和较快的收敛速度.

为了探究6种算法在不同稀疏度条件下的表现,本文自行抽取的10个数据集的稀疏度差别还不够突出,今后将考虑使用稀疏度差别更大的数据集进一步实验,分别验证6种算法性能表现.另外,尝试捕捉用户随时间动态变化的兴趣偏好也是未来的工作方向之一.