推荐算法概览（一）

资讯频道 → 企业架构

1顶
0踩

2016-07-29 11:10 by 副主编 mengyidan1988 评论(0) 有6925人浏览

算法

声明：ITeye资讯文章的版权属于ITeye网站所有，严禁任何网站转载本文，否则必将追究法律责任！

引用

原文：Overview of Recommender Algorithms
作者： MAYA.HRISTAKEVA
译者：孙薇
责编：钱曙光，关注架构和算法领域，寻求报道或者投稿请发邮件qianshg@csdn.net，另有「CSDN 高级架构师群」，内有诸多知名互联网公司的大牛架构师，欢迎架构师加微信qshuguang2008申请入群，备注姓名+公司+职位。

推荐算法概览（一）
为推荐系统选择正确的推荐算法非常重要，而可用的算法很多，想要找到最适合所处理问题的算法还是很有难度的。这些算法每种都各有优劣，也各有局限，因此在作出决策前我们应当对其做以衡量。在实践中，我们很可能需要测试多种算法，以便找出最适合用户的那种；了解这些算法的概念以及工作原理，对它们有个直观印象将会很有帮助。

推荐算法通常是在推荐模型中实现的，而推荐模型会负责收集诸如用户偏好、物品描述这些可用作推荐凭借的数据，据此预测特定用户组可能感兴趣的物品。

主要的推荐算法系列有四个（表格1-4）：

协同过滤（Collaborative Filtering）的推荐算法
基于内容过滤（Content-based Filtering）的推荐算法
混合型推荐算法
流行度推荐算法

此外，还有很多高级或非传统的方式，可参见表格5。

本文是系列文中的第一篇，将会以表格形式来介绍推荐算法的主要分类，包括算法简介、典型的输入内容、常见的形式及其优劣。在系列文的第二与第三篇中，我们将会更详细地介绍各种算法的不同，以便让大家更深入地理解其工作原理。本文的某些内容是基于一篇2014年的推荐算法2014教程《推荐问题再探（Recommender Problem Revisited）》来撰写的，该文的作者是Xavier Amatriain。

表格一：协同过滤推荐算法概览

表格二：基于内容过滤的推荐算法概览

表格三：混合方式的推荐算法概览

表格四：流行度推荐算法概览

表格五：高级或“非传统”推荐算法概览

引用

第一部分原文：Overview of Recommender Algorithms – Part 1

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

协同过滤（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推荐算法（即探索-利用）来解决。在下篇文章中我们会详细讨论其中一些算法。

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

引用

第二部分原文：Overview of Recommender Algorithms – Part 2

推荐算法概览（三）
本文是系列文中的第三篇。第一篇文章通过列表形式介绍了推荐算法的主要分类，第二篇文章介绍了不同类型的协同过滤算法，强调了其间的一些细微差别。在本文中，我们将会更加详细地介绍基于内容的过滤算法并讨论其优缺点，以更好地理解其工作原理。

基于内容的过滤算法会推荐与用户最喜欢的物品类似的那些。但是，与协同过滤算法不同，这种算法是根据内容（比如标题、年份、描述），而不是人们使用物品的方式来总结其类似程度的。例如，如果某个用户喜欢电影《魔戒》的第一部和第二部，那么推荐系统会通过标题关键字向用户推荐《魔戒》的第三部。在基于内容的过滤算法中，会假设每个物品都有足够的描述信息可作为特征向量（y）（比如标题、年代、描述），而这些特征向量会被用来创建用户偏好模型。各种信息检索（比如tf-idf）以及机器学习技术（比如朴素贝叶斯算法、支持向量机、决策树等）都可用于生成用户模型，之后再根据模型来进行推荐。

假设我们有一些用户已经表达了他们对某些书籍的偏好，他们越喜欢某本书，对这本书的评分也越高（评分范围是1分到5分）。我们可以在一个矩阵中重现他们的这种偏好，用行代表用户，用列代表书籍。

图一：用户书籍偏好所有偏好的范围都是1分到5分，5分是最高的（也就是最喜欢的）。第一个用户（行1）给第一本书（列1）的评分为4分，如果某个单元格为空，代表着用户并未对这本书作出评价。
在基于内容的协同过滤算法中，我们要做的第一件事就是根据内容，计算出书籍之间的相似度。在本例中，我们使用了书籍标题中的关键字（图二），这只是为了简化而已。在实际中我们还可以使用更多的属性。

图二：用户已经评论过的书籍标题
首先，通常我们要从内容中删除停止词（比如语法词、过于常见的词），然后用代表出现哪些词汇的向量（或数组）对书籍进行表示（图三），这就是所谓的向量空间表示。

图三：使用标题的词汇如果在标题中有这个词，我们以1为标记，否则为空。

有了这个表格，我们就可以使用各种相似指标直接对比各本书籍。在本例中，我们会使用余弦相似点。当我们使用第一本书籍，将其与其他五本书籍对比时，就能看到第一本书籍与其他书籍的相似程度（图四）。就像大多相似度指标一样，向量之间的相似度越高，彼此也就越相似。在本例中，第一本书与其他三本书都很类似，都有两个共同的词汇（推荐和系统）。而标题越短，两本书的相似程度越高，这也在情理之中，因为这样一来，不相同的词汇也就越少。鉴于完全没有共同词汇，第一本书与其他书籍中的两本完全没有类似的地方。

图四：第一本书与其他书籍间的相似性在单个维度中通过两本书之间的余弦相似度就能绘制出来。
我们还可以在相似矩阵中展示出所有书籍彼此间的相似程度（图五）。单元格的背景色表明了用户彼此间的相似程度，红色越深相似度越高。

图五：书籍间的相似矩阵，每个相似点都是基于书籍向量表示之间的余弦相似度。
现在我们知道每本书彼此间的相似程度了，可以为用户生成推荐结果。与基于物品的协同过滤方式类似，我们在之前的文章中也介绍过，推荐系统会根据用户之前评价过的书籍，来推荐其他书籍中相似度最高的。区别在于：相似度是基于书籍内容的，准确来说是标题，而不是根据使用数据。在本例中，系统会给第一个用户推荐第六本书，之后是第四本书（图六）。同样地，我们只取与用户之前评论过的书籍最相似的两本书。

图六：为某个用户生成推荐结果。我们取到他们之前评论过的书籍目录，找出与每本书籍最相似的两本，再对用户尚未评论过的书籍进行推荐。
基于内容的算法解决了协同过滤算法的某些限制，尤其能协助我们克服流行度偏见，以及新物品的冷启动问题，而这些我们已经在协同过滤的部分中讨论过了。然而，值得注意的是：纯粹基于内容的推荐系统通常在执行时效果不如那些基于使用数据的系统（比如协同过滤算法）。基于内容过滤的算法也会有过度专业化的问题，系统可能会向用户推荐过多相同类型的物品（比如获得所有《魔戒》电影的推荐），而不会推荐那些虽然类型不同，但是用户也感兴趣的物品。最后，基于内容的算法在实现时只会使用物品元数据中所含的词汇（比如标题、描述年份），更容易推荐更多相同的内容，限制了用户探索发现这些词汇之外的内容。关于基于内容过滤的优劣总结见表二。

引用

第三部分原文：Overview of Recommender Algorithms – Part 3