算法回顾：SVD在协同过滤推荐系统中的应用

作者: 张虾米试错 | 来源:发表于2019-05-19 20:16 被阅读0次

协同过滤一般分为两大类：一类为基于领域（记忆）的方法，第二类为基于模型的方法，即隐语义模型，矩阵分解模型是隐语义模型最为成功的一种实现。隐语义模型最早在文本挖掘领域被提出，用于寻找文本的隐含语义，相关的模型常见的有潜在语义分析（Latent Semantic Analysis,LSA）、LDA（Latent Dirichlet Allocation）的主题模型（Topic Model）、矩阵分解（Matrix Factorization）等等。本文主要介绍的是矩阵分解中SVD相关的方法。

大纲

传统的SVD
FunkSVD
FunkSVD在协同过滤中的应用
基于SVD的其他改进方法

1. SVD简介

在推荐系统中，我们根据用户行为通常可以得到user-item的评分矩阵。由于每个用户可能只在少部分商品上有历史行为，因此评分矩阵往往是稀疏的，如下：

user\item	item1	item2	item3	item4	item5	item6	item7
user1		3		5		1
user2	2	1					4
user3			4		3
user4	1	4					2

在推荐中，我们希望可以预测出用户对未评分商品的评分，从而将评分高的商品推荐给用户。矩阵分解就是解决该问题的其中一种方法。如果对SVD原理不了解的可以看看这篇博客强大的矩阵奇异值分解(SVD)及其应用，本文不详细介绍。

如果我们对user-item评分矩阵进行SVD分解，就可以得到：
$M_{m*n} = U_{m_k}^T\Sigma_{k*k}V_{k*n}$
其中 $k$ 是矩阵 $M$ 中较大的部分奇异值的个数，一般会远远的小于用户数和物品树。如果我们要预测第 $i$ 个用户对第 $j$ 个物品的评分 $M_{ij}$ ,则只需要计算 $U^T_i\Sigma V_j$ 即可。通过这种方法，我们可以将评分表里面所有没有评分的位置得到一个预测评分。通过找到最高的若干个评分对应的物品推荐给用户。到这里似乎很完美了，但是我们忽略了一个问题，传统的SVD要求矩阵是稠密的，因此为了让SVD解决该问题，我们需要对SVD进行缺失值填充。但是这样又会导致新的问题：

矩阵太稠密计算复杂度高
如何对缺失值进行填充

2. FunkSVD

为了解决上述传统SVD的问题，FunkSVD被提出，这种改进算法称为隐语义模型或潜在因素模型。该方法只将矩阵分解成2个矩阵——用户隐含特征组成的矩阵和项目隐含特征组成的矩阵：
$R \approx P_{m*k}^TQ_{k*n}$
其中 $k$ 表示隐特征的数量， $P$ 为 $k×m$ 矩阵，表示用户特征向量； $Q$ 为 $k×n$ 矩阵，表示物品特征向量。那么用户 $u$ 对用户 $i$ 的预测评分为：
$\hat r_{ui}=p_u^Tq_i$

2.1求解

求解方法是将问题转化为最小化误差函数，目标函数为：
$C = \sum_{(u, i) \in R} (r_{ui} - p_u^Tq_i)^2 + \lambda (||p_u||^2 +||q_i||^2 )$
目标
$\min_{p_u, q_i} C$

2.2优化方法

最常用的两种优化方法：随机梯度下降（SGD)和最小二乘（ALS）。通常SGD比ALS(Alternating Least Squares)简单而且快速；但是ALS的并行性能比较好，而且可以较好地处理稀疏数据，spark的实现方式就是ALS。

随机梯度下降

分别对 $p_u$ 和 $q_i$ 求导：
$\frac{\partial C }{\partial p_u} = -2(r_{ui} - p_u^Tq_i)q_i + 2\lambda p_u$
$\frac{\partial C }{\partial q_i} = -2(r_{ui} - p_u^Tq_i)p_u + 2\lambda q_i$
那么 $p_u$ , $q_i$ 的迭代公式为：
$p_u = \alpha[(r_ui - p_u^Tq_i)q_i - \lambda p_u]$
$q_i = \alpha[(r_ui - p_u^Tq_i)p_u - \lambda q_i]$

ALS

同样通过求偏导的方法，并令偏导等于0，可以得到
$p_u = (Q^TQ + \lambda E)^{-1} Q^Tr_u \space\space (1)$
$q_i = (P^TP + \lambda E)^{-1} P^T r_i \space\space (2)$
先固定 $Q$ ，通过公式（1）求解 $P$ ；再固定 $P$ ，通过公式（2）求解 $Q$ ；直到收敛。

3. FunkSVD在协同过滤中的应用

最后得到 $P$ , $Q$ 后，可以通过4种方式进行推荐：

直接使用 $p_u^Tq_i$
基于user-based推荐
先通过 $P$ 计算出相似用户，然后再推荐相似用户评分高的物品
基于item-based推荐
先通过 $Q$ 计算出相似物品，然后再根据该用户的历史行为推荐相似物品
基于主题的推荐(可能这种叫法不对)
这个有点类似于LDA, 通过 $P$ 可以得到用户最显著的隐特征，然后推荐在该隐特征上表现明显的商品。

4. 基于SVD的其他改进方法

Bias-SVD

用户对物品的评价有些因素与用户的喜好无关，而只取决于用户或物品本身特性。例如，对于乐观的用户来说，它的评分行为普遍偏高，而对批判性用户来说，他的评分记录普遍偏低，即使他们对同一物品的评分相同，但是他们对该物品的喜好程度却并不一样。同理，对物品来说，以电影为例，受大众欢迎的电影得到的评分普遍偏高，而一些烂片的评分普遍偏低，这些因素都是独立于用户或产品的因素，而和用户对产品的的喜好无关。
Bias-SVD把这些独立于用户或独立于物品的因素称为偏置(Bias)部分，将用户和物品的交互即用户对物品的喜好部分称为个性化部分。偏置部分由3部分组成：

训练集中所有评分记录的全局平均数 $\mu$ , 该值为常数
用户偏置bu
物品偏置bi
则偏置部分为：
$b = \mu + b_u + b_i$
将 $b$ 加入目标函数，则变成：
$\hat r_{ui} = p_u^Tq_i + \mu + b_u + b_i$
$C = \sum_{(u, i) \in R} (r_{ui} - \hat r_{ui})^2 + \lambda (||p_u||^2 +||q_i||^2 + b_u^2 + b_i^2)$

SVD++

SVD++算法在Bias-SVD算法上增加考虑了用户的隐式反馈。
对于某一个用户 $u$ ，它提供了隐式反馈的物品集合定义为 $N(u)$ ，这个用户对某个物品 $j$ 对应的隐式反馈修正的评分值为 $c_{ij}$ ，表示为 $q_i^Ty_s$ 那么该用户所有的评分修正值为 $\sum_{s \in N(u)}{c_{sj}}$ ，则加入了隐式反馈以后的优化目标函数J(p,q)是这样的：
$\hat r_{ui} = p^T_uq_i + \mu + b_i + b_u + q_i^T|N(u)|^{-\frac{1}{2}}\sum_{s \in N(i)}y_s$
$arg \min_{p_uq_i} \sum_{(u, i) \in R} (r_{ui} - \hat r_{ui})^2 + \lambda (||p_u||^2 +||q_i||^2 + b_u^2 + b_i^2 + \sum_{s \in N(u) }||y_s||^2)$
其中，引入 $|N(i)|^{−\frac{1}{2}}$ 是为了消除不同 $|N(i)|$ 个数引起的差异。如果需要考虑用户的隐式反馈时，使用SVD++是个不错的选择。