略微加速

略速 - 互联网笔记

推荐算法概览

2018-12-04 leiting (2219阅读)

标签 算法

推荐算法概览(一)


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


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


主要的推荐算法系列有四个(表格1-4):


  • 协同过滤(Collaborative Filtering)的推荐算法

  • 基于内容过滤(Content-based Filtering)的推荐算法

  • 混合型推荐算法

  • 流行度推荐算法


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


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


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


1.png


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


2.png


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


3.png


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


4.png


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


5.png


第一部分原文:Overview of Recommender Algorithms – Part 1(https://buildingrecommenders.wordpress.com/2015/11/16/overview-of-recommender-algorithms-part-1/


推荐算法概览(二)


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


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


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


  • 基于用户的协同过滤是探索对物品拥有相似品味的用户,并基于彼此喜爱的物品来进行互推。

  • 基于物品的协同过滤是用户喜爱的物品,推荐类似的东西。而这种相似性建立在物品同时出现的基础上,比如购买了x物品的用户也购买了y物品。


首先,在执行基于物品的协同过滤前,我们先看一个基于用户的协同过滤案例。

 

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


6.png


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


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


7.png


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


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


8.png

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


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


9.png

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


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


10.png


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


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


11.png

图六:书籍的相似矩阵


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


12.png


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


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


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


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


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


13.png


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


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


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


第二部分原文:Overview of Recommender Algorithms – Part 2(https://buildingrecommenders.wordpress.com/2015/11/18/overview-of-recommender-algorithms-part-2/


推荐算法概览(三)


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


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


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


14.png


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


在基于内容的协同过滤算法中,我们要做的第一件事就是根据内容,计算出书籍之间的相似度。在本例中,我们使用了书籍标题中的关键字(图二),这只是为了简化而已。在实际中我们还可以使用更多的属性。


15.png


图二:用户已经评论过的书籍标题


首先,通常我们要从内容中删除停止词(比如语法词、过于常见的词),然后用代表出现哪些词汇的向量(或数组)对书籍进行表示(图三),这就是所谓的向量空间表示。


16.png


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


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

aaa.png


图四:第一本书与其他书籍间的相似性在单个维度中通过两本书之间的余弦相似度就能绘制出来。


我们还可以在相似矩阵中展示出所有书籍彼此间的相似程度(图五)。单元格的背景色表明了用户彼此间的相似程度,红色越深相似度越高。


18.png


图五:书籍间的相似矩阵,每个相似点都是基于书籍向量表示之间的余弦相似度。


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


19.png


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


基于内容的算法解决了协同过滤算法的某些限制,尤其能协助我们克服流行度偏见,以及新物品的冷启动问题,而这些我们已经在协同过滤的部分中讨论过了。然而,值得注意的是:纯粹基于内容的推荐系统通常在执行时效果不如那些基于使用数据的系统(比如协同过滤算法)。基于内容过滤的算法也会有过度专业化的问题,系统可能会向用户推荐过多相同类型的物品(比如获得所有《魔戒》电影的推荐),而不会推荐那些虽然类型不同,但是用户也感兴趣的物品。最后,基于内容的算法在实现时只会使用物品元数据中所含的词汇(比如标题、描述年份),更容易推荐更多相同的内容,限制了用户探索发现这些词汇之外的内容。关于基于内容过滤的优劣总结见表二。


第三部分原文:Overview of Recommender Algorithms – Part 3(https://buildingrecommenders.wordpress.com/2015/11/19/overview-of-recommender-algorithms-part-3/


推荐算法概览(四)


本文是系列文中的第四篇。第一篇文章通过列表形式介绍了推荐算法的主要分类,第二篇文章介绍了不同类型的协同过滤算法,强调了其间的一些细微差别,在第三篇中我们详细介绍了基于内容的过滤算法。本文将会讨论基于之前提过算法而形成的混合型推荐系统,也会简单讨论如何利用流行度来解决一些协同过滤算法与基于内容过滤算法的限制。


混合算法结合了用户及物品的内容特性以及使用数据,以利用这两类数据的优点。结合了A算法与B算法的某个混合型推荐系统会尝试利用A算法的优点以解决B算法的缺点。例如,协同过滤算法存在新物品的问题,也就是说这种算法无法推荐用户未评价或使用过的物品。因为是基于内容(特性)预测的,这一点并不会对基于内容的算法产生限制。而结合了协同过滤与基于内容过滤算法的混合型推荐系统能够解决单个算法中的一些限制,比如冷启动的问题与流行度偏好的问题。表一列出了一些不同的方法,包括如何结合两种甚至更多基础推荐系统技术,以创建新的混合型系统。


表一:结合两种甚至更多的基础推荐算法,以创建新混合算法的不同方式。


20.png


假设我们有一些用户已经表达了他们对某些书籍的偏好,他们越喜欢某本书,对这本书的评分也越高(评分级别分别为1-5)。我们可以在一个矩阵中重现他们的这种偏好,用行代表用户,用列代表书籍。


21.jpeg


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


在本文所属系列的第二篇中,我们给出了两个案例,包括如何使用基于物品及基于用户的协同过滤算法来计算推荐结果;在本文所属系列的第三篇中,我们演示了如何使用基于内容的过滤算法来生成推荐结果。现在我们将这三种不同的算法结合起来,生成一种全新的混合型推荐结果。我们会使用加权法(表一)结合多种技术得出的结果,之后这三种算法便可按照不同的权值(根据重要性不同)结合得出一组新的推荐结果。


我们先以第一个用户为例,为其生成一些推荐。首先我们会根据第二篇中的基于用户的协同过滤算法,基于物品的协同过滤算法,以及第三篇中基于内容过滤的算法,各自生成推荐结果。值得注意的是,在这个小案例中,这三种方法为同一名用户生成的推荐结果有着轻微的差异,尽管输入的内容是完全相同的。


22.png

 

图二:为某个用户生成的推荐结果——分别使用基于用户的协同过滤算法,基于物品的协同过滤算法,以及基于内容的过滤算法。


下一步,我们使用加权混合推荐算法为指定用户生成推荐结果,加权值分别为:基于用户的协同过滤算法40%,基于物品的协同过滤算法30%,基于内容过滤的算法30%(图三)。在这个案例中,系统会向用户推荐他们从未看过的所有三本书,而使用单个算法只会推荐其中两本。


23.jpeg

图三:使用加权混合推荐系统为某个用户生成推荐结果,具体权值参见上文。


尽管混合型算法解决了CF与CB算法的一些重大挑战与限制(见图三),但在系统中平衡不同的算法也需要很多工作量。另一种结合单个推荐算法的方式是使用集成方法,关于如何结合不同算法得出的结果,我们研究得出了一个函数。值得注意的是:通常集成算法不仅结合了不同的算法,还结合了根据同一种算法得出的不同变体与模型。例如:获得Netflix Prize奖项的解决方案包含了从10多种算法(流行度、邻域算法、矩阵分解算法、受限波尔兹曼机、回归等等)得出的100多种不同的模型,并通过迭代决策树(GBDT)将这些算法与模型结合在一起。


另外,基于流行度的算法对于新用户的冷启动问题来说也是一个优秀的解决方案。这些算法通过某些流行度的测量标准,比如下载最多的或者购买最多的,来对物品进行排名,并将这些流行度最高的物品推荐给新用户。当拥有合适的流行度衡量指标时,这个办法虽然基础却很有效,通常可以为其他算法提供很好的基线标准。流行度算法也可以单独作为算法使用,以引导推荐系统在换到其他更切合用户兴趣点的算法(比如协同过滤算法以及基于内容过滤的算法)前获得足够的活跃度与使用量。流行度模型也可以引入混合算法中,从而解决新用户的冷启动问题。


第四部分原文:Overview of Recommender Algorithms – Part 4(https://buildingrecommenders.wordpress.com/2015/11/20/overview-of-recommender-algorithms-part-4/


推荐算法概览(五)


本文是推荐算法系列文中的第五篇。第一篇文章通过列表形式介绍了推荐算法的主要分类,第二篇文章介绍了不同类型的协同过滤算法,强调了其间的一些细微差别,在第三篇中我们详细介绍了基于内容的过滤算法,在第四篇中我们讲解了混合型推荐系统以及基于流行度的算法。在本篇中,我们会对简单了解一下如何对一些高级的推荐算法做以选择,再回顾一下基础算法得出的推荐结果差异有多大,以便本系列完美收官。除了我们截至目前提到的一些更为传统的推荐系统算法之外(比如流行度算法、协同过滤算法、基于内容过滤的算法、混合型算法),还有许多其他算法也可用于加强推荐系统的功能,包括有:


  • 深度学习算法

  • 社会化推荐

  • 基于机器学习的排序方法

  • Multi-armed bandits推荐算法(探索/利用)

  • 情景感知推荐(张量分解&分解机)


这些更为高级的非传统算法对于将现有推荐系统的质量推向更高层次很有好处,但理解起来也更困难,推荐工具的支持上也不够。在实践中,我们总要权衡实现高级算法的代价与对基础算法的增益相比较是否值得。根据经验来看,基础算法还能使用很久,为一些很优秀的产品提供服务。在本系列文中,我们希望介绍一些常见的推荐模块算法,包括基于用户的协同过滤算法,基于物品的协同过滤算法,基于内容的过滤算法,以及混合型算法。我们使用了一个案例,说明了这四种不同算法在输入数据相同时,应用于同一个案例时,为同一个用户生成的不同推荐结果(图一)。当应用于真实世界的大型数据时,这样的效应依然存在,因此决定使用哪种算法时,需要考虑相关的优缺点以及执行效果。

24.png

图一:四种推荐系统算法全部使用同一组数据,却得出了不同的结果。左侧我们给出了一个矩阵,标明了用户对大量物品的不同偏好,并列出了可以推荐的物品名称。在中间,我们展示了这四种不同算法如何为第一名用户生成推荐结果(也就是用户偏好矩阵中第一行的用户)。就像相似矩阵中展示的那样,这些算法对相似度有不同的定义。右侧则是每种推荐算法生成的一些物品,从上到下分别按照四种算法的介绍顺序来排序。


在实践中,一般如果在推荐模型中使用协同过滤算法,就不会犯太大错误。协同过滤算法似乎比其他算法更优秀,但在冷启动用户及物品方面会有问题,因此通常会使用基于内容的算法作为辅助。如果有时间的话,使用混合型算法就可以结合协同过滤及基于内容过滤算法优势了。将这些基础算法放在一起当然是个好办法,甚至比高级算法还要更好。


最后这一点值得牢记:推荐模型只是五个推荐系统组件中的一个。与所有组件类似,正确设置并努力建立模型非常重要,不过选择数据集、处理、后处理、在线模块及用户界面也同样重要。正如我们再三强调的那样,算法只是推荐系统的一部分,整个产品应当将你的决策纳入考量。


第五部分原文:Overview of Recommender Algorithms – Part 5 (https://buildingrecommenders.wordpress.com/2015/11/23/overview-of-recommender-algorithms-part-5/

https://mp.weixin.qq.com/s/Kh9y9XFaDYu7fngcdIuXPQ


北京半月雨文化科技有限公司.版权所有 京ICP备12026184号-3