推荐系统-协同过滤

在现今的推荐技术和算法中，最被大家广泛认可和采用的就是基于协同过滤的推荐方法。

什么是集体智慧

集体智慧 (Collective Intelligence) 并不是 Web2.0 时代特有的，只是在 Web2.0 时代，大家在 Web 应用中利用集体智慧构建更加有趣的应用或者得到更好的用户体验。集体智慧是指在大量的人群的行为和数据中收集答案，帮助你对整个人群得到统计意义上的结论，这些结论是我们在单个个体上无法得到的，它往往是某种趋势或者人群中共性的部分。

Wikipedia 和 Google 是两个典型的利用集体智慧的 Web 2.0 应用：

• Wikipedia 是一个知识管理的百科全书，相对于传统的由领域专家编辑的百科全书，Wikipedia 允许最终用户贡献知识，随着参与人数的增多，Wikipedia 变成了涵盖各个领域的一本无比全面的知识库。也许有人会质疑它的权威性，但如果你从另一个侧面想这个问题，也许就可以迎刃而解。在发行一本书时，作者虽然是权威，但难免还有一些错误，然后通过一版一版的改版，书的内容越来越完善。而在 Wikipedia 上，这种改版和修正被变为每个人都可以做的事情，任何人发现错误或者不完善都可以贡献他们的想法，即便某些信息是错误的，但它一定也会尽快的被其他人纠正过来。从一个宏观的角度看，整个系统在按照一个良性循环的轨迹不断完善，这也正是集体智慧的魅力。
• Google：目前最流行的搜索引擎，与 Wikipedia 不同，它没有要求用户显式的贡献，但仔细想想 Google 最核心的 PageRank 的思想，它利用了 Web 页面之间的关系，将多少其他页面链接到当前页面的数目作为衡量当前页面重要与否的标准；如果这不好理解，那么你可以把它想象成一个选举的过程，每个 Web 页面都是一个投票者同时也是一个被投票者，PageRank 通过一定数目的迭代得到一个相对稳定的评分。Google 其实利用了现在 Internet 上所有 Web 页面上链接的集体智慧，找到哪些页面是重要的。

什么是协同过滤

协同过滤是利用集体智慧的一个典型方法。要理解什么是协同过滤 (Collaborative Filtering, 简称 CF)，首先想一个简单的问题，如果你现在想看个电影，但你不知道具体看哪部，你会怎么做？大部分的人会问问周围的朋友，看看最近有什么好看的电影推荐，而我们一般更倾向于从口味比较类似的朋友那里得到推荐。这就是协同过滤的核心思想。

换句话说，就是借鉴和你相关人群的观点来进行推荐，很好理解。

User-Based CF和Item-Based CF

要实现协同过滤的推荐算法，要进行以下三个步骤：

收集数据——找到相似用户和物品——进行推荐

收集数据

这里的数据指的都是用户的历史行为数据，比如用户的购买历史，关注，收藏行为，或者发表了某些评论，给某个物品打了多少分等等，这些都可以用来作为数据供推荐算法使用，服务于推荐算法。需要特别指出的在于，不同的数据准确性不同，粒度也不同，在使用时需要考虑到噪音所带来的影响。

找到相似用户和物品

这一步也很简单，其实就是计算用户间以及物品间的相似度。以下是几种计算相似度的方法：

欧几里德距离

$$d(x, y)=\sqrt{\left(\sum\left(x_{i}-y_{i}\right)^{2}\right)} \quad \operatorname{sim}(x, y)=\frac{1}{1+d(x, y)}$$

　　皮尔逊相关系数

$$p(x, y)=\frac{\sum x_{i} y_{i}-n \overline{x y}}{(n-1) s_{x} s_{y}}=\frac{n \sum x_{i} y_{i}-\sum x_{i} \sum y_{i}}{\sqrt{n \sum x_{i}^{2}-\left(\sum x_{i}\right)^{2}} \sqrt{n \sum y_{i}^{2}-\left(\sum y_{i}\right)^{2}}}$$

Cosine 相似度

$$T(x, y)=\frac{x \bullet y}{\|x\|^{2} \times\|y\|^{2}}=\frac{\sum x_{i} y_{i}}{\sqrt{\sum x_{i}^{2}} \sqrt{\sum y_{i}^{2}}}$$

Tanimoto 系数

$$T(x, y)=\frac{x \bullet y}{\|x\|^{2}+\|y\|^{2}-x \bullet y}=\frac{\sum x_{i} y_{i}}{\sqrt{\sum x_{i}^{2}}+\sqrt{\sum y_{i}^{2}}-\sum x_{i} y_{i}}$$

进行推荐

在知道了如何计算相似度后，就可以进行推荐了。

在协同过滤中，有两种主流方法：基于用户的协同过滤，和基于物品的协同过滤。具体怎么来阐述他们的原理呢，看个图大家就明白了

基于用户的 CF 的基本思想相当简单，基于用户对物品的偏好找到相邻邻居用户，然后将邻居用户喜欢的推荐给当前用户。计算上，就是将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，找到 K 邻居后，根据邻居的相似度权重以及他们对物品的偏好，预测当前用户没有偏好的未涉及物品，计算得到一个排序的物品列表作为推荐。 下图给出了一个例子，对于用户 A，根据用户的历史偏好，这里只计算得到一个邻居 - 用户 C，然后将用户 C 喜欢的物品 D 推荐给用户 A。

基于物品的 CF 的原理和基于用户的 CF 类似，只是在计算邻居时采用物品本身，而不是从用户的角度，即基于用户对物品的偏好找到相似的物品，然后根据用户的历史偏好，推荐相似的物品给他。从计算的角度看，就是将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度，得到物品的相似物品后，根据用户历史的偏好预测当前用户还没有表示偏好的物品，计算得到一个排序的物品列表作为推荐。下图给出了一个例子，对于物品 A，根据所有用户的历史偏好，喜欢物品 A 的用户都喜欢物品 C，得出物品 A 和物品 C 比较相似，而用户 C 喜欢物品 A，那么可以推断出用户 C 可能也喜欢物品 C。

总结

以上两个方法都能很好的给出推荐，并可以达到不错的效果。但是他们之间还是有不同之处的，而且适用性也有区别。下面进行一下对比

计算复杂度

Item CF 和 User CF 是基于协同过滤推荐的两个最基本的算法，User CF 是很早以前就提出来了，Item CF 是从 Amazon 的论文和专利发表之后（2001 年左右）开始流行，大家都觉得 Item CF 从性能和复杂度上比 User CF 更优，其中的一个主要原因就是对于一个在线网站，用户的数量往往大大超过物品的数量，同时物品的数据相对稳定，因此计算物品的相似度不但计算量较小，同时也不必频繁更新。但我们往往忽略了这种情况只适应于提供商品的电子商务网站，对于新闻，博客或者微内容的推荐系统，情况往往是相反的，物品的数量是海量的，同时也是更新频繁的，所以单从复杂度的角度，这两个算法在不同的系统中各有优势，推荐引擎的设计者需要根据自己应用的特点选择更加合适的算法。

适用场景

在非社交网络的网站中，内容内在的联系是很重要的推荐原则，它比基于相似用户的推荐原则更加有效。比如在购书网站上，当你看一本书的时候，推荐引擎会给你推荐相关的书籍，这个推荐的重要性远远超过了网站首页对该用户的综合推荐。可以看到，在这种情况下，Item CF 的推荐成为了引导用户浏览的重要手段。同时 Item CF 便于为推荐做出解释，在一个非社交网络的网站中，给某个用户推荐一本书，同时给出的解释是某某和你有相似兴趣的人也看了这本书，这很难让用户信服，因为用户可能根本不认识那个人；但如果解释说是因为这本书和你以前看的某本书相似，用户可能就觉得合理而采纳了此推荐。

　　相反的，在现今很流行的社交网络站点中，User CF 是一个更不错的选择，User CF 加上社会网络信息，可以增加用户对推荐解释的信服程度。

基于模型的推荐算法ALS(交替最小二乘)

在用户数量以及用户评分不足的情况下，上述两种方法就不是那么地好使了，近年来，基于模型的推荐算法ALS(交替最小二乘)在Netflix成功应用并取得显著效果提升，ALS使用机器学习算法建立用户和物品间的相互作用模型，进而去预测新项。它已经集成到Spark的Mllib库中，使用起来比较方便。从协同过滤的分类来说，ALS算法属于User-Item CF，也叫做混合CF。它同时考虑了User和Item两个方面。

基本原理

用户对物品的打分行为可以表示成一个打分矩阵 R，例如下表所示：

矩阵中的打分值 $r_{ij}$ 表示用户 $u_i$ 对物品 $v_j$的打分，其中”?”表示用户没有打分，这也就是要通过机器学习的方法去预测这个打分值，从而达到推荐的目的。

在实际使用中，由于n和m的数量都十分巨大，因此R矩阵的规模很容易就会突破1亿项。这时候，传统的矩阵分解方法对于这么大的数据量已经是很难处理了。

另一方面，一个用户也不可能给所有商品评分，因此，R矩阵注定是个稀疏矩阵。矩阵中所缺失的评分，又叫做missing item。

模型抽象

按照User-Based CF的思想，R 的行向量对应每个用户 u ，按照Item-Based CF的思想，R 的列向量对应每个物品 v 。ALS 的核心思想是，将用户和物品都投影到 k 维空间，也就是说，假设有 k 个隐含特征，至于 k 个隐含特征具体指什么不用关心，将每个用户和物品都用 k 维向量来表示，把它们之间的内积近似为打分值，这样就可以得到如下近似关系：

$$R \approx U V^T$$

R 为打分矩阵($m \times n$)，m 个用户，n 个物品，U 为用户对隐含特征的偏好低秩矩阵($m \times k$)，V 为物品对隐含特征的偏好低秩矩阵($n \times k$)。

上述模型的参数就是矩阵 U 和 V，即求解出 U 和 V 我们就可以重现打分矩阵，填补原始打分矩阵中的缺失值”?”。同时，矩阵 U和 V，还可以用于比较不同的User（或Item）之间的相似度。

显示反馈代价函数

要求解上述模型中的 U 和 V，那么就需要一个代价函数来衡量参数的拟合程度，如果有比较明确的显式反馈打分数据，那么可以比较重构出来的打分矩阵与实际打分矩阵，即得到重构误差，由于实际打分矩阵有很多缺失值，所以仅计算已知打分的重构误差，下面函数为显示反馈代价函数。

$$J\left( U, V \right) = \sum_i \sum_j \left[ \left( r_{ij} - u_i v_j^T \right)^2 + \lambda \left( \|u_i\|^2 + \|v_j\|^2 \right) \right]$$

$r_{ij}$ 为矩阵 R 的第 i 行第 j 列，表示用户 $u_i $对物品 $v_j $的打分，$u_i $为矩阵 U 的第 i 行 $(1 \times k)$，$v_j^T$ 为矩阵$V^T $的第 j 列 $(k \times 1)$，$\lambda $为正则项系数。

隐式反馈代价函数

很多情况下，用户并没有明确反馈对物品的偏好，需要通过用户的相关行为来推测其对物品的偏好，例如，在视频推荐问题中，可能由于用户就懒得对其所看的视频进行反馈，通常是收集一些用户的行为数据，得到其对视频的偏好，例如观看时长等。通过这种方式得到的偏好值称之为隐式反馈值，即矩阵 R 为隐式反馈矩阵，引入变量 $p_{ij}$ 表示用户 $u_i$ 对物品 $v_j $的置信度，如果隐式反馈值大于0，置信度为1，否则置信度为0。

$$p_{ij} = \left\{\begin{matrix}1 \qquad r_{ij} > 0 & \\ 0 \qquad r_{ij} = 0 & \end{matrix}\right.$$

但是隐式反馈值为0并不能说明用户就完全不喜欢，用户对一个物品没有得到一个正的偏好可能源于多方面的原因，例如，用户可能不知道该物品的存在，另外，用户购买一个物品也并不一定是用户喜欢它，所以需要一个信任等级来显示用户偏爱某个物品，一般情况下，$r_{ij} $越大，越能暗示用户喜欢某个物品，因此，引入变量 $c_{ij}$，来衡量 $p_{ij}$ 的信任度。

$$c_{ij} = 1 + \alpha r_{ij}$$

$\alpha$ 为置信度系数

那么，代价函数则变成如下形式：

$$J\left( U, V \right) = \sum_i \sum_j \left[ c_{ij} \left( p_{ij} - u_i v_j^T \right)^2 + \lambda \left( \|u_i\|^2 + \|v_j\|^2 \right)\right]$$

算法

无论是显示反馈代价函数还是隐式反馈代价函数，它们都不是凸的，变量互相耦合在一起，常规的梯度下降法可不好使了。但是如果先固定 U 求解 V，再固定V 求解 U ，如此迭代下去，问题就可以得到解决了。

$$U^{(0)} \rightarrow V^{(1)} \rightarrow U^{(1)} \rightarrow V^{(2)} \rightarrow \cdots$$

那么固定一个变量求解另一个变量如何实现呢，梯度下降？虽然可以用梯度下降，但是需要迭代，计算起来相对较慢，试想想，固定 U 求解 V，或者固定 V 求解 U，其实是一个最小二乘问题，由于一般隐含特征个数 k 取值不会特别大，可以将最小二乘转化为正规方程一次性求解，而不用像梯度下降一样需要迭代。如此交替地解最小二乘问题，所以得名交替最小二乘法ALS，下面是基于显示反馈和隐式反馈的最小二乘正规方程。

显示反馈

固定 V 求解 U

$$U ^T = \left( V^T V + \lambda I \right)^{-1} V^T R^T$$

更直观一点，每个用户向量的求解公式如下：

$$u_i ^T = \left( V^T V + \lambda I \right)^{-1} V^T r_i^T$$

$u_i^T $为矩阵 U 的第 i 行的转置$(k \times 1)$，$r_i^T$ 为矩阵 R 的第 i 行的转置$(n \times 1)$。

固定 U 求解 V

$$V ^T = \left( U^T U + \lambda I \right)^{-1} U^T R$$

更直观一点，每个物品向量的求解公式如下：

$$v_j ^T = \left( U^T U + \lambda I \right)^{-1} U^T r_j^T$$

$v_j^T$ 为矩阵 $V^T$ 的第 j 列$(k \times 1)$，$r_j^T$ 为矩阵 R 的第 j 列$(m \times 1)$。

隐式反馈

固定 V 求解 U

$$U ^T = \left( V^T C_v V + \lambda I \right)^{-1} V^T C_v R^T$$

更直观一点，每个用户向量的求解公式如下：

$$u_i ^T = \left( V^T C_v V + \lambda I \right)^{-1} V^T C_v r_i^T$$

$u_i^T$ 为矩阵 U 的第 i 行的转置$(k \times 1)$，$r_i^T $为矩阵 R 的第 i 行的转置$(n \times 1)$，$C_v $为对角矩阵$(n \times n)$。

固定 U 求解 V

$$V ^T = \left( U^T C_u U + \lambda I \right)^{-1} U^T C_u R$$

更直观一点，每个物品向量的求解公式如下：

$$v_j ^T = \left( U^T C_u U + \lambda I \right)^{-1} U^T C_u r_j^T$$

$v_j^T$ 为矩阵$V^T$ 的第 j 列$(k \times 1)$，$r_j^T$ 为矩阵 R 的第 j 列$(m \times 1)$,， $C_u$ 为对角矩阵$(m \times m)$。

总结

ALS算法的缺点在于它是一个离线算法，无法准确评估新加入的User或Item，这个问题也被称为Cold Start问题。
ALS算法的核心就是将稀疏评分矩阵分解为User特征向量矩阵和Item特征向量矩阵的乘积。
交替使用最小二乘法逐步计算User/Item特征向量，使得误差平方和最小。
通过User/Item特征向量的矩阵来预测某个用户对某个产品的评分。

Reference：
https://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy2/index.html
https://www.cnblogs.com/luchen927/archive/2012/02/01/2325360.html
http://sharkdtu.com/posts/ml-als.html