推荐算法学习（五）：评分预测&矩阵分解

发表于 | 分类于

推荐系统的两大应用场景分别是评分预测（Rating Prediction）和Top-N推荐（Item Ranking）。其中评分预测主要用于评价网站，比如用户给自己看过的电影评多少分，或者用户给自己看过的书籍评价多少分，矩阵分解技术主要应用于评分预测问题；Top-N推荐常用于购物网站或拿不到显式评分的网站，通过用户的隐式反馈为用户提供一个可能感兴趣的Item列表，此排序任务需要排序模型进行建模。本文主要介绍如何利用矩阵分解来解决评分预测问题。

矩阵分解概述

在之前的文章中，我们介绍过常用的推荐算法，其中协同过滤是推荐系统的主流思想之一。协同过滤技术可划分为基于内存/邻域的协同过滤（Memory-based CF）与基于模型的协同过滤技术（Model-based CF）。这里基于模型的协同过滤技术中矩阵分解（Matrix Factorization，MF）技术最为普遍和流行，因为它的可扩展性好并且易于实现。

矩阵分解是一种隐语义模型。隐语义模型是通过隐含特征（Latent Factor）联系用户兴趣和物品，基于用户行为的自动聚类。在评分预测问题中，收集到的用户行为评分数据可用一个评分矩阵表示，矩阵分解要做的是预测出评分矩阵中缺失的评分，使得预测评分能反映用户的喜欢程度，从而可以把预测评分最高的前K个电影推荐给用户。为了预测缺失的评分，矩阵分解学习User矩阵和Item矩阵，使得User矩阵*Item矩阵与评分矩阵中已知的评分差异最小，此时评分预测问题转化为了一个最优化问题，求解该最优化问题即可将评分矩阵分解成User矩阵和Item矩阵，从而可以计算出缺失的评分。

0

以电影评分预测为例，用评分矩阵表示收集到的用户行为数据，12个用户，9部电影。

0

观察下图User矩阵，可知用户的观影爱好体现在User向量上，观察Item矩阵，可知电影的风格体现在Item向量上，MF用user向量和item向量的内积去拟合评分矩阵中该user对该item的评分，内积的大小反映了user对item的喜欢程度，内积大喜欢程度高，反之喜欢程度低。这里“动作”、“动画”、“爱情”为隐含特征，隐含特征个数k越大，隐类别分得越细，计算量越大。

0

把这两个矩阵相乘，就能预测每个用户对每部电影的预测评分了，评分值越大，表示用户喜欢该电影的可能性越大，该电影就越值得推荐给用户。

0

接下来我们将介绍矩阵分解的目标函数及目标函数最优化问题的求解，并梳理推荐系统中出现过的经典的矩阵分解方法。

矩阵分解目标函数

$r_{ui}$表示用户$u$对Item $i$ 的评分，当 $r_{ui}$>0时，表示有评分，当$r_{ui}$=0时，表示没有评分；$x_u$表示用户$u$ 的向量，k维列向量；$y_i$表示Item $i$ 的向量，k维列向量；用户矩阵X，用户数为N，$X=[x_1,x_2,…,x_N]$；商品矩阵Y，商品数为M，$Y=[y_1,y_2,…,y_M]$.

用户向量与物品向量的内积，表示用户u 对物品i 的预测评分矩阵的目标函数：

0

上式前半部分表示的是User矩阵*Item矩阵与评分矩阵中已知的评分差异，后半部分是L2正则项，保证数值计算稳定性，防止过拟合。

矩阵分解目标函数最优化问题求解

上述目标函数最优化问题的工程解法一般采用交替最小二乘法或随机梯度下降。

###　交替最小二乘法ALS

交替最小二乘法步骤：

  • Step1，固定Y 优化X

0

将目标函数转化为矩阵表达形式

0

其中0，表示用户u对m个物品的评分；0为m个物品的向量。

对目标函数$J$关于$x_u$求梯度，并令梯度为零，得到：

0

求解后可得：

0

  • Step2，固定X 优化Y

  • 重复Step1和2，直到X和Y收敛，每次固定一个矩阵，优化另一个矩阵，都是最小二乘问题

除了针对显式评分矩阵，ALS还可以对隐式矩阵进行分解，将评分看成行为的强度，比如浏览次数，阅读时间等。当 $r_{ui}$>0时，表示用户u对商品i有行为，当$r_{ui}$=0时，表示用户u对商品i没有行为。

0

上式 $p_{ui}$称为用户偏好：当用户u对物品i有过行为，认为用户u对物品i感兴趣，$p_{ui}$=1；当用户u对物品i没有过行为，认为用户u对物品i不感兴趣，$p_{ui}$=0.

对隐式矩阵进行分解的步骤：

  • 引入置信度：0

当 $r_{ui}$>0时，$c_{ui}$与$r_{ui}$线性递增；当$r_{ui}$=0时，$c_{ui}$=1，也就是$c_{ui}$最小值为1.

  • 目标函数

0

  • 利用ALS求解

ALS工具：

  • spark mllib库
  • spark ml库（官方推荐）
  • Python代码：https://github.com/tushushu/imylu/blob/master/imylu/recommend/als.py

随机梯度下降SGD

SGD基本思路是以随机方式遍历训练集中的数据，并给出每个已知评分的预测评分。用户和物品特征向量的调整就沿着评分误差越来越小的方向迭代进行，直到误差达到要求。所以，SGD不需要遍历所有的样本即可完成特征向量的求解。

梯度下降法：

0

其中 $\theta$为参数，代表权重，n为特征数用它来模拟y，需要最小化损失函数

0

0

  • 我们处于山中的某个位置，不知道极值点在哪里
  • 每一步，我们都以下降最多的路线来下山

$\alpha$表示学习率（步长），0（沿着梯度的反方向，即采用梯度下降的方式进行权重更新）

梯度下降更新过程：

0

0

  • 批量梯度下降：在每次更新时用所有样本；稳定，收敛慢
  • 随机梯度下降：每次更新时用1个样本，用1个样本来近似所有的样本；更快收敛，最终解在全局最优解附近
  • mini-batch梯度下降：每次更新时用b个样本，折中方法；速度较快

矩阵分解方法

矩阵分解就是将矩阵拆解为多个矩阵的乘积。本文将介绍特征分解EVD和奇异值分解SVD两种分解方法，并介绍推荐系统中常见的矩阵分解算法。

特征/谱分解EVD

特征分解是将矩阵分解为特征值和特征向量表示的矩阵之积的方法，也称为谱分解。

A是NxN维的方阵，对矩阵 A 进行特征分解：

0

其中U的列向量是A的特征向量，Λ是对角矩阵，对角元素是特征向量的特征值。

如果A对称方阵，那么其特征向量构成的矩阵U是正交矩阵，则有

0

0

0

奇异值分解SVD

在进行矩阵分解时，很多矩阵都是非对称的，矩阵A不是方阵，即维度为m*n，我们可以将它转化为对称的方阵，因为$A^TA$和$AA^T$都是对称的方阵，有

0

其中$\Lambda_1$和$\Lambda_2$为对角矩阵，具有相同非零对角元素$\sigma_1,\sigma_2,…,\sigma_k，k<=min(m,n)$，此时，$\lambda_1=\sqrt{\sigma_1},\lambda_2=\sqrt{\sigma_2},…,\lambda_k=\sqrt{\sigma_k}$为矩阵A的奇异值。

我们可以得到为奇异值分解:

0

其中P为左奇异矩阵，m.m维；Q为右奇异矩阵，n.n维；Λ对角线上的非零元素为奇异值$\lambda_1,\lambda_2,…,\lambda_k$。

奇异值分解还可表示为

0

其中p为左奇异矩阵的特征向量；q为右奇异矩阵的特征向量。

奇异值分解的应用十分广泛，如通过降维来压缩图片；在推荐系统中，可将user-item评分矩阵的分解转化为SVD矩阵分解。

传统SVD在推荐系统中的应用：

  • 我们可以通过k来对矩阵降维:0

  • 第i个用户对第j个物品的评分:0

  • 完整的SVD，可以将M无损的分解成为三个矩阵

  • 为了简化矩阵分解，我们可以使用k，远小于min(m,n)，对矩阵M近似还原

上述方法看似完美，但忽略了一个重要问题，SVD分解要求矩阵是稠密的，即矩阵中的元素不能有缺失。所以，类似于数据清洗，我们需要先对矩阵中的缺失元素进行补全。但我们在推荐系统中进行矩阵分解的目的就是为了补全缺失的矩阵来预测评分。这就面临着“先有鸡，还是先有蛋”的问题。实际上，评分矩阵往往是稀疏的，具有大量缺失值，计算量大，缺失值填充方式简单粗暴，产生的噪音大。传统SVD还是更适合做降维。

针对传统SVD在推荐系统中使用的局限性，学者们提出了FunkSVD、BiasSVD、SVD++等算法，接下来简单介绍一下这些算法。

FunkSVD算法

传统SVD解决评分预测问题时，需要补全矩阵再预测，产生的噪音大。事实上，矩阵分解之后的还原，只需要关注与原来矩阵中有值的位置进行对比即可，不需要对所有元素进行对比。FunkSVD算法的思路是：

  • 避开稀疏问题，而且只用两个矩阵进行相乘（设置k值，来对矩阵近似求解）：0

  • 损失函数=P和Q矩阵乘积得到的评分，与实际用户评分之差：

0

为了防止过拟合，增加正则项：

0

  • 让损失函数最小化 => 最优化问题：梯度下降法

BiasSVD算法

BiasSVD算法是在FunkSVD算法的基础上考虑了用户和商品的偏好。用户有自己的偏好(Bias)，比如乐观的用户打分偏高；商品也有自己的偏好(Bias)，比如质量好的商品，打分偏高；BiasSVD算法将与个性化无关的部分，设置为偏好(Bias)部分。

其目标函数表示为：

0

其中μ为所有记录的整体平均数；bi为用户偏好（自身属性，与商品无关）；bj为商品偏好（自身属性，与用户无关）。

在迭代过程中，bi,bj的初始值可以设置为0向量，然后进行迭代：

0

最终得到P和Q。

SVD++算法

SVD++算法是在BiasSVD算法的基础上考虑了用户的隐式反馈。隐式反馈是指没有具体的评分，但可能有点击，浏览等行为。

对于某一个用户$i$，假设他的隐式反馈item集合为$I(i)$，用户$i$对商品$j$对应的隐式反馈修正值为：$c_{ij}$，用户i所有的隐式反馈修正值之和为：0，目标函数表示为：

0

最小化目标函数，求解最优化问题，最终得到P和Q。

推荐系统工具：Surprise

常用的推荐系统库有Surprise和LightFM。Surprise是scikit系列中的一个推荐系统库；LightFM是一个Python推荐算法库，具有隐式和显式反馈的多种推荐算法实现，且易用、快速（通过多线程模型估计），能够产生高质量的结果。Surprise中涵盖了Baseline、基于邻域的协同过滤、矩阵分解（SVD，SVD++，PMF，NMF）、SlopeOne 协同过滤等常用推荐算法。Surprise中的评价指标包含均方根误差（RMSE）、平均绝对误差（MAE）以及一致对的分数（FCP）。接下来简单介绍Surprise中的Baseline算法和SlopeOne算法。

Baseline算法

Baseline算法（基于统计的基准预测线打分）假设训练数据为： <user, item, rating>三元组， 其中user为用户id， item为物品id，rating为user对item的投票分数， 其中用户u对物品i的真实投票分数我们记为$r_{ui}$，基线模型预估分数为$b_{ui}$，则可建模：

\[b_{ui}=\mu+b_u+b_i\]

其中$\mu$为所有已知评分数据的均值，$b_u$为用户的打分相对于平均值的偏差（如果某用户比较苛刻，打分都相对偏低， 则$b_u$会为负值；相反，如果某用户经常对很多片都打正分， 则$b_u$为正值）； $b_i$为该item被打分时，相对于平均值的偏差，可反映电影受欢迎程度。 该模型虽然简单， 但其中其实已经包含了用户个性化和item的个性化信息， 而且特别简单。

基线模型中，$\mu$可以通过统计得到，为了估计$b_u$和$b_i$，我们的目标函数可以写成：

0

使用ALS优化该目标函数步骤：

  • Step1，固定$b_u$，优化$b_i$
  • Step2，固定$b_i$，优化$b_u$
  • 重复Step1和2，直到收敛

0

SlopeOne算法

SlopeOne算法是由Daniel Lemire在2005年提出的一个Item-Based 的协同过滤推荐算法，最大优点在于算法很简单，易于实现，效率高且推荐准确度较高。其步骤为：

  • Step1，计算Item之间的评分差的均值，记为评分偏差（两个item都评分过的用户）

0

  • Step2，根据Item间的评分偏差和用户的历史评分，预测用户对未评分的item的评分

0 0

  • Step3，将预测评分排序，取topN对应的item推荐给用户

SlopeOne算法存在一个明显的问题是，如果有100个用户对Item1和Item2都打过分, 有1000个用户对Item3和Item2也打过分，显然这两个rating差的权重是不一样的，因此又提出了 Weighted Slope One算法，引入了权重对SlopeOne算法进行修正。

从上述内容不难看出，SlopeOne适用于item更新不频繁，且item数远小于user数的推荐场景，其依赖用户行为，也存在冷启动和稀疏性等问题。

实例1：采用funkSVD算法对电影进行评分预测

  • 数据集：Netflix数据集，https://www.kaggle.com/netflix-inc/netflix-prize-data/data，包含了1998年10月至2005年12月之间Netflix用户所有的电影评分数据，涵盖了48万用户对17000部电影的评分记录（超过1亿条），评分范围1-5星。

  • 使用推荐系统工具Surprise，运用funkSVD算法预测Netflix用户对电影的评分。

代码：https://github.com/Alice1214/RS/blob/master/RS05/SVD_netflix.ipynb

实例2：采用SVD方法对图片进行压缩

代码：https://github.com/Alice1214/RS/blob/master/RS06/image-svd/RS06-image-svd.py

实例3：使用Google Colab编辑器对MovieLens数据集进行评分预测

  • 数据集：MovieLens数据集

  • 使用Google Colab编辑器，针对MovieLens数据集，分别运用funkSVD、BiasSVD、SVD++算法进行评分预测，并计算RMSE。

代码：https://github.com/Alice1214/RS/blob/master/RS06/MovieLens/RS06_movielens_svd.py

实例4：新冠肺炎数据可视化呈现

  • 数据集：从腾讯新闻接口获取的当天疫情数据https://view.inews.qq.com/g2/getOnsInfo?name=disease_h5
  • 利用requests工具从腾讯新闻接口获取当天疫情数据，再使用pyecharts工具进行可视化呈现，生成一个html文件，在浏览器中打开即可看到可视化效果如下：

0

代码：https://github.com/Alice1214/RS/blob/master/RS06/nCoV/RS06-Action3.py