基于差异化资源分配的二部图推荐算法

张功国，江 洋，成振华，刘 颖

(1.重庆邮电大学通信与信息工程学院，重庆400065;2.重庆市质量和标准化研究院，重庆400023;3.重庆信科设计有限公司，重庆401121)

1 引言

随着大数据时代的到来，信息过载问题变得越来越严重，推荐系统是用于解决信息过载的有效途径，它用来给用户推荐可能感兴趣的事务[1]。推荐算法是推荐系统的核心，它用于处理输入信息并将其形成推荐信息。近年来，基于二部图的推荐算法受到了很多研究者的关注，该算法借鉴了物理学上热传导和物质扩散的思想[2]。周涛等人最早提出了一种基于二部图的物质扩散推荐算法[3]，该算法倾向于给用户推荐流行项目；文献[4]在此基础上对项目的初始资源进行修正，引入一个参数β，通过把项目初始资源k(o)调整为k(o)β，抑制了流行项目的影响，从而提高了算法推荐的多样性；Becatti等人在文献[5]中按照一定的重启动条件设定，在二部图网络结构中加入随机的游走过程，由此来寻找最佳的待推荐节点；He[6]等人考虑到项目对于用户的吸引作用，提出在二部图推荐系统中加入反馈调节，在多个数据集中实现了推荐新颖度的提高。

本文结合已有研究提出了一种基于差异化资源分配的二部图推荐算法。分别对项目初始资源和资源分配系数进行了差异化设置，通过实验验证了该算法相比其它类似的算法在推荐精度和多样性上都有所提升。

2 传统二部图推荐算法

将推荐系统建模成二部图，其中节点的两个集合分别代表用户集U和项目集O，当用户选择了项目则将它们相连，即两者形成连边[7]。一个由n个用户U={u1，u2…un}和m个项目O={o1，o2，…，om}构成的二部图可以用邻接矩阵A={aαi}n，m表示，如果用户uα选择了项目oi则aαi=1，未选择则aαi=0。二部图推荐算法认为，用户选择过的项目有向其推荐其它项目的能力，这样的能力可以在二部图中进行传递，从而产生推荐。

传统二部图推荐算法具体步骤如下：

1)项目初始资源配置

设用户uα为目标用户，则各项目初始资源值的表达式如式(1)所示

f(oi)=aαi

(1)

如果用户uα选择了项目oi则aαi=1，即该项目的初始资源为1，未选择则aαi=0。

2)项目将资源传递给用户

在传统二部图推荐算法中，第一次资源流转采用均匀分配的方式由项目流向用户，项目oi的初始资源f(oi)≥0，则经过第一次资源流转，任意用户uβ获得的资源如式(2)所示

(2)

其中，aβi为邻接矩阵A={aαi}n，m中的对应元素，k(oi)为项目oi的度即该项目被多少用户选择过。

3)用户将资源再次传递给项目

用户将第一阶段获得的资源传递给相对应的项目，也采用均匀分配原则。在该过程中任意项目oj所获得的资源如式(3)所示

(3)

其中，k(uβ)为用户uβ的度，即该用户选择过多少项目。

4)生成推荐列表

将目标用户未选择过的项目按照f(oj)的大小进行排序，将所获资源最多的前L项推荐给用户，L为推荐列表长度。

如图1所示，(a)表示该二部图由四个用户和三个项目组成，x，y，z分别表示三个项目的初始资源，(b)表示经第一步资源流转后每个用户所获得的相应资源值，(c)表示经两步资源流转以后每个项目最终所获得的资源。则三个项目的最终资源x′、y′、z′如式(4)所示

(4)

图1 基于二部图的资源分配推荐算法资源流转图

3 基于差异化资源分配的二部图推荐算法

传统二部图推荐算法在进行初始资源设置时往往仅依靠项目是否被目标用户选择而进行0/1设置，这样会丢失系统里面的很多有用信息；另外在进行资源流转时也仅仅依靠项目度和用户度来平均分配，这样会导致推荐有失准确性。针对以上问题，提出一种基于差异化资源分配的二部图推荐算法，新算法具体如下：

步骤一：初始资源差异化设置

在现实生活中可能存在着恶意评分等特殊因素，在这种情况下评分不能代表用户的真实偏好[8]。利用规范化对评分进行处理，消除评分不利影响。评分规范化的预处理方法如式(5)所示

(5)

其中，rαi为用户uα对项目oi的初始评分，Pi为项目oi得到的平均评分值，Qα为用户uα对所有项目评分的均值，预处理以后更能体现用户的真实喜好。若Pi>Qα则代表项目oi受用户的喜爱，因此对评分进行增强修正，反之对评分进行削弱修正。

为了减小由于用户评分尺度不同而带来的计算误差，进一步优化评分数据，采用最大最小值法[9]进行修正，如式(6)所示

(6)

其中，rmax、rmin分别表示用户uα在系统中给出的最大和最小评分值，为了预防分母为0，设定极小值p为0.001，同时为了实验方便，设定极小值q为0.01。

传统的大多数推荐算法都没有考虑到“兴趣偏移”问题，即用户的兴趣会随着时间的变化而改变，项目的流行度也会随时代而变。时间因素在推荐系统中也是一个重要信息，对用户的喜好有着很大的影响。本文基于德国心理学家艾宾浩斯所提出的记忆遗忘曲线[10]，将时间衰减函数定义为式(7)所示(时间计量单位为天)

(7)

其中，fα，i(t)表示当时间为t时，用户uα对项目oi“兴趣偏移”的衰减率，tα表示用户uα在系统中初次评分的时间，tα，i表示用户uα对项目oi进行评分操作的时间。fα，i(t)的取值范围在e-1到1之间，符合衰减率的要求。

经过评分规范化、最大最小值修正以及时间衰减函数的量化，最终实现了项目初始资源的差异化设置，如式(8)所示

(8)

步骤二：第一阶段资源分配

在基于二部图的推荐算法中，项目将资源根据用户项目相互之间的选择关系平均分配给相应的用户，考虑到以下两点：①如果两个用户共同选择的项目数比较多，那么他们的兴趣相似性可能比较高；②如果两个用户对项目的评分大小比较接近，代表其偏好更加的相近。基于此，本文利用修正后的用户评分相似性函数对第一阶段资源分配系数进行差异化设置，使得与目标用户兴趣相似的用户能够得到更多的资源。

两个用户共同选择的项目比例如式(9)所示

(9)

其中，Iα和Iβ分别表示用户uα和uβ所选择的项目的集合，两个用户共同选择的项目比例越大，他们的兴趣就可能越相近。

交互用户指的是有公共选择的用户，他们的交互关系指的是对于项目的喜爱程度是否一致。本文通过积极评分还是消极评分判定用户交互成功还是失败。如果用户对项目评分小于他给出的评分均值，说明它为消极评分；反之则为积极评分。倘若用户uα和uβ对相同项目oi给出的都是积极或消极评分，说明交互用户间持有相同观点，他们交互是成功的；反之交互是失败的。交互关系判定方法如式(10)所示

(10)

计算两个用户评分相似性，需要收集双方交互间历史总记录。假设s和f分别代表交互用户彼此间成功和失败次数。即每次交互用户间项目交互成功，那么s+1(i∈Is)，否则f+1(i∈If)。

结合项目比例系数、交互关系以及评分偏差，最终得到用户评分相似性函数，如式(11)所示

(11)

其中，Is表示两用户交互成功的项目集合，If表示交互失败的项目集合。

利用新构建的用户评分相似性函数得到第一阶段的资源分配系数，如式(12)所示

(12)

Hα，βi表示用户uβ与目标用户uα的相似度占所有选择了项目oi的用户与目标用户uα的相似度之和的比例，取值在0到1之间，Hα，βi越大表示在所有已经选择项目oi的用户群体中，用户uα与uβ比其他用户更为相似，则项目oi上的初始资源就会较多的传递到用户uβ。

假设选定用户uα为目标用户并为其推荐，则在第一阶段资源流转以后传递到任意用户uβ的资源量如式(13)所示

(13)

步骤三：第二阶段资源分配

在第二阶段资源分配中，推荐者是与目标用户有共同选择的用户，这些用户更倾向于推荐自己喜爱的项目。因此在第二阶段资源分配中也加入了用户的显性偏好，把资源分配系数定义成用户对项目的评分比例zβ，j，如式(14)所示

(14)

其中，Max(β)是用户uβ在系统中给出的最大评分，zβ，j越大则认为用户更加愿意推荐该项目给其他用户。由此所有作为邻居用户的推荐者推荐的项目都是各自认为最好的，并且避免了用户的评分尺度不一的问题。则在第二阶段资源流转后传递到任意项目oj的资源如式(15)所示

(15)

其中，k(uβ)为用户uβ的度，f(uβ)由步骤二所得。

步骤四：推荐：

将目标用户未选择过的项目按照f(oj)的大小进行排序，将所获资源最多的前L项推荐给用户，L为推荐列表长度。

4 实验分析

4.1 实验数据

在选择数据集时本文选用了推荐系统中最经典的MovieLens数据集和Netflix数据集。前者由943个用户和1682部电影组成，用户使用整数1-5对电影进行评分，评分越大表示用户喜爱程度越强。后者曾用于全球推荐系统竞赛，原始的Netflix数据集非常大，本文从中截取了一个由 10000个用户和6000个电影组成的数据子集，该数据集相对MovieLens数据集的选择关系要复杂很多。在实验中，将数据集随机分成两部分：80%作为训练集，用于建立推荐模型，其余20%作为测试集，用于验证模型性能。为了确保结果更加准确，实验均采用五折交叉法验证测试。

4.2 评价指标

准确率是指推荐算法的结果中用户实际选择的项目占推荐结果的项目总数的比例，定义如式(16)所示

(16)

其中，hits是为目标用户准确推荐的项目的数量，recset是推荐列表的长度。准确率越大，说明该推荐结果越能反映出用户的喜好。

召回率指的是推荐结果中实际的项目命中数占在理论上最大的可能命中数的比例，定义如式(17)所示

(17)

其中，hits是为目标用户准确推荐的项目的数量，testset是理论上最大的可能命中数。召回率越大，说明推荐结果对用户的喜好的覆盖率高，即推荐系统能够更大程度的满足用户的需求。

通常情况下Pr ecision和Re call都是越高越好，然而事实上两者在某些情况下是相互矛盾的。F1是Pr ecision和Re call的加权调和平均，能够有效的在准确率和召回率之间取得平衡。其定义如式(18)所示

(18)

F1的值越高，说明推荐算法的综合准确性越好。

本文使用汉明距离(Hamming distance，HD)来评估推荐算法的多样性，它描述了用户间推荐列表之间的差异性。如式(19)所示

(19)

其实，m表示用户数，L表示推荐列表的长度，Q=|βi∩βj|表示两用户的推荐列表中的相同项目的数量，HD越大表明推荐结果越多样化。

4.3 实验结果与分析

将本文所提出的基于差异化资源分配的二部图推荐算法(BGRA)与基于热传导的二部图推荐算法(HC)、基于物质扩散的二部图推荐算法(MD)、基于物质扩散与热传导的混合推荐算法(HPH)以及文献[11]提出的基于二部图网络的非均匀资源分配推荐算法(NURA)进行对比实验。

首先比较各个算法的推荐集质量，评价指标包括准确率Pr ecision、召回率Re call和F1系数。

图2 Precision值对比结果

如图2所示，在两个数据集中当推荐列表长度较小时，BGRA算法的准确率和HPH(α=0.5)、NURA表现差不多，随着推荐列表长度的增加，BGRA的准确率明显要高于其它几种算法，证明BGRA有着较好的准确率。只考虑推荐多样性的HC算法明显要比其中几种算法的推荐准确率低。

图3 Recall值对比结果

如图3所示，随着推荐列表长度的增加几种算法的召回率都有所上升，这是因为随着推荐列表的增加，算法能够预测到的用户喜爱的电影数量变多，相应的未能命中的数量就少了。在MovieLens数据集中，BGRA、HPH、NURA三种算法的召回率表现相似。但在相对复杂的Netflix数据集中，BGRA算法在召回率的总体表现要优于其它几种算法。

图4 F1值对比结果

如图4所示，各个算法的F1系数变化曲线转折点均在推荐列表长度为20的时候。只注重推荐多样性的HC算法依然是几种算法中F1系数表现最差的。在MovieLens数据集中，BGRA算法在F1系数方面并不太理想，但在Netflix数据集中优于其它四种算法。

其次在推荐多样性比较中，如图5所示。HC算法的推荐多样性要比MD、HPH算法好很多，在Netflix数据集中本文提出的BGRA算法要好于其它几种算法，这主要是因为在资源流转过程中加入了分配系数的差异化设置，使得算法推荐出来的电影更具多样化。

图5 HD值对比结果

5 结束语

本文提出了一种基于差异化资源分配的二部图推荐算法。首先利用评分规范化、最大最小值法以及时间遗忘曲线对项目的初始资源进行了差异化设置。然后分别利用用户评分相似性函数和用户偏好函数对两个阶段的分配系数进行了差异化设置，使资源流转变得更加合理。最后通过实验证明在较复杂的数据集中算法的准确率和多样性都有很大的提升。但是随着数据量的增加，推荐需要的开销变大，因此下一步研究的重点是如果改善推荐的可扩展性。