瓜斯拉的逆袭
0%

推荐系统基础5：矩阵分解SVD

发表于 更新于 分类于
本文字数： 10k 阅读时长 ≈ 26 分钟

任务5：矩阵分解SVD

代码地址： https://github.com/Guadzilla/Basics-of-Recsys

1. 隐语义模型与矩阵分解

隐语义模型（Latent factor model，简称LFM），是基于矩阵分解（Matrix Factorization，简称MF）的推荐算法。

协同过滤算法的特点就是完全没有利用到物品本身或者是用户自身的属性， 仅仅利用了用户与物品的交互信息就可以实现推荐，是一个可解释性很强， 非常直观的模型， 但是也存在一些问题， 第一个就是处理稀疏矩阵的能力比较弱， 所以为了使得协同过滤更好处理稀疏矩阵问题， 增强泛化能力， 从协同过滤中衍生出矩阵分解模型或者叫隐语义模型，两者差不多说的一个意思， 就是在协同过滤共现矩阵的基础上， 使用更稠密的隐向量表示用户和物品， 挖掘用户和物品的隐含兴趣和隐含特征， 在一定程度上弥补协同过滤模型处理稀疏矩阵能力不足的问题。下图直观展现了协同过滤算法和隐语义模型（矩阵分解算法）的区别。

image-20220425130039276

2. 隐语义模型

隐语义模型最早在文本领域被提出，用于找到文本的隐含语义。在2006年， 被用于推荐中， 它的核心思想是通过隐含特征（latent factor）联系用户和物品（item）， 基于用户的行为找出潜在的主题和分类。

我们下面拿一个音乐评分的例子来具体看一下隐含特征的含义。

假设每个用户都有自己的听歌偏好， 比如A喜欢带有小清新的， 吉他伴奏的， 王菲的歌曲，如果一首歌正好是王菲唱的， 并且是吉他伴奏的小清新， 那么就可以将这首歌推荐给这个用户。 也就是说是小清新， 吉他伴奏， 王菲这些元素连接起了用户和歌曲。 当然每个用户对不同的元素偏好不同， 每首歌包含的元素也不一样， 所以我们就希望找到下面的两个矩阵：

  1. 潜在因子—— 用户矩阵Q 这个矩阵表示不同用户对于不同元素的偏好程度， 1代表很喜欢， 0代表不喜欢， 比如下面这样：

在这里插入图片描述

  1. 潜在因子——音乐矩阵P 表示每种音乐含有各种元素的成分， 比如下表中， 音乐A是一个偏小清新的音乐， 含有小清新的Latent Factor的成分是0.9， 重口味的成分是0.1， 优雅成分0.2…..

在这里插入图片描述

利用上面的这两个矩阵， 我们就能得出张三对音乐A的喜欢程度：

张三对小清新的偏好 音乐A含有小清新的成分 + 张三对重口味的偏好 音乐A含有重口味的成分 + 张三对优雅的偏好 音乐A含有*优雅的成分….,

下面是对应的两个隐向量：

在这里插入图片描述

根据隐向量其实就可以得到张三对音乐A的打分，即： 按照这个计算方式， 每个用户对每首歌其实都可以得到这样的分数， 最后就得到了我们的评分矩阵：

在这里插入图片描述

这里的红色表示用户没有打分，我们通过隐向量计算得到的。

上面例子中的小清晰， 重口味， 优雅，伤感，五月天这些就可以看做是隐含特征， 而通过这个隐含特征就可以把用户和音乐联系起来。其实就是找到了每个用户、每个音乐的一个 5 维的隐向量表达形式（类似embedding）。

用户隐向量的每个维度代表该用户对这个隐含特征的相关性（兴趣），音乐隐向量的每个维度代表该音乐与这个隐含特征的相关性。

于是隐向量就可以反映出用户的兴趣和物品的风格，并能将相似的物品推荐给相似的用户等。 有没有感觉到是把协同过滤算法进行了一种延伸， 把用户的相似性和物品的相似性通过了一个叫做隐向量的方式进行表达。

但是， 真实的情况下我们其实是没有上面那两个矩阵的， 音乐那么多， 用户那么多， 我们没有办法去找一些隐特征去表示出这些东西， 另外一个问题就是即使能表示也不一定准， 对于每个用户或者每个物品的风格，我们每个人都有不同的看法。 所以事实上， 我们有的只有用户的评分矩阵， 也叫“共现矩阵”， 一般这种矩阵长这样：

user-item评分矩阵

上面说到过，如果直接用协同过滤算法去填充这个矩阵，很容易头部效应明显、泛化能力弱、长尾效应明显的问题。

如何才能将这个矩阵转化成我们想要的隐语义模型呢？矩阵分解算法实现了这一点。

3. 矩阵分解算法

矩阵分解算法其实就是在想办法基于这个评分矩阵去找到上面例子中的那两个矩阵， 也就是用户兴趣和物品的隐向量表达。 具体做法是：将评分矩阵分解成Q和P两个矩阵乘积的形式， 这时候就可以基于这两个矩阵去预测某个用户对某个物品的评分了。 然后基于这个评分去进行推荐。这就是矩阵分解算法的原理。

矩阵分解算法原理

在矩阵分解的算法框架下， 我们可以通过分解协同过滤的共现矩阵来得到用户和物品的隐向量， 就是上面的用户矩阵Q和物品矩阵P， 这也是“矩阵分解”名字的由来。

在这里插入图片描述

矩阵分解算法将 $m\times n$ 维的共现矩阵 $R$ 分解成 $m \times k$ 维的用户矩阵 $U$ 和 $k \times n$ 维的物品矩阵 $V$ 相乘的形式。 其中 $m$ 是用户数量， $n$ 是物品数量， $k$ 是隐向量维度， 也就是隐含特征个数， 只不过这里的隐含特征变得不可解释了， 即我们不知道具体含义了， 要模型自己去学。$k$ 的大小决定了隐向量表达能力的强弱， $k$ 越大， 表达信息的能力就越强， 理解起来就是把隐含特征分类划分的越具体。

那么如果有了用户矩阵和物品矩阵的话， 我们就能计算用户 $u$ 对物品 $i$ 的评分， 只需要

（熟悉推荐的同学应该对这个表达式非常熟悉，几乎所有预测得分都是这个计算得来的。）这里的 ${p_u}$ 就是用户 $u$ 的隐向量， 就类似与上面的张三向量， 注意这是列向量， $q_i$ 是物品 $i$ 的隐向量， 就类似于上面的音乐A向量， 这个也是列向量， 所以才用了 $p_{u}^{T} q_{i}$ 得到了一个标量， 也就是用户的最终评分， 计算过程其实和上面例子中一样。 这里的 $p_{u,k}$ 和 $q_{i,k}$ 是模型的参数， 也正是我们想办法要计算的， $p_{u,k}$度量的是用户 $u$ 对第 $k$ 个隐含特征的兴趣， 而 $q_{i,k}$ 度量了物品 $i$ 与第 $k$ 个隐含特征联系。

矩阵分解算法的求解

对矩阵进行矩阵分解的主要方法有三种：特征值分解（Eigen Decomposition）、奇异值分解（Singular Value Decomposition，SVD）和梯度下降（Gradient Descent）。

其中，特征值分解只能作用于方阵，显然不适用于分解用户-物品矩阵。

传统的SVD分解的具体描述如下：

image-20220425134607188

可以说，奇异值分解似乎完美地解决了矩阵分解的问题，但其存在两点缺陷，使其不宜作为互联网场景下矩阵分解的主要方法。（1）SVD分解；（2）SVD分解的计算复杂度达到了 $O(mn^2)$ 的级别，这对于商品数量动辄上百万、用户数量往往上千万的互联网场景来说几乎是不可接受的。原理详解参考文章：奇异值分解(SVD)的原理详解及推导

由于上述两个原因，传统奇异值分解也不适用于解决大规模稀疏矩阵的矩阵分解问题。因此，梯度下降法成了进行矩阵分解的主要方法，这里对其进行具体的介绍。

梯度下降法：Funk-SVD

2006年的Netflix Prize之后， Simon Funk公布了一个矩阵分解算法叫做Funk-SVD, 后来被Netflix Prize的冠军Koren称为Latent Factor Model(LFM)。 Funk-SVD的思想很简单： 把求解上面两个矩阵的参数问题转换成一个最优化问题， 可以通过训练集里面的观察值利用最小化来学习用户矩阵和物品矩阵。

我们上面已经知道， 如果有了用户矩阵和物品矩阵的话， 就能计算用户 $u$ 对物品 $i$ 的评分：

而现在， 我们有真实的 $r_{u,i}$ , 但是没有 $p_{u}^{T} q_{i}$ ，那么我们可以初始化一个啊， 随机初始化一个用户矩阵 $U$ 和一个物品矩阵 $V$ ， 然后不就有 $p_{u}^{T} q_{i}$ 了？ 当然你说， 随机初始化的肯定不准啊， 但是， 有了 $p_{u}^{T} q_{i}$ 之后， 我们就可以计算一个预测值 $\hat{r}_{u i}$ , 即

一开始预测肯定是不准的， 那么这个预测的和真实值之间就会有一个误差：

于是可以得到一个优化目标，即总的误差平方和：

我们想办法进行训练，把 SSE 降到最小，那么我们的两个矩阵参数就可以算出来。

所以就把这个问题转成了最优化的的问题， 可以利用非常标准的梯度下降过程完成。

（1）确定目标函数。我们的目标函数就是：

这里的 $K$ 表示所有用户评分样本的集合。为了减少过拟合现象，加入正则化项后，目标函数如下：

（2）对目标函数求偏导，求取梯度下降的方向和幅度

先对 $p_u$ 和 $q_i$ 求偏导

（3）利用第 2 步的求导结果，沿梯度的反方向更新参数：

其中 $\gamma$ 是学习率，原来的系数 2 可以省略，因为仅仅是放缩学习率。

（4）当迭代次数超过上限次数 $n$ ，或者损失低于阈值 $\theta$ 时，结束训练，否则循环第三步。

在完成矩阵分解过程后，即可得到所有用户和物品的隐向量。在对某用户进行推荐时，可利用该用户的隐向量与所有物品的隐向量进行逐一的内积运算，得出该用户对所有物品的评分预测，再依次进行排序，得到最终的推荐列表。

在了解了矩阵分解的原理之后，就可以更清楚地解释为什么矩阵分解相较协同过滤有更强的泛化能力。在矩阵分解算法中，由于隐向量的存在，使任意的用户和物品之间都可以得到预测分值。而隐向量的生成过程其实是对共现矩阵进行全局拟合的过程，因此隐向量其实是利用全局信息生成的，有更强的泛化能力；而对协同过滤来说，如果两个用户没有相同的历史行为，两个物品没有相同的人购买，那么这两个用户和两个物品的相似度都将为 0（因为协同过滤只能利用用户和物品自己的信息进行相似度计算，这就使协同过滤不具备泛化利用全局信息的能力）。

消除打分偏差

但在实际中， 单纯的 $\hat{r}_{u i}=p_{u}^{T} q_{i}$ 也是不够的， 还要考虑其他的一些因素， 比如一个评分系统， 有些固有的属性和用户物品无关， 而用户也有些属性和物品无关， 物品也有些属性和用户无关。 因此， Netfix Prize中提出了另一种LFM， 在原来的基础上加了偏置项， 来消除用户和物品打分的偏差， 即预测公式如下： 这个预测公式加入了3项偏置 $\mu,b_u,b_i$，作用如下：

  • $\mu$：训练集中所有记录的评分的全局平均数。 在不同网站中， 因为网站定位和销售物品不同， 网站的整体评分分布也会显示差异。 比如有的网站中用户就喜欢打高分， 有的网站中用户就喜欢打低分。 而全局平均数可以表示网站本身对用户评分的影响。
  • $b_u$：用户偏差系数， 可以使用用户 $u$ 给出的所有评分的均值， 也可以当做训练参数。 这一项表示了用户的评分习惯中和物品没有关系的那种因素。 比如有些用户比较苛刻， 对什么东西要求很高， 那么他评分就会偏低， 而有些用户比较宽容， 对什么东西都觉得不错， 那么评分就偏高。
  • $b_i$：物品偏差系数， 可以使用物品 $i$ 收到的所有评分的均值， 也可以当做训练参数。 这一项表示了物品接受的评分中和用户没有关系的因素。 比如有些物品本身质量就很高， 因此获得的评分相对比较高， 有的物品本身质量很差， 因此获得的评分相对较低。

加了用户和物品的打分偏差之后， 矩阵分解得到的隐向量更能反映不同用户对不同物品的“真实”态度差异， 也就更容易捕捉评价数据中有价值的信息， 从而避免推荐结果有偏。 注意此时的目标函数会发生变化：

此时如果把 $b_u$ 和 $b_i$ 当做训练参数的话， 那么它俩的梯度是：

更新公式为：

而对于 $p_{u}$ 和$q_{i}$， 导数没有变化， 更新公式也没有变化。

矩阵分解算法的代码实现

我们这里用代码实现一下上面的算法来预测上一篇文章里面的那个预测 Alice 对物品 5 的评分， 看看矩阵分解到底是怎么进行预测或者是推荐的。 我把之前的例子拿过来：

在这里插入图片描述

任务就是根据这个评分矩阵， 猜测Alice对物品5的打分。

在实现 MF 之前， 先来回忆一下 ItemCF 和 UserCF 对于这个问题的做法：

首先 ItemCF 的做法， 根据已有的用户打分计算物品之间的相似度， 得到物品的相似度矩阵， 根据这个相似度矩阵， 选择出前 K 个与物品 5 最相似的物品， 然后基于 Alice 对这 K 个物品的得分， 猜测 Alice 对物品 5 的得分， 有一个加权的计算公式。

UserCF的做法，根据用户对其他物品的打分， 计算用户之间的相似度， 选择出与Alice最相近的K个用户， 然后基于那K个用户对物品5的打分计算出Alice对物品5的打分。

但是，这两种方式有个问题， 就是如果矩阵非常稀疏的话， 当然这个例子是个特例， 一般矩阵都是非常稀疏的， 那么预测效果就不好， 因为两个相似用户对同一物品打分的概率以及 Alice 同时对两个相似物品打分的概率可能都比较小。 另外， 这两种方法显然没有考虑到全局的物品或者用户， 只是基于了最相似的例子， 很可能有偏。

那么 MF 在解决这个问题上是这么做的：

  1. 首先， 它会先初始化用户矩阵 P 和物品矩阵 Q ， P 的维度是[users_num, K], Q的维度是[item_nums, K]， 这个 K 是隐向量的维度。 也就是把通过隐向量的方式把用户的兴趣和物品的特点关联了起来。 初始化这两个矩阵的方式很多， 但根据经验， 随机数需要和 $\frac{1}{\sqrt{K}}$ 成正比。 下面代码中会发现。
  2. 有了两个矩阵之后， 我就可以根据用户已经打分的数据去更新参数， 这就是训练模型的过程， 方法很简单， 就是遍历用户， 对于每个用户， 遍历它打分的物品， 这样就拿到了该用户和物品的隐向量， 然后两者相乘加上偏置就是预测的评分， 这时候与真实评分有个差距， 根据上面的梯度下降就可以进行参数的更新

这样训练完之后， 我们就可以得到用户 Alice 和物品 5 的隐向量， 根据这个就可以预测 Alice 对物品 5 的打分。下面的代码的逻辑就是上面这两步， 这里使用带有偏置项和正则项的 MF 算法：

1
2
3
4
5
6
7
8
9
10
11
12
class SVD():
    def __init__(self, rating_data, F=5, alpha=0.1, lmbda=0.1, max_iter=100):
        self.F = F           # 这个表示隐向量的维度
        self.P = dict()          #  用户矩阵P  大小是[users_num, F]
        self.Q = dict()     # 物品矩阵Q  大小是[item_nums, F]
        self.bu = dict()   # 用户偏差系数
        self.bi = dict()    # 物品偏差系数
        self.mu = 1.0        # 全局偏差系数
        self.alpha = alpha   # 学习率
        self.lmbda = lmbda    # 正则项系数
        self.max_iter = max_iter    # 最大迭代次数
        self.rating_data = rating_data # 评分矩阵

​ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
    # 初始化矩阵P和Q, 方法很多， 一般用随机数填充， 但随机数大小有讲究， 根据经验， 随机数需要和1/sqrt(F)成正比
    cnt = 0    # 统计总的打分数， 初始化mu用
    for user, items in self.rating_data.items():
        self.P[user] = [random.random() / math.sqrt(self.F)  for x in range(0, F)]
        self.bu[user] = 0
        cnt += len(items) 
        for item, rating in items.items():
            if item not in self.Q:
                self.Q[item] = [random.random() / math.sqrt(self.F) for x in range(0, F)]
                self.bi[item] = 0
    self.mu /= cnt
    
# 有了矩阵之后， 就可以进行训练, 这里使用随机梯度下降的方式训练参数P和Q
def train(self):
    for step in range(self.max_iter):
        for user, items in self.rating_data.items():
            for item, rui in items.items():
                rhat_ui = self.predict(user, item)   # 得到预测评分
                # 计算误差
                e_ui = rui - rhat_ui
                
                self.bu[user] += self.alpha * (e_ui - self.lmbda * self.bu[user])
                self.bi[item] += self.alpha * (e_ui - self.lmbda * self.bi[item])
                # 随机梯度下降更新梯度
                for k in range(0, self.F):
                    self.P[user][k] += self.alpha * (e_ui*self.Q[item][k] - self.lmbda * self.P[user][k])
                    self.Q[item][k] += self.alpha * (e_ui*self.P[user][k] - self.lmbda * self.Q[item][k])
                
        self.alpha *= 0.1    # 每次迭代步长要逐步缩小

# 预测user对item的评分， 这里没有使用向量的形式
def predict(self, user, item):
    return sum(self.P[user][f] * self.Q[item][f] for f in range(0, self.F)) + self.bu[user] + self.bi[item] + self.mu

下面我建立一个字典来存放数据， 之所以用字典， 是因为很多时候矩阵非常的稀疏， 如果用pandas的话， 会出现很多Nan的值， 反而不好处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 定义数据集， 也就是那个表格， 注意这里我们采用字典存放数据， 因为实际情况中数据是非常稀疏的， 很少有情况是现在这样
def loadData():
    rating_data={1: {'A': 5, 'B': 3, 'C': 4, 'D': 4},
           2: {'A': 3, 'B': 1, 'C': 2, 'D': 3, 'E': 3},
           3: {'A': 4, 'B': 3, 'C': 4, 'D': 3, 'E': 5},
           4: {'A': 3, 'B': 3, 'C': 1, 'D': 5, 'E': 4},
           5: {'A': 1, 'B': 5, 'C': 5, 'D': 2, 'E': 1}
          }
    return rating_data
 
# 接下来就是训练和预测
rating_data = loadData()
basicsvd = SVD(rating_data, F=10)
basicsvd.train()
for item in ['E']:
    print(item, basicsvd.predict(1, item))
 
## 结果：
E 3.252210242858994

通过这个方式， 得到的预测评分是3.25， 这个和隐向量的维度， 训练次数和训练方式有关， 这里只说一下这个东西应该怎么用， 具体结果可以不用纠结。

pytorch的代码实现已给出。

比较SVD与协同过滤的精度，哪一个模型的RMSE评分更低？

$RMSE=\sqrt{\frac{1}{m}\sum^m_{i=1}(f(x_i)-y_i)^2}$

用基于皮尔逊相似度的 ItemCF 协同过滤算法，推荐的 TopN 物品的评分与对应真实评分计算 RMSE 。

SVD 算法可以计算所有用户对所有物品的评分，所以计算所有验证集的预测得分与对应真实评分计算 RMSE。

课后思考

  1. 矩阵分解算法后续有哪些改进呢？针对这些改进，是为了解决什么的问题呢？请大家自行探索

    SVD，计算复杂度太高。Funk-SVD，用梯度下降法，大大减少复杂度。BiasSVD，消除用户和物品打分偏差。SVD++，考虑邻域影响。TSVD，加入时间信息。

  2. 矩阵分解的优缺点分析

    • 优点：
      • 泛化能力强： 一定程度上解决了稀疏问题
      • 空间复杂度低： 由于用户和物品都用隐向量的形式存放， 少了用户和物品相似度矩阵， 空间复杂度由$n^2$降到了$(n+m)*f$
      • 更好的扩展性和灵活性：矩阵分解的最终产物是用户和物品隐向量， 这个深度学习的embedding思想不谋而合， 因此矩阵分解的结果非常便于与其他特征进行组合和拼接， 并可以与深度学习无缝结合。

    但是， 矩阵分解算法依然是只用到了评分矩阵， 没有考虑到用户特征， 物品特征和上下文特征， 这使得矩阵分解丧失了利用很多有效信息的机会， 同时在缺乏用户历史行为的时候， 无法进行有效的推荐。 所以为了解决这个问题， 逻辑回归模型及后续的因子分解机模型， 凭借其天然的融合不同特征的能力， 逐渐在推荐系统领域得到了更广泛的应用。

参考资料