Spark 高级分析:第三章第2节

问题导读

1.什么是协同过滤？
2.什么是ALS？原理是什么？
3.？Spark MLib 推荐算法借鉴的是什么算法？






上一篇：Spark 高级分析:第三章第1节
http://www.aboutyun.com/forum.php?mod=viewthread&tid=23338&extra=

交替最小二乘的推荐算法

我们需要选择一种适合于这种隐式反馈数据的算法。这个数据集全部是用户与作家的歌曲之间的交互行为数据。它没有包含用户和作家本身除了名字之外的其他属性信息。这个就是典型的协同过滤算法。举个例子：比如决定两个用户具有相同的品味的原因是他们有相同的年龄，这个不是协同过滤。决定两个用户都喜欢同一首歌曲的原因是他们之间有很多共同喜欢的歌曲，这才是协同过滤。

这个数据集很大，因为他包含1千万多条用户播放记录。但是从另一个方面来说，它又很小数据量不够，因为它很稀疏。平均起来，每个用户才放过171个艺术家的歌曲，而总共的艺术家有 1.6 百万个。有些用户甚至只是听歌一个作曲家的歌曲，我们需要一种算法，能够对这种用户也给出合理的推荐。毕竟，每个人刚开始在系统中开始产生记录的那一刻都只听过一个作家。这个也说明算法对新用户准确度低，这种情况当用户交互行为变多的时候会慢慢变好。   

最后，我们需要一种算法，它既能构建大型模型，又能快速创建推荐。推荐需要近实时，在一秒钟内实现，而不是明天。

这个示例将使用一系列称为潜在因素模型的算法的成员。他们试图通过大量未被观察到的潜在原因来解释大量用户和产品之间观察到的相互作用。这类似于解释为什么数以百万计的人会通过描述用户和专辑的口味来购买成千上万张可能的专辑，其中可能有几十种不同的风格，这些口味并不是直接观察或作为数据提供的。

更具体地说，这个例子将使用一种矩阵分解模型。在数学上，这些算法将用户和产品数据视作一个大型稀疏矩阵A，如果用户i播放了作家j的作品则J在行i和列j上存在相应实。们把A作为两个较小矩阵X和Y的矩阵乘积。X和Y他们很瘦--都有许多行和列，但都只是几列（k）。这k列就是用来解释交互数据的潜在因素。

因式分解只能是近似的因为k值很小，如图3-1所示：

图3-1 矩阵分解

这些算法有时被称为矩阵完成算法，因为原始矩阵A可能是相当稀疏的，但近似乘积XYT是完全稠密的。它是一个模型，在这个意义上，它为A的每个条目生成一个值，甚至是原始A中缺少的条目。

幸运的是，线性代数直接优美地映射到直觉。这两个矩阵分别包含了每个用户和每个艺术家对应的行。这些行包含了k个值。每个值对应于模型中的潜在特性。因此，行表示了多少用户和艺术家与这些潜在特征相关联，这些特征可能与品味或风格相一致。它仅仅是一个用户特性和特性艺术家矩阵的产物，同时产生了一个完整的、密集的用户艺术家交互矩阵的完整估计。

坏消息是，A=XYT一般没有解决方案，因为X和Y不够大（从技术上讲，秩太小）足以完美地代表A。A只是所有可能发生的相互作用的极小样本。在某种程度上，我们相信A是一个非常参差不齐的，因此很难解释，对一个更简单的基本事实的看法，只有少数几个因素能很好地解释。想象一个描绘猫的拼图游戏：最后的谜题很简单——一只猫。然而，当你只保留几个小块时，你所看到的画面是很难描述的。

XYT仍应该尽可能接近A。毕竟，我们必须继续做向导。我们不会也不应该完全复制它。坏消息是，无法解决在同一时间内保证最好的X和最好的Y。好消息是，如果Y是已知的求最优的X在数学上是最简单的，反之亦然。但是，当然，关键是事先都不知道！

幸运的是，有算法，可以逃脱这个双环困境，找到合适的解决方案。更具体地说，本章中的例子将使用交替最小二乘（ALS）算法来计算X和Y。这种类型的方法在Netflix Prize的推广中被普及，如对隐式反馈数据集的协同过滤和Netflix奖的大规模并行协同过滤。事实上，Spark MLlib的ALS的实现是从这些论文借鉴的思路。

Y不知道，但是，它可以被初始化为一个充满随机选择的行向量的矩阵，结果证明一个随机的解决方案是一个好的开始。然后，简单的线性代数即可给出x的最佳解。事实上，把X的每一行分别作为Y的函数和A的一行的计算可达的。因为它可以单独完成，所以可以并行完成，这对于大规模计算来说是极好的特性。

公式3-1.ALS的正规方程

同样，完全相等不能完全实现，所以实际上目标是最小化| AiY (Y T Y )-1 - Xi|，或两者之间的平方差。这就是名字中的“最小平方”的来由。此外，在实践中这不是通过实际计算逆解决的，而是通过更快和更直接的像QR分解的方法一样的方法。方程3-1简单地阐述了如何计算行向量的理论。

同样可以从X计算每个Yj。再从Y计算X，等等。这就是“交替”部分的来源。只有一个小问题：Y是随机生成的！X是最佳计算，是的，但给Y的一个虚假的解决方案，幸运的是，如果这个过程重复，X和Y最终收敛到相当好的解决方案。

当用于表示隐式数据的矩阵时，ALS分解稍微复杂一些。它不是直接分解输入矩阵A，而是0和1矩阵P，A矩阵有值的地方值为1。A中的值稍后作为权重合并。这一细节超出了本书的范围，但不必理解使用该算法。

最后，ALS算法还可以利用输入数据的稀疏性这一点。它依赖简单优化的线性代数，以及它的数据并行性，使它在很大程度上非常快。这是本章题目的主要原因。事实是ALS是Spark MLlib目前实现的唯一推荐算法！

来过！！！%%%%%%