基于随机森林修正的加权二部图推荐算法

李 玲，李晋宏

（北方工业大学计算机学院 知识工程研究所，北京 100144）

0 引言

在当今的互联网时代，海量的信息膨胀导致了严重的信息过载，如何帮助用户在海量的信息中更准确的筛选所需，是当前研究的热点方向。而个性化推荐系统[1-3]是解决这个问题的有效方法，通过分析用户的行为特性进行兴趣预测，为用户推荐可能会感兴趣的信息，从而提高了用户筛选的效率，节约了信息筛选的时间。目前的推荐算法主要有协同过滤推荐算法（Collaborative Filtering，CF）[4]，基于内容的推荐算法[5]，混合推荐算法和基于网络结构的推荐算法等等，已经被大量的应用在商业化环境当中。协同过滤推荐算法是通过用户对商品的评价，计算用户之间的相似性，寻找邻居，然后根据邻居的信息进行推荐，但是往往存在数据稀疏性等问题。基于内容的推荐算法是以用户选择过的商品信息为依据，选择相似度高的商品推荐给用户。该方法是对商品的信息（种类、用途等）和用户的爱好进行分析并推荐，也属于对信息的过滤，但是由于信息数据格式的限制，往往无法对非文本的商品信息（视频等）进行处理。

现今基于二部图网络结构的推荐技术（Network-Based Inference，NBI）[6-8]是个性化推荐领域一个越来越被人关注的研究热点，由于其推荐复杂度低，准确性高和推荐的内容多样化而被大量关注。它的基本思想是把用户和项目分别看作抽象的节点集合，将用户对项目的选择看成对节点的连边。在物质扩散的启发下，zhou等人[6]提出了利用资源分配的推荐算法；在此基础上，zhang等[9]引入了资源分配权重的概念，将评分看作权重，提出了加权的二部图推荐算法，在不增加时间和空间计算复杂度的情况下提高了准确性；Wang等人[10]根据评分能量分配权重进行了算法的改进，并且添加了项目度与权值的比值，降低了推荐项目的流行性的影响，推荐的多样性也得以提高；在此基础上Li等人[11]在用户推荐时增加了对项目相似性的考虑。

虽然学者们为提高推荐的准确度提出了多种方法，但是目前基于二部图的推荐方法仍然有以下两个不足：第一，设置权重时没有更精细的划分；第二，绝大多数的算法改进都是选择评分或者人为选择用户行为或者项目因素进行加权计算或者推理的，这种人为选择的因素在一定程度上忽视了其他特征因素对推荐结果准确性的影响，使得推荐结果说服力有限，应用局限性比较大。针对以上问题，本文提出了一种基于随机森林修正的二部图推荐算法（RF-WNBI），基本思想是先构建用户-项目特征二部图，对项目进行初步的评分预测，再用随机森林分类预测评分结果进行修正。在构建二部图时细化评分权重，考虑项目度和用户之间共同评分项目影响，最终参考项目特征对评分修正。对比试验结果，证明改进后的算法能够有效提高推荐准确性和多样性[12]。

1 相关工作

1.1 基于二部图网络结构的推荐算法

假设在输入中有m个用户和n个项目，用户 ui对项目 oj进行过选择，那么在 ui与 oj之间就有一条边相连，这样就构成了二部图网络结构G。用U来代表用户，用O来代表项目，定义一个|U|×|O|的邻接矩阵A = ( aij)。如果用户 ui对项目 oj进行过选择，则 aαi= 1，否则 aαi= 0 。

受物理学中复杂物质扩散理论的影响，Zhou等人[6]提出了利用资源分配思想的相似度计算方法。首先，假设给每个用户分配一个单位的能量。接着，进行资源分配，按照平均分配的方式，各个用户将能量分发给该用户选择过的各个项目，分配完成后每个项目将得到一定的能量。

下一步，将每个项目得到的能量值按照相同的方式再次传递给选择过它的各个用户，得到各个用户此时拥有的能量值。simαβ表示的是用户uα在分配过程中从用户uβ获得的资源比例，即用户之间的相似性。能量分配的过程如图1所示。

图1 基于二部图网络结构的能量分配过程Fig.1 Energy distribution process based on the two parts graph network structure

能量分配的过程可以由下列公式表示：

其中 d (uβ)表示的是用户uβ的度（即该用户选择过多少个项目）； d(oi)表示的是项目 oi的度（即该项目被多少个用户选择过）。

目标用户uα对未评分项目 oi的评分计算公式为：

传统的基于二部图网络结构的推荐算法是针对用户与项目之间的关系进行能量分发来对用户进行推荐的，忽略了用户兴趣的影响，不能充分发掘冷门项目，且不能对用户的选择进行充分的解释。因此，文中融合了随机森林算法对特征的分类模型，并以此修正对用户推荐的评分。

1.2 随机森林算法

随机森林（Random Forest）是由Leo breiman[14]提出的，作为一种常用的分类方法，是建立多棵决策树[15-16]将结果进行投票集成分类的。决策树的根节点作为训练集合，节点是作为测试属性，节点分支代表基于单个特征作为分类，叶子节点代表分类结果。

构建随机森林有如下几个步骤：

（1）用 bootstrap方法[17]有放回地随机选择训练的样本集，第k个样本集生成随机向量θk，使用h(x,θk)作为第k棵分类树模型。

（2）对得到的样本分别建立分类树，使用在属性集合中选择最大信息增益的方式选择分裂属性。

首先计算样本的熵，其中 pj表示第j个类别在节点D的概率：

然后计算按特征A划分对样本集合D划分所需要的期望信息，样本集合D被划分的范围为jD。

最后通过由式(4)与(5)得出信息增益，选出具有最大增益率的属性作为分裂属性。

（3）经过分裂得到多个决策树分类模型｛h(x, θk) ,k = 1 ,2… n ｝，参数集 ｛θk｝是独立同分布的随机向量。其最终结果为决策树的投票集成：

其中 H (x)代表分类组合模型， Y是目标变量，I（°）表示指示函数。

2 基于随机森林修正的加权二部图推荐算法

2.1 改进相似度的加权二部图推荐方法

传统的二部图网络只关注用户与项目之间是否有边相连，即是否进行过选择，并不对用户对不同项目的喜爱程度进行区分，选择过的项目即为 1，未选择的项目即设为 0。而用户对项目的评分在很大程度上是用户对项目喜爱程度的反映，不加以区分会对推荐结果的准确性造成影响。而在文献[9]算法直接将他认为的高分项目直接设定权重值为 1，这造成用户信息的损失。在文献[10]提出的算法中，直接忽略了低分项目，只认为得到高分的项目才被用户选择过，也是一定程度上的信息疏漏。

为了细化评分对推荐的影响，考虑用户对项目评分由于每个人的个人倾向不同而有所变化，因此，根据用户对项目的喜爱程度（即显式评分）进行标准化，来对用户和项目的边的权重iαω进行分配。

在式中，irα是用户uα对项目oi的评分，maxr 是用户α全部评分项目的评分最大值，minr 是用户ua全部评分项目的评分最小值，为了预防出现分母为0的情况，设定一个极小值ε为0.01，同时为了区分低分项目与未评分项目，设定一个极小值λ为0.1。在资源分配过程中，引入 IUF系数（Inverse User Frequence）[11]来定义 θ：

其中，D(i)表示项目io的评分集合， ()Dα表示用户uα评分的项目集合， ()Dβ表示用户uβ评分项目的集合。θ的取值为0～1，一方面，衡量了用户的共同评分项目，惩罚了其中的热门项目，便于用户选择出更加符合个人喜好的项目；另一方面，降低了活跃用户对相似性的贡献，往往选择项目少的用户兴趣点更明确，因此活跃度高的用户对相似性的影响应当低于活跃度低的用户。因此在算法中，经过多次试验，引入函数()fθδθ=+的sigmoid函数即可调节，θ的取值为0～1，其中δ为可调参数。进行两步资源分配之后，最终得到的用户相似性计算公式为：

式中υ是两个用户之间共同评分项目个数与目标用户度的比值，即。 ()Dα表示用户uα评分的项目集合， D （β） 表示用户uβ评分项目的集合。在推荐算法中，两个用户选择了同样的项目，那么这个项目可以看作两个用户共同的兴趣点所在，则二者的相似度就越高。但如果目标用户选择的项目很多，那么该用户的兴趣比较广泛，目标用户与其他用户的共同评分项目就只能代表目标用户的部分兴趣；相反的，如果目标用户选择的项目较少，与其他用户共同选择的项目就更能代表目标用户的兴趣所在。

文献[11]中提出，在评分预测中加入用户的评分期望能够提高预测精度，如式（9）所示，并经过验证，证明式（9）进行评分预测准确率明显优于式（2）。因此文中采用式（9）进行评分计算。目标用户uβ对项目jo的评分预测公式：

这里 oj表示有过对 oi项目评分行为的用户；sim(α ,β)表示用户uα、uβ的相似性。rα，rβ表示用户uα、uβ的平均评分。

2.2 生成推荐

给定用户uα及其特征向量集合Ti= ｛ （xi, yi）｝，i∈N。其中x={,…}为特征向量，

+i∈ ｛ 0,1｝是类标签。取特征向量集合构建随机森林，得到分类模型。

对用户uα进行2.3节中基于加权二部图的改进方法进行矩阵计算，得到了用uα户的初步推荐结果N ′ = { (tj, rj)}， tj为项目， rj是评分。对已得到的用户uα的推荐项目进行评分分类，得到分类结果N = { (tj, yj)}， tj为项目， yj是评分修正标签。设定rj≥rα对应的评分标签为1，rj＜rα对应的评分标签为0。对比 rj与 yj，二者相同，保留该项目及评分，不同则降低该项目在评分列表中的排名。最终将推荐列表的前N个推荐给用户。

在推荐方法 RF-WNBI中，改进相似度的加权二部图推荐方法（IWNBI）不但可以生成初始推荐评分，也可以作为推荐方法之一。

2.3 算法流程

算法设计流程如图如图2所示。

图2 总体流程图Fig.2 The overall flow diagram

RF-WNBI的算法描述如下

输入：用户-项目评分矩阵，特征矩阵，目标用户uα，近邻数k，可调参数δ。

输出：用户uα的Top N推荐项目

参数：可调参数δ，近邻数k

（1）对于 uα∊U 且 β≠α，根据公式计算 sim(α,β)，找到分值最高的k个作为最近邻居；

（2）利用步骤(1)的结果，根据公式计算评分iVα；

（3）找出评分值最高的m个项目，依照评分进行降序排序，构成对uα的推荐列表l；

（4）随机森林分类器对l中的项目进行分类；

（5）根据分类结果对 l进行重排序，形成新的推荐列表l'；

（6）取l′中的前N个，形成Top N推荐。

3 实验分析

3.1 数据集

本文使用GroupLens实验室在MovieLens数据集提供的扩展数据库中的公开数据集（http://ir.ii.uam.es/hetrec2011/datasets.html）进行实验，检测算法性能。数据集中包含了800000条数据记录，其中包括 2113名用户和 10197部电影。将数据集分为80%的训练集和 20%的测试集，数据集中每条记录包含以下字段：用户ID、项目ID、用户评分（1～5）、特征向量集合Ti。本数据的矩阵密度为：

3.2 评价标准

本文采用平均排序值、平均绝对误差（MAE）、均方根误差（RMAE）[18]和汉明距离来度量推荐的质量。

（1）平均排序值（Ranking score）用评测用户推荐列表准确度的高低，在测试集中，用户选择过项目io，io排在推荐列表的位置为iL，N代表推荐列表的长度。用户实际选择项目在推荐列表中排名越高，证明推荐结果越准确。当目标用户不同时，对每个 r求均值，即得到算法的平均排序值。则平均排序值（Ranking score）计算公式为：

（2）根据预测值与实际误差值得偏差来表示评分准确率的高低，平均绝对误差值越小，推荐精度越高，如：预测用户的评分集合是{ p1, p2, p3,p4, … pN-1, pN}，用户实际评分集合是{q1， q2， q3，q4， …qN-1，qN}，则平均绝对误差与均方根误差为：

（3）汉明距离（HD）根据不同用户推荐列表中相同项目的数量来评价预测结果的多样性。用户ui与 uj推荐列表之间的汉明距离为：

其中：ijQ代表用户iu与ju推荐列表之间公共项目的集合，|ijQ|代表集合ijQ 中元素的个数，L代表推荐列表长度。如果两个推荐列表是完全一致的，则ijQ=0；如果两个推荐列表没有任何相同的项目，则ijQ=1。所有用户的汉明距离的平均值即是整个系统的汉明距离HD：

其中：m表示用户数量。汉明距离越大，表示推荐结果的多样性越高。

3.3 动态可调参数δ校准

图3展示了动态δ对算法准确率的影响。从图中可知，当δ变化时，产生的推荐结果的MAE和RMSE也随之变化，当δ取到0.4左右的值时，效果最好。

图3 动态因子δ对算法准确性的影响Fig. 3 The effect of dynamic factor δ on the accuracy of algorithm

3.4 不同的近邻数K对推荐准确度的影响

选择适合的最近邻居个数，能够提高计算精度，降低计算时间。由图4可以看出，当随着近邻数K的增加，平均绝对误差(MAE)和均方根误差(RMAE)也随之下降，这是因为当选取相似度高的用户增多时，进而带来的推荐结果更加准确。但当K达到45左右时，MAE和RMAE曲线变得平稳，因此设定K值为50。

图4 近邻数K对算法准确性的影响Fig.4 The influence of nearest neighbor K on the accuracy of algorithm

3.5 算法结果分析

下面进行对比实验，在实验中选择动态因子 的值为0.4，近邻数阈值设为50。对比试验结果如下。

（1）对比平均排序值（Ranking score）

将文献[6]提出的基于二部图的推荐算法（NBI）、文献[11]提出的基于增加相似度系数的加权二部图推荐算法（ISWNBI）、改进相似度的加权二部图推荐方法（IWNBI）、本文基于随机森林修正的加权二部图算法（RF-WNBI）进行Ranking score的对比，实验结果如图5所示。

图5 各算法关于Ranking score的实验对比图Fig.5 The experimental comparison of ranking score of each algorithm

由上图所示，随着推荐列表长度增大，四种算法的平均排序比都逐渐增大且IWNBI和RF-WNBI在推荐列表长度增加时均低于另外两种算法NBI和ISWNBI的平均排序值。并且RF-WNBI的Ranking score明显相对更低。说明本文提出的RF-WNBI会命中更多实际推荐列表中的项目。因此在推荐精度和多样性方面只对NBI、ISWNBI和RF-WNBI进行比较。（2）对比精度（MAE、RMSE）和多样性（HD）图 6是 NBI、ISWNBI和 RF-WNBI关于 MAE、RMSE和HD的对比。

图6 各算法关于推荐精度与推荐多样性的比较Fig.6 The comparison between the proposed algorithm and the recommended diversity

由上图对各MAE和RMSE的对比可以知道，RF-WNBI在推荐精度上明显优于NBI和ISWNBI，可以证明 RF-WNBI具有较高的精度，更容易为用户推荐其喜爱的项目。对三个算法的HD进行对比，RF-WNBI比 NBI的多样性更好，虽然比 ISWNBI的多样性低，但也具有较好的多样性。

综合以上实验结果，可以看出本文提出RF-WNBI具有较好的合理性和较强的推荐效果。

4 结语

文中构建了基于随机森林修正的加权二部图推荐算法，通过对评分权重作出更细致的划分，平衡了项目的权重，充分考虑到对冷门项目的挖掘。完善了相似度计算，提高了推荐的精度。将特征数据进行标准化后建立随机森林模型，对二部图算法阶段产生的预测列表进行评分区间的修正校验。通过和基于加权二部图的推荐算法（NBI）和基于增加相似性系数的加权二部图推荐算法（ISWNBI）进行比较，证明本文算法在保证了较好多样性的同时，提高了推荐的准确性和推荐精度。

[1] Ricci F, Rokach L, Shapira B. Introduction to recommender systems handbook. Recommender Systems Handbook. Springer US, 2011: 1-35.

[2] Xu HL, Wu X, Liu XD, Yan BP. Comparison study of Internet recommendation system[J]. Journal of software, 2009,20(2): 1-10(in China). [许海玲, 吴潇, 李晓东, 等. 互联网推荐系统比较研究[J]. 软件学报, 2009, 20(2): 1-10.]

[3] Li S-T, Xiao B. Recommender system based on social network [J]. Software, 2013, 34(12): 41-45. [李善涛, 肖波. 基于社交网络的信息推荐系统[J]. 软件, 2013, 34(12): 41-45.]

[4] Schafer J-B, Frankowski D, Herlocker J, et al. Collaborative filtering recommender systems[A]. In: The Adaptive Web,Springer-Verlag, 2007: 291-324.

[5] Jiang Z-F, Jiang J, E J-H. A content-based recommendation algorithm with social tagging. Software, 2015, 36(1): 1-5. [江周峰, 杨俊, 鄂海红. 结合社会化标签的基于内容的推荐算法[J]. 软件, 2015, 36(1): 1-5.]

[6] ZHOU T, REN J, MEDO M, et al. Bipartite network projection and personal recommendation[J]. Physical Review E,2007, 76(4): 6116-6123.

[7] LIU Jian-guo, ZHOU Tao, CHE Hong-an, et al. Effects of high-ordercorrelations on personalized recommendations for bipartite networks[J]. Physica A, 2010, 389: 881-886.

[8] SHANG Ming-sheng, LV Lin-yuan, ZHANG Yi-cheng, et al.Empirical analysis of Web-based user-object bipartite networks[J]. Europhysics Letters, 2010, 90(4): 48006．

[9] ZHANG X M, JIANG S Y. Personalized recommendation algorithm based on weighted bipartite network[J]. Journal of Computer Applications, 2012, 32(3): 654-657. (in Chinese).[张新猛, 蒋盛益. 基于加权二部图的个性化推荐算法[J].计算机应用, 2012, 32(3): 654-657.]

[10] WANG Q, DUAN S-Y. Improved recommendation algorithm based on bipartite networks[J]. Application Research of Computers, 2013, 30(3): 771-774 (in Chinese). [王茜, 段双艳. 一种改进的基于二部图网络结构的推荐算法[J]. 计算机应用研究, 2013, 30(03): 771-774.]

[11] LI Z-D, LUO Q, SHI L L. Weighted bipartite network recommendation based on increasing similarity coefficient[J].Computer Science, 2016, 43(7): 259-264 (in Chinese). [李镇东, 罗琦, 施力力. 基于增加相似度系数的加权二部图推荐算法[J]. 计算机科学, 2016, 43(07): 259-264.]

[12] HE Lei. Research of information recommendation algorithm based on bipartite network[D]. Nanchang;Nanchang Hangkong University, 2013(in China). [何磊. 基于网络结构的信息推荐算法的研究[D]. 南昌航空大学, 2013.]

[13] BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithms for collaborative filtering.[C]//Proceedings of the 14th Conference on Uncertainty in Artifi-cial Intelligence. San Francisco, CA: Morgan KaufmannPublishers, 2013: 43-52．

[14] Breiman L, 2001a. Random forests. Mach. Learn. 45: 5-32.

[15] Breiman L. Bagging Preditors[J]. Machine Learning, 1996,24(2).

[16] Ho T K. The Random Subspace Method for Constructing Decision Forests[J]. Trans.on Pattern Analysis and Machine Intelligence, 1998, 20(8).

[17] Ma H, Wang Q, Han Z-D, Zhang X-X, Hao G. Application of decision tree algorithm to personal book recommendation.Software, 2012, 33(8): 100-101. [马华, 王清, 韩忠东, 张西学, 郝刚. 决策树分类算法在个性化图书推荐中的应用[J]. 软件, 2012, 33(8): 100-101.]

[18] Sexton J, Laake P. Standard Errors for Bagged and Random Forest Estimators[J]. Computational Statistics& Data Analysis, 2009, 53(1).

[19] Jonathan L. Herlocker, Joseph A. Konstan, Loren G. Terveen,John T. Riedl. Evaluating collaborative filtering recommender systems[J]. ACM Transactions on Information Systems (TOIS). 2004(1): 5-53.