随着互联网的不断飞速发展，数据指数级的增长带来了信息过载等一系列问题，于是推荐系统由此诞生并得到飞速发展。如国外的亚马逊、ebay等，国内的京东、阿里巴巴等都在推荐系统上做出了各种尝试^[1–2]。其广泛应用于电子商务、音乐、视频及新闻等各种领域。目前主要的推荐算法有基于协同过滤的推荐、基于关联规则的推荐、基于内容的推荐、基于图的推荐及混合推荐等。其中协同过滤算法是最经典且最成功的推荐算法之一^[3–5]，该算法主要分为基于用户的协同过滤算法和基于项目的协同过算法。基于用户的协同过滤算法的主要思想为参照与目标用户相似的其他用户，计算相似度并找出最近邻居，最后根据最近邻居的评分预测出目标用户对目标项目的评分；基于项目的协同过滤算法则是从项目角度出发，找出与其最相似的项目集合，最后预测评分^[6–7]。传统的协同过滤算法的优点是无需考虑内容信息和一些复杂的概念，缺点是推荐精度不高，以及存在稀疏性、扩展性、冷启动等一些问题^[8–9]。

针对推荐精度不高的问题，研究人员提出了很多改进方法。文献[10]提出一种基于时间段划分的协同过滤算法，传统的协同过滤算法认为用户的兴趣是静态的，没有考虑用户兴趣的转变，且用户有长时间的兴趣和短时间的兴趣。对此，本文引入了时间因子，将用户评分历史划分为几个周期，分析在这些周期中用户兴趣的分布，并量化用户兴趣，通过设置时间窗口发现用户最近的兴趣。

文献[11]提出一种不确定近邻的协同过滤推荐算法，该算法自适应地选择目标用户的最近邻居作为推荐群，提高了推荐质量。文献[12]提出一种基于时间上下文的协同过滤算法，考虑到用户的兴趣会发生改变，故加入时间上下文，在不需要额外信息的前提下，进一步缓解稀疏性。除此之外，二部图算法也得到了广泛的应用^[13–14]，且与协同过滤相结合提高推荐精度。文献[15]提出一种结合二部图投影与排序的协同过滤，该算法将用户和项目看成节点，用户对项目的评分则可用边权表示，利用二部图投影和随机游走对节点进行排序，最终形成推荐。

上述方法虽然在一定程度上提高了推荐质量，但还是具有不足的地方。比如，在相似度计算时只依赖共同评分项目，但当共同评分项目个数较少时，计算出来的相似度可信度会非常低。另外，在预测评分时也均只考虑了正相关最近邻居，忽略了负相关最近邻居对预测评分的价值，若两个用户之间的负相关程度较高，说明这两个用户的评分呈现较高的相反趋势，可从另一个角度对评分进行预测。

基于此，为进一步提高推荐精度，提出一种基于正相关和负相关最近邻居的协同过滤算法（PNCF）。在相似度计算时，通过用户之间变异系数的差异反映出用户评分特点的接近程度，从而对相似度计算结果进行修正，弥补了只依赖共同评分项目计算相似度带来的不足；在邻居选取时根据一定的选取规则分别选取正相关最近邻居和负相关最近邻居，并在评分预测的同时考虑这两类不同的最近邻居，将基于正相关最近邻居和负相关最近关邻居的预测评分进行加权，作为最终的预测评分。利用GroupLens提供的标准数据集MovieLens^[16]进行算法验证，实验表明本文算法有效地提高了推荐的准确度和多样性。

1 传统的协同过滤算法 1.1 构建评分矩阵

协同过滤算法所需要的输入数据 $I = (U,P,{{R}})$ ，其中： $U = \{{u_1},{u_2},{u_3},\cdots,{u_n}\}$ 为用户id构成的集合， $\left| U \right| = n$ ； $P = \{{p_1},{p_2},{p_3},\cdots,{p_m}\}$ ， $P$ 为项目id构成的集合， $\left| P \right| = m$ ； ${ R}$ 为 $U$ 和 $P$ 构成的 $n \times m$ 的矩阵，若评分为显式的，则 ${ R}$ 存储的为评分值的大小， ${R_{{ij}}}$ 表示 $i$ 用户对 $j$ 项目的评分值，其值的大小代表评分尺度^[17]；若评分为隐式的，则 ${ R}$ 取值为0或1，0表示用户没有对项目产生过行为（购买、点击等），1表示产生过行为。

1.2 相似度计算

相似度的计算是协同过滤算法中非常重要的一部分，利用第1.1节中构建的用户–项目评分矩阵可计算用户之间的相似度，常用的计算相似度的方法有Pearson相关系数和修正的余弦相似度。Pearson相关系数^[18]的公式为：

$sim(i,j) = \frac{{\displaystyle\sum\limits_{p \in {P_{ij}}} {({r_{ip}} - {\overline {r}_i} )({r_{jp}} - {\overline {r}_{j}} )} }}{{\sqrt {\displaystyle\sum\limits_{p \in {P_{ij}}} {{{({r_{ip}} - {\overline {r}_i} )}^2}} } \sqrt {\displaystyle\sum\limits_{p \in {P_{ij}}} {{{({r_{jp}} - {\overline {r}_j} )}^2}} } }}$

(1)

式中， $i$ 、 $j$ 为用户， ${P_{{ij}}}$ 为 $i$ 用户和 $j$ 用户共同评分的项目集合， ${r_{{ip}}}$ 和 ${r_{{jp}}}$ 分别为 $i$ 用户对 $p$ 项目的评分和 $j$ 用户对 $p$ 项目的评分， ${\overline{r}_{i}} $ 和 ${\overline {r}_{j}} $ 分别为 $i$ 用户对项目的平均评分和 $j$ 用户对项目的评分。Pearson相关系数取值为 $[ - 1, 1]$ 。

修正的余弦相似度^[19]公式为：

$sim(i,j) = \frac{{\displaystyle\sum\limits_{p \in {P_{ij}}} {({r_{ip}} - {\overline {r}_i} )({r_{jp}} - {\overline {r}_j} )} }}{{\sqrt {\displaystyle\sum\limits_{p \in {P_i}} {{{({r_{ip}} - {\overline {r}_i} )}^2}} } \sqrt {\displaystyle\sum\limits_{p \in {P_j}} {{{({r_{jp}} - {\overline {r}_j} )}^2}} } }}$

(2)

式中， $i$ 、 $j$ 为用户， ${P_{{ij}}}$ 为 $i$ 、 $j$ 共同评分的项目集合， ${P_{i}}$ 和 ${P_{j}}$ 分别为 $i$ 用户已评分的项目集合和 $j$ 用户已评分的项目集合， ${r_{{ip}}}$ 和 ${r_{{jp}}}$ 分别为 $i$ 用户对 $p$ 项目的评分和 $j$ 用户对 $p$ 项目的评分， ${\overline {r}_i} $ 和 ${\overline {r}_j} $ 分别为 $i$ 用户和 $j$ 用户对项目的平均评分。修正的余弦相似度取值也为 $[ - 1, 1]$ 。

1.3 评分预测

计算出目标用户与其他用户的相似度后，按相似度值从大到小进行排序得到邻居集合 $Q$ ，根据相似度阈值或最近邻居个数选取集合 $Q$ 中的一部分邻居作为目标用户的最近邻居集合 $N$ ，其中 $N = \{{n_1},{n_2},$ ${n_3},\cdots,{n_k}\}$ 。基于得到的邻居集合对目标用户未评分的项目进行评分预测，按照预测的评分大小进行排序，并取top $N$ 推荐给用户。其中评分预测公式^[20]为：

$pred(i,p) = {\overline {r}_i} + \frac{{\displaystyle\sum\limits_{j \in N} {sim(i,j) \cdot ({r_{jp}} - {\overline r}_j )} }}{{\displaystyle\sum\limits_{j \in N} {sim(i,j)} }}$

(3)

式中， $pred(i,p)$ 为预测用户 $i$ 对 $p$ 项目的预测评分， ${\overline r}_{i} $ 和 ${\overline r}_{j} $ 分别为用户 $i$ 和 $j$ 的平均评分， $N$ 为用户 $i$ 的最近邻居集合。

2 基于正相关和负相关最近邻居的协同过滤算法 2.1 相似度计算

引入变异系数（coefficient of variation）对相似度的计算结果进行修正，变异系数用以衡量数据的离散程度，其值越大表明离散程度越大；反之，离散程度越小。

对于一个用户，通过对项目的评分计算变异系数的值。变异系数的公式^[21]：

$C{V_i} = \frac{{\sqrt {\displaystyle\frac{1}{{\left| {{p_i}} \right|}}{{\displaystyle\sum\limits_{p \in {P_i}} {({r_{ip}} - {\overline {r}_i} )} }^2}} }}{{\overline r_i} }$

(4)

式中， $C{V_{i}}$ 为用户 $i$ 的变异系数， ${P_{i}}$ 为用户 $i$ 的评分项目集合， ${\overline {r}_{i}} $ 为用户 $i$ 对项目的平均评分， ${r_{{ip}}}$ 为用户 $i$ 对项目 $p$ 的评分。

计算出所有用户的变异系数之后，对于任意两个用户计算相似度，可利用其变异系数的差值对相似度进行修正，差值越小表明这两个用户评分的离散程度越接近，由此引入平衡因子 $\lambda $ ，计算公式：

$\lambda (i,j) = 1 - \left| {C{V_i} - C{V_j}} \right|$

(5)

式中，当用户 $i$ 和 $j$ 的变异系数差值的绝对值越小， $\lambda (i,j)$ 值越大；反之越小。

最后将平衡因子 $\lambda $ 加入传统的相似度计算方法，得到新的相似度计算公式 $simCV$ ：

$simCV(i,j) = \lambda (i,j) \cdot sim(i,j)$

(6)

式中， $sim(i,j)$ 为传统的相似度计算方法，如第1.2节中提到的Pearson相关系数和修正的余弦相似度，实验中采用Pearson相关系数。

改进后的用户相似度计算流程见图1。

2.2 邻居选取

传统的协同过滤算法在选取最近邻居时往往只考虑正相关最近邻居，即相似度为正的情况。由于Pearson相关系数和修正的余弦相似度取值为 $[ - 1,1]$ ，其中，1代表强正相关，–1代表强负相关。若两个用户之间的相似度取值越接近1，表示两个用户相似性越大；若两个用户之间的相似度取值越接近–1表示两个用户的差异性越大，其对项目的评分喜好也越相反。据此可发现，正相关最近邻居和负相关最近邻居都可为预测评分提供参考价值。因此，在考虑正相关最近邻居的同时考虑负相关最近邻居，对基于用户的协同过滤算法进行改进，提出基于正相关和负相关最近邻居的协同过滤推荐算法。首先，给出基于正相关最近邻居和负相关最近邻居的邻居选取算法，如算法1所示；对于正相关最近邻居的选取，给定一个数值，使得从正相关邻居中选取的正相关最近邻居个数等于给定的数值。其次，对于负相关最近邻居的选取，一般情况下，认为只有具有较强负相关性的最近邻居才能从认知的相反角度，提供推荐的有用信息。为避免选取负相关性不强的最近邻居影响推荐的准确度，给定负相关最近邻居选取阈值 $\beta $ ，只有负相关性满足 $\beta $ 的负相关邻居才会被选择为负相关最近邻居。通常 $\beta \in [0,1]$ ，其合理取值将在第3.3节中进一步讨论。

算法1 基于正相关和负相关最近邻居的邻居选取算法。

输入：用户–项目评分矩阵 ${ R}$ 、需要选取的正相关最近邻居个数 $s$ 、阈值 $\beta $

输出：正相关最近邻居列表 $Pos$ 和负相关最近邻居列表 $Neg$

Step 1 根据用户–项目评分矩阵 ${ R}$ 计算出目标用户 $a$ 与其他用户 $x$ 的相似度 $simCV(a,x)$ 。

Step 2 将Step 1中 $simCV(a,x) \ge 0$ 的邻居放入正相关邻居列表 $P$ 中， $simCV(a,x) < 0$ 的邻居放入负相关邻居列表 $N$ 中；对 $P$ 中的元素按相似度从大到小排序，对 $N$ 中的元素按相似度从小到大排序。

Step 3 对于给定需要选取的正相关最近邻居个数 $s$ ，取 $P$ 列表中的前 $s$ 个正相关邻居加入正相关最近邻居 $Pos$ 列表中；同时遍历列表 $N$ 中的负相关邻居，若目标用户的相似度绝对值大于等于给定的 $\beta $ 参数且 $Neg$ 列表个数小于等于 $s$ ，则加入负相关最近邻居 $Neg$ 列表中。

Step 4 输出 $Pos$ 列表和 $Neg$ 列表。

基于正相关和负相关最近邻居的邻居选取算法流程如图2所示。

2.3 预测评分

基于选取的正相关最近邻居和负相关最近邻居分别进行预测评分。最后，将基于正相关最近邻居和负相关最近邻居的预测评分进行加权，作为最终的预测评分。对于第2.2节得到的 $Pos$ 和 $Neg$ 列表， $Pos$ 列表中的元素全部为正相关最近邻居，相似度为正，且值越大，表明对同一物品的评分越接近； $Neg$ 列表中的元素全为负相关最近邻居，相似度为负，且值越小，表明对同一物品的评分差异越大。

对于 $Pos$ 列表中的正相关最近邻居，采用的预测评分公式：

$pre{d_{{Pos}}}(i,p) = {\overline {r}_i} + \frac{{\displaystyle\sum\limits_{j \in Pos} {simCV(i,j) \cdot ({r_{jp}} - {\overline {r}_j} )} }}{{\displaystyle\sum\limits_{j \in Pos} {simCV(i,j)} }}$

(7)

式中， $pre{d_{Pos}}(i,p)$ 为用户 $i$ 对项目 $p$ 的预测评分， ${\overline {r}_{i}} $ 、 ${\overline {r}_{j}} $ 分别为用户 $i$ 和 $j$ 的平均评分， ${r_{jp}}$ 为用户 $j$ 对项目 $p$ 的评分， $Pos$ 为正相关最近邻居集合， $sim(i,j)$ 为用户 $i$ 和 $j$ 的相似度。

对于负相关的最近邻居，由于其与目标用户的评分呈相反趋势，所以定义如下的预测评分：

$pre{d_{Neg}}(i,p) = {\overline {r}_i} - \frac{{\displaystyle\sum\limits_{j \in Neg} {simCV(i,j) \cdot ({r_{jp}} - {\overline {r}_j} )} }}{{\displaystyle\sum\limits_{j \in Neg} {simCV(i,j)} }}$

(8)

式中， $pre{d_{Neg}}(i,p)$ 为用户 $i$ 对项目 $p$ 的预测评分， ${\overline r}_i $ 、 ${\overline r}_j $ 分别为用户 $i$ 和 $j$ 的平均评分， ${r_{jp}}$ 为用户 $j$ 对项目 $p$ 的评分， $Neg$ 为负相关最近邻居集合， $sim(i,j)$ 为用户 $i$ 和 $j$ 的相似度。

最后设置权重参数 $\alpha $ ，将正、负相关最近邻居得到的预测评分 $pre{d_{Pos}}$ 和 $pre{d_{Neg}}$ 进行加权计算，作为最终的预测评分。最终的预测评分计算公式为：

$pred(i,p) = \alpha \cdot pre{d_{Pos}}(i,p) + (1 - \alpha ) \cdot pre{d_{Neg}}(i,p)$

(9)

式中，权重参数 $\alpha \in [0,1]$ 。

对于 $\alpha $ 的计算，提出一种根据每个用户正、负相关最近邻居个数的比例动态计算权值 $\alpha $ 的方法：

$\alpha = \frac{{\left| {Pos} \right|}}{{\left| {Pos} \right| + \left| {Neg} \right|}}$

(10)

式中， $Pos$ 为当前目标用户的正相关最近邻居集合， $Neg$ 为当前目标用户的负相关最近邻居集合。

评分预测流程如图3所示。

3 实验及结果分析

通过实验比较本文基于正相关和负相关邻居的协同过滤算法（PNCF）、传统的基于用户的协同过滤算法（CF）、基于优化用户相似度的改进协同过滤推荐算法（ICFOS）^[22]的推荐精度。并通过实验给出通常情况下阈值 $\beta $ 的合理取值范围。

3.1 数据集

实验采用的MovieLens 100 k数据集是GroupLens小组从MovieLens网站（http://movielens.org）不同时期收集并整理的评分数据集合，由943名用户对1 682部电影的100 000个评分构成，评分值大小为1～5，评分值越大表明用户对电影的喜爱程度越大，且每个用户至少有20个评分。

3.2 评价标准

采用3种评价标准，分别为均方根误差（root mean squared error，RMSE）、平均绝对偏差（mean absolute error，MAE）^[23]及多样性（diversification）^[24]。MAE和RMSE都是利用预测评分与实际评分的偏差判断预测评分的准确性，其值越大，表明偏差越大，推荐精度越差；反之，表明推荐精度越好，预测越准确。多样性用以衡量用户推荐列表的多样化程度，其值越大，表示多样性越高。

$MAE$ 的定义公式：

${MAE} = \frac{{\displaystyle\sum\limits_{p \in {T_i}} {\left| {{R_{i,p}} - {P_{i,p}}} \right|} }}{{\left| {{T_i}} \right|}}$

(11)

$RMSE$ 的定义公式：

${RMSE} = \sqrt {\frac{{\displaystyle\sum\limits_{p \in {T_i}} {{{({R_{i,p}} - {P_{i,p}})}^2}} }}{{\left| {{T_i}} \right|}}} $

(12)

多样性的定义公式：

${Diversification = }\frac{{\displaystyle2\sum\limits_{i \ne j} {(1 - \frac{{\left| {{L_i} \cap {L_j}} \right|}}{{\left| {{L_i}} \right|}})} }}{{n(n - 1)}}$

(13)

式中， ${R_{i,p}}$ 为用户 $i$ 对项目 $p$ 的实际评分， ${P_{i,p}}$ 为用户 $i$ 对项目 $p$ 的预测评分， ${T_i}$ 为测试集中用户 $i$ 评分的项目集合， ${L_i}$ 和 ${L_j}$ 分别为 $i$ 和 $j$ 用户的推荐列表。

3.3 阈值 $\beta $ 取值及实验对比

由于基于正相关和负相关最近邻居的改进协同过滤推荐算法在选取负相关最近邻居时需要设置阈值 $\beta $ ，阈值 $\beta $ 的不同取值直接影响推荐的准确度。为给出 $\beta $ 的合理取值，以0.1为步长，设置 $\beta $ 取值为0、0.1、0.2、 $\cdots$ 、0.9、1；设置正相关最近邻居个数以10为间隔选取，分别取10、20、 $\cdots$ 、50。然后运行改进的协同过滤算法，比较对于不同的正相关最近邻居个数，当 $\beta $ 取不同值时的 $MAE$ ，以此对 $\beta $ 参数进行训练，给出 $\beta $ 的合理取值范围，结果如图4所示。

由图4可以看出，当 $\beta $ 取值为0.8时， $MAE$ 值较低，推荐效果较好。故在接下来的实验中，设置阈值 $\beta $ 取值为0.8。

比较本文基于正相关和负相关最近邻居的改进协同过滤算法（PNCF）、传统的基于用户的协同过滤算法（CF）、基于优化用户相似度的改进协同过滤推荐算法（ICFOS）^[22]的 $MAE$ 、 $RMSE$ 及多样性值。在本文算法中，设置阈值 $\beta $ 为0.8，正相关最近邻居的个数从10到100，以步长10递增变化。

$MAE$ 值、 $RMSE$ 值的对比实验结果分别如图5、6所示。

由图5可以看出，本文算法的 $MAE$ 值，在所有给定的正相关最近邻居个数下，均低于CF算法；在大多数情况下均低于ICFOS算法。由图6可以看出，本文算法的 $RMSE$ 值，在所有给定的正相关最近邻居个数下，均低于CF算法和ICFOS算法。因此PNCF算法具有更高的推荐准确率。

多样性值的对比结果如图7所示。由图7可以看出，当正相关最近邻居个数分别取10、20、50时，本文算法在所有给定的推荐长度 $d$ 下多样性的值均高于CF算法和ICFOS算法。因此，本文算法在提高推荐准确率的同时也提高了推荐的多样性，给用户更加个性化的推荐。

4 结　论

针对传统协同过滤算法推荐精度不高的问题，提出基于正相关和负相关最近邻居的协同过滤算法。算法对相似度的计算过程进行了修正，综合考虑正相关最近邻居和负相关最近邻居，基于选取的正相关最近邻居和负相关最近邻居分别进行预测评分，然后将两次结果进行加权计算，作为最终的预测评分。实验结果表明本文算法在有效提高推荐准确度的同时，使推荐更加多样化。但本文算法还有进一步改进的空间，由于正相关最近邻居及负相关最近邻居的选取需要相似度值介于 $[ - 1,1]$ ，虽然常用的Pearson相关系数及修正的余弦相似度的值都满足该范围要求，但还有一部分相似度计算方法得到的值介于 $[0,1]$ ，这样就无法选取负相关最近邻居。针对这个问题，可考虑利用相关函数将 $[0,1]$ 的值映射到 $[ - 1,1]$ 。下一步研究工作就是利用相关信息构建映射函数，从而解决部分相似度计算方法得到的结果不在[–1,1]的问题，确保负相关最近邻居的选取。