﻿ 基于改进加权二部图和用户信任度的协同过滤推荐算法
 计算机系统应用  2019, Vol. 28 Issue (5): 125-130 PDF

1. 重庆医药高等专科学校 医学技术学院, 重庆 401331;
2. 重庆农村商业银行 科技信息部, 重庆 400023

Collaborative Filtering Recommendation System Based on Improved Bipartite Graph and User Reliability
DENG Xiao-Yan1, ZHANG Xiao-Bin2
1. Medical Technology Department, Chongqing Medical and Pharmaceutical College, Chongqing 401331, China;
2. Science and Technology Information Department, Chongqing Rural Commercial Bank, Chongqing 400023, China
Abstract: The application of bipartite graph theory in collaborative filtering recommendation based on substance diffusion theory of complex networks has attracted more and more attention from scholars. Existing algorithms mainly consider the positive rating when calculating neighbor users, ignoring the negative rating of users. In order to improve the accuracy of recommendation algorithm, a collaborative filtering recommendation algorithm based on improved bipartite graph and user reliability is proposed. The algorithm quantifies both positive ratings and negative ratings into the weight of the path, which controls the user’s energy distribution, and takes users’ reliability into account when predicting the rating, therefore, the accuracy of recommendation result is significantly improved. A series of comparative experiments are carried out on MovieLens and Eachmove datasets. The experimental results show that the improved algorithm has lower mean absolute error.
Key words: collaborative filtering     bipartite graph     reliability     mean absolute error

1 基于加权二部图的协同过滤推荐算法

 ${\rm{e}}n{g_{wv}} = \dfrac{1}{{d({u_v})}}\sum\limits_{k = 1}^q {\dfrac{{{a_{wk}}{a_{vk}}}}{{d({i_k})}}}$ (1)

 ${r_{wk}} = \frac{{\displaystyle\sum\limits_{v = 1, v \ne w}^p {en{g_{wv}}{a_{vk}}} }}{{\displaystyle\sum\limits_{v = 1, v \ne w}^p {en{g_{wv}}} }}$ (2)

${r_{wk}}$ 值由高到低排列, 取前N项作为对用户的最终推荐.

BNCF算法在建立用户-项目模型时仅考虑用户是否选择过项目, 用户选择过某一个项目则说明用户对该项目有偏好. 这种假设具有很大的局限性, 仅适用于粗略的用户偏好统计, 在基于用户评分的体系中, 用户偏好划分更加精细, BNCF算法的推荐结果就不再准确. 例如在一个5分等级的评价系统中, 用户对某一个项目给出5分的评价说明用户喜欢该项目, 若用户对某一个项目给出2分的评价, 则不能再认为用户喜欢该项目. 为避免低分评价对判断用户偏好的影响, 部分学者提出忽略低分评价、只考虑高分评价的算法, 这种算法更加符合用户偏好的实际, 能取得更加准确的评分预测结果. 更进一步地, 部分学者认为低分评价中也具有参考意义, 不应该直接丢弃, 提出基于加权二部图的协同过滤推荐算法, 其中典型的是基于参数化的加权二部图算法(PB-BNCF)和基于比例的加权二部图算法(RB-BNCF).

1.1 基于参数化的加权二部图算法

 ${{e}}n{g_{wv}} = \frac{1}{{{{f}}({u_v})}}\sum\limits_{k = 1}^q {\frac{{{{{e}}_{wk}}{{{e}}_{vk}}}}{{f({i_k})}}}$ (3)

 ${r_{wk}} = \frac{{\displaystyle\sum\limits_{v = 1, v \ne w}^p {en{g_{wv}} \cdot {{\rm{e}}_{vk}}} }}{{\displaystyle\sum\limits_{v = 1, v \ne w}^p {en{g_{wv}}} }}$ (4)

PB-BNCF算法使用参数 $\lambda$ 作为调节因子, 控制低分评价对用户偏好的影响, 起到了提高推荐准确度的效果, $\lambda$ 取值大小与数据集关系较大, 需要通过大量数据分析取得适合具体数据集的最佳 $\lambda$ 值.

1.2 基于比例的加权二部图算法

 ${{{t}}_{wk}} = \dfrac{{{r_{wk}}}}{{\overline {{{{r}}_{{{{u}}_{{w}}}}}} }}$ (5)

 ${{e}}n{g_{wv}} = \frac{1}{{{{f}}({u_v})}}\sum\limits_{k = 1}^q {\frac{{{{{t}}_{wk}}{{{t}}_{vk}}}}{{f({i_k})}}}$ (6)

 ${r_{wk}} = \frac{{\displaystyle\sum\limits_{v = 1, v \ne w}^p {en{g_{wv}} \cdot {{{r}}_{vk}}} }}{{\displaystyle\sum\limits_{v = 1, v \ne w}^p {en{g_{wv}}} }}$ (7)

RB-BNCF算法通过数据预处理消除了用户评分习惯对分析用户偏好的影响, 并且不需要输入控制参数, 对不同数据集都有较高的推荐准确度.

2 基于改进加权二部图和用户信任度的协同过滤推荐算法

PB-BNCF算法和RB-BNCF算法根据用户对项目的评分为用户-项目的连边赋予一定的权重, 当边上权重较小时, 通过这条边传递的用户能量就较少, 达到弱化低分评价对判断用户偏好的影响的目的. 这两种算法的共同点将用户共同喜欢的项目作为衡量是否有共同的兴趣偏好的量化标准, 对于用户不喜欢的项目采取的是忽略或弱化影响的处理方式. 但是, 不难想象, 两个用户如果共同不喜欢的项目较多, 也能说明两个用户兴趣偏好相似, 用户的低分评价也蕴含着用户偏好信息, 需要进行挖掘和分析.

2.1 评分数据处理

 ${{{t}}_{wk}} = \frac{{{r_{wk}}{\rm{ - }}\overline {{{{r}}_{{{{u}}_{{w}}}}}} }}{{\overline {{{{r}}_{{{{u}}_{{w}}}}}} }}$ (8)

 ${{\rm{t}}_{wk}} = \dfrac{{{r_{wk}}}}{{\overline {{{\rm{r}}_{{{\rm{u}}_{\rm{w}}}}}} }}{\rm{ - }}1$ (9)

 ${{e}}n{g^ + }_{wv} = \frac{1}{{{{{f}}^ + }({u_v})}}\sum\limits_{k = 1}^q {\frac{{{{{t}}_{wk}}{{{t}}_{vk}}}}{{{f^ + }({i_k})}}}$ (10)

 ${\rm{e}}n{g^{\rm{ - }}}_{wv} = \frac{1}{{{{\rm{f}}^{\rm{ - }}}({u_v})}}\displaystyle\sum\limits_{k = 1}^q {\frac{{\left| {{{\rm{t}}_{wk}}{{\rm{t}}_{vk}}} \right|}}{{{f^{\rm{ - }}}({i_k})}}}$ (11)

 ${{e}}n{g_{wv}} = \sqrt {{{\left( {{{e}}n{g^{\rm{ - }}}_{wv}} \right)}^2} + {{\left( {{{e}}n{g^ + }_{wv}} \right)}^2}}$ (12)
2.2 用户信任度

(1) 评分数量权重

 ${\omega _{{{w}}, \chi }} = \left\{ {\begin{array}{*{20}{c}} 1, \\ {{n_{w, \chi }}/H}, \end{array}} \right.\begin{array}{*{20}{c}} {} \\ {} \end{array}\begin{array}{*{20}{c}} {{n_{w, \chi }} \geqslant H} \\ {{n_{w, \chi }} < H} \end{array}$ (13)

(2) 评分准确度权重

 ${{{E}}_{w, k}} = 1 - \frac{{\left| {{r_{wk}} - \overline {{r_{{{{i}}_k}}}} } \right|}}{S}$ (14)

 ${{{T}}_{w, \chi }} = {\omega _{{{w}}, \chi }} \times \frac{{\displaystyle\sum\limits_{k \in \chi } {{E_{w, k}}} }}{{\left| \chi \right|}}$ (15)

2.3 评分预测

 ${r_{wk}} = \frac{{\displaystyle\sum\limits_{v = 1, v \ne w, {{k}} \in \chi }^p {en{g_{wv}} \cdot {{{T}}_{w, \chi }} \cdot {{{r}}_{vk}}} }}{{\displaystyle\sum\limits_{v = 1, v \ne w}^p {en{g_{wv}}} }}$ (16)
2.4 推荐流程

 图 1 本文算法推荐流程

3 实验分析 3.1 实验设计

3.2 评估指标

 $MA{E_w} = \frac{{\displaystyle\sum\nolimits_{k = 1}^N {\left| {{r_{wk}} - r_{wk}^, } \right|} }}{N}$ (17)

3.3 实验结果分析

 图 2 采用MovieLens数据集实验结果

 图 3 采用Eachmovie数据集实验结果

4 总结和展望

 [1] 李龙生, 艾均, 苏湛, 等. 结合用户行为和物品标签的协同过滤推荐算法. 计算机应用与软件, 2018, 35(6): 248-253. DOI:10.3969/j.issn.1000-386x.2018.06.045 [2] 赵宇峰, 李新卫. 基于歌曲标签聚类的协同过滤推荐算法的研究. 计算机应用与软件, 2018, 35(6): 259-262. DOI:10.3969/j.issn.1000-386x.2018.06.047 [3] Zhou T, Ren J, Medo M, et al. Bipartite network projection and personal recommendation. Physical Review E, 2007, 76: 046115. DOI:10.1103/PhysRevE.76.046115 [4] Liu JG, Wang BH, Guo Q. Improved collaborative filtering algorithm via information transformation. International Journal of Modern Physics C, 2009, 20(2): 285-293. DOI:10.1142/S0129183109013613 [5] Zhang YC, Blattner M, Yu YK. Heat conduction process on community networks as a recommendation model. Physical Review Letters, 2007, 99(15): 154301. DOI:10.1103/PhysRevLett.99.154301 [6] 刘朋. 混合个性化推荐方法研究[硕士学位论文]. 北京: 北方工业大学, 2018. [7] 李玲. 基于二部图的个性化推荐系统研究[硕士学位论文]. 北京: 北方工业大学, 2018. [8] 高长元, 段文彬, 张树臣. 基于差异路径权重的二部图网络推荐算法. 计算机应用研究, 2019(3): 1-6. [9] 陈诚. 基于二部图的推荐算法的研究与应用[硕士学位论文]. 北京: 北京邮电大学, 2016. [10] 王茜, 段双艳. 一种改进的基于二部图网络结构的推荐算法. 计算机应用研究, 2013, 30(3): 771-774. DOI:10.3969/j.issn.1001-3695.2013.03.033 [11] 曹易, 张宁. 二部图在用户-网站中的实证研究. 计算机系统应用, 2012, 21(6): 132-135. DOI:10.3969/j.issn.1003-3254.2012.06.028 [12] 唐敏, 关健, 邓国强, 等. 一种求解二部图最大匹配问题新算法及其应用. 计算机系统应用, 2012, 21(3): 72-75, 28. DOI:10.3969/j.issn.1003-3254.2012.03.016 [13] 黄波, 严宣辉, 林建辉. 基于有向图分割的推荐算法. 计算机系统应用, 2015, 24(12): 196-203. DOI:10.3969/j.issn.1003-3254.2015.12.031 [14] 任琛. 融入生活体验的二部图推荐算法[硕士学位论文]. 西安: 西安电子科技大学, 2017. [15] 黄熠姿, 杨金鑫, 孙维. 基于改进二部图与专家信任的混合推荐算法. 价值工程, 2017, 36(19): 160-164. [16] 卢竹兵, 唐雁. 一种基于信任网络的协同过滤推荐策略. 西南师范大学学报(自然科学版), 2008, 33(2): 123-126.