推荐系统总结2（系统落地）

协同过滤和推荐系统几乎可以划等号，协同过滤的重点在于“协同”，所谓协同，也就是群体互帮互助，互相支持是集体智慧的体现，协同过滤也是这般简单直接，历久弥新。

6.1 分类（User-Based）

基于记忆的协同过滤（Memory-Based）；二次分类：User-Based Item-Based

基于模型的协同过滤（Model-Based）。

6.2 User-Based的套路

第一步，准备用户向量，从这个矩阵中，理论上可以给每一个用户得到一个向量，这个向量有这么三个特点：

向量的维度就是物品的个数；向量是稀疏的，也就是说并不是每个维度上都有数值，原因当然很简单，这个用户并不是消费过所有物品；向量维度上的取值可以是简单的 0 或者 1，也就是布尔值，1 表示喜欢过，0 表示没有，当然因为是稀疏向量，所以取值为 0 的就忽略了

第二步，用每一个用户的向量，两两计算用户之间的相似度，设定一个相似度阈值或者设定一个最大数量，为每个用户保留与其最相似的用户。

这里两两计算相似度如何计算，市面上有很多相似度计算方法，也可以自己设计，基本想法是余弦。

第三步，为每一个用户产生推荐结果。

把和他“臭味相投”的用户们喜欢过的物品汇总起来，去掉用户自己已经消费过的物品，剩下的排序输出就是推荐结果，是不是很简单。具体的汇总方式我们用一个公式来表示。

这个公式也是很简单的。等号左边就是计算一个物品 i 和一个用户 u 的匹配分数，等号右边是这个分数的计算过程，分母是把和用户 u 相似的 n 个用户的相似度加起来，分子是把这 n 个用户各自对物品 i 的态度，按照相似度加权求和。这里的态度最简单就是 0 或者 1，1 表示喜欢过，0 表示没有，如果是评分，则可以是 0 到 5 的取值。整个公式就是相似用户们的态度加权平均值。

6.3 User-Based的坑

只有原始用户行为日志，需要从中构造出矩阵，怎么做？

如果用户的向量很长，计算一个相似度则耗时很久，怎么办？

如果用户量很大，而且通常如此，两两计算用户相似度也是一个大坑，怎么办？

在计算推荐时，看上去要为每一个用户计算他和每一个物品的分数，又是一个大坑，怎么办？

1 构造矩阵

我们在做协同过滤计算时，所用的矩阵是稀疏的，说人话就是：很多矩阵元素不用存，因为是 0。这里介绍典型的稀疏矩阵存储格式。

CSR：这个存储稍微复杂点，是一个整体编码方式。它有三个组成：数值、列号和行偏移共同编码。

COO：这个存储方式很简单，每个元素用一个三元组表示（行号，列号，数值），只存储有值的元素，缺失值不存储。

这些存储格式，在常见的计算框架里面都是标准的，如 Spark 中，Python 的 NumPy 包中。一些著名的算法比赛也通常都是以这种格式提供数据。

2 相似度计算

相似度计算是个问题。首先是单个相似度计算问题，如果碰上向量很长，无论什么相似度计算方法，都要遍历向量，如果用循环实现就更可观了，所以通常降低相似度计算复杂度的办法有两种。

对向量采样计算。道理很简单，两个一百维的向量计算出的相似度是 0.7，我现在忍受一些精度的损失，不用 100 维计算，随机从中取出 10 维计算，得到相似度是 0.72，显然用 100 维计算出的 0.7 更可信一些，但是在计算复杂度降低十倍的情形下，0.72 和它误差也不大，后者更经济。这个算法由 Twitter 提出，叫做 DIMSUM 算法，已经在 Spark 中实现了。

向量化计算。与其说这是一个小技巧，不如说这是一种思维方式。在机器学习领域，向量之间的计算是家常便饭，难道向量计算都要用循环实现吗？并不是，现代的线性代数库都支持直接的向量运算，比循环快很多。也就是我们在任何地方，都要想办法把循环转换成向量来直接计算，一般像常用的向量库都天然支持的，比如 Python 的 NumPy 。

其次的问题就是，如果用户量很大，两两之间计算代价就很大。

有两个办法来缓解这个问题：

第一个办法是：将相似度计算拆成 Map Reduce 任务，将原始矩阵 Map 成键为用户对，值为两个用户对同一个物品的评分之积，Reduce 阶段对这些乘积再求和，Map Reduce 任务结束后再对这些值归一化；

第二个办法是：不用基于用户的协同过滤。

另外，这种计算对象两两之间的相似度的任务，如果数据量不大，一般来说不超过百万个，然后矩阵又是稀疏的，那么有很多单机版本的工具其实更快，比如 KGraph、 GraphCHI 等。

3 推荐计算

得到了用户之间的相似度之后。接下来还有一个硬骨头，计算推荐分数。显然，为每一个用户计算每一个物品的推荐分数，计算次数是矩阵的所有元素个数，这个代价，你当然不能接受啊。这时候，你注意回想一下前面那个汇总公式，有这么几个特点我们可以来利用一下：

只有相似用户喜欢过的物品需要计算，这个大大的赞，这个数量相比全部物品少了很多；

把计算过程拆成 Map Reduce 任务。

拆 Map Reduce 任务的做法是：1.遍历每个用户喜欢的物品列表；2.获取该用户的相似用户列表；

把每一个喜欢的物品 Map 成两个记录发射出去，一个是键为 < 相似用户 ID，物品 ID，1> 三元组，可以拼成一个字符串，值为 < 相似度 >，另一个是键为 < 相似用户 ID，物品 ID，0> 三元组，值为 < 喜欢程度 * 相似度 >，其中的 1 和 0 为了区分两者，在最后一步中会用到；

Reduce 阶段，求和后输出；

< 相似用户 ID，物品 ID, 0> 的值除以 < 相似用户 ID，物品 ID, 1> 的值

一般来说，中小型公司如果没有特别必要的话，不要用分布式计算，看上去高大上、和大数据沾上边了，实际上得不偿失。拆分 Map Reduce 任务也不一定非要用 Hadoop 或者 Spark 实现。也可以用单机实现这个过程。

因为一个 Map 过程，其实就是将原来耦合的计算过程解耦合了、拍扁了，这样的话我们可以利用多线程技术实现 Map 效果。例如 C++ 里面 OpenMP 库可以让我们无痛使用多线程，充分剥削计算机所有的核。

4 一些改进（非常非常重要）

对于基于用户的协同过滤有一些常见的改进办法，改进主要集中在用户对物品的喜欢程度上：

惩罚对热门物品的喜欢程度，这是因为，热门的东西很难反应出用户的真实兴趣，更可能是被煽动，或者无聊随便点击的情形，这是群体行为常见特点；（以APP推荐来看，如果以用户相似度来看推荐，可以乘以下载量的逆倒数，可以避免把热门应用推荐给所有人）

增加喜欢程度的时间衰减，一般使用一个指数函数，指数就是一个负数，值和喜欢行为发生时间间隔正相关即可，这很好理解，小时候喜欢的东西不代表我现在的口味，人都是会变的，这是人性。

最后，说一说基于用户的协同过滤有哪些应用场景。基于用户的协同过滤有两个产出：

相似用户列表；

基于用户的推荐结果。

所以我们不但可以推荐物品，还可以推荐用户！比如我们在一些社交平台上看到：“相似粉丝”“和你口味类似的人”等等都可以这样计算。对于这个方法计算出来的推荐结果本身，由于是基于口味计算得出，所以在更强调个人隐私场景中应用更佳，在这样的场景下，不受大 V 影响，更能反应真实的兴趣群体，而非被煽动的乌合之众。

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

7 看了这个商品的还看了（Item-Based)

基于物品的协同过滤算法诞生于 1998 年，是由亚马逊首先提出的，并在 2001 年由其发明者发表了相应的论文（ Item-Based Collaborative Filtering Recommendation Algorithms ）。这篇论文在 Google 学术上引用数已近 7000，并且在 WWW2016 大会上被授予了“时间检验奖”，颁奖词是：“这篇杰出的论文深深地影响了实际应用”。历经了 15 年后仍然在发光发热，这个奖它显然受之无愧。

7.1 基于物品（Item-Based）原理

在基于物品的协同过滤出现之前，信息过滤系统最常使用的是基于用户的协同过滤。基于用户的协同过滤首先计算相似用户，然后再根据相似用户的喜好推荐物品，这个算法有这么几个问题：

用户数量往往比较大，计算起来非常吃力，成为瓶颈；

用户的口味其实变化还是很快的，不是静态的，所以兴趣迁移问题很难反应出来；

数据稀疏，用户和用户之间有共同的消费行为实际上是比较少的，而且一般都是一些热门物品，对发现用户兴趣帮助也不大。

基于物品的算法怎么就解决了上面这些问题呢？

首先，物品的数量，或者严格的说，可以推荐的物品数量往往少于用户数量；所以一般计算物品之间的相似度就不会成为瓶颈。

其次，物品之间的相似度比较静态，它们变化的速度没有用户的口味变化快；所以完全解耦了用户兴趣迁移这个问题。

最后，物品对应的消费者数量较大，对于计算物品之间的相似度稀疏度是好过计算用户之间相似度的。

7.2 落实计算物品相似度

从用户物品关系矩阵中得到的物品向量长什么样子呢？

它是一个稀疏向量；

向量的维度是用户，一个用户代表向量的一维，这个向量的总共维度是总用户数量；

向量各个维度的取值是用户对这个物品的消费结果，可以是行为本身的布尔值，也可以是消费行为量化如时间长短、次数多少、费用大小等，还可以是消费的评价分数；

没有消费过的就不再表示出来，所以说是一个稀疏向量。

接下来就是如何两两计算物品的相似度了，一般选择余弦相似度，当然还有其他的相似度计算法方法也可以。计算公式如下：

用文字解释一下这个公式：

分母是计算两个物品向量的长度，求元素值的平方和再开方。分子是两个向量的点积，相同位置的元素值相乘再求和。这个公式的物理意义就是计算两个向量的夹角余弦值，相似度为 1 时，对应角度是 0，好比时如胶似漆，相似度为 0 时，对应角度为 90 度，毫不相干，互为路人甲。

看上去计算量很大，貌似每一个求和的复杂度都是和向量维度、也就是用户数量一样的。但是别忘了，前面我说过他们都是稀疏向量，也就是向量中绝大多数值都是 0，求和时不用算，点积时更不用算，甚至求点积时只用管两个物品的公共用户，只是少许几个乘积而已。

7.3 改进

物品之间的相似度计算是这个算法最可以改进的地方。通常的改进方向有下面两种。

1. 物品中心化。把矩阵中的分数，减去的是物品分数的均值；先计算每一个物品收到评分的均值，然后再把物品向量中的分数减去对应物品的均值。这样做的目的是什么呢？去掉物品中铁杆粉丝群体的非理性因素，例如一个流量明星的电影，其脑残粉可能会集体去打高分，那么用物品的均值来中心化就有一定的抑制作用。

2. 用户中心化。把矩阵中的分数，减去对应用户分数的均值；先计算每一个用户的评分均值，然后把他打过的所有分数都减去这个均值。

这样做的目的又是什么呢？每个人标准不一样，有的标准严苛，有的宽松，所以减去用户的均值可以在一定程度上仅仅保留了偏好，去掉了主观成分。

上面提到的相似度计算方法，不只是适用于评分类矩阵，也适用于行为矩阵。所谓行为矩阵，即矩阵元素为 0 或者 1 的布尔值，也就是在前面的专栏中讲过的隐式反馈。隐式反馈取值特殊，有一些基于物品的改进推荐算法无法应用，比如著名的 Slope One 算法。

7.4 计算推荐结果

在得到物品相似度之后，接下来就是为用户推荐他可能会感兴趣的物品了，基于物品的协同过滤，有两种应用场景。

第一种属于 TopK 推荐，形式上也常常属于类似“猜你喜欢”这样的。

出发方式是当用户访问首页时，汇总和“用户已经消费过的物品相似”的物品，按照汇总后分数从高到低推出。我们在计算时不必对所有物品都计算一边，只需要按照用户评分过的物品，逐一取出和它们相似的物品出来就可以了。这个过程都是离线完成后，去掉那些用户已经消费过的，保留分数最高的 k 个结果存储。当用户访问首页时，直接查询出来即可。

第二种属于相关推荐，也就是我们今天专栏题目所指的场景。

这类推荐不需要提前合并计算，当用户访问一个物品的详情页面时，或者完成一个物品消费的结果面，直接获取这个物品的相似物品推荐，就是“看了又看”或者“买了又买”的推荐结果了。

Slope One 算法

经典的基于物品推荐，相似度矩阵计算无法实时更新，整个过程都是离线计算的，而且还有另一个问题，相似度计算时没有考虑相似度的置信问题。例如，两个物品，他们都被同一个用户喜欢了，且只被这一个用户喜欢了，那么余弦相似度计算的结果是 1，这个 1 在最后汇总计算推荐分数时，对结果的影响却最大。

Slope One 算法针对这些问题有很好的改进。在 2005 年首次问世，Slope One 算法专门针对评分矩阵，不适用于行为矩阵。Slope One 算法计算的不是物品之间的相似度，而是计算的物品之间的距离，相似度的反面。举个例子就一目了然，下面是一个简单的评分矩阵：

这个矩阵反应了这些事实：用户 1 给物品 A、B、C 都评分了，分别是 5，3，2；用户 2 给物品 A、B 评分了，分别是 3、4；用户 3 给物品 B、C 评分了，分别是 2、5。现在首先来两两计算物品之间的差距：

括号里表示两个物品的共同用户数量，代表两个物品差距的置信程度。比如物品 A 和物品 B 之间的差距是 0.5，共同用户数是 2，反之，物品 B 和物品 A 的差距是 -0.5，共同用户数还是 2。知道这个差距后，就可以用一个物品去预测另一个物品的评分。

如果只知道用户 3 给物品 B 的评分是 2，那么预测用户 3 给物品 A 的评分呢就是 2.5，因为从物品 B 到物品 A 的差距是 0.5。（andy：这个是单个物品预测）

在此基础上继续推进，如果知道用户给多个物品评分了，怎么汇总这些分数呢？

方法是把单个预测的分数按照共同用户数加权求平均。比如现在知道用户 3 不但给物品 B 评分为 2，还给物品 C 评分为 5，物品 B 对物品 A 的预测是 2.5 分，刚才计算过了，物品 C 给物品 A 的预测是 8 分，再加权平均。

8∗1+2.5∗2(1+2)=4.338∗1+2.5∗2(1+2)=4.33

就得到了推荐分数为 4.33 分。是不是很简单？

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

8 协同过滤中的相似度计算

推荐系统中，推荐算法分为两个门派，一个是机器学习派，另一个就是相似度门派。机器学习派是后起之秀，而相似度派则是泰山北斗，以致撑起来推荐系统的半壁江山。推荐算法中的相似度门派，实际上有这么一个潜在假设：如果两个物体很相似，也就是距离很近，那么这两个物体就很容易产生一样的动作。如果两篇新闻很相似，那么他们很容易被同一个人先后点击阅读，如果两个用户很相似，那么他们就很容易点击同一个新闻。这种符合直觉的假设，大部分时候很奏效。

其实属于另一门派的推荐算法——机器学习中，也有很多算法在某种角度看做是相似度度量。例如，逻辑回归或者线性回归中，一边是特征向量，另一边是模型参数向量，两者的点积运算，就可以看做是相似度计算，只不过其中的模型参数向量值并不是人肉指定的，而是从数据中由优化算法自动总结出来的。在近邻推荐中，最常用的相似度是余弦相似度。然而可以选用的相似度并不只是余弦相似度，还有欧氏距离、皮尔逊相关度、自适应的余弦相似度、局部敏感哈希等。

8.1 欧氏距离

欧氏距离，如名字所料，是一个欧式空间下度量距离的方法。两个物体，都在同一个空间下表示为两个点，假如叫做 p 和 q，分别都是 n 个坐标。那么欧式距离就是衡量这两个点之间的距离，从 p 到 q 移动要经过的距离。欧式距离不适合布尔向量之间。

计算方式可以表示如下，我在文稿中放了一个公式，你可以点击查看。

这个公式就是，每一个坐标上的取值相减，求平方和，最后输出方根。

显然，欧式距离得到的值是一个非负数，最大值是正无穷。通常相似度计算度量结果希望是 [-1，1] 或者 [0，1] 之间，所以欧式距离要么无法直接使用到这个场景中，要么需要经过二次转化得到，下面是最常用的转化公式。

距离加一后取倒数。这个公式能够把范围为 0 到正无穷的欧式距离转换为 0 到 1 的相似度。

欧式距离度量的是空间中两个点的绝对差异，适用于分析用户能力模型之间的差异，比如消费能力、贡献内容的能力等。

8.2 余弦相似度

大名鼎鼎的余弦相似度，度量的是两个向量之间的夹角，其实就是用夹角的余弦值来度量，所以名字叫余弦相似度。当两个向量的夹角为 0 度时，余弦值为 1，当夹角为 90 度时，余弦值为 0，为 180 度时，余弦值则为 -1。

余弦相似度在度量文本相似度、用户相似度、物品相似度的时候都较为常用；但是在这里需要提醒你一点，余弦相似度的特点：它与向量的长度无关。因为余弦相似度计算需要对向量长度做归一化：

经过向量长度归一化后的相似度量方式，背后潜藏着这样一种思想：两个向量，只要方向一致，无论程度强弱，都可以视为“相似”。

这简直就是：招聘人才时只看价值观，不考核代码能力，只要肯干，搬砖嘛，谁搬不是搬。这样做错不错呢？很显然，有非常大的合理性。

比如，我用 140 字的微博摘要了一篇 5000 字的博客内容，两者得到的文本向量可以认为方向一致，词频等程度不同，但是余弦相似度仍然认为他们是相似的。

在协同过滤中，如果选择余弦相似度，某种程度上更加依赖两个物品的共同评价用户数，而不是用户给予的评分多少。这就是由于余弦相似度被向量长度归一化后的结果。

余弦相似度对绝对值大小不敏感这件事，在某些应用上仍然有些问题。

举个小例子，用户 A 对两部电影评分分别是 1 分和 2 分，用户 B 对同样这两部电影评分是 4 分和 5 分。用余弦相似度计算出来，两个用户的相似度达到 0.98。这和实际直觉不符，用户 A 明显不喜欢这两部电影。

针对这个问题，对余弦相似度有个改进，改进的算法叫做调整的余弦相似度（Adjusted Cosine Similarity）。调整的方法很简单，就是先计算向量每个维度上的均值，然后每个向量在各个维度上都减去均值后，再计算余弦相似度。

前面这个小例子，用调整的余弦相似度计算得到的相似度是 -0.1，呈现出两个用户口味相反，和直觉相符。

8.3 皮尔逊相关度

皮尔逊相关度，实际上也是一种余弦相似度，不过先对向量做了中心化，向量 p 和 q 各自减去向量的均值后，再计算余弦相似度。

皮尔逊相关度计算结果范围在 -1 到 1。-1 表示负相关，1 比表示正相关。皮尔逊相关度其实度量的是两个随机变量是不是在同增同减。

如果同时对两个随机变量采样，当其中一个得到较大的值另一也较大，其中一个较小时另一个也较小时，这就是正相关，计算出来的相关度就接近 1，这种情况属于沆瀣一气，反之就接近 -1。

由于皮尔逊相关度度量的时两个变量的变化趋势是否一致，所以不适合用作计算布尔值向量之间相关度，因为两个布尔向量也就是对应两个 0-1 分布的随机变量，这样的随机变量变化只有有限的两个取值，根本没有“变化趋势，高低起伏”这一说。

4 杰卡德（Jaccard）相似度

杰卡德相似度，是两个集合的交集元素个数在并集中所占的比例。由于集合非常适用于布尔向量表示，所以杰卡德相似度简直就是为布尔值向量私人定做的。对应的计算方式是：

分子是两个布尔向量做点积计算，得到的就是交集元素个数；

分母是两个布尔向量做或运算，再求元素和。

余弦相似度适用于评分数据，杰卡德相似度适合用于隐式反馈数据。例如，使用用户的收藏行为，计算用户之间的相似度，杰卡德相似度就适合来承担这个任务。

总结：这里的场景是按照数据形式划分的，按照向量维度取值是否是布尔值来看，杰卡德相似度就只适合布尔值向量，余弦相似度弹性略大，适合两种向量。欧式距离度量的是绝对差异，余弦相似度度量的是方向差异，但是调整的余弦相似度则可以避免这个弱点。

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

10 Netflix （SVD）

矩阵分解确实可以解决一些以上（KNN ,协同过滤）无法解决的问题：

1.物品之间存在相关性，信息量并不随着向量维度增加而线性增加；

2.矩阵元素稀疏，计算结果不稳定，增减一个向量维度，导致近邻结果差异很大的情况存在。

上述两个问题，在矩阵分解中可以得到解决。矩阵分解，直观上说来简单，就是把原来的大矩阵，近似分解成两个小矩阵的乘积，在实际推荐计算时不再使用大矩阵，而是使用分解得到的两个小矩阵。具体说来就是，假设用户物品的评分矩阵 A 是 m 乘以 n 维，即一共有 m 个用户，n 个物品。我们选一个很小的数 k，这个 k 比 m 和 n 都小很多，比如小两个数量级这样，通过一套算法得到两个矩阵 U 和 V，矩阵 U 的维度是 m 乘以 k，矩阵 V 的维度是 n 乘以 k。这两个矩阵有什么要求呢？要求就是通过下面这个公式复原矩阵 A。

类似这样的计算过程就是矩阵分解，还有一个更常见的名字叫做 SVD；但是，SVD 和矩阵分解不能划等号，因为除了 SVD 还有一些别的矩阵分解方法。

10.1 基础的 SVD 算法

介绍的 SVD 是由 Netflix Prize 中取得骄人成绩的 Yehuda Koren 提出的矩阵分解推荐算法。但了解他的方法前，先介绍基础的 SVD 算法，然后是考虑偏置信息，接着是超越评分矩阵增加多种输入，最后是增加时间因素。

从物理意义上解释一遍。矩阵分解，就是把用户和物品都映射到一个 k 维空间中，这个 k 维空间不是我们直接看得到的，也不一定具有非常好的可解释性，每一个维度也没有名字，所以常常叫做隐因子，代表藏在直观的矩阵数据下面的。每一个物品都得到一个向量 q，每一个用户也得到一个向量 p。对于物品，与它对应的向量 q 中的元素，有正有负，代表着这个物品背后暗藏的一些用户关注的因素。对于用户，与它对应的向量 p 中的元素，也有正有负，代表这个用户在若干因素上的偏好。物品被关注的因素，和用户偏好的因素，它们的数量和意义是一致的，就是我们在矩阵分解之处人为指定的 k。

举个例子，用户 u 的向量是 pu，物品 i 的向量是 qi，那么，要计算物品 i 推荐给用户 u 的推荐分数，直接计算点积即可：

看上去很简单，难在哪呢？难在如何得到每一个用户，每一个物品的 k 维向量。这是一个机器学习问题。按照机器学习框架，一般就是考虑两个核心要素：

损失函数；

优化算法。

SVD 的损失函数是这样定义的：

不需要理解这个函数（如果不是数学专业），但要知道：这个损失函数由两部分构成，加号前一部分控制着模型的偏差，加号后一部分控制着模型的方差。前一部分就是：用分解后的矩阵预测分数，要和实际的用户评分之间误差越小越好。后一部分就是：得到的隐因子向量要越简单越好，以控制这个模型的方差，换句话说，让它在真正执行推荐任务时发挥要稳定。这部分的概念对应机器学习中的过拟合，有兴趣可以深入了解

整个 SVD 的学习过程就是：

1.准备好用户物品的评分矩阵，每一条评分数据看做一条训练样本；

2.给分解后的 U 矩阵和 V 矩阵随机初始化元素值；

3.用 U 和 V 计算预测后的分数；

4.计算预测的分数和实际的分数误差；

5.按照梯度下降的方向更新 U 和 V 中的元素值；

重复步骤 3 到 5，直到达到停止条件。

过程中提到的梯度下降是优化算法的一种，想深入了解可以参见任何一本机器学习的专著。得到分解后的矩阵之后，实质上就是得到了每个用户和每个物品的隐因子向量，拿着这个向量再做推荐计算就简单了，拿着物品和用户两个向量，计算点积就是推荐分数了。

10.2 增加偏置信息 （优化重点）

到现在，你已经知道基础的 SVD 是怎么回事了。现在来多考虑一下实际情况，试想一下：有一些用户会给出偏高的评分，比如标准宽松的用户；有一些物品也会收到偏高的评分，比如一些目标观众为铁粉的电影，甚至有可能整个平台的全局评分就偏高。所以，原装的 SVD 就有了第一个变种：把偏置信息抽出来的 SVD。一个用户给一个物品的评分会由四部分相加：

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

针对前面三项偏置分数，我在这里举个例子，假如一个电影评分网站全局平均分是 3 分，《肖申克的救赎》的平均分比全局平均分要高 1 分。

你是一个对电影非常严格的人，你一般打分比平均分都要低 0.5，所以前三项从左到右分别就是 3，1，-0.5。如果简单的就靠这三项，也可以给计算出一个你会给《肖申克的救赎》打的分数，就是 3.5。

增加了偏置信息的 SVD 模型目标函数稍有改变：

和基本的 SVD 相比，要想学习两个参数：用户偏置和物品偏置。学习的算法还是一样的。

10.3 增加历史行为-隐式 （优化重点）

探讨完增加偏执信息的 SVD 后，再思考一个问题：有的用户评分比较少。事实上这很常见，相比沉默的大多数，主动点评电影或者美食的用户是少数。换句话说，显式反馈比隐式反馈少，那么能不能利用隐式反馈来弥补这一点呢？

另外，再考虑多一点，对于用户的个人属性，比如性别等，是不是也可以加入到模型中来弥补冷启动的不足呢？

是的，都是可以的，在 SVD 中结合用户的隐式反馈行为和属性，这套模型叫做 SVD++。

先说隐式反馈怎么加入，方法是：除了假设评分矩阵中的物品有一个隐因子向量外，用户有过行为的物品集合也都有一个隐因子向量，维度是一样的。把用户操作过的物品隐因子向量加起来，用来表达用户的兴趣偏好。

类似的，用户属性，全都转换成 0-1 型的特征后，对每一个特征也假设都存在一个同样维度的隐因子向量，一个用户的所有属性对应的隐因子向量相加，也代表了他的一些偏好。

综合两者，SVD++ 的目标函数中，只需要把推荐分数预测部分稍作修改，原来的用户向量那部分增加了隐式反馈向量和用户属性向量：

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

10.4 考虑时间因素

截止到目前，我们还没有正视过一个人性：人是善变的。这个是一个广义的评价，我们在进步也是在变化，今天的我们和十年前的我们很可能不一样了。这是常态，因此，在 SVD 中考虑时间因素也变得顺理成章。

在 SVD 中考虑时间因素，有几种做法：

1.对评分按照时间加权，让久远的评分更趋近平均值；

2.对评分时间划分区间，不同的时间区间内分别学习出隐因子向量，使用时按照区间使用对应的隐因子向量来计算；

3.对特殊的期间，如节日、周末等训练对应的隐因子向量。

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

11 矩阵分解plus-交替最小二乘（多种方法的融合时候使用）

矩阵分解要将用户物品评分矩阵分解成两个小矩阵，一个矩阵是代表用户偏好的用户隐因子向量组成，另一个矩阵是代表物品语义主题的隐因子向量组成。这两个小矩阵相乘后得到的矩阵，维度和原来的用户物品评分矩阵一模一样。比如原来矩阵维度是 m x n，其中 m 是用户数量，n 是物品数量，再假如分解后的隐因子向量是 k 个，那么用户隐因子向量组成的矩阵就是 m x k，物品隐因子向量组成的矩阵就是 n x k。

得到的这两个矩阵有这么几个特点：

1.每个用户对应一个 k 维向量，每个物品也对应一个 k 维向量，就是所谓的隐因子向量，因为是无中生有变出来的，所以叫做“隐因子”；

2.两个矩阵相乘后，就得到了任何一个用户对任何一个物品的预测评分，具体这个评分靠不靠谱，那就是看功夫了。

所以矩阵分解，所做的事就是矩阵填充。那到底怎么填充呢，换句话也就是说两个小矩阵怎么得到呢？这个公式依然由两部分构成：加号左边是误差平方和，加号右边是分解后参数的平方。

按照机器学习的套路，就是使用优化算法求解下面这个损失函数。这种模式可以套在几乎所有的机器学习训练中：就是一个负责衡量模型准不准，另一个负责衡量模型稳不稳定。行话是这样说的：一个衡量模型的偏差，一个衡量模型的方差。偏差大的模型欠拟合，方差大的模型过拟合。有了这个目标函数后，就要用到优化算法找到能使它最小的参数。优化方法常用的选择有两个，一个是随机梯度下降（SGD），另一个是交替最小二乘（ALS）。

在实际应用中，交替最小二乘更常用一些，这也是社交巨头 Facebook 在他们的推荐系统中选择的主要矩阵分解方法，今天，重点交替最小二乘原理 (ALS)。

11.1 交替交替最小二乘

最小二乘的核心是交替，什么意思呢？你的任务是找到两个矩阵 P 和 Q，让它们相乘后约等于原矩阵 R：

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

也就是 R 矩阵乘以 Q 矩阵的逆矩阵就得到了结果。反之知道了 P 再求 Q 也一样。简单的说，先用一个假的结果让算法先运转起来，然后不断迭代最终得到想要的结果，一直到误差可以接受为止。交替最小二乘有这么几个好处：在交替的其中一步，也就是假设已知其中一个矩阵求解另一个时，要优化的参数是很容易并行化的；在不那么稀疏的数据集合上，交替最小二乘通常比随机梯度下降要更快地得到结果，事实上这一点就是我马上要说的，也就是关于隐式反馈的内容。

11.2 隐式反馈

矩阵分解算法，是为解决评分预测问题而生的，比如说，预测用户会给商品打几颗星，然后把用户可能打高星的商品推荐给用户，然而事实上却是，用户首先必须先去浏览商品，然后是购买，最后才可能打分。相比“预测用户会打多少分”，“预测用户会不会去浏览”更加有意义，而且，用户浏览数据远远多于打分评价数据。也就是说，实际上推荐系统关注的是预测行为，行为也就是一再强调的隐式反馈。

那如何从解决评分预测问题转向解决预测行为上来呢？这就是另一类问题了，行话叫做 One-Class。这是什么意思呢？如果把预测用户行为看成一个二分类问题，猜用户会不会做某件事，但实际上收集到的数据只有明确的一类：用户干了某件事，而用户明确“不干”某件事的数据却没有明确表达。所以这就是 One-Class 的由来，One-Class 数据也是隐式反馈的通常特点。对隐式反馈的矩阵分解，需要将交替最小二乘做一些改进，改进后的算法叫做加权交替最小二乘：Weighted-ALS。

这个加权要从哪说起？用户对物品的隐式反馈，通常是可以多次的，你有心心念念的衣服或者电子产品，但是刚刚剁完手的你正在吃土买不起，只能每天去看一眼。这样一来，后台就记录了你查看过这件商品多少次，查看次数越多，就代表你越喜欢这个。也就是说，行为的次数是对行为的置信度反应，也就是所谓的加权。加权交替最小二乘这样对待隐式反馈：

1.如果用户对物品无隐式反馈则认为评分是 0；

2.如果用户对物品有至少一次隐式反馈则认为评分是 1，次数作为该评分的置信度。

那现在的目标函数在原来的基础上变成这样：

多出来的 Cui 就是置信度，在计算误差时考虑反馈次数，次数越多，就越可信。置信度一般也不是直接等于反馈次数，根据一些经验，置信度 Cui 这样计算：

其中阿尔法是一个超参数，需要调教，默认值取 40 可以得到差不多的效果，C 就是次数了。这里又引出另一个问题，那些没有反馈的缺失值，应对这个问题的做法就是负样本采样：挑一部分缺失值作为负类别样本即可。什么样的样本最适合做负样本？就是展示给用户了，他也知道这个物品的存在了，但就是没有对其作出任何反馈。问题就是很多时候不知道到底是用户没有意识到物品的存在呢，还是知道物品的存在而不感兴趣呢？因此按照物品热门程度采样的思想就是：一个越热门的物品，用户越可能知道它的存在。那这种情况下，用户还没对它有反馈就表明：这很可能就是真正的负样本。按照热门程度采样来构建负样本，在实际中是一个很常用的技巧。

11.3 推荐计算

在得到了分解后的矩阵后，相当于每个用户得到了隐因子向量，这是一个稠密向量，用于代表他的兴趣。同时每个物品也得到了一个稠密向量，代表它的语义或主题。而且可以认为这两者是一一对应的，用户的兴趣就是表现在物品的语义维度上的。看上去，让用户和物品的隐因子向量两两相乘，计算点积就可以得到所有的推荐结果了。但是实际上复杂度还是很高，尤其对于用户数量和物品数量都巨大的应用，如 Facebook，就更不现实。于是 Facebook 提出了两个办法得到真正的推荐结果。

第一种，利用一些专门设计的数据结构存储所有物品的隐因子向量，从而实现通过一个用户向量可以返回最相似的 K 个物品。Facebook 给出了自己的开源实现 Faiss，类似的开源实现还有 Annoy，KGraph，NMSLIB。如果需要动态增加新的物品向量到索引中，推荐使用 Faiss，如果不是，推荐使用 NMSLIB 或者 KGraph。用户向量则可以存在内存数据中，这样可以在用户访问时，实时产生推荐结果。http://36kr.com/p/5069188.html

第二种，就是拿着物品的隐因子向量先做聚类，海量的物品会减少为少量的聚类。然后再逐一计算用户和每个聚类中心的推荐分数，给用户推荐物品就变成了给用户推荐物品聚类。得到给用户推荐的聚类后，再从每个聚类中挑选少许几个物品作为最终推荐结果。这样做的好处除了大大减小推荐计算量之外，还可以控制推荐结果的多样性，因为可以控制在每个类别中选择的物品数量。

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

12 贝叶斯个性化排序（BPR 模型） 

矩阵分解的优势：既有协同过滤的血统，又有机器学习的基因。

矩阵分解的不足：矩阵分解，本质上都是在预测用户对一个物品的偏好程度，哪怕不是预测评分， 只是预测隐式反馈，也难逃这个事实。这种针对单个用户对单个物品的偏好程度进行预测，得到结果后再排序的问题，在排序学习中的行话叫做 point-wise，其中 point 意思就是：只单独考虑每个物品，每个物品像是空间中孤立的点一样。与之相对的，还有直接预测物品两两之间相对顺序的问题，就叫做 pair-wise，pair，顾名思义就是成对成双，前面讲的矩阵分解都属于 point-wise 模型。这类模型的尴尬是：只能收集到正样本，没有负样本，于是认为缺失值就是负样本，再以预测误差为评判标准去使劲逼近这些样本。逼近正样本没问题，但是同时逼近的负样本只是缺失值而已，还不知道真正呈现在用户面前，到底是不喜欢还是喜欢呢？虽然这些模型采取了一些措施来规避这个问题，比如负样本采样，但是尴尬还是存在的，为了排序而绕路也是事实。

解决这个问题应该换一个思维：更直接的推荐模型应该是能够较好地为用户排列出更好的物品相对顺序，而非更精确的评分。

12.1 Area Under Curve

均方根误差，是经典的用于评价模型预测精准程度的。那么现在要关注的是相对排序，用什么指标比较好呢？答案是 AUC，AUC 全称是 Area Under Curve，意思是曲线下的面积，这里的曲线就是 ROC 曲线。

AUC 怎么计算呢？一般步骤如下。

1.用模型给样本计算推荐分数，比如样本都是用户和物品这样一对一对的，同时还包含了有无反馈的标识；

2.得到打过分的样本，每条样本保留两个信息，第一个是分数，第二个是 0 或者 1，1 表示用户消费过，是正样本，0 表示没有，是负样本；

3.按照分数对样本重新排序，降序排列；

4.给每一个样本赋一个排序值，第一位 r1 = n，第二位 r2 = n-1，以此类推；其中要注意，如果几个样本分数一样，需要将其排序值调整为他们的平均值；

5.最终按照下面这个公式计算就可以得到 AUC 值。

这个公式看上去复杂，其实很简单，由两部分构成：

第一部分： 分母是所有我们关心的那类样本，也就是正样本，有 M 个，以及其他样本有 N 个，这两类样本相对排序总共的组合可能性，是 M x N；

第二部分： 分子也不复杂，原本是这样算的：第一名的排序值是 r1，它在排序上不但比过了所有的负样本，而且比过了自己以外的正样本。

但后者是自己人，所以组合数要排除，于是就有 n - M 种组合，以此类推，排序值为 rM 的就贡献了 rM - 1，把这些加起来就是分子。关于 AUC，越接近 1 越好是肯定的，但是并不是越接近 0 就越差，最差的是接近 0.5，如果 AUC 很接近 0 的话，只需要把模型预测的结果加个负号就能让 AUC 接近 1，具体的原因自行体会。

12.2 BPR 模型

主角出场了，BPR 模型，它提出了一个优化准则和学习框架，使得原来传统的矩阵分解放进来能够焕发第二春。

BPR 做了什么事情呢？主要有三点：

a.一个样本构造方法；

b.一个模型目标函数；

c.一个模型学习框架。

通过这套三板斧，便可以脱离评分预测，来做专门优化排序的矩阵分解。

a-构造样本：前面介绍的矩阵分解，在训练时候处理的样本是：用户、物品、反馈，这样的三元组形式。其中反馈又包含真实反馈和缺失值，缺失值充当的是负样本职责。BPR 则不同，提出要关心的是物品之间对于用户的相对顺序，于是构造的样本是：用户、物品 1、物品 2、两个物品相对顺序，这样的四元组形式，其中，“两个物品的相对顺序”，取值是：

如果物品 1 是消费过的，而物品 2 不是，那么相对顺序取值为 1，是正样本；如果物品 1 和物品 2 刚好相反，则是负样本；样本中不包含其他情况：物品 1 和物品 2 都是消费过的，或者都是没消费过的。

这样一来，学习的数据是反应用户偏好的相对顺序，而在使用时，面对的是所有用户还没消费过的物品，这些物品仍然可以在这样的模型下得到相对顺序，这就比三元组 point-wise 样本要直观得多。

b-目标函数:现在，每条样本包含的是两个物品，样本预测目标是两个物品的相对顺序。按照机器学习的套路，就该要上目标函数了。要看 BPR 怎么完成矩阵分解，你依然需要像交替最小二乘那样的思想。先假装矩阵分解结果已经有了，于是就计算出用户对于每个物品的推荐分数，只不过这个推荐分数可能并不满足均方根误差最小，而是满足物品相对排序最佳。得到了用户和物品的推荐分数后，就可以计算四元组的样本中，物品 1 和物品 2 的分数差，这个分数可能是正数，也可能是负数，也可能是 0。你和我当然都希望的情况是：如果物品 1 和物品 2 相对顺序为 1，那么希望两者分数之差是个正数，而且越大越好；如果物品 1 和物品 2 的相对顺序是 0，则希望分数之差是负数，且越小越好。用个符号来表示这个差：Xu12，表示的是对用户 u，物品 1 和物品 2 的矩阵分解预测分数差。然后再用 sigmoid 函数把这个分数差压缩到 0 到 1 之间。

也其实就是用这种方式预测了物品 1 排在物品 2 前面的似然概率，所以最大化交叉熵就是目标函数了。目标函数通常还要防止过拟合，加上正则项，正则项其实认为模型参数还有个先验概率，这是贝叶斯学派的观点，也是 BPR 这个名字中“贝叶斯”的来历。

BPR 认为模型的先验概率符合正态分布，对应到正则化方法就是 L2 正则，目标函数写一下：

所有样本都计算：模型参数先验概率 p theta，和似然概率的乘积，最大化这个目标函数就能够得到分解后的矩阵参数，其中 theta 就是分解后的矩阵参数。最后说一句，把这个目标函数化简和变形后，和把 AUC 当成目标函数是非常相似的，也正因为如此，BPR 模型的作者敢于宣称该模型是为 AUC 而生的。

c-训练方法.有了目标函数之后，就要有请训练方法了。显然是老当益壮的梯度下降可以承担这件事，梯度下降又有批量梯度和随机梯度下降两个选择，前者收敛慢，后者训练快却不稳定。因此 BPR 的作者使用了一个介于两者之间的训练方法，结合重复抽样的梯度下降。具体来说是这样做的：

从全量样本中有放回地随机抽取一部分样本；

用这部分样本，采用随机梯度下降优化目标函数，更新模型参数；

重复步骤 1，直到满足停止条件。

这样，就得到了一个更符合推荐排序要求的矩阵分解模型了。BPR 就是这样一整套针对排序的推荐算法，它事实上提出了一个优化准则和一个学习框架，至于其中优化的对象是不是矩阵分解并不是它的重点。

、 所有样本都计算：模型参数先验概率 p theta，和似然概率的乘积，最大化这个目标函数就能够得到分解后的矩阵参数，其中 theta 就是分解后的矩阵参数。