在这样一个信息爆炸的时代，Web上的信息无时无刻不在飞速增长，用户在面对大量的信息时很难快速、准确地找到理想的信息. 通常，只有少部分的商品被众人选择，大量的商品不会被注意. 在很多情况下，用户浏览网页或查找信息时，其中的大部分内容对用户来讲都是无用且不必要的，用户必须花费很多精力仔细浏览来获取所需信息. 推荐系统的诞生不但可以使用户更快、更准确地找到自己真正喜欢或有用的信息，给用户带来了良好的体验，而且为商人带来极大的便利，给他们的信息与商品带来了推广，因此在现实应用场景中，推荐系统的表现十分优秀. 在众多推荐技术中，由Goldberg等提出的协同过滤推荐算法（collaborative filtering recommendation algorithm，CF算法）精度高，应用范围广，成果显著^[1].

Slope One推荐算法^[2]是Daniel Lemire和Anna Maclachlan在2005年提出的基于项目的协同过滤算法，它被设计成一个简单易懂的形式，使其易于实现和维护. 许多实验证明，Slope One推荐算法在保证推荐精度的同时具有简洁、高效等特性，已被应用在诸多推荐系统中^[3].

由于传统的协同过滤技术对于稀疏的评分矩阵处理效果不好^[4]，许多国内外的专家都针对CF算法中评分矩阵的稀疏性问题提出改进. 其中矩阵分解技术是较常用的方案之一，非负矩阵分解（NMF）具有容易解释、算法相对简单等优点，在解决稀疏性问题上有良好的表现.

研究表明，Slope One 算法在比较稠密的数据集下，推荐效果较好，但在比较稀疏的数据集下推荐效果很差^[5]，基于矩阵分解的方法在抗稀疏性方面很有效，因此将非负矩阵分解引入到Slope One算法中，提出基于非负矩阵分解的Slope One算法.

Slope One算法的基本原理是一个非常简洁的一元方程 $w = f\left( v \right) + b$. 已知一组训练点 $\left( {{v_i},{w_i}} \right)_{i = 1}^n$，通过该线性模型最小化预测误差的平方和^[6]，可得

(1) $b = \frac{{\mathop \sum \limits_i {w_i} - {v_i}}}{n}.$

式中：w_i和v_i分别为不同用户对同一项目的评分. 通过式（1）计算出 $b$的取值后，对于新的数据点v_new，根据公式 ${w_{{\rm{new}}}} = b + {v_{{\rm{new}}}}$计算新数据点的预测值. 直观上可以将式（1）中求 $b$的偏移方法理解为 ${w_i}$与 ${v_i}$差值的平均值^[7]. 如图1所示，有2个用户A、B，其中用户A对项目i与项目j完成过评价，用户B对项目i完成了评价，预测用户B对项目j的评分.

根据Slope One算法，计算用户B对项目j的评分为：2+（1.5−1）=2.5.

定义项目i相对于项目j的平均偏差计算公式：

(2) ${\rm{de{v}}}_{j,i} = \mathop \sum \limits_{u \in {S_{j,i\left( x \right)}}} \frac{{{u_j} - {u_i}}}{{{\rm{card}}\left( {{S_{j,i}}\left( x \right)} \right)}}.$

式中：S_j，i为同时对项目i与项目j进行过评分的用户集合，u_i和u_j分别为用户对项目i和项目j的评分，card为集合中的元素数量.

在以上定义的基础上，能够使用dev_j，i+u_i来计算用户u对项目j的预测值. 将全部这种可能的预测值取平均，可得

(3) $p{\left( u \right)_j} = \frac{1}{{{\rm{card}}\left( {{R_j}} \right)}}\mathop \sum \limits_{i \in {R_j}} \left( {{\rm{de{v}}}_{j,i} + {u_i}} \right).$

式中：R_j表示用户u进行过评分且满足条件（i≠j且S_j，i非空）的所有项目集合.

对于足够稠密的数据集，可以使用近似：

$\bar u = \mathop \sum \limits_{i \in {S{\left( u \right)}}} \frac{{{u_i}}}{{{\rm{card}}\left( {S\left( u \right)} \right)}} \approx \mathop \sum \limits_{i \in {R_j}} \frac{{{u_i}}}{{{\rm{card}}\left( {{R_j}} \right)}}.$

式中：S（u）为用户u评过分的所有项目集合.

将式（3）简化为

(4) ${p^{S1}}{\left( u \right)_j} = \bar u + \frac{1}{{{\rm{card}}\left( {{R_j}} \right)}}\mathop \sum \limits_{i \in {R_j}} \left( {{\rm{de{v}}}_{j,i}} \right).$

Slope One算法在计算项目i相对于项目j的平均偏差dev_j，i的过程中，未考虑不同用户间的可信度差异^[8]. 若有1 000名用户都对项目k与项目j进行过评价，但仅有10名用户都对项目i与项目j完成过评价，计算得到的dev_j，k比dev_j，i更具有说服力.

其中的一个修正是对最终的平均使用加权，即Weighted Slope One^[9]，预测公式如下：

(5) ${p^{{\rm{wS}}1}}{\left( u \right)_j} = \frac{{\mathop \sum \limits_{i \in S\left( u \right) - \left\{ j \right\}} \left( {{\rm{de{v}}}_{j,i} + {u_i}} \right){c_{j,i}}}}{{\mathop \sum \limits_{i \in S\left( u \right) - \left\{ j \right\}} {c_{j,i}}}}.$

式中：c_j，i=card（S_j，i（x）），dev_j，i为项目i与项目j评分的平均偏差，u_i为用户u对项目i的评分.

Weighted Slope One在原有Slope One算法的基础上，考虑到每一个项目（商品）对目标项目的影响，使算法推荐更加准确. Weighted Slope One存在不足，该算法仅考虑不同项目的评分偏差，忽略不同用户存在的相似性，带来了新的误差. Lemire教授提出Bi-Polar Slope One算法^[10]，考虑到了不同用户的相似性.

Bi-Polar Slope One算法在Weighted Slope One的基础上，将用户进行过评分的项目区分为like与dislike 2种. 如果用户u对项目i的评分u_i比该用户对所有项目的平均评分大，则用户u喜欢项目i，否则用户不喜欢项目i：

$\begin{split} & {S^{{\rm{like}}}}\left( u \right) = \left\{ {i \in S\left( u \right)\left| {{u_i}} \right. > \bar u} \right\},\\ & {S^{{\rm{dislike}}}}\left( u \right) = \{ i \in S\left( u \right)|{u_i} < \bar u\} \end{split}.$

式中： $\bar u$为用户 $u$进行过评分的项目的平均评分.

类似地，可以定义对项目i与项目j具有相同喜好的用户集合：

$\begin{split} & S_{i,j}^{{\rm{like}}} = \{ u \in x|i,j \in {S^{{\rm{like}}}}\left( u \right)\} ,\\ & S_{i,j}^{{\rm{dislike}}} = \{ u \in x|i,j \in {S^{{\rm{dislike}}}}\left( u \right)\} . \end{split}$

根据以上定义，能够通过下式得出新的偏差：

$\begin{split} & {\rm{dev}}_{j,i}^{{\rm{like}}} = \mathop \sum \limits_{u \in S_{j,i}^{{\rm{like}}}\left( x \right)} \frac{{{u_j} - {u_i}}}{{{\rm{card}}\left( {S_{j,i}^{{\rm{like}}}\left( x \right)} \right)}},\\& {\rm{dev}}_{j,i}^{{\rm{dislike}}} = \mathop \sum \limits_{u \in S_{j,i}^{{\rm{dislike}}}\left( x \right)} \frac{{{u_j} - {u_i}}}{{{\rm{card}}\left( {S_{j,i}^{{\rm{dislike}}}\left( x \right)} \right)}}. \end{split}$

于是，可以从项目i计算得到预测值：

$\begin{split} & p_{j,i}^{{\rm{like}}} = {\rm{dev}}_{j,i}^{{\rm{like}}} + {u_i},\\ & p_{j,i}^{{\rm{dislike}}} = {\rm{dev}}_{j,i}^{{\rm{dislike}}} + {u_i}. \end{split}$

Bi-Polar Slope One的预测公式如下：

(6) ${p^{{\rm{bpS}}1}}{\left( u \right)_j} = \frac{{\mathop \sum \limits_{i \in {S^{{\rm{like}}}}\left( u \right) - \left\{ j \right\}} p_{j,i}^{{\rm{like}}}c_{j,i}^{{\rm{like}}} + \mathop \sum \limits_{i \in {S^{{\rm{dislike}}}}\left( u \right) - \left\{ j \right\}} p_{j,i}^{{\rm{like}}}c_{j,i}^{{\rm{like}}}}}{{\mathop \sum \limits_{i \in {S^{{\rm{like}}}}\left( u \right) - \left\{ j \right\}} c_{j,i}^{{\rm{like}}} + \mathop \sum \limits_{i \in {S^{{\rm{dislike}}}}\left( u \right) - \left\{ j \right\}} c_{j,i}^{{\rm{like}}}}}.$

Bi-Polar Slope One在Weighted Slope One的基础上加入用户间的相似性的判断，提升了精确度. 只粗略地根据用户对项目的平均评分来区分like与dislike，会引起误差，不能满足推荐需要.

Lee等^[11]首次公布了非负矩阵分解算法（NMF）. NMF解决了许多常规矩阵分解技术中存在的问题，在当时引起了世界上许多研究人员的讨论与深入研究.

NMF的基本思想是将数据非负的矩阵R分解为低维的非负矩阵P、Q，满足R≈PQ，其中R为原始矩阵，P为基矩阵，Q为系数矩阵. 在原始的非负矩阵R中，每个列向量为矩阵P的全部行向量的加权和，权重系数为Q中相对应的列向量的元素. 假设对m个n维空间的样本进行相应的数据处理，m×n的原始矩阵R，m×k的基矩阵P与k×n的系数矩阵Q，这样一组基向量构造出了k维，Q中的每一列都可以大略地看作原始矩阵R对应的列向量对于k维空间的投影^[12].

通过以上公式能够看出，该算法仅仅是一种近似算法^[13]，不要求R=PQ. 为了衡量矩阵分解前、后的近似程度，通常使用损失函数来进行评价，即NMF的核心是找到可以使损失函数f（P，Q）取最小值的矩阵P与Q且这2个矩阵非负^[14]. 通常用欧式距离作为损失函数，如下所示：

(7) $f\left( {{{P}},{{Q}}} \right) \!=\! \frac{1}{2}\left\|{{R}}\! -\! {{PQ}}\right\|_{\rm{F}}^2 \!=\! \frac{1}{2}\mathop \sum \nolimits_{i,j} {\left( {{{{R}}_{ij}} \!-\! {{\left( {{{PQ}}} \right)}_{ij}}} \right)^2}.$

在推荐系统中，在R上完成预处理操作，变换成非负矩阵，算法步骤如下.

由1.2节可知，进行非负矩阵分解后的矩阵P、Q的乘积，即原有矩阵的近似矩阵是一个m×n的矩阵. 若将近似矩阵的每一行看作该行所对应的用户的特征，则选择Pearson系数完成相似性的计算，可得m×m的用户相似度矩阵S_pearson，其中S_pearson（i，j）为用户i与用户j之间的相似度.

(8) ${S_{{\rm{pearson}}}}\left( {i,j} \right) = \frac{{\mathop \sum \limits_{k \in {U_i}} \left( {{R_{k1}} - \overline {{R_1}} } \right)\left( {{R_{k2}} - \overline {{R_2}} } \right)}}{{\sqrt {\mathop \sum \limits_{k \in {U_j}} {{\left( {{R_{k1}} - \overline {{R_1}} } \right)}^2}} \sqrt {\mathop \sum \limits_{k \in {U_j}} {{\left( {{R_{k2}} - \overline {{R_2}} } \right)}^2}} }}.$

式中： $\overline {{R_1}} $与 $\overline {{R_2}} $为用户i与用户j的评分均值.

在上述数据模型和设计思想的基础上，归纳NMF-Slope One算法的输入、输出及步骤如下.

使用的数据集来自MovieLens网站（http://movielens.umn.edu）^[15]. 该网站是由美国Minnersota大学GroupLens研究小组所建立与维护的一个非赢利、以研究为宗旨的实验性网站. 每天均有数以百计的用户浏览MovieLens网站，参与到电影的评分或接受网站的推荐.

在MovieLens上的数据集中，随机选取943名使用者对1 682部影片参与的100 000评分数据信息. 其中，使用者对影片的打分为（1，2，3，4，5）的离散型整数，越接近5表示用户对影片的评价越好，即对该影片的喜好程度越高.

为了衡量推荐算法的优劣，通过选取MAE（预测到用户评分和真实评分的平均误差）、RMSE（均方根误差）2个值来完成定量分析. 若采用NMF-Slope One算法预测出的用户评分为{p₁，p₂，p₃，…，p_n}，用户的真实评分为{q₁，q₂，q₃，…，q_n}，则MAE与RMSE的计算公式如下：

(9) ${\rm{MAE}} = {{\mathop \sum \limits_{i = 1}^n \left| {{p_i} - {q_i}} \right|}}\Big/{n} ,$

(10) ${\rm{RMSE}} = \frac{1}{n}\sqrt {\mathop \sum \limits_{i = 1}^n \left| {{p_i} - {q_i}} \right|} = \frac{1}{n}\sqrt {\mathop \sum \limits_{i = 1}^n {{\left( {{p_i} - {q_i}} \right)}^2}}. $

对于NMF-Slope One算法来说，近似矩阵的维数k的选取十分重要，因此首先要进行k的选取，通过实验得出取值在哪种情况下算法的MAE与RMSE最小. 选取基于阈值的动态最近邻算法，因此将相似度阈值设为0.2^[16]，k分别选取为10、15、20、25、30. 关于k的选取，实验结果如图2、3所示.

由图3可知，当k=15时，NMF-Slope One算法的RMSE与MAE最小. 其中，RMSE=0.912 6，MAE=0.762 4，即当k=15时，NMF-Slope One算法的推荐效果最佳.

将相似度阈值设为0.2，在k=15的条件下进行实验，比较NMF-Slope One算法、Weighted Slope One算法与Bi-Polar Slope One算法的推荐效果. 实验结果如表1所示.

从表1的实验结果可知，NMF-Slope One比传统的Weighted Slope One算法与Bi-Polar Slope One算法的推荐效果更好.

在相似度阈值设为0.2，k=15的条件下进行实验，比较NMF-Slope One算法、基于用户的CF算法与基于项目的CF算法的推荐效果. 实验结果如表2所示.

由表2的数据可知，NMF-Slope One算法与传统的基于用户的CF算法与基于项目的CF算法相比，效果更好.

本文介绍了Slope One算法的原理，针对传统Slope One算法的不足，提出基于非负矩阵分解的Slope One改进算法. 利用该改进算法，有效解决了Slope One算法在数据较稀疏条件下的推荐效果不如传统协同过滤算法的问题. 将NMF-Slope One与Weighted Slope One、Bi-Polar Slope One算法进行比较，实验结果证明了改进后的算法有更好的推荐效果. 在数据稀疏的条件下，确定参数进行实验. 在与原始的CF算法比较后，从实验数据得出NMF-Slope One算法有较好的推荐效果.