达观数据：想写出人见人爱的推荐系统，先了解经典矩阵分解技术

随着大数据时代的来临，网络中的信息量呈现指数式增长，随之带来了信息过载问题。推荐系统是大数据时代下应运而生的产物，目前已广泛应用于电商、社交、短视频等领域。本文将针对推荐系统中基于隐语义模型的矩阵分解技术来进行讨论。

1、评分矩阵、奇异值分解与FunkSVD

对于一个推荐系统，其用户数据可以整理成一个user-item矩阵。矩阵中每一行代表一个用户，而每一列则代表一个物品。若用户对物品有过评分，则矩阵中处在用户对应的行与物品对应的列交叉的位置表示用户对物品的评分值。这个user-item矩阵被称为评分矩阵。

上图即为评分矩阵的一个例子。其中的？表示用户还没有对物品做出评价，而推荐系统最终的目标就是对于任意一个用户，预测出所有未评分物品的分值，并按分值从高到低的顺序将对应的物品推荐给用户。

说到矩阵分解技术，首先想到的往往是特征值分解（eigendecomposition）与奇异值分解（Singular value decomposition，SVD）。

对于特征值分解，由于其只能作用于方阵，因此并不适合分解评分矩阵这个场景。

而对于奇异值分解，其具体描述为假设矩阵M是一个m*n的矩阵，则一定存在一个分解M=UΣVT，其中U是m*m的正交矩阵，V是n*n的正交矩阵，Σ是m*n的对角阵，可以说是完美契合分解评分矩阵这个需求了。其中，对角阵Σ还有一个特殊的性质，它的所有元素都非负，且依次减小。这个减小也特别快，在很多情况下，前10%的和就占了全部元素之和的99%以上，这就是说我们可以使用最大的k个值和对应大小的U、V矩阵来近似描述原始的评分矩阵。

于是我们马上能得到一个解决方案：对原始评分矩阵M做奇异值分解，得到U、V及Σ，取Σ中较大的k类作为隐含特征，则此时M(m*n)被分解成U(m*k) Σ(k*k)V(k*n)，接下来就可以直接使用矩阵乘法来完成对原始评分矩阵的填充。但是实际上，这种方法存在一个致命的缺陷——奇异值分解要求矩阵是稠密的。也就是说SVD不允许待分解矩阵中存在空白的部分，这一开始就与我们的问题所冲突了。当然，也可以想办法对缺失值先进行简单的填充，例如使用全局平均值。然而，即使有了补全策略，在实际应用场景下，user和item的数目往往是成千上万的，面对这样的规模传统SVD算法O(n^3)的时间复杂度显然是吃不消的。因此，直接使用传统SVD算法并不是一个好的选择。

既然传统SVD在实际应用场景中面临着稀疏性问题和效率问题，那么有没有办法避开稀疏问题，同时提高运算效率呢？

实际上早在2006年，Simon Funk就提出了FunkSVD算法，其主要思路是将原始评分矩阵M（m*n）分解成两个矩阵P（m*k）和Q（k*n），同时仅考察原始评分矩阵中有评分的项分解结果是否准确，而判别标准则是均方差。

即对于矩阵M(m*n)，我们想办法将其分解为P(m*k)、Q(k*n)，此时对于原始矩阵中有评分的位置MUI来说，其在分解后矩阵中对应的值就是：

那么对于整个评分矩阵而言，总的损失就是：

只要我们能想办法最小化上面的损失SSE，就能以最小的扰动完成对原始评分矩阵的分解，在这之后只需要用计算M’ 的方式来完成对原始评分矩阵的填充即可。

这种方法被称之为隐语义模型（Latent factor model，LFM），其算法意义层面的解释为通过隐含特征（latent factor）将user兴趣与item特征联系起来。

对于原始评分矩阵R，我们假定一共有三类隐含特征，于是将矩阵R（3*4）分解成用户特征矩阵P（3*3）与物品特征矩阵Q（3*4）。考察user1对item1的评分，可以认为user1对三类隐含特征class1、class2、class3的感兴趣程度分别为P11、P12、P13，而这三类隐含特征与item1相关程度则分别为Q11、Q21、Q31。

回到上面的式子，可以发现用户U对物品I最终的评分就是由各个隐含特征维度下U对I感兴趣程度的和，这里U对I的感兴趣程度则是由U对当前隐含特征的感兴趣程度乘上I与当前隐含特征相关程度来表示的。

于是，现在的问题就变成了如何求出使得SSE最小的矩阵P和Q。

2、随机梯度下降法