推荐系统实践（项亮）第八章

第八章 评分预测问题

之前一直讨论的是TopN推荐，这也是实际系统的需求，即给用户提供一个个性化推荐列表。除此之外，还有一个重要的问题是评分预测问题。

评分预测最基本的数据集由三元组$(u,i,r)$表示，表示用户$u$给物品$i$打了评分$r$，用户不可能对所有物品评分，因此评分预测问题就是如何通过已知的用户历史评分记录预测未知的用户评分记录。

例如通过下表的数据，我们希望预测用户A对变形金刚和黑客帝国的评分，并且提高这个分数的预测精度。

8.1 离线实验方法

一般用均方根误差RMSE度量预测的精度，我们用$r_{ui}$表示用户$u$给物品$i$的评分：
$$
RMSE=\frac{\sqrt{\sum_{(u,i)\in T}(r_{ui}-\hat r_{ui})}}{|Test|}
$$
对于和事件无关的预测任务，可以随机划分。否则可以将每个用户的评分记录按照从早打完进行排序，然后将用户最后10%的评分记录作为测试集，前90%作为训练集。

8.2 评分预测算法

代码

8.2.1 平均值

利用平均值预测用户对物品的评分是最简单的一种算法。

1 全局平均值

定义为训练集中所有评分记录的平均值
$$
\mu=\frac{\sum_{(u,i)\in Train}r_{ui}}{\sum_{(u,i)\in Train}1}\\hat r_{ui}=\mu
$$

2 用户评分平均值

定义为用户$u$在训练集中所有评分的平均值
$$
\bar r_u=\frac{\sum_{i\in N(u)}r_{ui}}{\sum_{i\in N(u)}1}\\hat r_{ui}=\bar r_u
$$

3 物品评分评分值

定义为物品$i$在训练集中接受的所有评分的平均值
$$
\bar r_i=\frac{\sum_{u\in N(i)}r_{ui}}{\sum_{u\in N(i)}1}\\hat r_{ui}=\bar r_i
$$

4 用户分类对物品分类的平均值

假设有用户分类函数$\phi$和物品分类函数$\varphi$。$\phi(u)$定义了用户$u$所属的类，$\varphi(i)$定义了物品$i$所属的类，可以用训练集中同类用户对同类物品评分的平均值预测用户对物品的评分：
$$
\hat r_{ui}=\frac{\sum_{(v,j)\in Train,\phi(u)=\phi(v),\varphi(i)=\varphi(j)}r_{vj}}{\sum_{(v,j)\in Train,\phi(u)=\phi(v),\varphi(i)=\varphi(j)}1}
$$

• $\phi(u)=0,\varphi(i)=0$，对应全局平均值。
• $\phi(u)=u,\varphi(i)=0$，对应用户评分平均值
• $\phi(u)=0,\varphi(i)=i$，对应物品评分平均值

还可以定义其他分类函数

• 用户和物品的平均分 将所有用户按照评分平均分从小到大排序，并将用户按照平均分平均分成$N$类。物品也可以用同样的方式分类。
• 用户活跃度和物品流行度 对于一个用户，将他评分的物品数量定义为他的活跃度。可以将用户通过活跃度从小到大排序，然后平均分为$N$类。物品的流行度定义为给物品评分的用户数目，物品也可以按照流行度均匀分成$N$类。

8.2.2 基于邻域的方法

基于用户和基于物品的邻域算法都可以应用到评分预测中。

基于用户的邻域算法

该算法认为预测一个用户对一个物品的评分，需要参考和这个用户兴趣相似的用户对该物品的评分：
$$
\hat r_{ui}=\bar r_u+\frac{\sum_{v\in S(u,K)\cap N(i)}w_{uv}(r_{vi}-\bar r_v)}{\sum_{v\in S(u,K)\cap N(i)}|w_{uv}|}
$$
用户之间的相似度可以通过皮尔逊系数计算：
$$
w_{uv}=\frac{\sum_{i\in I}(r_{ui}-\bar r_u)\cdot (r_{vi}-\bar r_v)}{\sqrt{\sum_{i\in I}(r_{ui}-\bar r_u)^2\sum_{i\in I} (r_{vi}-\bar r_v)^2}}
$$

基于物品的邻域算法

该算法预测时，会参考用户$u$对和物品$i$相似的其他物品的的评分，即：
$$
\hat r_{ui}=\bar r_i+\frac{\sum_{j\in S(i,K)\cap N(u)}w_{ij}(r_{uj}-\bar r_i)}{\sum_{j\in S(i,K)\cap N(u)}|w_{ij}|}
$$
物品的相似度可采用：

• 普通的余弦相似度

$$
w_{ij}=\frac{\sum_{u\in U}r_{ui}\cdot r_{uj}}{\sqrt{\sum_{u\in U}r_{ui}^2 \sum_{u\in U}r_{uj}^2}}
$$

• 皮尔逊系数（pearson correlation）

$$
w_{ij}=\frac{\sum_{u\in U}(r_{ui}-\bar r_i)\cdot (r_{uj}-\bar r_j)}{\sqrt{\sum_{u\in U}(r_{ui}-\bar r_i)^2 \sum_{u\in U}(r_{uj}-\bar r_j)^2}}
$$

• 修正的余弦相似度

$$
w_{ij}=\frac{\sum_{u\in U}(r_{ui}-\bar r_u)\cdot (r_{uj}-\bar r_u)}{\sqrt{\sum_{u\in U}(r_{ui}-\bar r_u)^2 \sum_{u\in U}(r_{uj}-\bar r_u)^2}}
$$

8.2.3 隐语义模型与矩阵分解模型

实际上，隐含类别模型，隐语义模型（LFM）、矩阵分解模型、pLSA、LDA、Topic Model、Matrix Factorization、Factorized Model等等都是同一种思想体恤的不同扩展，在推荐系统领域，提得最多的就是潜语义模型和矩阵分解模型，他们都是通过降维的方法将评分矩阵$R$中的缺失值（missing value）补全。

1 传统的SVD分解

一个含有缺失值的矩阵有多种补全方法，我们希望找到一种对矩阵扰动最小的补全方法。一般认为，如果补全后的矩阵的特征值和补全之前矩阵的特征值相差不大，就算是扰动比较小。因此最早的矩阵分解模型是从数学上的SVD（奇异值分解）开始的。

给定$m$个用户和$n$个物品，以及评分矩阵$R\in \mathbb R^{m\times n}$，首先利用平均值或基于邻域的方法将评分矩阵缺失值补全，得到补全后的矩阵$R’$，使用SVD分解：
$$
R’=U^TSV
$$
$U\in\mathbb R^{k\times m},V\in \mathbb R^{k\times n}$是两个正交矩阵，$S\in\mathbb R^{k\times k}$是对角阵，对角线上的每一个元素都是矩阵的奇异值。为了对$R’$降维，可以取最大的$f$个奇异值组成对角矩阵$S_f$，并且找到这$f$个奇异值中每个值在$U、V$中对应的行和列，得到$U_f、V_f$，形成一个降维后的评分矩阵：
$$
R_f’=U^T_fS_fV_f
$$
$R_f’(u,i)$就是用户$u$对物品$i$评分的预测值。

SVD是早期推荐系统常用的矩阵分解方法，但有以下缺点：

• 该方法首先需要用一个简单的方法补全稀疏评分矩阵。一般来说，推荐系统中的评分矩阵是非常稀疏的，一般都有95%以上的元素是缺失的。而一旦补全，评分矩阵就会变成一个稠密矩阵，从而使评分矩阵的存储需要非常大的空间，这种空间的需求在实际系统中是不可能接受的。
• 该方法依赖的SVD分解方法的计算复杂度很高，特别是在稠密的大规模矩阵上更是非常慢。一般来说，这里的SVD分解用于1000维以上的矩阵就已经非常慢了，而实际系统动辄是上千万的用户和几百万的物品，所以这一方法无法使用。如果仔细研究关于这一方法的论文可以发现，实验都是在几百个用户、几百个物品的数据集上进行的。

2 Funk-SVD

Simon Funk认为，尽然能用RMSE作为评测指标，那若能找到合适的$P、Q$来最小化训练集的预测误差，那么应该也能最小化测试集的预测误差，因此，定义损失函数：
$$
C(p,q)=\sum_{(u,i)\in Train}(r_{ui}-\hat r_{ui})^2=\sum_{(u,i)\in Train}(r_{ui}-\sum_{f=1}^Fp_{uf}q_{if})^2
$$
同时加入正则化项防止过拟合：
$$
C(p,q)=\sum_{(u,i)\in Train}(r_{ui}-\sum_{f=1}^Fp_{uf}q_{if})^2+\lambda(\Vert p_u \Vert+\Vert q_i \Vert)^2
$$
利用SVD优化参数：
$$
\frac{\partial C}{\partial p_{uk}}=-2q_{ik}+2\lambda p_{uk}\qquad\frac{\partial C}{\partial q_{ik}}=-2p_{uk}+2\lambda q_{ik}\p_{uk}=p_{uk}+\alpha (q_{ik}-\lambda p_{uk})\qquad q_{ik}=q_{ik}+\alpha (p_{uk}-\lambda q_{ik})
$$
LearningLFM主要分两步：首先随机化$P、Q$，根据经验，随机数一般和$\frac{1}{sqrt(F)}$正比。然后随机梯度下降优化参数。

下面介绍一些对LFM的各种改进，有些改进是针对模型的，有些是将新的数据引入到模型中。

3 加入偏置项后的LFM（BiasSVD）

上面的公式$ \hat r_{ui} = \sum_{f=1}^F p_{uf}q_{if}$通过隐类将用户和物品联系，但实际情况下，一个评分系统有些固有属性和用户物品无关，而用户也有些属性和物品无关，物品有些属性和用户无关。因此Netflix Prize提出了另一种LFM，预测公式如下：
$$
\hat r_{ui} = \mu +b_u+b_i+p_u^T\cdot q_i\qquad b_u、b_i需要通过SVD学习
$$

• $\mu$ 训练集中所有记录的评分的全局平均数 网站的评分基准不一，有的虚高有的过低，该指标可以表示网站本身对用户评分的影响
• $b_u$ 用户偏置（user bias）项 有的用户比较苛刻，整体评分都很低。因此该指标表示用户的评分习惯中和物品无关的那种因素
• $b_i$ 物品偏置（item bias）项 有的物品评分很高。因此该指标表示物品接受的评分中和用户没什么关系的因素。

4 考虑邻域影响的LFM（SVD++）

之前的模型没有显式考虑用户的历史行为对用户评分预测的影响。SVD++将用户历史评分的物品加入到了LFM模型中。

首先将ItemCF的预测算法做一些改变，将其设计为一个可学习的模型：
$$
\hat r_{ui}=\frac{1}{\sqrt{|N(u)|}}\sum_{j\in N(u)}w_{ij}r_{uj}
$$
这里的$w_{ij}$不再是物品相似度矩阵，而是一个和$P、Q$一样的参数，$w_{ij}$可以通过下面的损失函数优化：
$$
C(w)=\sum_{(u,i)\in Train}(r_{ui}-\sum_{j\in N(u)}w_{ij}r_{uj})^2+w_{ij}^2
$$
不过该模型有一个缺点，矩阵$w$是一个比较稠密的矩阵。如果有$n$个物品，则该模型参数就是$n^2$个，参数过多容易造成模型过拟合。因此使用两个$F$维的向量$x_i、y_i$对$w$进行分解，将参数降低到$2\ast n\ast F$个：
$$
\hat r_{ui}=\frac{1}{\sqrt{|N(u)|}}\sum_{j\in N(u)}x_i^Ty_j=\frac{1}{\sqrt{|N(u)|}}x_i^T\sum_{j\in N(u)}y_j
$$
再进一步，将其与BiasSVD结合：
$$
\hat r_{ui}=\mu +b_u+b_i+p_u^T\cdot q_i+\frac{1}{\sqrt{|N(u)|}}x_i^T\sum_{j\in N(u)}y_j
$$
同样的，为了减少参数，令$x=q$，从而得到最终的SVD++模型：
$$
\hat r_{ui}=\mu +b_u+b_i+ q_i^T\cdot(p_u+\frac{1}{\sqrt{|N(u)|}}\sum_{j\in N(u)}y_j)
$$
现在便可通过SVD训练模型了。

8.2.4 加入时间信息

利用时间信息（降低预测误差）的方法主要分为两种：

• 将时间信息应用到基于邻域的模型中
• 将时间信息应用到矩阵分解模型中

1 基于邻域的模型融合时间信息（TItemCF）

对于用户数过多的数据集，基于用户的邻域模型很少被使用，因为存储用户相似度矩阵非常困难。

TItemCF是一种融入时间信息的基于邻域的模型，该算法通过下式预测用户在某一个时刻会给物品什么评分：
$$
\hat r_{uit}=\frac{\sum_{j\in N(u)\cap S(i,K)}f(w_{ij},\Delta t)r_{uj}}{\sum_{j\in N(u)\cap S(i,K)}f(w_{ij},\Delta t)}
$$
$\Delta t=t_{ui}-t_{uj}$是用户$u$对物品$i$和物品$j$评分的时间差，$f(w_{ij},\Delta t)$是一个考虑了时间衰减后的相似度函数，其主要目的是提高用户最近的评分行为对推荐结果的影响，原作者使用的$f$为：
$$
f(w_{ij},\Delta t)=\sigma(\delta\cdot w_{ij}\cdot exp(\frac{-|\Delta t|}{\beta})+\gamma)\ \sigma(x)=\frac{1}{1+exp(-x)}
$$
显然，随着$\Delta t$增加，$f(w_{ij},\Delta t)$会变小，也就是说用户很久之前的行为对预测用户当前评分的影响越来越小。

2 基于矩阵分解的模型融合时间信息（TSVD）

引入时间信息后，用户评分矩阵变成了三维矩阵，但依然可以仿照二维进行矩阵分解，回顾之前的BiasSVD模型：
$$
\hat r_{ui} = \mu +b_u+b_i+p_u^T\cdot q_i
$$
$\mu$可看作对二维矩阵的零维分解，$b_u、b_i$可看做对二维矩阵的一维分解，而$p_u^T\cdot q_i$则可看作对二维矩阵的二维分解。仿照这种形式，对用户—物品—时间三维矩阵做如下分解：
$$
\hat r_{uit} = \mu +b_u+b_i+b_t +p_u^T\cdot q_i +x_u^T\cdot y_t +s_i^T\cdot z_t+\sum_fg_{u,f}h_{i,f}l_{t,f}
$$
$b_t$表示系统整体平均分随时间变化的效应，$x_u^T\cdot y_t$建模了用户平均分随时间变化的效应，$s_i^T\cdot z_t$建模了物品平均分随时间变化的效应，而$\sum_fg_{u,f}h_{i,f}l_{t,f}$建模了用户兴趣随时间影响的效应。这个模型也可以SVD进行训练。

Koren在SVD++模型的基础上也引入了时间效应，回顾一下SVD++模型：
$$
\hat r_{ui}=\mu +b_u+b_i+ q_i^T\cdot(p_u+\frac{1}{\sqrt{|N(u)|}}\sum_{j\in N(u)}y_j)
$$
做如下改进以融合时间信息：
$$
\hat r_{ui}=\mu +b_u(t)+b_i(t)+ q_i^T\cdot(p_u(t)+\frac{1}{\sqrt{|N(u)|}}\sum_{j\in N(u)}y_j)\
b_u(t)=b_u+\alpha_u\cdot dev_u(t)+b_{ut}+b_{i,period(t)}\
dev_u(t)=sign(t-t_u)\cdot |t-t_u|^{\beta}\
b_i(t)=b_i+b_{it}+b_{i,period(t)}\
p_{uf}(t)=p_{uf}+p_{utf}
$$
$t_u$是用户所有评分的平均时间。$period(t)$考虑了季节效应，为时刻$t$所在的月份。

8.2.5 模型融合

代码

模型融合对提高评分预测的精度很重要，下面是两种模型融合的技术：

1 模型级联融合

假设已经有一个预测器$\hat r^{(k)}$，对于每个用户—物品对$(u,i)$都给出预测值，那么可以在这个预测器的基础上设计下一个预测器$\hat r^{(k+1)}$来最小化损失函数：
$$
C=\sum_{u,i \in Train}(r_{ui}-\hat r_{ui}^{(k)}-\hat r_{ui}^{(k+1)})^2
$$
级联融合很像Adaboost算法。和Adaboost算法类似，该方法每次产生一个新模型，按照一定的参数加到旧模型上去，从而使训练集误差最小化。不同的是，这里每次生成新模型时并不对样本集采样，针对那些预测错的样本，每次都还是利用全样本集进行预测，但每次使用的模型都有区别。

2 模型加权融合

假设有K个不同的预测器$\hat r^{(1)},\hat r^{(2)},…,\hat r^{(K)}$，本节主要讨论如何将它们融合起来获得最低的预测误差。

最简单的融合算法就是线性融合，即最终的预测器$\hat r$是这$K$个预测器的线性加权：
$$
\hat r=\sum_{k=1}^K\alpha_k\hat r^{(k)}
$$
一般来说，评分预测问题的解决需要在训练集上训练$K$个不同的预测器，然后在测试集上作出预测。但如果继续在训练集上融合$K$个预测器，得到线性加权系数，就会造成过拟合。因此，在模型融合时一般采用：

• 假设数据集已经被分为了训练集$A$和测试集$B$，首先将训练集$A$按照相同的分割方法分为$A1$和$A2$，其中$A2$的生成方法和$B$的生成方法一致，且大小相似。
• 在**$A1$上训练**$K$个不同的预测器，在**$A2$上作出预测**。因为我们知道$A2$上的真实评分值，所以可以在$A2$上利用最小二乘法计算出线性融合系数$\alpha$。（注意$\alpha$是如何产生的）
• 在$A$上训练$K$个不同的预测器，在$B$上作出预测，并且将这$K$个预测器在$B$上的预测结果按照已经得到的线性融合系数加权融合，以得到最终的预测结果。

除了线性融合，还有很多复杂的融合方法，比如利用人工神经网络的融合算法。其实，模型融合问题就是一个典型的回归问题，因此所有的回归算法都可以用于模型融合。

8.2.6 相关实验结果

Netflix Prize比赛的3年时间里，很多研究人员在同一个数据集上重复实验了前面几节提到的各种算法。因此，本章我们引用他们的实验结果对比各个算法的性能。Netflix Prize采用RMSE评测预测准确度，因此本节的评测指标也是RMSE。

后记

本书着重介绍了推荐系统的各种算法设计和系统设计的方法，并且利用一些公开的数据集离线评测了各种算法。对于无法通过离线评测知道算法性能的情况，本书引用了很多著名的用户调查实验来比较不同的算法。

首先需要申明，本书的很多离线实验都是在一两个数据集上完成的，所以本书得到的所有结论都不是定论，可能换一个数据集就会得到完全相反的结论。这主要是因为不同网站中的用户行为有很大的差异，所以推荐系统很难有放之四海而皆准的结论。因此本书非常鼓励读者在自己的数据集上重复本书的实验，再得到适合自己具体情况的结论。这也是本书书名中“实践”一词希望达到的效果。

最后，我想引用2009年ACM推荐系统大会上Strand研究人员做的一个报告“推荐系统十堂课”，在这个报告中Strand的研究人员总结了他们设计推荐系统的经验，提出了10条在设计推荐系统中学习到的经验和教训。

（1）确定你真的需要推荐系统。推荐系统只有在用户遇到信息过载时才必要。如果你的网站物品不太多，或者用户兴趣都比较单一，那么也许并不需要推荐系统。所以不要纠结于推荐系统这个词，不要为了做推荐系统而做推荐系统，而是应该从用户的角度出发，设计出能够真正帮助用户发现内容的系统，无论这个系统算法是否复杂，只要能够真正帮助用户，就是一个好的系统。

（2）确定商业目标和用户满意度之间的关系。对用户好的推荐系统不代表商业上有用的推荐系统，因此要首先确定用户满意的推荐系统和商业上需求的差距。一般来说，有些时候用户满意和商业需求并不吻合。但是一般情况下，用户满意度总是符合企业的长期利益，因此这一条的主要观点是要平衡企业的长期利益和短期利益之间的关系。

（3）选择合适的开发人员。一般来说，如果是一家大公司，应该雇用自己的开发人员来专门进行推荐系统的开发。

（4）忘记冷启动的问题。不断地创新，互联网上有任何你想要的数据。只要用户喜欢你的产品，他们就会不断贡献新的数据。

（5）平衡数据和算法之间的关系。使用正确的用户数据对推荐系统至关重要。对用户行为数据的深刻理解是设计好推荐系统的必要条件，因此分析数据是设计系统中最重要的部分。数据分析决定了如何设计模型，而算法只是决定了最终如何优化模型。

（6）找到相关的物品很容易，但是何时以何种方式将它们展现给用户是很困难的。不要为了推荐而推荐。

（7）不要浪费时间计算相似兴趣的用户，可以直接利用社会网络数据。

（8）需要不断地提升算法的扩展性。

（9）选择合适的用户反馈方式。

（10）设计合理的评测系统，时刻关注推荐系统各方面的性能。