基于资源分配的推荐算法研究

DOI：10.19850/j.cnki.2096-4706.2021.08.036

摘  要：针对马太效应中过度流行性偏见问题，通过定义新的节点权重来初始化项目资源值，达到降低项目流行性的目的;进一步考虑用户可信度因素，结合统计学中的3σ原则，根据数据统计量筛选出系统中存在的异常用户或欺诈用户。在此基础上给出一个新的推荐算法（UTMT）。在数据集MovieLens_100K上对算法进行试验，并与资源分配中的热传导算法作比较，结果表明，构建的UTMT推荐算法预测结果的准确率较之热传导算法有较大的提升。

关键词：二分图;马太效应;用户可信度;资源分配;推荐算法

中图分类号：TP391.3      文献标识码：A   文章编号：2096-4706（2021）08-0127-03

Research on Recommendation Algorithm Based on Resource Allocation

CHI Luyang

（College of Sciences，Northeastern University，Shenyang  110004，China）

Abstract：Aiming at the problem of excessive popularity bias in Matthew effect，a new node weight is defined to initialize the project resource value，so as to achieve the aim of reducing the project popularity. Further considering the user credibility factor and combining with the 3σ principle of statistics，the abnormal users or fraudulent users existing in the system are filtered out according to the data statistics. On this basis，a new recommendation algorithm（UTMT）is proposed. Test the algorithm on the dataset MovieLens_100k and make a comparison with heat conduction algorithm in resource allocation. The final results show that the constructed recommendation algorithm UTMT has a big improvement in the accuracy rate of predict outcomes than that of the heat conduction algorithm.

Keywords：bipartite graph;Matthew effect;user credibility;resource allocation;recommendation algorithm

0  引  言

隨着互联网的飞速发展，网络中爆发式增长的资源虽然能满足人们的各项需求，但却突破了人们可以有效利用的范围，严重导致了信息过载问题。这在一定程度上凸显了采用个性化推荐系统的关键性和重要性。近年来，将复杂网络与推荐系统相结合的思想也应运而生。一些研究将网络中节点链接关系预测方法应用到推荐系统中。Zhu等人^[1]通过分析共同邻居节点来预测推荐效果。Zhang等人^[2]运用似然分析法评估节点之间推荐的可能性。

基于二分图的推荐算法^[3]可视为一个资源分配的过程，科研人员经常采用单模映射的方法压缩二分图来展示其中复杂的节点关系。通常，最原始的方法是把二分图映射到一个无权图上^[4]，如果一个图上只有A节点，那么这就是A的单模映射结果。若映射结果中两个节点存在一条无向边，那么说明两个节点至少有一个共同邻居。无权重的单模映射会导致在资源传递的过程中丢失很多信息，因此需要在映射图中设置每条边的权重。在此基础上，Zhou等人提出了一种计算边权值来解决问题的方法^[5]，根据节点权重经过多次迭代得出用户推荐列表。基于二分图的推荐算法的原理是通过对这些连接的边进行分析，预测用户的喜好和倾向，与此同时计算出每个项目对应于不同用户的资源值。最终计算出的项目资源值则作为推荐列表中排序的依据。在二分图中通过资源传递来模拟得出节点（包括用户和项目）的资源值。但是以上对节点的分析属于单一类型的研究，没有考虑到节点复杂性的情况，有些算法不适用于实际网络，并且其中涉及的复杂理论研究的结果仍存在可解释性问题。

本文是在基于二分图的推荐算法上进行改进，提高算法性能。具体做法是通过引入用户可信度来改进原始的资源分配推荐算法。此外，由于原始推荐算法存在流行偏见问题，在进行用户推荐时可解释性较低，所以在此基础上考虑了更改资源值的方法以解决相关问题。

1  基于马太效应商品过度推荐的改进

马太效应反映的是强者越发强大、弱者越发弱小的现象。如果推荐系统是以资源分配为框架，那么就会增大流行和非流行项目之间的热门度差距，从而使信息领域也存在马太效应^[6]。商品越热门，就越容易被推荐给用户，从而该商品就会越来越流行;此时，非热门商品反而不容易出现在推荐列表中，导致非热门商品越来越冷门。而对于那些热门项目，不需要借助推荐系统这一媒介，用户也能获取热门项目的资源。本文根据马太效应，推荐那些用户可能会喜欢但不一定是热门的项目。本文选择在推荐过程中降低热门节点的初始值，对其进行适度惩罚，从而降低推荐度。

原始项目初始资源值f=1，本文通过引入一个可调参数α，节点热门度估计重新设定为：

其中a_ij=0或1，当用户i不喜欢项目j时，a_ij=0;当用户i喜欢项目j时，a_ij=1。k（Oj）为项目j的度。参数α就是降低热门项目程度的关键性指标，通过实验得出使推荐效果达到最优时α的取值。

2  用户可信度

2.1  项目偏好平均值

实验过程中，考虑到数据集中可能存在异常数据，所以在实验过程中对噪声数据进行了筛选。一般认为评分数值不在均值±3个标准差范围内的属于异常数据，应做剔除处理。项目偏好平均值（简记为RIPV）的计算过程为：

输入：项目评分数据集

输出：项目偏好平均值RIPV

Step 1.对已清洗好的数据集的评分数据逐一扫描。计算每个项目的期望值E（x）、每个项目评分数值的最小值min、最大值max及相应的标准差σ;

Step 2.若某个项目的[min，max]?[E（x）-3δ，E（x）+3δ]，执行Step 4，否则执行Step 3;

Step 3.根据Step 1中计算得出的期望和标准差，剔除异常数据后重新计算统计值，结束后执行Step 2;

Step 4.RIPV=E（x），算法结束。

2.2  用户误差平均值

本文定义用户误差平均值，简记为UMRE。用户误差平均值是指将每个用户对项目的评分值与RIPV之间的差值的累加，最后除以用戶已经评价的项目数量的总和。它代表用户的评分误差度，UMRE的数值越小，说明用户越可信。用户误差平均值（UMRE）计算公式为：

其中，W_ij为用户U_i对项目Ii的评分，|W_ij>0|表示用户U_i已经评价，可以看出RIPV是以每个项目为对象计算出的结果，UMRE是以每个用户为对象计算出结果的项目总个数。

2.3  用户可信度

为了防止用户误差平均值对结果产生决定性影响，将用户误差平均值以激活函数的形式定义出，公式为：

3  UTMT算法

在以上分析的基础上给出一个新的推荐算法，记为UTMT，算法主要步骤为：

（1）在全体用户数据集中选择目标用户U_i，根据式（1）初始化目标用户喜欢的所有项目的资源值。

（2）在基于资源传递的框架上，目标用户U_i喜欢的项目的初始资源值通过“项目—用户”的传递过程，将初始资源值传递给每一个也同样喜欢该项目的其他用户，同时计算出每个用户的资源值。

（3）计算出用户可信度UT值，将UT值以权重乘积的方式集成到“用户—项目”资源传递过程中，累计不同用户传递给项目的资源值，通过相似度进行相似性搜索，完成最终的资源分配。资源传递终止时项目的资源值，就是该目标用户Ui对各个项目的喜爱程度。

（4）将迭代后项目对应的最终资源值按照从大到小的顺序排列，排除目标用户已选择过的物品，排名前L的项目就形成了UTMT算法中目标用户的推荐列表。

算法伪代码为：

4  实验与结果分析

利用MomieLens_100K数据集对算法进行实验，该数据集包含943位用户对1 682部电影的100 000条评分数据，用户对电影的评分为1～5分制，每位用户至少对20部电影进行了评分。整个实验数据集须进一步划分为训练集和测试集。

利用准确率和MAP指标评价本文算法的有效性。

准确率^[7]是常用的评价推荐准确程度的指标。用户的平均准确率为：

其中，n为用户总数量，L为推荐列表的长度，d_i（L）为在推荐列表中有物品被准确预测的个数。准确率P值越高，推荐效果越好。

MAP为考虑了物品推荐排序的平均准确率。MAP值定义为：

其中，D（i）为测试集中物品的总数量，rc为第c个共同物品在推荐列表中的排序位置。在推荐结果中，推荐准确的物品排序越小，MAP值越大，推荐效果则越好。

图1和图2分别是用MATLAB实现UTMT算法，取α∈[0，1]，根据式（1）进行仿真实验，得出使得算法推荐准确率最高的参数α和最佳推荐个数L的折线图。

计算结果通过五次独立实验得到。由实验可知，当参数α=0.15、L=10时，推荐算法的准确率最高，性能最好。取这组参数，在MovieLens_100K数据集上，将提出的UTMT算法与热传导算法HC^[8]进行实验对比，结果如表2所示。

表2中每行的准确率和MAP值是5次独立实验结果的平均值。表2中最后一行表示UTMT（α=0.15）算法相对HC算法的性能提升幅度。与经典的热传导（HC）算法相比，本文提出的算法UTMT具有更好的推荐效果，P值和MAP值分别提升了9.349 9%和3.240 0%。

5  结  论

UTMT算法不仅可以抑制热门物品，提升冷门物品推荐度，解决用户个性化推荐问题，还考虑了可信用户的行为特征和评分特征，将用户作为共同邻居的节点，增加了推荐结果的可解释性。同时实验表明，本文提出算法的准确率相较于传统算法有较大的提升。

参考文献：

[1] ZHU J Q，LU L，MA C M. From Interest to Location：Neighbor-Based Friend Recommendation in Social Media [J].Journal of Computer Science and Technolog，2015（30）：1188-1200.

[2] ZHANG W，DU Y，SONG W. Followee Recommendation Based Formal Concept Analysis In Social Network [J].International journal of innovative computing，information & control：IJICIC，2015，11（4）：1155-1164.

[3] ZHOU T，REN J，MEDO M. Bipartite network projection and personal recommendation [J].Physical Review E，2007，76（4）：046115.

[4] NEWMAN M E. The structure of scientific collaboration networks [J].Proceedings of the National Academy of Sciences of the United States of America，2001，98（2）：404-409.

[5] ZHOU T，REN J，MEDO M，et al. How to project a bipartite network？ [J/OL].arXiv：0707.0540v2[physics.soc-ph].（2007-07-31）.https：//arxiv.org/abs/0707.0540v2.

[6] 郝治翰，陳阳，王蒲生.“马太效应”与科研网络中的择优依附 [J].自然辩证法研究，2019，35（11）：39-45.

[7] L? L Y，MEDO M，YEUNG C H，et al. Recommender systems [J].Physics Reports，2012，519（1）：1-49.

[8] ZHANG Y C，BLATTNER M，YU Y K. Heat conduction process on community networks as a recommendation model [J].Physical Review Letters，2007，99（15）：154301.

作者简介：迟露阳（1996—），女，蒙古族，内蒙古赤峰人，硕士研究生，研究方向：推荐系统、数据分析。

收稿日期：2021-01-10