`
m635674608
  • 浏览: 5041079 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

协同过滤推荐算法在MapReduce与Spark上实现对比

 
阅读更多

MapReduce为大数据挖掘提供了有力的支持,但是复杂的挖掘算法往往需要多个MapReduce作业才能完成,多个作业之间存在着冗余的磁盘 读写开销和多次资源申请过程,使得基于MapReduce的算法实现存在严重的性能问题。大处理处理后起之秀Spark得益于其在迭代计算和内存计算上的 优势,可以自动调度复杂的计算任务,避免中间结果的磁盘读写和资源申请过程,非常适合数据挖掘算法。腾讯TDW Spark平台基于社区最新Spark版本进行深度改造,在性能、稳定和规模方面都得到了极大的提高,为大数据挖掘任务提供了有力的支持。

 

本文将介绍基于物品的协同过滤推荐算法案例在TDW Spark与MapReudce上的实现对比,相比于MapReduce,TDW Spark执行时间减少了66%,计算成本降低了40%。

 

算法介绍

 

互 联网的发展导致了信息爆炸。面对海量的信息,如何对信息进行刷选和过滤,将用户最关注最感兴趣的信息展现在用户面前,已经成为了一个亟待解决的问题。推荐 系统可以通过用户与信息之间的联系,一方面帮助用户获取有用的信息,另一方面又能让信息展现在对其感兴趣的用户面前,实现了信息提供商与用户的双赢。

 

协同过滤推荐(Collaborative Filtering Recommendation)算法是最经典最常用的推荐算法,算法通过分析用户兴趣,在用户群中找到指定用户的相似用户,综合这些相似用户对某一信息的评价,形成系统对该指定用户对此信息的喜好程度预测。协同过滤可细分为以下三种:

 

  • User-based CF: 基于User的协同过滤,通过不同用户对Item的评分来评测用户之间的相似性,根据用户之间的相似性做出推荐;

  • Item-based CF: 基于Item的协同过滤,通过用户对不同Item的评分来评测Item之间的相似性,根据Item之间的相似性做出推荐;

  • Model-based CF: 以模型为基础的协同过滤(Model-based Collaborative Filtering)是先用历史资料得到一个模型,再用此模型进行预测推荐。

 

问题描述

 

输入数据格式:Uid,ItemId,Rating (用户Uid对ItemId的评分)。

 

输出数据:每个ItemId相似性最高的前N个ItemId。

 

由于篇幅限制,这里我们只选择基于Item的协同过滤算法解决这个例子。

 

算法逻辑

 

基于Item的协同过滤算法的基本假设为两个相似的Item获得同一个用户的好评的可能性较高。因此,该算法首先计算用户对物品的喜好程度,然后根据用户的喜好计算Item之间的相似度,最后找出与每个Item最相似的前N个Item。该算法的详细描述如下:

 

  • 计算用户喜好:不同用户对Item的评分数值可能相差较大,因此需要先对每个用户的评分做二元化处理,例如对于某一用户对某一Item的评分大于其给出的平均评分则标记为好评1,否则为差评0。

  • 计算Item相似性:采用Jaccard系数作为计算两个Item的相似性方法。狭义Jaccard相似度适合计算两个集合之间的相似程度,计算方法为两个集合的交集除以其并集,具体的分为以下三步。

 

1)Item好评数统计,统计每个Item的好评用户数。

2)Item好评键值对统计,统计任意两个有关联Item的相同好评用户 数。

3)Item相似性计算,计算任意两个有关联Item的相似度。

 

  • 找出最相似的前N个Item。这一步中,Item的相似度还需要归一化后整合,然后求出每个Item最相似的前N个Item,具体的分为以下三步。

 

1)Item相似性归一化。

2)Item相似性评分整合。

3)获取每个Item相似性最高的前N个Item。

 

基于MapReduce的实现方案

 

使 用MapReduce编程模型需要为每一步实现一个MapReduce作业,一共存在包含七个MapRduce作业。每个MapReduce作业都包含 Map和Reduce,其中Map从HDFS读取数,输出数据通过Shuffle把键值对发送到Reduce,Reduce阶段 以<key,Iterator<value>>作为输入,输出经过处理的键值对到HDFS。其运行原理如图1 所示。

 

 

七个MapReduce作业意味着需要七次读取和写入HDFS,而它们的输入输出数据存在关联,七个作业输入输出数据关系如图2所示。

 

 

基于MapReduce实现此算法存在以下问题:

 

  • 为了实现一个业务逻辑需要使用七个MapReduce作业,七个作业间的数据交换通过HDFS完成,增加了网络和磁盘的开销。

  • 七个作业都需要分别调度到集群中运行,增加了Gaia集群的资源调度开销。

  • MR2和MR3重复读取相同的数据,造成冗余的HDFS读写开销。

 

这些问题导致作业运行时间大大增长,作业成本增加。

 

基于Spark的实现方案

 

相比与MapReduce编程模型,Spark提供了更加灵活的DAG(Directed Acyclic Graph) 编程模型, 不仅包含传统的map、reduce接口, 还增加了filter、flatMap、union等操作接口,使得编写Spark程序更加灵活方便。使用Spark编程接口实现上述的业务逻辑如图3所示。

 

 

相对于MapReduce,Spark在以下方面优化了作业的执行时间和资源使用。

 

  • DAG 编程模型。 通过Spark的DAG编程模型可以把七个MapReduce简化为一个Spark作业。Spark会把该作业自动切分为八个Stage,每个Stage 包含多个可并行执行的Tasks。Stage之间的数据通过Shuffle传递。最终只需要读取和写入HDFS一次。减少了六次HDFS的读写,读写 HDFS减少了70%。

  • Spark作业启动后会申请所需的Executor资源,所有Stage的Tasks以线程的方式运行,共用Executors,相对于MapReduce方式,Spark申请资源的次数减少了近90%。

  • Spark 引入了RDD(Resilient Distributed Dataset)模型,中间数据都以RDD的形式存储,而RDD分布存储于slave节点的内存中,这就减少了计算过程中读写磁盘的次数。RDD还提供了 Cache机制,例如对上图的rdd3进行Cache后,rdd4和rdd7都可以访问rdd3的数据。相对于MapReduce减少MR2和MR3重复 读取相同数据的问题。

 

效果对比

 

测试使用相同规模的资源,其中MapReduce方式包含200个Map和100个Reduce,每个Map和Reduce配置4G的内存; 由于Spark不再需要Reduce资源, 而MapReduce主要逻辑和资源消耗在Map端,因此使用200和400个Executor做测试,每个Executor包含4G内存。测试结果如下表所示,其中输入记录约38亿条。

 

 

对比结果表的第一行和第二行,Spark运行效率和成本相对于MapReduce方式减少非常明显,其中,DAG模型减少了70%的HDFS读写、cache减少重复数据的读取,这两个优化即能减少作业运行时间又能降低成本;而资源调度次数的减少能提高作业的运行效率。

 

对比结果表的第二行和第三行,增加一倍的Executor数目,作业运行时间减少约50%,成本增加约25%,从这个结果看到,增加Executor资源能有效的减少作业的运行时间,但并没有做到完全线性增加。这是因为每个Task的运行时间并不是完全相等的, 例如某些task处理的数据量比其他task多;这可能导致Stage的最后时刻某些Task未结束而无法启动下一个Stage,另一方面作业是一直占有Executor的,这时候会出现一些Executor空闲的状况,于是导致了成本的增加。

 

小结

 

数 据挖掘类业务大多具有复杂的处理逻辑,传统的MapReduce/Pig类框架在应对此类数据处理任务时存在着严重的性能问题。针对这些任务,如果利用 Spark的迭代计算和内存计算优势,将会大幅降低运行时间和计算成本。TDW目前已经维护了千台规模的Spark集群,并且会在资源利用率、稳定性和易 用性等方面做进一步的提升和改进,为业务提供更有利的支持。

 

 

http://www.wtoutiao.com/a/717856.html

分享到:
评论
1 楼 大漠小帆 2018-07-10  
麻烦问下,“获取每个Item相似性最高的前N个Item”,这个有什么优化的方法?不可能是每两个计算一下相似度,再排序吧???

相关推荐

    基于物品的协同过滤推荐算法

    基于物品的协同过滤推荐算法是推荐系统中一种广泛使用的...总的来说,基于物品的协同过滤推荐算法借助MapReduce和Hadoop,能够处理海量用户行为数据,实现个性化推荐,而这种分布式实现方式是应对大数据挑战的关键。

    基于MapReduce的商品推荐算法.zip

    在Hadoop生态系统中,我们可以通过Apache Mahout或者Spark MLlib等库实现基于MapReduce的推荐算法。Mahout提供了丰富的推荐算法实现,包括基于用户和物品的协同过滤,而Spark的并行计算能力则使得实时推荐成为可能。...

    Netflix数据集上的协同过滤算法

    《Netflix数据集上的协同过滤算法》是一篇深入探讨在Netflix数据集上应用协同过滤技术的硕士论文。Netflix数据集是著名的公开数据集,用于研究和评估推荐系统的效果,特别是基于用户的协同过滤算法。本文将围绕这个...

    基于MapReduce实现物品协同过滤算法(ItemCF)

    本话题主要探讨如何利用MapReduce来实现物品协同过滤算法(Item-based Collaborative Filtering, 简称ItemCF),这是一种推荐系统中常用的算法。我们将深入理解ItemCF的原理,以及如何将其与MapReduce相结合。 **...

    基于协同过滤算法的大数据中信息推荐系统设计.docx

    《基于协同过滤算法的大数据中信息推荐系统设计》是一篇深度探讨协同过滤推荐算法及其在大数据环境下应用的毕业论文。协同过滤是推荐系统中的核心算法之一,它通过分析用户的行为历史和兴趣偏好,找出相似的用户或...

    Sparkvs.MapReduce时间节约66%,计算节约40%

    本文将介绍基于物品的协同过滤推荐算法案例在TDWSpark与MapReudce上的实现对比,相比于MapReduce,TDWSpark执行时间减少了66%,计算成本降低了40%。MapReduce为大数据挖掘提供了有力的支持,但是复杂的挖掘算法往往...

    基于springboot协同过滤算法商品推荐系统.zip

    总结,基于SpringBoot的协同过滤算法商品推荐系统是一个综合运用了Java技术栈、大数据处理、推荐算法以及移动端开发的项目。它的实现既展示了技术的综合应用,也为电商平台提供了有效的个性化推荐方案,有助于提升...

    基于ssm协同过滤算法的图书推荐系统.zip

    《基于SSM协同过滤算法的图书推荐...综上所述,基于SSM协同过滤算法的图书推荐系统是将Java Web技术与机器学习算法相结合的实践案例,旨在为用户提供个性化的图书推荐服务,同时也展示了现代Web开发的流程和技术栈。

    基于Spark MLlib分布式学习算法的研究.pdf

    本文研究的是如何利用Spark MLlib实现分布式学习算法,尤其是在处理电子商务服务中海量用户数据的场景下,对比传统的单机算法,Spark MLlib的分布式学习算法在性能上具有明显的优势。 在研究的背景下,由于电子商务...

    基于大数据的餐饮推荐系统,整体采用Lambda架构,读取餐饮评分数据并通过Spark的MLlib中的ALS建立推荐模型后进行推荐

    本篇将深入探讨一种基于大数据的餐饮推荐系统,该系统利用Lambda架构设计,结合Apache Spark的MLlib库中的协同过滤算法(Alternating Least Squares, ALS)来构建推荐模型,旨在为用户提供精准的美食推荐。...

    计算机课程毕设:基于hbase + spark 实现常用推荐算法(主要用于精准广告投放和推荐系统).zip

    项目文件"project"可能包含了源代码、配置文件、数据集、README文档等,其中源代码会详细展示如何在Spark上实现上述过程。通过阅读和学习这些代码,学生不仅可以掌握HBase和Spark的基本用法,还能深入理解推荐系统的...

    MapReduce高阶实现

    - 实际应用中,MapReduce被广泛应用于搜索引擎的索引构建、推荐系统的协同过滤、日志分析等场景。通过学习这些案例,可以更好地理解MapReduce的实际价值和适用场景。 在“MapReduce高阶实现”的课程中,你将有机会...

    基于Spark的分布式实时推荐系统.pdf

    Spark作为一个快速的分布式计算系统,支持内存计算,能够实现快速的迭代计算,对于需要多次迭代的算法(如协同过滤算法)具有明显优势。Spark通过弹性分布式数据集(RDD)实现数据操作,通过DAG(有向无环图)执行...

    计算机课程毕设:基于Spark ML实现的豆瓣电影推荐系统.zip

    在电影推荐系统中,通常采用协同过滤算法,通过分析用户对电影的评分历史,找出具有相似口味的用户,然后推荐他们喜欢的电影给其他用户。 4. **协同过滤**:协同过滤是推荐系统中最常见的算法之一,分为用户-用户...

    JAVA毕业设计之springboot基于协同过滤算法商品推荐系统项目(springboot完整源码+说明).zip

    8. **性能优化**:在大数据量下,协同过滤算法可能会面临计算复杂度高和内存消耗大的问题,因此可能需要进行一些优化,比如使用MapReduce或Spark进行分布式计算。 9. **测试与部署**:编写单元测试和集成测试,确保...

    Spark电商推荐项目源码.zip

    3. 推荐算法:常见的推荐算法有基于用户的协同过滤、基于物品的协同过滤、矩阵分解等,Spark MLlib库提供了丰富的机器学习算法实现。 4. 模型评估:通过离线评估和在线A/B测试,持续优化模型性能。 四、...

    毕业设计:基于Spark+Mlib的在线交友智能推荐系统的设计与实现.zip

    在本项目中,我们可能采用了物品-物品协同过滤,通过分析用户对不同物品的评价历史,找出物品之间的相似性,进而推荐与用户过去喜欢的物品相似的新物品。 4. 在线交友推荐系统 系统首先需要收集用户的基本信息、...

    基于Spark机器学习的电商推荐系统设计与实现.zip

    推荐系统主要分为基于内容的推荐和协同过滤推荐。基于内容的推荐通过分析用户的历史行为和商品属性,推荐与用户偏好相似的商品;协同过滤则利用用户之间的相似性或商品之间的相似性进行推荐。本项目采用协同过滤方法...

    基于Spark ML实现的豆瓣电影推荐系统.zip

    8. **优化策略**:为了提高推荐系统的效率和准确性,可以考虑引入更高级的协同过滤变种,如矩阵分解,或者结合其他推荐算法如基于内容的推荐、深度学习等。 9. **项目开发流程**:整个项目通常包括需求分析、数据...

    MapReduce实现推荐系统.pptx

    在这个过程中,你可能会使用到如协同过滤、矩阵分解等推荐算法。 4. **项目构建**:在Eclipse这样的集成开发环境中,创建一个新的Java工程,如这里的`recommendation`工程,定义对应的包结构(如`com.uicc.shizhan`...

Global site tag (gtag.js) - Google Analytics