矩阵分解推荐算法

A. ab与ba的特征值相同吗

如果A，B都是方阵。则AB与BA的特征值相同。

矩阵分解的含义：

矩阵分解算法将m×n维的矩阵R分解为m×k的用户矩阵P和k×n维的物品矩阵Q相乘的形式。其中m为用户的数量，n为物品的数量，k为隐向量（Latent Factor）的维度。k的大小决定了隐向量表达能力的强弱，实际应用中，其取值要经过多次的实验来确定。

在得到了用户矩阵和物品矩阵Q后，将两个矩阵相乘，就可以得到一个满秩的矩阵。那么，我们就对未被评价过的物品，有了一个预测评分。接下来，可以将评分进行排序，推荐给用户。这就是矩阵分解对于推荐系统最基本的用途。

B. 推荐系统中——矩阵分解

在推荐系统中，我们经常会拿到一种数据是user—item的表格，然后对应的是每位user对每个item的评分，如下图：

对于这个问题我们通常会选择矩阵分解的方法来解决。

我们常见的推荐系统矩阵分解有BPR、SVD（funkSVD）、ALS、NMF、WRMF。

接下来就来看看推荐系统中常用的几种矩阵分解的区别，主要通过公式、特点和适合哪种数据这几个方面来讲。

对于 矩阵 进行SVD分解，把矩阵 分解为：

其中 是矩阵 中较大的部分奇异值的个数，一般会远远的小于用户数和物品数。如果我们要预测第 个用户对第 个物品的评分 ,则只需要计算 即可。通过这种方法，我们可以将评分表里面所有没有评分的位置得到一个预测评分。通过找到最高的若干个评分对应的物品推荐给用户。

可以看出这种方法简单直接。但是有一个很大的问题我们忽略了，就是SVD分解要求矩阵是稠密的，也就是说矩阵的所有位置不能有空白。所以传统的SVD实际上在推荐系统中还是比较难用的。

前面说到，传统的SVD要求的矩阵是稠密的。那么我们现在要解决的问题就是避开矩阵稀疏的问题。

FunkSVD是将矩阵 分解为两个矩阵 ，这里采用了线性回归的思想。我们的目标是让用户的评分和用矩阵乘积得到的评分残差尽可能的小，也就是说，可以用均方差作为损失函数，来寻找最终的 。

对于某一个用户评分 ，用FunkSVD分解，则对应的表示为 ，采用均方差做为损失函数，则我们期望均方差尽可能小：

在实际应用中，我们为了防止过拟合，会加入一个L2的正则化项，因此正式的FunkSVD的优化目标函数 ：

其中 为正则化稀疏，需要调参。对于这个优化问题，我们一般通过梯度下降法来进行优化得到结果。

将上式分别对 求导，然后利用梯度下降法迭代， 的迭代公式如下：

还有许多基于FunkSVD的方法进行改进的，例如BiasSVD、SVD++等，这里就不细说了。

在很多推荐场景中，我们都是 基于现有的用户和商品之间的一些数据，得到用户对所有商品的评分，选择高分的商品推荐给用户 ，funkSVD算法的做法最基本的做法，使用起来十分有效，而且模型的可扩展性也非常优秀，其基本思想也能广泛运用于各种场景中。并且对于相似度计算方法的选择，有多种相似度计算方法，每种都有对应优缺点，可针对不同场景使用最适合的相似度计算方法。由于funkSVD时间复杂度高，训练速度较慢，可以使用梯度下降等机器学习相关方法来进行近似计算，以减少时间消耗。

参考： https://www.cnblogs.com/pinard/p/6351319.html

https://zhuanlan.hu.com/p/34497989

https://blog.csdn.net/syani/article/details/52297093

在有些推荐场景中，我们是为了在千万级别的商品中推荐个位数的商品给用户，此时，我们更关心的是用户来说，哪些极少数商品在用户心中有更高的优先级，也就是排序更靠前。也就是说，我们需要一个排序算法，这个算法可以把每个用户对应的所有商品按喜好排序。BPR就是这样的一个我们需要的 排序算法 。

在BPR算法中，我们将任意用户 对应的物品进行标记，如果用户 在同时有物品 和 的时候点击了 ，那么我们就得到了一个三元组 ，它表示对用户 来说， 的排序要比 靠前

BPR是基于矩阵分解的一种排序算法，但是和funkSVD之类的算法比，它不是做全局的评分优化，而是 针对每一个用户自己的商品喜好分贝做排序优化 。因此在迭代优化的思路上完全不同。同时对于训练集的要求也是不一样的， funkSVD只需要用户物品对应评分数据二元组做训练集，而BPR则需要用户对商品的喜好排序三元组做训练集 。

参考： https://www.cnblogs.com/pinard/p/9128682.html

ALS是交替最小二乘的简称。在机器学习中，ALS特指使用交替最小二乘求解的一个协同推荐算法。如：将用户（user）对商品（item）的评分矩阵分解成2个矩阵：user对item 潜在因素的偏好矩阵(latent factor vector)，item潜在因素的偏好矩阵。

假设有m个user和n个item，所以评分矩阵为R。ALS(alternating least squares)希望找到2个比较低纬度的矩阵（X和Y）来逼近这个评分矩阵R。

ALS的核心就是这样一个假设：打分矩阵是近似低秩的。换句话说，就是一个 的打分矩阵可以由分解的两个小矩阵 和 的乘积来近似。这就是ALS的矩阵分解方法。

为了让X和Y相乘能逼近R，因此我们需要最小化损失函数(loss function)，因此需要最小化损失函数，在此定义为平方误差和(Mean square error, MSE)。

一般损失函数都会需要加入正则化项(Regularization item)来避免过拟合的问题，通常是用L2，所以目标函数会被修改为：

上面介绍了“最小二乘（最小平方误差）”，但是还没有讲清楚“交替”是怎么回事。因为X和Y都是未知的参数矩阵，因此我们需要用“交替固定参数”来对另一个参数求解。

先固定Y, 将loss function对X求偏导，使其导数等于0：

再固定X, 将loss function对Y求偏导，使其导数等于0：

然后进行迭代。

在实际应用中，由于待分解的矩阵常常是非常稀疏的，与SVD相比， ALS能有效的解决过拟合问题 。基于ALS的矩阵分解的协同过滤算法的可扩展性也优于SVD。与随机梯度下降的求解方式相比，一般情况下随机梯度下降比ALS速度快；但有两种情况ALS更优于随机梯度下降：（1）当系统能够并行化时，ALS的扩展性优于随机梯度下降法。（2）ALS-WR能够有效的处理用户对商品的隐式反馈的数据。

但是ALS算法是无法准确评估新加入的用户或商品。这个问题也被称为冷启动问题。

参考： https://flashgene.com/archives/46364.html

https://flashgene.com/archives/52522.html

https://lumingdong.cn/recommendation-algorithm-based-on-matrix-decomposition.html#ALS

非负矩阵分解(Non-negative Matrix Factorization，NMF)算法，即NMF是在矩阵中所有元素均为非负数约束条件之下的矩阵分解方法。NMF中要求原始的矩阵V的所有元素的均是非负的，并且矩阵V可以分解出的两个小矩阵也是非负的，

给定一个打分矩阵R，NMF的目标是求解两个非负秩矩阵  最小化目标函数如下：

计算 的梯度如下：

其中：

采用梯度下降的参数优化方式, 可得W以及H的更新迭代方式见下式：

在矩阵分解基础上，加入了隐向量的非负限制。然后使用非负矩阵分解的优化算法求解。

要用NMF做矩阵分解有一个很大的前提—— 用户item之间的评分矩阵要求是非负并且分解出的小矩阵也要满足非负约束 。NMF分解是对原矩阵的近似还原分解，其存在的问题和ALS相像，对于未知的评分预测相当不准确。

参考： https://flashgene.com/archives/52522.html

http://tripleday.cn/2017/01/12/sparse-nmf/

在有些场景下，虽然 没有得到用户具体的评分，但是能够得到一些类似于“置信度”的信息（也称为隐式反馈信息） ，例如用户的游戏时长、观看时长等数据。虽然时长信息不能直接体现用户的喜好，但是能够说明用户喜欢的概率更大。在此场景下，用户-物品记录可以表示为一个置信度 和一个0-1指示量 （用户-物品是否有交互），如果用户-物品没有交互，那么置信度就为0。

“带权”就是根据置信度计算每条记录对应损失的权重，优化的目标函数如下：

权重通过置信度计算得到，可以使用 。由于未发生的交互也存在于损失函数中，因此惯用的随机梯度下降存在性能问题，为此采用ALS来优化模型，因此训练过程如下：

（1）更新每个用户的向量：

（2）更新每个物品的向量：

前面除了BPR以外，我们讲的算法都是针对显式反馈的评分矩阵的，因此当数据集只有隐式反馈时，应用上述矩阵分解直接建模会存在问题。而WRMF就可以解决隐式反馈的问题。

参考： https://sine-x.com/gorse-2/

https://flashgene.com/archives/52522.html

基于现有的用户和商品之间的一些数据，得到用户对所有商品的评分，选择高分的商品推荐给用户，可以根据以往的评分矩阵做全局的评分优化。有多种从SVD的改进算法可选择，如：表示biasSVD、SVD++、TimesSVD等

funkSVD可以解决矩阵稀疏的问题，但是其时间复杂度高，训练速度较慢，可以使用梯度下降等机器学习相关方法来进行近似计算，以减少时间消耗。

ALS算法和SVD的使用场景相似，也是基于用户——商品评分数据得到全局用户对商品的评分。

ALS能有效的解决过拟合问题，但是ALS算法是无法准确评估新加入的用户或商品。这个问题也被称为冷启动问题。

要用NMF做矩阵分解有一个很大的前提—— 用户item之间的评分矩阵要求是非负并且分解出的小矩阵也要满足非负约束 。NMF分解是对原矩阵的近似还原分解，NMF用法和SVD、ALS相似。

NMF存在的问题和ALS相像，对于未知的评分预测相当不准确。

BPR是基于矩阵分解的一种排序算法，但是，它不是做全局的评分优化，而是 针对每一个用户自己的商品喜好分贝做排序优化 。因此在迭代优化的思路上完全不同。 BPR需要用户对商品的喜好排序三元组做训练集 。

当 没有得到用户具体的评分，但是能够得到一些类似于隐式反馈信息时，就可使用WRMF进行矩阵分解。

C. 矩阵分解算法

矩阵分解算法主要用于解决协同过滤算法泛化能力弱的问题。

在现实中人和商品可以进行分类，比如将人分为偏好刺激的、偏好自然的，将电影分为恐怖的、温馨的。当我们以这样信息对人和物进行标定后就可以根据他们直接的距离来判断他们的相似程度。

一般协同过滤的思路通过物品找到相似的人，在给用户1推荐和他相似的用户喜欢的物品。

对用户和物品在映射到低维度下计算他们之间的距离。

原有的 大小的共现矩阵 ，我们的目标是将它分解为 , 表示降维后的用户矩阵， 表示降维后的物品矩阵, 表示降温的程度一般 是远小于 。

如何进行矩阵分解？接下来介绍几种策略

在推荐模型中出现矩阵分解思路时自然想到了SVD（奇异值分解），SVD可以将一个矩阵 分解为 的形式，D中主对角线上是从到到小排序的奇异值，我们选择前几个奇异值和对应U和V的向量这样实现了降让行茄维。

降维后的 可以作为用户矩阵,降维后的 可以作为物品矩阵。接着使用 , 公式对所有的用户产品组合进行评分，这样我们就把原共现矩阵中用户没有评分的物品也打上分了，利用这些评分就可以完成推荐。

问题就这样完美解决了？并不是。

矩阵 要进行SVD分解它就不能存在空的数据，而我们待分解的矩阵由于用户操作的低频特点，肯定会有空的位置出现，并且如果已经有了一个填满数据的共现矩阵，那就不用进行分解直接用就可以了。针对空数据可以采用填0、填平均值等方式暴力补全数据，但是这样的操作会影响准确度而且对越稀疏的矩阵影响越大，同时存放一个暴力填满的矩阵要求更多的存储空间，还有SVD的时间复杂度 也很可观。坦察

这个模型感觉和SVD关系不大了，他的目标是得到矩阵 和 ，这两个矩阵可以很好的反应已知的用户数据，根据以上目标构造待优化的目标函数

这里 表示用户评分样本集合。为了避免过拟合引入正则项后目标函数变为

接着利用梯度下降求解 和 。

Funk-SVD模式解决了SVD模型中空数据需要保留填写、SVD分解耗时、占用空间多的问题。同时考虑一些偏置。

用户偏置 ：一些用户喜欢打带知高分、一些用户喜欢打低分

物品偏置 ：一些电影普遍得分高

整体偏置 ：数据整体的平均得分

这样可以消除偏置，让预测更合理。

该模型依然存在利用信息有限的缺点。

深度学习推荐系统 王喆

推荐系统之矩阵分解家族

推荐系统实践 项亮

D. 推荐算法简介

写在最前面：本文内容主要来自于书籍《推荐系统实践》和《推荐系统与深度学习》。

推荐系统是目前互联网世界最常见的智能产品形式。从电子商务、音乐视频网站，到作为互联网经济支柱的在线广告和新颖的在线应用推荐，到处都有推荐系统的身影。推荐算法是推荐系统的核心，其本质是通过一定的方式将用户和物品联系起来，而不同的推荐系统利用了不同的方式。

推荐系统的主要功能是以个性化的方式帮助用户从极大的搜索空间中快速找到感兴趣的对象。因此，目前所用的推荐系统多为个性化推荐系统。个性化推荐的成功应用需要两个条件：

在推荐系统的众多算法中，基于协同的推荐和基于内容的推荐在实践中得到了最广泛的应用。本文也将从这两种算法开始，结合时间、地点上下文环境以及社交环境，对常见的推荐算法做一个简单的介绍。

基于内容的算法的本质是对物品内容进行分析，从中提取特征，然后基于用户对何种特征感兴趣来推荐含有用户感兴趣特征的物品。因此，基于内容的推荐算法有两个最基本的要求：

下面我们以一个简单的电影推荐来介绍基于内容的推荐算法。

现在有两个用户A、B和他们看过的电影以及打分情况如下：

其中问好（?）表示用户未看过。用户A对《银河护卫队 》《变形金刚》《星际迷航》三部科幻电影都有评分，平均分为 4 .7 分 （ (5+4+5 ) / 3=4.7 ）；对《三生三世》《美人鱼》《北京遇上西雅图》三部爱情电影评分平均分为 2.3 分 （ ( 3十2+2 ) /3=2.3 ）。现在需要给A推荐电影，很明显A更倾向于科幻电影，因此推荐系统会给A推荐独立日。而对于用户B，通过简单的计算我们可以知道更喜欢爱情电影，因此给其推荐《三生三世》。当然，在实际推荐系统中，预测打分比这更加复杂些，但是其原理是一样的。

现在，我们可以将基于内容的推荐归纳为以下四个步骤：

通过上面四步就能快速构建一个简单的推荐系统。基于内容的推荐系统通常简单有效，可解释性好，没有物品冷启动问题。但他也有两个明显的缺点：

最后，顺便提一下特征提取方法：对于某些特征较为明确的物品，一般可以直接对其打标签，如电影类别。而对于文本类别的特征，则主要是其主题情感等，则些可以通过tf-idf或LDA等方法得到。

基于协同的算法在很多地方也叫基于邻域的算法，主要可分为两种：基于用户的协同算法和基于物品的协同算法。

啤酒和尿布的故事在数据挖掘领域十分有名，该故事讲述了美国沃尔玛超市统计发现啤酒和尿布一起被购买的次数非常多，因此将啤酒和尿布摆在了一起，最后啤酒和尿布的销量双双增加了。这便是一个典型的物品协同过滤的例子。

基于物品的协同过滤指基于物品的行为相似度（如啤酒尿布被同时购买）来进行物品推荐。该算法认为，物品A和物品B具有很大相似度是因为喜欢物品A的用户大都也喜欢物品B。

基于物品的协同过滤算法主要分为两步：

基于物品的协同过滤算法中计算物品相似度的方法有以下几种：
（1）基于共同喜欢物品的用户列表计算。

此外，John S. Breese再其论文中还提及了IUF（Inverse User Frequence，逆用户活跃度）的参数，其认为活跃用户对物品相似度的贡献应该小于不活跃的用户，应该增加IUF参数来修正物品相似度的公式：

上面的公式只是对活跃用户做了一种软性的惩罚， 但对于很多过于活跃的用户， 比如某位买了当当网80%图书的用户， 为了避免相似度矩阵过于稠密， 我们在实际计算中一般直接忽略他的兴趣列表， 而不将其纳入到相似度计算的数据集中。

（2）基于余弦相似度计算。

（3）热门物品的惩罚。
从上面（1）的相似度计算公式中，我们可以发现当物品 i 被更多人购买时，分子中的 N(i) ∩ N(j) 和分母中的 N(i) 都会增长。对于热门物品，分子 N(i) ∩ N(j) 的增长速度往往高于 N(i)，这就会使得物品 i 和很多其他的物品相似度都偏高，这就是 ItemCF 中的物品热门问题。推荐结果过于热门，会使得个性化感知下降。以歌曲相似度为例，大部分用户都会收藏《小苹果》这些热门歌曲，从而导致《小苹果》出现在很多的相似歌曲中。为了解决这个问题，我们对于物品 i 进行惩罚，例如下式， 当α∈(0, 0.5) 时，N(i) 越小，惩罚得越厉害，从而使热门物品相关性分数下降（ 博主注：这部分未充分理解 ）：

此外，Kary pis在研究中发现如果将ItemCF的相似度矩阵按最大值归一化， 可以提高推荐的准确率。 其研究表明， 如果已经得到了物品相似度矩阵w， 那么可以用如下公式得到归一化之后的相似度矩阵w'：

归一化的好处不仅仅在于增加推荐的准确度，它还可以提高推荐的覆盖率和多样性。一般来说，物品总是属于很多不同的类，每一类中的物品联系比较紧密。假设物品分为两类——A和B， A类物品之间的相似度为0.5， B类物品之间的相似度为0.6， 而A类物品和B类物品之间的相似度是0.2。 在这种情况下， 如果一个用户喜欢了5个A类物品和5个B类物品， 用ItemCF给他进行推荐， 推荐的就都是B类物品， 因为B类物品之间的相似度大。 但如果归一化之后， A类物品之间的相似度变成了1， B类物品之间的相似度也是1， 那么这种情况下， 用户如果喜欢5个A类物品和5个B类物品， 那么他的推荐列表中A类物品和B类物品的数目也应该是大致相等的。 从这个例子可以看出， 相似度的归一化可以提高推荐的多样性。

那么，对于两个不同的类，什么样的类其类内物品之间的相似度高，什么样的类其类内物品相似度低呢？一般来说，热门的类其类内物品相似度一般比较大。如果不进行归一化，就会推荐比较热门的类里面的物品，而这些物品也是比较热门的。因此，推荐的覆盖率就比较低。相反，如果进行相似度的归一化，则可以提高推荐系统的覆盖率。

最后，利用物品相似度矩阵和用户打过分的物品记录就可以对一个用户进行推荐评分：

基于用户的协同算法与基于物品的协同算法原理类似，只不过基于物品的协同是用户U购买了A物品，会计算经常有哪些物品与A一起购买（也即相似度），然后推荐给用户U这些与A相似的物品。而基于用户的协同则是先计算用户的相似性（通过计算这些用户购买过的相同的物品），然后将这些相似用户购买过的物品推荐给用户U。

基于用户的协同过滤算法主要包括两个步骤：

步骤（1）的关键是计算用户的兴趣相似度，主要是利用用户的行为相似度计算用户相似度。给定用户 u 和 v，N(u) 表示用户u曾经有过正反馈（譬如购买）的物品集合，N(v) 表示用户 v 曾经有过正反馈的物品集合。那么我们可以通过如下的 Jaccard 公式简单的计算 u 和 v 的相似度：

或通过余弦相似度：

得到用户之间的相似度之后，UserCF算法会给用户推荐和他兴趣最相似的K个用户喜欢的物品。如下的公式度量了UserCF算法中用户 u 对物品 i 的感兴趣程度：

首先回顾一下UserCF算法和ItemCF算法的推荐原理：UserCF给用户推荐那些和他有共同兴趣爱好的用户喜欢的物品， 而ItemCF给用户推荐那些和他之前喜欢的物品具有类似行为的物品。

（1）从推荐场景考虑
首先从场景来看，如果用户数量远远超过物品数量，如购物网站淘宝，那么可以考虑ItemCF，因为维护一个非常大的用户关系网是不容易的。其次，物品数据一般较为稳定，因此物品相似度矩阵不必频繁更新，维护代价较小。

UserCF的推荐结果着重于反应和用户兴趣相似的小群体的热点，而ItemCF的推荐结果着重于维系用户的历史兴趣。换句话说，UserCF的推荐更社会化，反应了用户所在小型兴趣群体中物品的热门程度，而ItemCF的推荐更加个性化，反应了用户自己的个性传承。因此UserCF更适合新闻、微博或微内容的推荐，而且新闻内容更新频率非常高，想要维护这样一个非常大而且更新频繁的表无疑是非常难的。

在新闻类网站中，用户的兴趣爱好往往比较粗粒度，很少会有用户说只看某个话题的新闻，而且往往某个话题也不是每天都会有新闻。 个性化新闻推荐更强调新闻热点，热门程度和时效性是个性化新闻推荐的重点，个性化是补充，所以 UserCF 给用户推荐和他有相同兴趣爱好的人关注的新闻，这样在保证了热点和时效性的同时，兼顾了个性化。

（2）从系统多样性（也称覆盖率，指一个推荐系统能否给用户提供多种选择）方面来看，ItemCF的多样性要远远好于UserCF，因为UserCF更倾向于推荐热门物品。而ItemCF具有较好的新颖性，能够发现长尾物品。所以大多数情况下，ItemCF在精度上较小于UserCF，但其在覆盖率和新颖性上面却比UserCF要好很多。

在介绍本节基于矩阵分解的隐语义模型之前，让我们先来回顾一下传统的矩阵分解方法SVD在推荐系统的应用吧。

基于SVD矩阵分解在推荐中的应用可分为如下几步：

SVD在计算前会先把评分矩阵 A 缺失值补全，补全之后稀疏矩阵 A 表示成稠密矩阵，然后将分解成 A' = U∑V T 。但是这种方法有两个缺点：（1）补成稠密矩阵后需要耗费巨大的储存空间，对这样巨大的稠密矩阵进行储存是不现实的；（2）SVD的计算复杂度很高，对这样大的稠密矩阵中进行计算式不现实的。因此，隐语义模型就被发明了出来。

更详细的SVD在推荐系统的应用可参考 奇异值分解SVD简介及其在推荐系统中的简单应用 。

隐语义模型（Latent Factor Model）最早在文本挖掘领域被提出，用于找到文本的隐含语义。相关的算法有LSI，pLSA，LDA和Topic Model。本节将对隐语义模型在Top-N推荐中的应用进行详细介绍，并通过实际的数据评测该模型。

隐语义模型的核心思想是通过隐含特征联系用户兴趣和物品。让我们通过一个例子来理解一下这个模型。

现有两个用户，用户A的兴趣涉及侦探小说、科普图书以及一些计算机技术书，而用户B的兴趣比较集中在数学和机器学习方面。那么如何给A和B推荐图书呢？

我们可以对书和物品的兴趣进行分类。对于某个用户，首先得到他的兴趣分类，然后从分类中挑选他可能喜欢的物品。简言之，这个基于兴趣分类的方法大概需要解决3个问题：

对于第一个问题的简单解决方案是找相关专业人员给物品分类。以图书为例，每本书出版时，编辑都会给出一个分类。但是，即使有很系统的分类体系，编辑给出的分类仍然具有以下缺点：（1）编辑的意见不能代表各种用户的意见；（2）编辑很难控制分类的细粒度；（3）编辑很难给一个物品多个分类；（4）编辑很难给一个物品多个分类；（5）编辑很难给出多个维度的分类；（6）编辑很难决定一个物品在某一个类别中的权重。

为了解决上述问题，研究员提出可以从数据出发，自动找到那些分类，然后进行个性化推荐。隐语义模型由于采用基于用户行为统计的自动聚类，较好地解决了上面提出的5个问题。

LFM将矩阵分解成2个而不是3个：

推荐系统中用户和物品的交互数据分为显性反馈和隐性反馈数据。隐式模型中多了一个置信参数，具体涉及到ALS（交替最小二乘法，Alternating Least Squares）中对于隐式反馈模型的处理方式——有的文章称为“加权的正则化矩阵分解”：

一个小细节：在隐性反馈数据集中，只有正样本（正反馈）没有负反馈（负样本），因此如何给用户生成负样本来进行训练是一个重要的问题。Rong Pan在其文章中对此进行了探讨，对比了如下几种方法：

用户行为很容易用二分图表示，因此很多图算法都可以应用到推荐系统中。基于图的模型（graph-based model）是推荐系统中的重要内容。很多研究人员把基于领域的模型也称为基于图的模型，因为可以把基于领域的模型看作基于图的模型的简单形式。

在研究基于图的模型之前，需要将用户行为数据表示成图的形式。本节的数据是由一系列用户物品二元组 (u, i) 组成的，其中 u 表示用户对物品 i 产生过行为。

令 G(V, E) 表示用户物品二分图，其中 V=V U UV I 由用户顶点 V U 和物品节点 V I 组成。对于数据集中每一个二元组 (u, i) ，图中都有一套对应的边 e(v u , v i )，其中 v u ∈V U 是用户对应的顶点，v i ∈V I 是物品i对应的顶点。如下图是一个简单的物品二分图，其中圆形节点代表用户，方形节点代表物品，用户物品的直接连线代表用户对物品产生过行为。比如下图中的用户A对物品a、b、d产生过行为。

度量图中两个顶点之间相关性的方法很多，但一般来说图中顶点的相关性主要取决于下面3个因素：

而相关性高的一对顶点一般具有如下特征：

举个例子，如下图，用户A和物品c、e没有边直连，但A可通过一条长度为3的路径到达c，而Ae之间有两条长度为3的路径。那么A和e的相关性要高于顶点A和c，因而物品e在用户A的推荐列表中应该排在物品c之前，因为Ae之间有两条路径。其中，（A,b,C,e）路径经过的顶点的出度为（3，2，2，2），而 (A,d,D,e) 路径经过了一个出度比较大的顶点D，所以 (A,d,D,e) 对顶点A与e之间相关性的贡献要小于（A,b,C,e）。

基于上面3个主要因素，研究人员设计了很多计算图中顶点相关性的方法，本节将介绍一种基于随机游走的PersonalRank算法。

假设要给用户u进行个性化推荐，可以从用户u对应的节点 v u 开始在用户物品二分图上进行随机游走。游走到任一节点时，首先按照概率α决定是继续游走还是停止这次游走并从 v u 节点重新开始游走。若决定继续游走，则从当前节点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。这样，经过很多次随机游走后，每个物品被访问到的概率会收敛到一个数。最终的推荐列表中物品的权重就是物品节点的访问概率。

上述算法可以表示成下面的公式：

虽然通过随机游走可以很好地在理论上解释PersonalRank算法，但是该算法在时间复杂度上有明显的缺点。因为在为每个用户进行推荐时，都需要在整个用户物品二分图上进行迭代，知道所有顶点的PR值都收敛。这一过程的时间复杂度非常高，不仅无法在线进行实时推荐，离线计算也是非常耗时的。

有两种方法可以解决上面PersonalRank时间复杂度高的问题：
（1）减少迭代次数，在收敛之前停止迭代。但是这样会影响最终的精度。

（2）从矩阵论出发，重新涉及算法。另M为用户物品二分图的转移概率矩阵，即：

网络社交是当今社会非常重要甚至可以说是必不可少的社交方式，用户在互联网上的时间有相当大的一部分都用在了社交网络上。

当前国外最着名的社交网站是Facebook和Twitter，国内的代表则是微信/QQ和微博。这些社交网站可以分为两类：

需要指出的是，任何一个社交网站都不是单纯的社交图谱或兴趣图谱。如QQ上有些兴趣爱好群可以认识不同的陌生人，而微博中的好友也可以是现实中认识的。

社交网络定义了用户之间的联系，因此可以用图定义社交网络。我们用图 G(V,E,w) 定义一个社交网络，其中V是顶点集合，每个顶点代表一个用户，E是边集合，如果用户va和vb有社交网络关系，那么就有一条边 e(v a , v b ) 连接这两个用户，而 w(v a , v b )定义了边的权重。一般来说，有三种不同的社交网络数据：

和一般购物网站中的用户活跃度分布和物品流行度分布类似，社交网络中用户的入度（in degree，表示有多少人关注）和出度（out degree，表示关注多少人）的分布也是满足长尾分布的。即大部分人关注的人都很少，被关注很多的人也很少。

给定一个社交网络和一份用户行为数据集。其中社交网络定义了用户之间的好友关系，而用户行为数据集定义了不同用户的历史行为和兴趣数据。那么最简单的算法就是给用户推荐好友喜欢的物品集合。即用户u对物品i的兴趣 p ui 可以通过如下公式计算。

用户u和用户v的熟悉程度描述了用户u和用户在现实社会中的熟悉程度。一般来说，用户更加相信自己熟悉的好友的推荐，因此我们需要考虑用户之间的熟悉度。下面介绍3中衡量用户熟悉程度的方法。

（1）对于用户u和用户v，可以使用共同好友比例来计算他们的相似度：

上式中 out(u) 可以理解为用户u关注的用户合集，因此 out(u) ∩ out(v) 定义了用户u、v共同关注的用户集合。

（2）使用被关注的用户数量来计算用户之间的相似度，只要将公式中的 out(u) 修改为 in(u)：

in(u) 是指关注用户u的集合。在无向社交网络中，in(u)和out(u)是相同的，而在微博这种有向社交网络中，这两个集合的含义就不痛了。一般来说，本方法适合用来计算微博大V之间的相似度，因为大v往往被关注的人数比较多；而方法（1）适用于计算普通用户之间的相似度，因为普通用户往往关注行为比较丰富。

（3）除此之外，还可以定义第三种有向的相似度：这个相似度的含义是用户u关注的用户中，有多大比例也关注了用户v：

这个相似度有一个缺点，就是在该相似度下所有人都和大v有很大的相似度，这是因为公式中的分母并没有考虑 in(v) 的大小，所以可以把 in(v) 加入到上面公式的分母，来降低大v与其他用户的相似度：

上面介绍了3种计算用户之间相似度（或称熟悉度）的计算方法。除了熟悉程度，还需要考虑用户之间的兴趣相似度。我们和父母很熟悉，但很多时候我们和父母的兴趣确不相似，因此也不会喜欢他们喜欢的物品。因此，在度量用户相似度时，还需要考虑兴趣相似度，而兴趣相似度可以通过和UserCF类似的方法度量，即如果两个用户喜欢的物品集合重合度很高，两个用户的兴趣相似度很高。

最后，我们可以通过加权的形式将两种权重合并起来，便得到了各个好有用户的权重了。

有了权重，我们便可以针对用户u挑选k个最相似的用户，把他们购买过的物品中，u未购买过的物品推荐给用户u即可。打分公式如下：

其中 w' 是合并后的权重，score是用户v对物品的打分。

node2vec的整体思路分为两个步骤：第一个步骤是随机游走（random walk），即通过一定规则随机抽取一些点的序列；第二个步骤是将点的序列输入至word2vec模型从而得到每个点的embedding向量。

随机游走在前面基于图的模型中已经介绍过，其主要分为两步：（1）选择起始节点；（2）选择下一节点。起始节点选择有两种方法：按一定规则抽取一定量的节点或者以图中所有节点作为起始节点。一般来说会选择后一种方法以保证所有节点都会被选取到。

在选择下一节点方法上，最简单的是按边的权重来选择，但在实际应用中需要通过广度优先还是深度优先的方法来控制游走范围。一般来说，深度优先发现能力更强，广度优先更能使社区内（较相似）的节点出现在一个路径里。

斯坦福大学Jure Leskovec教授给出了一种可以控制广度优先或者深度优先的方法。

以上图为例，假设第一步是从t随机游走到v，这时候我们要确定下一步的邻接节点。本例中，作者定义了p和q两个参数变量来调节游走，首先计算其邻居节点与上一节点t的距离d，根据下面的公式得到α：

一般从每个节点开始游走5~10次，步长则根据点的数量N游走根号N步。如此便可通过random walk生成点的序列样本。

得到序列之后，便可以通过word2vec的方式训练得到各个用户的特征向量，通过余弦相似度便可以计算各个用户的相似度了。有了相似度，便可以使用基于用户的推荐算法了。

推荐系统需要根据用户的历史行为和兴趣预测用户未来的行为和兴趣，因此大量的用户行为数据就成为推荐系统的重要组成部分和先决条件。如何在没有大量用户数据的情况下设计个性化推荐系统并且让用户对推荐结果满意从而愿意使用推荐系统，就是冷启动问题。

冷启动问题主要分为三类：

针对用户冷启动，下面给出一些简要的方案：
（1）有效利用账户信息。利用用户注册时提供的年龄、性别等数据做粗粒度的个性化；
（2）利用用户的社交网络账号登录（需要用户授权），导入用户在社交网站上的好友信息，然后给用户推荐其好友喜欢的物品；
（3）要求用户在登录时对一些物品进行反馈，手机用户对这些物品的兴趣信息，然后给用推荐那些和这些物品相似的物品；
（4）提供非个性化推荐。非个性化推荐的最简单例子就是热门排行榜，我们可以给用户推荐热门排行榜，然后等到用户数据收集到一定的时候，在切换为个性化推荐。

对于物品冷启动，可以利用新加入物品的内容信息，将它们推荐给喜欢过和他们相似的物品的用户。

对于系统冷启动，可以引入专家知识，通过一定高效的方式快速建立起物品的相关度表。

在上面介绍了一些推荐系统的基础算法知识，这些算法大都是比较经典且现在还在使用的。但是需要注意的是，在实践中，任何一种推荐算法都不是单独使用的，而是将多种推荐算法结合起来，也就是混合推荐系统，但是在这里并不准备介绍，感兴趣的可以查阅《推荐系统》或《推荐系统与深度学习》等书籍。此外，在推荐中非常重要的点击率模型以及基于矩阵的一些排序算法在这里并没有提及，感兴趣的也可自行学习。

虽然现在用的很多算法都是基于深度学习的，但是这些经典算法能够让我们对推荐系统的发展有一个比较好的理解，同时，更重要的一点——“推陈出新”，只有掌握了这些经典的算法，才能提出或理解现在的一些更好地算法。

E. 正定矩阵因子分解法（PMF）

3.2.4.1 方法建立

就全国范围而言，我国地下水质量总体较好，根据国家《地下水质量标准》（GB/T 14848—93），我国63%的地区地下水可直接饮用，17%经适当处理后可供饮用，12%不宜饮用，剩余8%为天然的咸水和盐水，由此可见，不宜饮用的地下水和天然咸水、盐水占到了20%，对于这些地下水型水源地饮用水指标并不一定受到污染而存在超标现象，其水质可能受到地下水形成演化影响更为明显，因此，考虑选择反映地下水形成、演化的地下水水化学类型常规指标，进行影响因素解析。地下水水质指标在取样与分析过程中，由于取样和样品处理、试剂和水纯度、仪器量度和仪器洁净、采用的分析方法、测定过程以及数据处理等过程均会产生测量误差（系统误差，随机误差，过失误差）。从取样到分析结果计算误差都绝对存在，虽然在各个过程中进行质量控制，但无法完全消除不确定性的影响，为确保分析结果的可靠性，采用PMF法对地下水水质指标考虑一定的不确定性误差，使分析数据能够准确地反映实际情况。

PMF（Positive Matrix Factorization）与主成分分析（PCA）、因子分析（FA）都是利用矩阵分解来解决实际问题的分析方法，在这些方法中，原始的大矩阵被近似分解为低秩的V＝WH形式。但PMF与PCA和FA不同，PCA、FA方法中因子W和H中的元素可为正或负，即使输入的初始矩阵元素全是正的，传统的秩削减算法也不能保证原始数据的非负性。在数学上，从计算的观点看，分解结果中存在负值是正确的，但负值元素在实际问题中往往是没有意义的。PMF是在矩阵中所有元素均为非负数约束条件之下的矩阵分解方法，在求解过程中对因子载荷和因子得分均做非负约束，避免矩阵分解的结果中出现负值，使得因子载荷和因子得分具有可解释性和明确的物理意义。PMF使用最小二乘方法进行迭代运算，能够同时确定污染源谱和贡献，不需要转换就可以直接与原始数据矩阵作比较，分解矩阵中元素非负，使得分析的结果明确而易于解释，可以利用不确定性对数据质量进行优化，是美国国家环保局（EPA）推荐的源解析工具。

3.2.4.2 技术原理

PMF：模型是一种基于因子分析的方法，具有不需要测量源指纹谱、分解矩阵中元素非负、可以利用数据标准偏差来进行优化等优点。目前PMF模型此方法成功用于大气气溶胶、土壤和沉积物中持久性有毒物质的源解析，已有成熟的应用模型 PMF1.1，PMF2.0，PMF3.0等。PMF模型基本方程为：

X_nm＝G_npF_pm+E （3.7）

式中：n——取样点数；

m——各取样点测试的成分数量；

p——污染源个数；

X_nm——取样点各成分含量；

G_np——主要源的贡献率；

F_pm——源指纹图谱。

基本计算过程如下：

1）样品数据无量纲化，无量纲化后的样品数据矩阵用D表示。

2）协方差矩阵求解，为计算特征值和特征向量，可先求得样品数据的协方差矩阵，用D′为D的转置，算法为：

Z＝DD′ （3.8）

3）特征值及特征向量求解，用雅各布方法可求得协方差矩阵Z的特征值矩阵E和特征向量矩阵Q，Q′表示Q的转置。这时，协方差矩阵可表示为：

Z＝QEQ′ （3.9）

4）主要污染源数求解，为使高维变量空间降维后能尽可能保留原来指标信息，利用累计方差贡献率提取显着性因子，判断条件为：

地下水型饮用水水源地保护与管理：以吴忠市金积水源地为例

式中：n——显着性因子个数；

m——污染物个数；

λ——特征值。

5）因子载荷矩阵求解，提取显着性因子后，利用求解得到的特征值矩阵E和特征向量矩阵Q进一步求得因子载荷矩阵S和因子得分矩阵C，这时，因子载荷矩阵可表示为：

S＝QE^1/2 （3.11）

因子得分矩阵可表示为：

C＝（S′S）^-1S′D （3.12）

6）非负约束旋转，由步骤5求得的因子载荷矩阵S和因子得分矩阵C分别对应主要污染源指纹图谱和主要污染源贡献，为解决其值可能为负的现象，需要做非负约束的旋转。

7）首先利用转换矩阵T₁对步骤5求得的因子载荷矩阵S和因子得分矩阵C按下式进行旋转：

地下水型饮用水水源地保护与管理：以吴忠市金积水源地为例

C₁＝T₁C （3.14）

式中：S₁——旋转后的因子载荷矩阵；

C₁——旋转后的因子得分矩阵；

T₁——转换矩阵，且T₁＝（C^∗C′）（C^∗C′）^-1（其中：C^∗为把C中的负值替换为零后的因子得分矩阵）。

8）利用步骤7中旋转得到的因子载荷矩阵S₁构建转换矩阵T₂对步骤5中旋转得到的因子载荷矩阵S₁和因子得分矩阵C₁继续旋转：

S₂＝S₁T₂ （3.15）

地下水型饮用水水源地保护与管理：以吴忠市金积水源地为例

式中：S₂——二次旋转后的因子载荷矩阵；

C₂——二次旋转后的因子得分矩阵；

T₂——二次转换矩阵，且T₂＝（S′₁+S₁）^-1（S′₁+

）（其中：

为S₁中的负值换为零后的因子载荷矩阵）。

9）：重复步骤7、8，直到因子载荷中负值的平方和小于某一设定的误差精度e而终止，最终得到符合要求的因子载荷矩阵S，即主要污染源指纹图谱。

3.2.4.3 方法流程

针对受体采样数据直接进行矩阵分解，得到各污染源组分及其贡献率的统计方法（图3.5）。

图3.5 方法流程图

（1）缺失值处理

正定矩阵因子分析是基于多元统计的分析方法，对数据有效性具有一定的要求，因此在进行分析之前首先对数据进行预处理。根据已有数据的特征结合实际情况主要有以下5种处理方法。

1）采样数据量充足的情况下直接丢弃含缺失数据的记录。

2）存在部分缺失值情况下用全局变量或属性的平均值来代替所有缺失数据。把全局变量或是平均值看作属性的一个新值。

3）先根据欧式距离或相关分析来确定距离具有缺失数据样本最近的K个样本，将这K个值加权平均来估计该样本的缺失数据。

4）采用预测模型来预测每一个缺失数据。用已有数据作为训练样本来建立预测模型，如神经网络模型预测缺失数据。该方法最大限度地利用已知的相关数据，是比较流行的缺失数据处理技术。

5）对低于数据检测限的数据可用数据检测限值或1/2检测限以及更小比例检测限值代替。

（2）不确定性处理

计算数据不确定性。

地下水型饮用水水源地保护与管理：以吴忠市金积水源地为例

式中：s——误差百分数；

c——指标浓度值；

l——因子数据检出限。

（3）数据合理性分析

本研究所用数据在放入模型前以信噪比S/N（Signal to Noise）作为标准进行筛选，信噪比S/N为：

地下水型饮用水水源地保护与管理：以吴忠市金积水源地为例

式中：x_ij——第i采样点第j个样品的浓度；

s_ij——第i采样点第j个样品的标准偏差。

信噪比小，说明样品的噪声大，信噪比越大则表示样品检出的可能性越大，越适合模型。

（4）数据输入及因子分析

与其他因子分析方法一样，PMF不能直接确定因子数目。确定因子数目的一般方法是尝试多次运行软件，根据分析结果和误差，Q值以及改变因子数目时Q值的相对变化等来确定合理的因子数目。

3.2.4.4 适用范围

PMF对污染源和贡献施加了非负限制，并考虑了原始数据的不确定性，对数据偏差进行了校正，使结果更具有科学的解释。PMF使用最小二乘方法，得到的污染源不需要转换就可以直接与原始数据矩阵作比较，PMF方法能够同时确定污染源和贡献，而不需要事先知道源成分谱。适用于水文地质条件简单，观测数据量较大，污染源和污染种类相对较少的地区，运用简便，可应用分析软件进行计算。

3.2.4.5 NMF 源解析

NMF在实现上较PMF算法简单易行，非负矩阵分解根据目的的不同大致可以分为两种：一是在保证数据某些性质的基础上，将高维空间的样本点映射到某个低维空间上，除去一些不重要的细节，获得原数据的本质信息；二是在从复杂混乱的系统中得到混合前的独立信息的种类和强度。因此，基于非负矩阵分解过程应用领域的不同，分解过程所受的约束和需要保留的性质都不相同。本书尝试性地将NMF算法应用于水质影响因素的分离计算中（表3.2）。

表3.2 RMF矩阵分解权值表

依照非负矩阵分解理论的数学模型，寻找到一个分解过程V≈WH，使WH和V无限逼近，即尽可能缩小二者的误差。在确保逼近的效果，定义一个相应的衡量标准，这个衡量标准就叫作目标函数。目标函数一般采用欧氏距离和散度偏差来表示。在迭代过程中，采用不同的方法对矩阵W和H进行初始化，得到的结果也会不同，算法的性能主要取决于如何对矩阵W和H进行初始化。传统的非负矩阵算法在对矩阵W和H赋初值时采用随机方法，这样做虽然简单并且容易实现，但实验的可重复性以及算法的收敛速度是无法用随机初始化的方法来控制的，所以这种方法并不理想。许多学者提出改进W和H的初始化方法，并发展出专用性比较强的形式众多的矩阵分解算法，主要有以下几种：局部非负矩阵分解（Local Non-negative Matrix Factorization，LNMF）、加权非负矩阵分解（Weighted Non-negative Matrix Factorization，WNMF）、Fisher非负矩阵分解（Fisher Non-negative Matrix Factorization，FNMF）、稀疏非负矩阵分解（Sparse Non-negative Matrix Factorization，SNMF）、受限非负矩阵分解（Constrained Non-negative Matrix Factorization，CNMF）、非平滑非负矩阵分解（Non-smooth Non-negative Matrix Factorization，NSNMF）、稀疏受限非负矩阵分解（Nonnegative Matrix Factorization with Sparseness Constraints，NMF-SC）等理论方法，这些方法针对某一具体应用领域对NMF算法进行了改进。

本书尝试应用MATLAB工具箱中NNMF程序与改进的稀疏非负矩阵分解（SNMF）对研究区11项指标（同PMF数据）进行分解，得到各元素在综合成分中的得分H，初始W₀，H₀采用随机法取初值。r为分解的基向量个数，合适的r取值主要根据试算法确定，改变r值观察误差值变化情况，本书利用SMNF算法计算时，r分别取2，3，4，采用均方误差对迭代结果效果进行评价，结果显示当r取2，4时误差值为0.034，取3时误差值为0.016，因此r＝3是较合理的基向量个数。采用NNMF算法进行计算时，利用MATLAB工具箱提供的两种计算法分别进行计算，乘性法则（Multiplicative Update Algorithm）计算结果误差项比最小二乘法（Alternating Least-squares Algorithm）计算误差值小且稳定，但总体NNMF计算误差较大，改变初始W₀，H₀取值和增加迭代次数误差均未明显减小，调整r取值，随着r值的增大误差逐渐减小。

对比SNMF和NNMF算法所得权值结果，两种方法所得权值趋势一致，但得分值有所不同，由于SNMF算法对矩阵进行了稀疏性约束，计算结果中较小的权值更趋近于0，两次结果中在三个基向量上总体权值较大的元素项为T-Hard、

、Mg²⁺、Ca²⁺、

，从盲源分离的角度来看该几种元素对地下水具有较大的影响，但从地下水水质影响因素来看，该方法对数据的分析偏重于突出局部数据的特征，在各因素相关性较大但含量不高的情况下，容易忽略了关键的影响因素。从权值得分来看，SNMF法解析的第一个基向量上的元素包括EC、T-Hard、NH₄—N、

、

、TDS；第二基向量主要有Na⁺、Mg²⁺、Cl^-；第三个基向量

、Ca²⁺，从结果可以看出该方法进行矩阵分解并未得到可合理解释的源项结果，方法有待进一步研究及验证。

F. 【转】矩阵分解之SVD和SVD++

前面的内容是关于近邻推荐的相关知识，来看下另外一种推荐方法：矩阵分解。

协同过滤可以解决我们关注的很多问题，但是仍然有一些问题存在，比如：

上述两个问题，在矩阵分解中可以得到解决。原始的矩阵分解只适用于评分预测问题，这里所讨论的也只是针对于评分预测问题。常用的分解算法有SVD和SVD++。

矩阵分解，简单来说，就是把原来的大矩阵，近似分解成两个小矩阵的乘积，在实际推荐计算时不再使用大矩阵，而是使用分解得到的两个小矩阵。

具体来说，假设用户物品评分矩阵为 R，形状为 mxn，即 m 个用户， n 个物品。我们选择一个很小的数 k，k 比 m 和 n 都小很多，然后通过算法生成两个矩阵 P 和 Q，这两个矩阵的要求如下：P 的形状是 mxk，Q 的形状是 nxk， P 和 Q 的转置相乘结果为 R。也就是说分解得到的矩阵P和Q可以还原成原始的矩阵R。

用公式来描述就是：

其中 R 表示真实的用户评分矩阵，一般有很多缺失值（缺失值表示用户没有对该物品评分），带尖帽的 R 表示使用分解矩阵预测的用户评分矩阵，它补全了所有的缺失值。

从另一个角度来看，矩阵分解就是把用户和物品都映射到一个 k 维空间中（这里映射后的结果用户用矩阵P表示，物品用矩阵Q表示），这个 k 维空间不是我们直接看得到的，也不一定具有非常好的可解释性，每一个维度也没有名字，所以常常叫做隐因子。用户向量代表了用户的兴趣，物品向量代表了物品的锋帆特点，且每一个维度相互对应，两个向量的内积表示用户对该物品的喜好程度。

SVD 全程奇异值分解，原本是是线性代数中的一个知识，在推荐算法中用到的 SVD 并非正统的奇异值分解。

前面已经知道通过矩阵分解，可以得到用户矩阵和物品矩阵。针对每个用户和物品，假设分解后得到的用户 u 的向量为 p_u，物品 i 的向量为 q_i，那么用户 u 对物品 i 的评分为：

其中，K 表示隐因子个数。

问题关键来了，如何为每个用户和物品生成k维向量呢？这个问题可以转化成桐瞎机器学习问题，要解决机器学习问题，就需要寻找损失函数以及优化算法。

这里单个用户对单个物品的真实评分与预测评分之间的差值记为 e{ui}。

将所有用户对物品的真实评分与预测评分之间的差值的平方之和作为损失函数，即

其中，R 表示所有的用户对所有物品的评分集合，K 表示隐因子个数。

我们要做的就是求出用户向量 p_u 和物品向量 q_i ，来保证损失函数结果最小。

求解损失函数优化算法常用的选择有两个，一个是梯度下降（GD），另一个是交替最小二乘（ALS） 。这里以梯度下降为例。

梯度下降算法的一个关键点在于计算损失函数对于每个参数的梯度。

在实际应用中，会存在以下情况：相比于其他用户，有些用户给分就是偏高或偏低。相比于其他物品，有些物品就是能得到偏高的评分。所以使用 pu*qi^T 来定义评分是有失偏颇的。我们可以认为 评分 = 兴趣 + 偏见。

其局基空中，μ表示全局均值， bu表示用户偏见，bi表示物品偏见。

举例来说，一个电影网站全局评分为 3.5 分，你评分电影时比较严格，一般打分比平均分都要低 0.5，《肖申克的救赎》的平均分比全局平均分要高 1 分。这里 u=3.5，bu=-0.5，bi=1分。

实际生产中，用户评分数据很稀少，也就是说显式数据比隐式数据少很多，这些隐式数据能否加入模型呢？

SVD++ 就是在 SVD 模型中融入用户对物品的隐式行为。我们可以认为 评分=显式兴趣 + 隐式兴趣 + 偏见。

那么隐式兴趣如何加入到模型中呢？首先，隐式兴趣对应的向量也是 k 维，它由用户有过评分的物品生成。

其中，|N(u)|表示用户u的行为物品集，yj表示物品j所表达的隐式反馈。

介绍了在评分数据中非常受欢迎 SVD 算法以及改进。比如加入偏置信息，考虑隐式反馈等。

推荐系统百问百答

参考：

G. 矩阵分解的一点总结

------------------------------------------------------------------------------------------------------------------------------------------------

对于推荐系统来说存在两大场景即评分预测（rating prediction）与Top-N推荐（item recommendation，item ranking）。矩阵分解主要应用于评分预测场景。

推荐系统的评分预测场景可看做是一个矩阵补全的游戏，矩阵补全是推荐系统的任务，矩阵分解是其达到目的的手段。因此，矩阵分解是为了更好的完成矩阵补全任务（欲其补全，先其分解之）。之所以可以利用矩阵分解来完成矩阵补全的操作，那是因为基于这样的假设：假设UI矩阵是低秩的，即在大千世界中，总会存在相似的人或物，即物以类聚，人以群分，然后我们可以利用两个小矩阵相乘来还原它。

矩阵分解就是把原来的大矩阵，近似的分解成小矩阵的乘积，在实际推荐计算时不再使用大矩阵，而是使用分解得到的两个小矩阵。

具体来说就是，假设用户物品的评分矩阵A是m乘n维，即一共有m个用户，n个物品.通过一套算法转化为两个矩阵U和V,矩阵U的维度是m乘k，矩阵V的维度是n乘k。

这两个矩阵的要求就是通过下面这个公式可以复原矩阵A:

说起矩阵分解，我们第一个想起的就是SVD。

SVD分解的形式为3个矩阵相乘，左右两个矩阵分别表示用户/项目隐含橘巧因子矩阵，中间矩阵为奇异值矩阵并且是对角矩阵，每个元素满足非负性，并且逐渐减小。因此我们可以只需要前个K因子来表示它。

但SVD分解要求矩阵是稠密的，也就是说矩阵的所有位置不能有空白。有空白时我们的M是没法直接去SVD分解的。大家会说，如果这个矩阵是稠密的，那不就是说我们都已经找到所有用户物品的评分了嘛，那还要SVD干嘛! 的确，这是一个问题，传统SVD采用的方法是对评分矩阵中的缺失值进行简单的补全，比如用全局平均值或者用用户物品平均值补全，得到补全后的矩阵。接着可以用SVD分解并降燃伍逗维。

虽然有了上面的补全策略，我们的传统SVD在推荐算法上还是较难使用。因为我们的用户数和物品一般都是超级大，随便就成千上万了。这么大一个矩阵做SVD分解是非常耗时的。那么有没有简化版的矩阵分解可以用呢？我们下面来看看实际可以用于推荐系统的矩阵分解。

FunkSVD是在传统SVD面临计算效率问题时提出来的，既然将一个矩阵皮卖做SVD分解成3个矩阵很耗时，同时还面临稀疏的问题，那么我们能不能避开稀疏问题，同时只分解成两个矩阵呢？也就是说，现在期望我们的矩阵M这样进行分解：

SVD分解已经很成熟了，但是FunkSVD如何将矩阵M分解为P和Q呢？这里采用了线性回归的思想。目标是让用户的评分和用矩阵乘积得到的评分残差尽可能的小，也就是说，可以用均方差作为损失函数，来寻找最终的P和Q。

在实际应用中，为了防止过拟合，会加入一个L2的正则化项。加入了正则化系数，需要调参。对于这个优化问题，一般通过梯度下降法来进行优化得到结果。

在FunkSVD算法火爆之后，出现了很多FunkSVD的改进版算法。其中BiasSVD算是改进的比较成功的一种算法。BiasSVD假设评分系统包括三部分的偏置因素：一些和用户物品无关的评分因素，用户有一些和物品无关的评分因素，称为用户偏置项。而物品也有一些和用户无关的评分因素，称为物品偏置项。这其实很好理解。比如一个垃圾山寨货评分不可能高，自带这种烂属性的物品由于这个因素会直接导致用户评分低，与用户无关。

一个用户给一个物品的评分会由四部分相加：

从左到右分别代表：全局平均分、物品的评分偏置、用户的评分偏置、用户和物品之间的兴趣偏好

BiasSVD增加了一些额外因素的考虑，因此在某些场景会比FunkSVD表现好。

SVD++算法在BiasSVD算法上进一步做了增强，这里它增加考虑用户的隐式反馈。它是基于这样的假设：用户除了对于项目的显式历史评分记录外，浏览记录或者收藏列表等隐反馈信息同样可以从侧面一定程度上反映用户的偏好，比如用户对某个项目进行了收藏，可以从侧面反映他对于这个项目感兴趣，具体反映到预测公式为：

学习算法依然不变，只是要学习的参数多了两个向量：x和y。一个是隐式反馈的物品向量，另一个是用户属性的向量，这样在用户没有评分时，也可以用他的隐式反馈和属性做出一定的预测。

它是基于这样的假设：用户的兴趣或者偏好不是一成不变的，而是随着时间而动态演化。于是提出了timeSVD，其中用户的和物品的偏置随着时间而变化，同时用户的隐含因子也随着时间而动态改变，在此物品的隐含表示并未随时间而变化（假设物品的属性不会随着时间而改变）。

其中，t为时间因子，表示不同的时间状态。

通过之前构建目标函数之后，就要用到优化算法找到能使它最小的参数。优化方法常用的选择有两个，一个是随机梯度下降(SGD)，另一个是交替最小二乘(ALS),在实际应用中，交替最小二乘更常用一些，这也是推荐系统中选择的主要矩阵分解方法。
找到两个矩阵P和Q，让它们相乘后约等于原矩阵R:

P和Q两个都是未知的，如果知道其中一个的话，就可以按照代数标准解法求得，比如知道Q，那么P就可以这样算：

也就是R矩阵乘Q矩阵的逆矩阵就得到了结果，反之，知道了P 再求Q 也一样，交替最小二乘通过迭代的方式解决这个鸡生蛋蛋生鸡的难题：
1)、初始化随机矩阵Q里面的元素值

2)、把Q矩阵当做已知的，直接用线性代数的方法求得矩阵P

3)、得到了矩阵P后，把P当做已知的，故技重施，回去求解矩阵Q

4)、 上面两个过程交替进行，一直到误差可以接受为止

使用交替最小二乘好处：
1.在交替的其中一步，也就是假设已知其中一个矩阵求解另一个时，要优化的参数是很容易并行的；
2.在不是很稀疏的数据集合上，交替最小二乘通常比随机梯度下降要更快的得到结果。

在很多推荐场景中，我们都是基于现有的用户和商品之间的一些数据，得到用户对所有商品的评分，选择高分的商品推荐给用户，这是funkSVD之类算法的做法，使用起来也很有效。但是在有些推荐场景中，我们是为了在千万级别的商品中推荐个位数的商品给用户，此时，我们更关心的是用户来说，哪些极少数商品在用户心中有更高的优先级，也就是排序更靠前。也就是说，我们需要一个排序算法，这个算法可以把每个用户对应的所有商品按喜好排序。BPR就是这样的一个我们需要的排序算法。

BPR根据像交替最小二乘那样完成矩阵分解，先假装矩阵分解结果已经有了，于是就计算出用户对于每个物品的推荐分数，只不过这个推荐分数可能并不满足均方根误差最小，而是满足物品相对排序最佳

得到了用户和物品的推荐分数后，就可以计算四元组的样本中，物品1和物品2的分数差，这个分数可能是正数，也可能是负数，也可能是0。如果物品1和物品2相对顺序为1，那么希望两者分数之差是个正数，而且越大越好；如果物品1和物品2的相对顺序是0，则希望分数之差是负数，且越小越好。
目标函数：

把这个目标函数化简和变形后，和把AUC当成目标函数是非常相似的，也正是因为如此，BPR模型宣称该模型是为AUC而生的。

SVDFeature 是由上海交大Apex Data & Knowledge Management Lab(APEX)开发的一个推荐系统工具包。他们提出了一种基于feature 的矩阵分解的框架。

它的目的是有效地解决基于特征的矩阵分解。新的模型可以只通过定义新的特征来实现。

这种基于特征的设置允许我们把很多信息包含在模型中，使得模型更加与时俱进。使用此工具包，可以很容易的把其他信息整合进模型，比如时间动态，领域关系和分层信息。除了评分预测，还可以实现pairwise ranking任务。

SVDFeature的模型定义如下：

输入包含三种特征<α，β，γ>，分别是用户特征，物品特征和全局特征。

SVD ：要求矩阵是稠密的，时间复杂度高。不推荐使用。
FunkSVD ：不在将矩阵分解为3个矩阵，而是分解为2个低秩的用户项目矩阵，同时降低了时间复杂度。
BiasSVD ：考虑偏置项时使用，也就是用户的爱好。
SVD++ ：考虑用户的隐式反馈时使用。主动点评电影或者美食的用户是少数，也就是说显示反馈比隐式反馈少，这个时候就可以根据用户的隐式反馈推荐。
timeSVD ：考虑时间因素时使用。人是善变的，随着时间的流逝，兴趣也会发生变化。
ALS ：考虑建模时间时使用。强烈推荐使用，这也是社交巨头 Facebook 在他们的推荐系统中选择的主要矩阵分解算法。
BPR ：考虑排序结果时使用。
SVDFeature ：当我们有多个特征时，可以使用。SVDFeature的目的就是解决基于特征的矩阵分解。

矩阵分解算法的缺点 ：都没有解决冷启动问题

准确率表示预测正确的样本数占总样本数的比例。

TP（true positive）：表示样本的真实类别为正，最后预测得到的结果也为正；
FP（false positive）：表示样本的真实类别为负，最后预测得到的结果却为正；
FN（false negative）：表示样本的真实类别为正，最后预测得到的结果却为负；
TN（true negative）：表示样本的真实类别为负，最后预测得到的结果也为负.

精确率表示预测为正样本的样本中，正确预测为正样本的概率。

召回率表示正确预测出正样本占实际正样本的概率。

折中了召回率与精确率。

对于评分预测任务，一般都是根据原有的评分数据，利用矩阵分解等方法去拟合原评分，使得优化后的模型可以去预测新的评分，这里就要衡量你预测的评分和实际评分的差异了，指标也很简单，分为RMSE和MSE。
MSE 是指参数估计值与参数真值之差平方的期望值;
MSE可以评价数据的变化程度，MSE的值越小，说明预测模型描述实验数据具有更好的精确度。
RMSE ：RMSE是MSE的算术平方根。

AUC 这个值在数学上等价于：模型把关心的那一类样本排在其他样本前面的概率。最大是 1，完美结果，而 0.5 就是随机排列，0 就是完美地全部排错。
这个非常适合用来评价模型的排序效果，很适合作为BPR的评价指标。得到一个推荐模型后，按照它计算的分数，可以把用户想要的物品排在最前面。

具体的计算过程可看我的另一篇 文章

其中Rel表示与用户 u 相关的商品集（测试集）， Rec表示推荐给用户的前K个列表，二者的交集除以Rec的集合元素个数（其实就是K），得到Precision@K。一般是算出每个用户的Precision@K，然后取平均值。

其中Rel表示与用户u相关的商品集（测试集），Rec表示推荐给用户的前K个列表，二者的交集除以Rec的集合元素个数（也就是测试集中用户u评过分的商品数），得到Recall@K。一般是算出每个用户的Recall@K，然后取平均值。

MAP(Mean Average Precision)：单个主题的平均准确率是每篇相关文档检索出后的准确率的平均值。

主集合的平均准确率(MAP)是每个主题的平均准确率的平均值。

MAP 是反映系统在全部相关文档上性能的单值指标。

系统检索出来的相关文档越靠前(rank 越高)，MAP就可能越高。如果系统没有返回相关文档，则准确率默认为0。
例如：

假设有两个主题，主题1有4个相关网页，主题2有5个相关网页。

某系统对于主题1检索出4个相关网页，其rank分别为1, 2, 4, 7；

对于主题2检索出3个相关网页，其rank分别为1,3,5。

对于主题1，平均准确率为(1/1+2/2+3/4+4/7)/4=0.83。对于主题2，平均准确率为(1/1+2/3+3/5+0+0)/5=0.45。

则MAP= (0.83+0.45)/2=0.64。

正确检索结果值在检索结果中的排名来评估检索系统的性能。

其中Q是用户的个数，rank是对于第i个用户，推荐列表中第一个在ground-truth结果中的item所在的排列位置。

举个例子：假如检索三次的结果如下，需要的结果（cat，torus，virus）分别排在3,2,1的话，此系统地MRR为（1/3 + 1/2 + 1)/3 = 11/18

比较复杂，可参考这篇 文章

参考文章：
https://blog.csdn.net/qq_40006058/article/details/89432773
https://blog.csdn.net/weixin_41362649/article/details/82848132
https://blog.csdn.net/qq_19446965/article/details/82079367
https://www.cnblogs.com/pinard/p/9128682.html
https://time.geekbang.org/column/article/5055

H. 个性化推荐算法

算法评估

1.个性化召回

用户行为在个性化推荐系统中一般分两种——显性反馈行悔磨为（explicit feedback）和隐性反馈行为（implicit feedback）
隐性反馈行为指的是那些不能明确反应用户喜好的行为。最具代表性的隐性反馈行为就是页面浏览行为。

按照反馈的明确性分，用户行为数据可以分为显性反馈和隐性反馈，但按照反馈的方向分，
又可以分为正反馈和负反馈。正反馈指用户的行为倾向于指用户喜欢该物品，而负反馈指用户的
行为倾向于指用户不喜欢该物中帆品。在显性反馈中，很容易区分一个用户行为是正反馈还卖前雹是负反馈，
而在隐性反馈行为中，就相对比较难以确定。

P55

1 .1 LFM (latent factor model )
协同算法
矩阵分解算法的一种
LFM 应用

正则化防止过拟合

CF？？？算法

I. 矩阵分解的奇异值分解法

奇异值分解 (singular value decomposition,SVD) 是另一种正交矩阵分解法；SVD是最可靠的分解法，但是它比QR 分解法要花上近十倍的计算时间。[U,S,V]=svd(A)，其中U和V分别代表两个正交矩阵，而S代表一对角矩阵。 和QR分解法相同， 原矩阵A不必为正方矩阵。使用SVD分解法的用途是解最小平方误差法和数据压缩。
MATLAB以svd函数来执行svd分解法， 其语法为[S,V,D]=svd(A)。

J. 矩阵分解在协同过滤推荐算法中的应用

矩阵分解在协同过滤推荐算法中的应用
推荐系统是当下越来越热的一个研究问题，无论在学术界还是在工业界都有很多优秀的人才参与其中。近几年举办的推荐系统比赛更是一次又一次地把推荐系统的研究推向了高潮，比如几年前的Neflix百万大奖赛，KDD CUP 2011的音乐推荐比赛，去年的网络电影推荐竞赛，还有最近的阿里巴巴大数据竞赛。这些比赛对推荐系统的发展都起到了很大的推动作用，使我们有机会接触到真实的工业界数据。我们利用这些数据可以更好地学习掌握推荐系统，这些数据网上很多，大家可以到网上下载。
推荐系统在工业领域中取得了巨大的成功，尤其是在电子商务中。很多电子商务网站利用推荐系统来提高销售收入，推荐系统为Amazon网站每年带来30%的销售收入。推荐系统在不同网站上应用的方式不同，这个不是本文的重点，如果感兴趣可以阅读《推荐系统实践》（人民邮电出版社，项亮）第一章内容。下面进入主题。
为了方便介绍，假设推荐系统中有用户集合有6个用户，即U={u1,u2,u3,u4,u5,u6}，项目（物品）集合有7个项目，即V={v1,v2,v3,v4,v5,v6,v7}，用户对项目的评分结合为R，用户对项目的评分范围是[0, 5]。R具体表示如下：

推荐系统的目标就是预测出符号“？”对应位置的分值。推荐系统基于这样一个假设：用户对项目的打分越高，表明用户越喜欢。因此，预测出用户对未评分项目的评分后，根据分值大小排序，把分值高的项目推荐给用户。怎么预测这些评分呢，方法大体上可以分为基于内容的推荐、协同过滤推荐和混合推荐三类，协同过滤算法进一步划分又可分为基于基于内存的推荐（memory-based）和基于模型的推荐（model-based），本文介绍的矩阵分解算法属于基于模型的推荐。
矩阵分解算法的数学理论基础是矩阵的行列变换。在《线性代数》中，我们知道矩阵A进行行变换相当于A左乘一个矩阵，矩阵A进行列变换等价于矩阵A右乘一个矩阵，因此矩阵A可以表示为A=PEQ=PQ（E是标准阵）。
矩阵分解目标就是把用户-项目评分矩阵R分解成用户因子矩阵和项目因子矩阵乘的形式，即R=UV，这里R是n×m， n =6， m =7，U是n×k，V是k×m。直观地表示如下：

高维的用户-项目评分矩阵分解成为两个低维的用户因子矩阵和项目因子矩阵，因此矩阵分解和PCA不同，不是为了降维。用户i对项目j的评分r_ij =innerproct(u_i, v_j)，更一般的情况是r_ij =f(U_i, V_j)，这里为了介绍方便就是用u_i和v_j内积的形式。下面介绍评估低维矩阵乘积拟合评分矩阵的方法。
首先假设，用户对项目的真实评分和预测评分之间的差服从高斯分布，基于这一假设，可推导出目标函数如下：

最后得到矩阵分解的目标函数如下：

从最终得到得目标函数可以直观地理解，预测的分值就是尽量逼近真实的已知评分值。有了目标函数之后，下面就开始谈优化方法了，通常的优化方法分为两种：交叉最小二乘法（alternative least squares）和随机梯度下降法（stochastic gradient descent）。
首先介绍交叉最小二乘法，之所以交叉最小二乘法能够应用到这个目标函数主要是因为L对U和V都是凸函数。首先分别对用户因子向量和项目因子向量求偏导，令偏导等于0求驻点，具体解法如下：

上面就是用户因子向量和项目因子向量的更新公式，迭代更新公式即可找到可接受的局部最优解。迭代终止的条件下面会讲到。
接下来讲解随机梯度下降法，这个方法应用的最多。大致思想是让变量沿着目标函数负梯度的方向移动，直到移动到极小值点。直观的表示如下：

其实负梯度的负方向，当函数是凸函数时是函数值减小的方向走；当函数是凹函数时是往函数值增大的方向移动。而矩阵分解的目标函数L是凸函数，因此，通过梯度下降法我们能够得到目标函数L的极小值（理想情况是最小值）。
言归正传，通过上面的讲解，我们可以获取梯度下降算法的因子矩阵更新公式，具体如下：

（3）和（4）中的γ指的是步长，也即是学习速率，它是一个超参数，需要调参确定。对于梯度见（1）和（2）。
下面说下迭代终止的条件。迭代终止的条件有很多种，就目前我了解的主要有
1） 设置一个阈值，当L函数值小于阈值时就停止迭代，不常用
2） 设置一个阈值，当前后两次函数值变化绝对值小于阈值时，停止迭代
3） 设置固定迭代次数
另外还有一个问题，当用户-项目评分矩阵R非常稀疏时，就会出现过拟合（overfitting）的问题，过拟合问题的解决方法就是正则化（regularization）。正则化其实就是在目标函数中加上用户因子向量和项目因子向量的二范数，当然也可以加上一范数。至于加上一范数还是二范数要看具体情况，一范数会使很多因子为0，从而减小模型大小，而二范数则不会它只能使因子接近于0，而不能使其为0，关于这个的介绍可参考论文Regression Shrinkage and Selection via the Lasso。引入正则化项后目标函数变为：

（5）中λ_1和λ_2是指正则项的权重，这两个值可以取一样，具体取值也需要根据数据集调参得到。优化方法和前面一样，只是梯度公式需要更新一下。
矩阵分解算法目前在推荐系统中应用非常广泛，对于使用RMSE作为评价指标的系统尤为明显，因为矩阵分解的目标就是使RMSE取值最小。但矩阵分解有其弱点，就是解释性差，不能很好为推荐结果做出解释。
后面会继续介绍矩阵分解算法的扩展性问题，就是如何加入隐反馈信息，加入时间信息等。