推荐算法概览

推荐算法概览（二）

本文是系列文中的第二篇，将会列出推荐算法的备忘列表，介绍推荐算法的主要分类。在本文中，我们会更详细地介绍协同过滤推荐算法，并讨论其优劣，以便大家更深刻地理解其工作原理。

协同过滤（CF）推荐算法会寻找用户的行为模式，并据此创建用户专属的推荐内容。这种算法会根据系统中的用户使用数据——比如用户对读过书籍的评论来确定用户对其喜爱程度。关键概念在于：如果两名用户对于某件物品的评分方式类似，那么他们对于某个新物品的评分很可能也是相似的。值得注意的是：这种算法无需再额外依赖于物品信息（比如描述、元数据等）或者用户信息（比如感兴趣的物品、统计数据等）。协同过滤推荐算法可分为两类：基于邻域的与基于模型的。在前一种算法（也就是基于内存的协同过滤推荐算法）中，用户-物品评分可直接用以预测新物品的评分。而基于模型的算法则通过评分来研究预测性的模型，再根据模型对新物品作出预测。大致理念就是通过机器学习算法，在数据中找出模式，并将用户与物品间的互动方式模式化。

基于邻域的协同过滤则着眼于物品之间的关系（即基于物品的协同过滤）或者用户之间的关系（基于用户的协同过滤）。

基于用户的协同过滤是探索对物品拥有相似品味的用户，并基于彼此喜爱的物品来进行互推。
基于物品的协同过滤是用户喜爱的物品，推荐类似的东西。而这种相似性建立在物品同时出现的基础上，比如购买了x物品的用户也购买了y物品。

首先，在执行基于物品的协同过滤前，我们先看一个基于用户的协同过滤案例。
假设我们有一些用户已经表达了他们对某些书籍的偏好，他们越喜欢某本书，对这本书的评分也越高（评分范围是1分到5分）。我们可以在一个矩阵中重现他们的这种偏好，用行代表用户，用列代表书籍。

图一：用户书籍偏好所有偏好的范围都是1分到5分，5分是最高（也就是最喜欢的）。第一个用户（行1）给第一本书（列1）的评分为4分，如果某个单元格为空，代表着用户并未对这本书作出评价。

在基于用户的协同过滤算法中，我们要做的第一件事就是根据用户对书籍的偏好，计算出他们彼此间的相似度。我们从某个单独用户的角度来看一下这个问题，以图一中第一行的用户为例。通常我们会将每个用户都作为向量（或者数组），其中包含了用户对物品的偏好。通过多种类似的指标对用户进行对比是相当直接的。在本例中，我们会使用余弦相似点。我们将第一位用户与其他五位相对比，可以发现第一位与其他用户的相似度有多少（图二）。就像大多相似度指标一样，向量之间的相似度越高，彼此也就越相似。在本例中，第一位用户与其中两位有两本相同的书籍，相似度较高；与另两位只有一本相同书籍，相似度较低；与最后一位没有相同书籍，相似度为零。

图二：第一位用户与其他用户的相似性。可以在一个单独的维度中绘制用户间的余弦相似性。

更常见的情况下，我们可以计算出每名用户与所有用户的相似程度，并在相似性矩阵中表现出来（图三）。这是一个对称矩阵，也就是说其中一些有用的属性是可以执行数学函数运算的。单元格的背景色表明了用户彼此间的相似程度，红色越深则相似度越高。

图三：用户间的相似矩阵，每个用户的相似度是基于用户阅读书籍间的相似性。

现在，我们准备使用基于用户的协同过滤来生成给用户的推荐。对于特定的用户来说，这代表着找出与其相似性最高的用户，并根据这些类似用户喜爱的物品进行推荐，具体要参照用户相似程度来加权。我们先以第一个用户为例，为其生成一些推荐。首先我们找到与这名用户相似程度最高的n名用户，删除这名用户已经喜欢过的书籍，再对最相似用户阅读过的书籍进行加权，之后将所有结果加在一起。在本例中，我们假设n=2，也就是说取两名与第一位用户最相似的用户，以生成推荐结果，这两名用户分别是用户2及用户3（图四）。由于第一名用户已经对书籍1和书籍5做出了评分，推荐结果生成书籍3（分数4.5）及书籍4（分数3）。

图四：为一名用户生成推荐。我们取这两名最相似的用户所阅读的书籍，进行加权，然后对这名用户尚未评分的书籍进行推荐。

现在我们对基于用户的协同过滤有了更深刻的理解，之后来看一个基于物品的协同过滤的案例。我们还是用同一组用户（图一）为例。

在基于物品的协同过滤中，与基于用户的协同过滤类似，我们要做的第一件事就是计算相似度矩阵。但这一回，我们想要针对物品而非用户来看看它们之间的相似性。与之前类似，我们以书籍作为喜爱者的向量（或数组），将其与余弦相似度函数相对比，从而揭示出某本书籍与其他书籍之间的相似程度。由于同一组用户给出的评分大致类似，位于列1的第一本书与位于列5的第五本书相似度是最高的（图五）。其次是相似度排名第三的书籍，有两位相同的用户喜爱；排名第四和第二的书籍只有一位共同读者；而排名最后的书籍由于没有共同读者，相似度为零。

图五：第一本书与其他书籍的对比。书籍通过所阅读用户的评价来表现。通过余弦相似度指标（0-1）来进行对比，相似度越高，两本书就越相似。

我们还可以在相似矩阵中展示出所有书籍彼此间的相似程度（图六）。同样以背景颜色区分了两本书彼此间的相似程度，红色越深相似程度也越高。

图六：书籍的相似矩阵

现在我们知道每本书彼此间的相似程度了，可以为用户生成推荐结果。在基于物品的协同过滤中，我们根据用户此前曾评过分的物品，推荐与其最为相似的物品。在案例中，第一位用户获得的推荐结果为第三本书籍，然后是第六本（图七）。同样地，我们只取与用户之前评论过的书籍最相似的两本书。

图七：为某位用户生成推荐结果。我们取到他们之前评论过的书籍目录，找出与每本书籍最相似的两本，再对用户尚未评论过的书籍进行推荐。

根据上述描述，基于用户与基于物品的协同过滤似乎非常类似，因此能得出不同的结果这一点确实很有意思。即便在上例中，这两种方式都能为同一名用户得出不同的推荐结果，尽管两者的输入内容是相同的。在构建推荐时，这两种形式的协同过滤方式都是值得考虑的。尽管在向外行描述时，这两种方法看起来非常类似，但实际上它们能得出非常不同的推荐结果，从而为用户带来完全不同的体验。

由于简单高效，且生成的推荐结果准确、个性化，邻域方法也是相当受欢迎的。但由于要计算（用户或物品间的）相似度，随着用户或物品数量的增长，也会出现一些伸缩性方面的局限。在最糟的情况下，需要计算O(m*n)，但在现实中情况略好一些，只要计算O(m+n)即可，部分原因在于利用了数据的稀疏度。尽管稀疏度有助于扩展实现，但同时也为基于邻域的方法提出了挑战，因为在海量的物品中，仅有少量是有用户评论过的。例如，Mendeley系统中有数百万篇文章，而一名用户也许只读过其中几百篇。两名各读过100篇文章的用户具有相似度的可能性仅为0.0002（在5000万篇文章的目录中）。

基于模型的协同过滤方式可以克服基于邻域方法的限制。与使用用户-物品评分直接预测新物品评分的邻域方式不同，基于模型的方法则使用评分来研究预测性模型，并根据模型来预测新物品。大致理念就是通过机器学习算法，在数据中找出模式，并将用户与物品间的互动方式模式化。总体来讲，基于模型的协同过滤方式是构建协同过滤更高级的算法。很多不同的算法都能用来构建模型，以进行预测；例如贝叶斯网络、集群、分类、回归、矩阵因式分解、受限波尔兹曼机等，这些技术其中有些在获得Netflix Prize奖项时起到了关键性作用。Netflix在2006年到2009年间举办竞赛，当时还为能够生成准确度超过其系统10%的推荐系统制作团队提供100万美元的大奖。胜出的解决方案是一套综合了逾100种不同算法模型，并在生产环境中采用了矩阵因式分解与受限玻尔兹曼机的方法。

矩阵因式分解（比如奇异值分解、SVD++）将物品与用户都转化为同一个隐空间，表现了用户与物品间的底层互动（图八）。矩阵因式分解背后的原理在于：其潜在特性代表了用户如何对物品进行评分。根据用户与物品的潜在表现，我们就可以预测用户对未评分的物品的喜爱程度。

图八：矩阵分解算法的演示，用户偏好矩阵可以分解为用户主题矩阵乘以物品主题矩阵。

在表一中，我们列出了邻域算法与基于模型的协同过滤算法的关键优劣点。由于协同过滤算法只依赖于用户的使用数据，想要生成足够优秀的推荐结果无需对技术工作有太多了解，但这种算法也有其局限。例如，CF更容易推荐流行物品，因此为品味独特的用户推荐物品时就会比较困难（即对其感兴趣的物品可能不具有太多的使用数据），也就是流行度偏好的问题，这一点通常可以通过基于内容的过滤算法解决。CF算法更重要的一个限制就是所谓的“冷启动问题”——系统无法为没有或使用行为很少的用户提供推荐（也就是新用户的问题），也无法为没有或使用行为很少的物品提供推荐（也就是新物品的问题）。新用户的“冷启动问题”可以通过流行度和混合算法来解决，而新物品问题可以通过基于内容过滤或multi-armed bandit推荐算法（即探索-利用）来解决。在下篇文章中我们会详细讨论其中一些算法。

本文中，我们介绍了三种基本的协同过滤算法实现。基于物品、基于用户的协同过滤算法，以及矩阵分解算法之间的区别都很细微，通常很难简单地解释其差异。理解这些算法间的差异有助于我们选择推荐系统最适合的算法。在下篇文章中，我们会继续深入探讨推荐系统的流行算法。