重温经典推荐算法——协同过滤（二）

欢迎大家来到IT世界,在知识的湖畔探索吧!

在上一篇文章中，讲述了memory-based 协同过滤推荐算法，其具体分为基于用户和基于物品两种方式。

简而言之，基于用户的推荐，就是找到和你相似的用户，把他喜欢的物品推荐给你。基于物品的推荐，就是找到和你喜欢的物品相似的物品，然后推荐给你。其中，最关键的步骤，在于计算用户和用户之间的相似度，以及物品和物品之间的相似度。

通常，我们会把用户对于物品的行为，抽象成了一个m*n的矩阵，矩阵中的每个元素x(i,j)，代表第i个用户对第j个物品的评分，即矩阵中的每一行代表用户对所有的物品评分，每一列代表所有用户对这一物品的评分。

用户对每个物品的评分，可以看作一个m维向量，可以用其代表用户对物品的偏好，而所有用户对于一个物品的评分，可以看作一个n维向量，可以用其代表这个物品的特性。我们通过计算向量之间的相似度，通常采用杰卡德距离，计算出相似用户和相似物品，然后进行推荐。

这就是Memory-based 协同过滤的基本思想和具体实现过程，但是在实际应用中，存在一些缺陷。

首先，很多场景里，用户和物品的规模都是很庞大的，例如头条、微博、淘宝等APP，其用户物品矩阵的维度往往达到上亿，在计算相似度时，其计算和存储的性能会受到限制，这在实际应用中是不可被接受的。

另外，由于用户对大多数物品是没有行为的，所以矩阵是极为稀疏的，基于上述方式计算相似度时，用户的行为过于稀疏时使得相似度计算不够精准，导致中长尾用户和物品的推荐效果不好。

为了解决上述问题，model-based协同过滤方法被提出。Model-based方法，本质上是将推荐问题转化成一个机器学习预测问题，通过用户对物品的历史评分，来预测用户对于未知物品的评分，并将预测评分最高的物品集合推荐给用户。

算法思想

在2006年，Netflix举办了一个推荐系统比赛，比赛题目就是预测用户对于电影的评分，奖金高达百万美金，引来众多团队参与。其中矩阵分解（Matrix Factorization，MF）方法在比赛中大放异彩，这就是一种model-based方法。

矩阵分解，直观上讲，我们将用户物品矩阵M，分解成U和V两个矩阵相乘。假设M的维度为m*n，m和n分别是用户数量和物品数量，而分解的子矩阵U的维度是m*k，V的维度是k*n。其中k的值远小于m和n。用户i对于物品j的评分，就等于U的第i行与V的第j列的向量乘积。U的每一行和V的每一列的k维向量，我们称之为隐式向量（Latent Factor Vector）。

矩阵分解推荐算法的思想，就是将矩阵分解后得到的隐式向量，当作用户和物品的特征向量。区别于显示向量，隐式向量的每一个维度具有不可解释性，但其因为从用户和物品的交互行为中产生，所以我们可以将用户的隐向量看作用户的偏好特征，物品的隐向量看作物品的属性特征，只不过不知道每一维的具体名称。从降维的视角看，用户和物品的隐向量本质上是原始高维向量(即用户物品矩阵每一行和每一列)的一种降维，且保留了最重要的信息。

综上所述，我们得到了用户和物品的隐式向量矩阵，二者相乘，就可以预测出用户对于未知物品的评分。那么矩阵是如何分解的呢？下面介绍。

算法实现

矩阵分解在线性代数中有很多类，其中最为常用的就是SVD矩阵分解。其可以将矩阵A分解成三个矩阵相乘。如图所示，其中左侧矩阵U和V是正交矩阵，中间是对角阵，其对角线每个元素就是矩阵A的奇异值，每个奇异值代表这个维度的向量对于矩阵A的重要性，奇异值越高，其蕴含的信息量越大。

SVD可以用在数据压缩和降维，在矩阵维度过高时，例如用户物品矩阵，通过SVD矩阵分解成三个子矩阵，然后只保留奇异值最高的k维，抛弃掉其余维度，留下的U（m*k维）和V（n*k维）矩阵，就代表用户和物品的特征矩阵。当我们要预测用户对于某个商品的评分，将三个子矩阵相乘还原为A*（m*n维）。其中，的每一个元素x(i,j),就是用户i对物品j的预测评分。因为是采用截取Topk奇异值的子矩阵，所以计算用户对物品的评分时，计算速度很快。

但是使用SVD矩阵分解方法依旧存在两个问题，首先，用户物品矩阵是稀疏的，而SVD矩阵分解时要求矩阵是稠密的，于是不得不进行大量的缺失值填充，但这样会导致效果很差。其次，对于大规模矩阵，SVD分解时间复杂度很高，在实际应用中性能无法被接受。

于是，我们采用机器学习方法，利用已知的用户对物品的评分，训练一个回归模型。其原理是，我们初始化一个随机的用户和物品的特征矩阵U和V，将用户和物品向量乘积得到的预测评分，去拟合真实的用户物品评分，利用预测分和真实分的误差平方（MSE）作为损失函数，去不断迭代学习用户和物品的向量矩阵。

具体实现如下，假设用户i对物品j的评分为r，我们将用户i映射到一个k维向量u，物品j映射到一个k维向量v，向量u和v的乘积为用户i对物品j的预测得分r*。这就是一条样本，针对所有的样本，我们可以得到模型的目标函数：

针对这一目标函数，我们通过梯度下降法进行求解u和v。当预测分和真实分的误差足够小时，我们就可以得到准确的用户和物品的特征向量，进而推算出用户对于未知物品的评分。通常，训练的样本量越大，结果也越准确。

除此之外，我们还可以用户侧加一些bias项，因为不同用户打分的倾向是不同的，有的可能打分偏高，有的偏低，加入bias后可以对此进行平滑，以加大预测的准确性。

总结

以上就是经典的model-based协同过滤，基于矩阵分解的推荐算法，又称作SVD推荐算法。相比于memory-based协同过滤，其推荐的准确率更高。同时，矩阵分解借助机器学习回归模型，避免了直接进行矩阵分解时较高的计算复杂度，用较低的成本学习得到用户和物品的向量矩阵。在实际应用中，模型的训练可以放在离线进行，线上直接用向量进行预测，大大提升了推荐的时效性。

矩阵分解算法自诞生后，也衍生了很多变种，例如SVD++、TimeSVD、SLIM、FLSM等，这些方法通过加入更多的用户和物品特征、隐式反馈、以及优化目标函数等方式，获得了更好的性能，我们将在后续文章中介绍。