协同过滤算法通过计算用户的兴趣相似性, 筛选兴趣最相近的用户为邻居为用户推荐商品, 是推荐系统研究的热点^[1,2]. 有学者将物质扩散和热传导理论^[3–5]应用于协同过滤推荐技术, 取得了很好的效果, 典型的是基于二部图的协同过滤推荐研究, 该算法令能量在“用户-项目”以及“项目-其他用户”间扩散, 扩散完成后即获取到准确的邻居用户, 预测评分更加准确, 已经成为协同过滤领域研究的一个新方向^[6], 不断有学者在此基础上研究新的改进措施来进一步提高推荐的准确度. 文献[7]提出了一种基于随机森林修正的加权二部图推荐算法, 首先建立评分权重矩阵, 再用二部图做能量分配, 获取到初始推荐结果, 最后采用随机森林对推荐结果进行再次修正, 提高了推荐的准确度; 文献[8]提出了一种利用差异路径权重控制能量传递的二部图算法, 该算法在第一阶段能量传递时采用用户相似性作为路径权重, 使与目标用户相似的用户节点获得更多的能量; 在第二阶段采用项目属性的相似性作为路径权重, 使与目标用户已购项目具有相似属性的项目获得更多的能量, 达到了提高推荐结果多样性的目标; 文献[9,10]综合考虑项目度、用户评分标准信息和时间动态因素, 对二部图上的用户-项目关联关系做了加权处理, 推荐列表的平均绝对偏差和均方根误差都有明显下降.

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

二部图是图论中的一种特殊的无向图, 图中顶点集合V被划分成V1和V2两部分, 且 ${{V}}1 \cap {{V}}2 = \varphi $ , 图中的每条边所关联的两个顶点都分别属于这两个顶点集^[11–13]. 二部图应用于协同过滤推荐研究时, 将用户 $U = \{ {u_1}, {u_2}, {u_3}, $ $ \cdots , {u_p}\} $ 和项目 ${{I}} = {\rm{\{ }}{{{i}}_{\rm{1}}},{{{i}}_{2}},{{{i}}_{3}},\cdots,{{{i}}_{{q}}}{\rm{\} }}$ 作为图中两个不相交的集合, 用户 ${{{u}}_w}$ 选择过项目 ${i_k}$ 则在用户和项目间连一条边 ${{{a}}_{wk}}$ ^[14]. 基于二部图的协同过滤推荐算法^[3] (BNCF)通过两次能量分配计算邻居用户, 假定每个用户有一单位的能量, 第一次分配时用户把自己的能量平均分配给与其有连边的项目; 第二次分配时每个项目把自己获得的能量平均分配回与其有连边的用户; 经过两次能量分配后, 用户能量被分散到与其有共同项目顶点连边的用户节点上, 用户获得的能量越多, 说明用户间兴趣越相似^[15], 用户 ${{{u}}_v}$ 从用户 ${u_w}$ 获得的能量用 $en{g_{wv}}$ 表示, 计算方法如式(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)

其中, $d({u_v})$ 代表用户 ${u_v}$ 选择过的项目数, 即二部图中 ${u_v}$ 顶点的度; $d({i_k})$ 代表项目 ${i_k}$ 被多少用户选择过, 即二部图中 ${i_k}$ 的度; ${{\rm{a}}_{wk}}$ 代表用户 ${u_w}$ 和项目 ${i_k}$ 间是否有连边, 若有, 则 ${{{a}}_{wk}} = 1$ ; 若没有, 则 ${{{a}}_{wk}} = 0$ . $en{g_{wv}}$ 越高表示用户 ${{{u}}_v}$ 和用户 ${u_w}$ 共同选择过的项目数越多, 兴趣越相似. 按照 $en{g_{wv}}$ 由高到低排列, 选取前M个用户作为邻居用户. 最后, 由邻居用户对当前用户进行推荐, 计算用户 ${{{u}}_w}$ 对项目 ${i_k}$ 的评分 ${r_{wk}}$ 的方法如式(2)所示.

${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, 当用户 ${{{u}}_w}$ 未评价过项目 ${{{i}}_k}$ 时, ${{{e}}_{wk}} = 0$ ; 当用户 ${{{u}}_w}$ 对项目 ${{{i}}_k}$ 评分大于等于3时, ${{{e}}_{wk}}= $ $ 1 $ ; 当用户 ${{{u}}_w}$ 对项目 ${{{i}}_k}$ 评分小于3时, ${{{e}}_{wk}} = \lambda $ , 其中 $\lambda $ 为可调因子, 用于调节低分对推荐结果的影响, 取值在 0 和 1 之间, 当 $\lambda $ 取值为0时, 算法变成忽略低分评价的算法; 当 $\lambda $ 取值为1时, 算法变成只考虑用户是否评价过项目的算法. 用户 ${{{u}}_v}$ 和用户 ${u_w}$ 相似性使用式(3)计算.

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

(3)

其中, 函数f表示对图中某一顶点有连边的权值进行求和, 即 ${{f}}({u_v}) = \displaystyle\sum\nolimits_{{{k}} = 1}^q {{e_{vk}}} $ ; ${{f}}({i_k}) = \displaystyle\sum\nolimits_{{{v}} = 1}^p {{e_{vk}}} $ .

计算用户 ${{{u}}_w}$ 对项目 ${i_k}$ 的评分 ${r_{wk}}$ 的方法如式(4).

${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 基于比例的加权二部图算法

基于比例的加权二部图算法考虑用户评分习惯问题, 部分用户可能习惯性地给所有项目高分, 而部分用户习惯性地给所有项目低分, 单纯地以某一个绝对分值来判定用户偏好不准确, 因此提出先对用户评分数据按照式(5)进行处理.

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

(5)

其中, $\overline {{{{r}}_{{{{u}}_{{w}}}}}} $ 代表用户 ${u_w}$ 的平均评分, ${{{t}}_{wk}}$ 即是用户 ${u_w}$ 和项目 ${{{i}}_k}$ 的连边的权值, 用户 ${{{u}}_v}$ 和用户 ${u_w}$ 相似性使用式(6)计算.

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

(6)

计算用户 ${{{u}}_w}$ 对项目 ${i_k}$ 的评分 ${r_{wk}}$ 的方法如式(7).

${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 评分数据处理

在本文的改进算法中, 为体现用户评分对用户喜欢或不喜欢某一个项目的判断, 需要对用户的评分用式(8)进行预处理.

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

(8)

其中, $\overline {{{{r}}_{{{{u}}_{{w}}}}}} $ 表示用户 ${u_w}$ 对所有项目的平均评分, ${{{t}}_{wk}}$ 可能为正值, 也可能是负值. 当 ${{{t}}_{wk}}$ 为正值时代表用户 ${u_w}$ 喜欢项目 ${{{i}}_k}$ , 且 ${{{t}}_{wk}}$ 值越大说明喜欢程度越高; 当 ${{{t}}_{wk}}$ 为负值时代表用户 ${u_w}$ 不喜欢项目 ${{{i}}_k}$ , 且 ${{{t}}_{wk}}$ 值越大说明不喜欢程度越高, 式(8)经简化后得到式(9), 计算得到的 ${{{t}}_{wk}}$ 作为连接用户 ${u_w}$ 和项目 ${{{i}}_k}$ 的边上的权重. 在沿权值为正值的边扩散的是用户“喜欢”的能量, 在沿权值为负值的边扩散的是用户“不喜欢”的能量.

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

(9)

计算用户 ${{{u}}_v}$ 和用户 ${u_w}$ 相似性的时候需要分别计算 ${{{u}}_v}$ 沿正值边获取的能量 ${{e}}n{g^ + }_{wv}$ 和 ${{{u}}_v}$ 沿负值边获取的能量 ${{e}}n{g^{\rm{ - }}}_{wv}$ , 计算公式如式(10)和式(11)所示.

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

(10)

函数 ${{{f}}^ + }$ 表示从某一顶点出发的所有边上权值为正值的权值加和, 即 ${{{f}}^ + }({u_v}) = \displaystyle\sum\nolimits_{{{k}} = 1}^q {{t_{vk}}} $ , 其中 ${t_{vk}}$ >0; ${{{f}}^ + }({i_k}) =$ $ \displaystyle\sum\nolimits_{{{v}} = 1}^p {{t_{vk}}}$ , 其中 ${t_{vk}}$ >0.

${\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)

函数 ${{{f}}^{\rm{ - }}}$ 表示从某一顶点出发的所有边上权值为负值的权值加和的绝对值, 即 ${{{f}}^{\rm{ - }}}({u_v}) = $ $ \displaystyle\sum\nolimits_{{{k}} = 1}^q {\left| {{t_{vk}}} \right|}$ , 其中 ${t_{vk}}$ <0; ${{{f}}^{\rm{ - }}}({i_k}) = \displaystyle\sum\nolimits_{{{v}} = 1}^p {\left| {{t_{vk}}} \right|} $ , 其中 ${t_{vk}}$ >0.

用户 ${{{u}}_v}$ 和用户 ${u_w}$ 相似性采用式(12)计算.

${{e}}n{g_{wv}} = \sqrt {{{\left( {{{e}}n{g^{\rm{ - }}}_{wv}} \right)}^2} + {{\left( {{{e}}n{g^ + }_{wv}} \right)}^2}} $

(12)

2.2 用户信任度

为进一步提高推荐准确度, 众多学者在推荐过程中引入用户信任度. 比较有代表性的是卢竹兵等人提出的基于信任网络的协同过滤推荐算法^[16], 算法认为用户的信任度具有传递性, 用户A信任用户B, 用户B信任用户C, 则认为用户A也信任用户C. 根据用户的信任关系结合用户评分构建邻居用户模型, 可以得到更加准确的推荐结果. 分析此类算法后发现, 学者还隐含地认为用户信任度具有全局性, 即如果AB间有信任关系, 则对用户A推荐所有领域的项目时都采用B做邻居用户, 这与实际情况不符, 现实情况是很难有一个用户对所有领域都熟悉, 用户A在选择不同领域的项目时更倾向于咨询具体领域内的可信用户. 因而本文将用户信任度的形式定义如表1所示.

若用户 ${u_{{w}}}$ 在领域 ${c_\chi }$ 下信任度 ${{{T}}_{w, \chi }}$ 比较高需满足两个条件, 一是用户 ${u_{{w}}}$ 在该领域内的评分数量比较多, 二是用户的评分比较准确.

(1) 评分数量权重

本文定义评分数量因子 ${\omega _{{\rm{w}}, \chi }}$ 来衡量用户 ${u_w}$ 在领域 $\chi $ 下的权重, 如式(13)所示.

${\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)

其中, ${n_{w, \chi }}$ 代表用户 ${u_w}$ 评价过并且属于领域 $\chi $ 的项目数量, H为常量, 通常取该领域下项目数量的一定比例(如领域下项目数量的80%), 若用户 ${u_w}$ 评价过领域 $\chi $ 的项目数达到H时, 认为用户 ${u_w}$ 比较可信, 否则, 不太可信, 评分数量因子等于用户 ${u_w}$ 评价过的项目数量与H的比值.

(2) 评分准确度权重

衡量用户 ${u_w}$ 对项目 ${{{i}}_k}$ 评分准确度权重 ${{{E}}_{w, k}}$ 采用式(14)计算.

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

(14)

其中, S为项目的评分范围, 若项目评分采用5分制, 则S = 5; $\overline {{r_{{{{i}}_k}}}} $ 代表所有用户对项目 ${{{i}}_k}$ 评分的平均值.

由评分数量因素 ${\omega _{{{w}}, \chi }}$ 和评分准确度因素 ${{{E}}_{w, k}}$ 确定的用户 ${u_w}$ 在领域 $\chi $ 内的信任度 ${{{T}}_{w, \chi }}$ 以式(15)计算.

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

(15)

其中, $\left| \chi \right|$ 代表分类 $\chi $ 内的项目数量, ${{{T}}_{w, \chi }}$ 的取值范围是[0, 1].

2.3 评分预测

综合以上用户相似性和用户信任度的因素, 计算用户 ${u_w}$ 对某一未评分项目 ${{{i}}_k}$ 的预测评分时用式(16)计算.

${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 实验设计

本文采用美国Minnesota大学的GroupLens 项目MovieLens和Eachmovie两个真实的电影评分数据集进行实验, 其中MovieLens数据集中包括943个用户对1682部电影的100 000个评分记录, 每个用户至少对20部电影进行了评分, 评分范围为1–5; Eachmovie数据集中有72 916个用户对1628部电影的2811 983个评分记录, 评分范围为0–1, 为使不同数据集的实验结果具有可比性, 将Eachmovie数据集中的用户评分进行线性处理, 使评分落在1–5之间. 随机选取每个数据集中的80%作为训练集, 构建协同过滤推荐模型, 剩余20%作为测试集, 检验推荐效果.

3.2 评估指标

由于改进算法着眼于提高推荐的准确度, 因此采用学者最常使用的平均绝对偏差(MAE)来评估算法的效果. MAE表示算法预测评分与用户实际评分之间的差距, 计算对单个用户推荐准确度的方法如式(17).

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

(17)

其中, N为测试集中某一用户 ${u_w}$ 评过分的项目数量; ${r_{wk}}$ 为算法预测用户 ${u_w}$ 对项目 ${{{i}}_k}$ 的评分; $r_{wk}^, $ 为用户 ${u_w}$ 对项目 ${{{i}}_k}$ 的实际评分. 计算测试集中所有用户的 $MA{E_w}$ 值后再取平均值即得到算法的平均绝对偏差MAE, 算法的MAE值越小, 说明推荐结果越准确.

3.3 实验结果分析

实验对传统二部图算法、基于参数化的加权二部图算法、基于比例的加权二部图算法以及本文改进算法进行了对比分析, 采用两种数据集时各算法的推荐准确度对比情况如图2和图3所示, 图中纵轴是不同算法的MAE值, 横轴是实验中设置的邻居用户数.

从图2纵向来看, BNCF算法在MovieLens数据集中预测评分结果偏差比较大, PB-BNCF算法和RB-BNCF算法MAE值明显低于BNCF算法, 本文提出的算法则在不同邻居用户数情况下均优于对比算法; 从横向来看, BNCF算法随着邻居用户数从5增加到40, 推荐准确度呈现不稳定的表现, PB-BNCF算法、RB-BNCF算法以及本文提出的算法在邻居用户数较少(5–10)时MAE值相对较高, 在邻居数为15–20时达到最佳的推荐效果, 在邻居数超过30时, MAE值趋向于稳定.

从图3可以看出, BNCF算法在Eachmovie数据集上预测评分结果偏差仍然比较大, 说明BNCF算法在基于评分的推荐系统上推荐效果不佳, 对路径进行加权处理后可以明显提高推荐的准确度; RB-BNCF在Eachmovie数据集上MAE值略有升高, 可能和Eachmovie数据集评分稀疏度比MovieLens数据集高有关; PB-BNCF算法在Eachmovie数据集上的MAE值远高于在MovieLens数据集上的结果, 可能原因是PB-BNCF算法对不同数据集的最佳参数 $\lambda $ 取值不同, 本实验为进行实验对比分析, 统一取 $\lambda $ 值为0.5, 这一参数更适合MovieLens数据集. 而本文提出的算法在Eachmovie数据集上依然最优.

对比各种算法在Eachmovie和MovieLens数据集的实验结果来看, 本文提出的算法在不同的数据集上MAE值均低于其它算法, 推荐效果准确且稳定.

4 总结和展望

为了提高协同过滤推荐的准确度, 本文提出了一种基于改进的加权二部图和用户信任度的协同过滤推荐系统. 算法充分挖掘了用户低分评价中包含的用户兴趣信息, 在二部图进行能量扩散过程中同时扩散“喜欢”和“不喜欢”的能量, 并结合用户在具体领域中的信任度对项目进行预测评分. 实验结果表明, 改进算法在两种数据集上均能取得更准确的推荐结果, 算法表现稳定. 由于算法充分挖掘了隐藏的用户的兴趣信息, 因而可以更进一步地解决协同过滤数据稀疏性的问题, 笔者将在接下来的工作中在此方面进行研究和探讨, 不断优化算法的推荐效果.