学校编码 :10384 分类号密级学号 : UDC 硕士学位论文基于云的分布式机器学习框架 Cloud Based Distributed Machine Learning 蒋文瑞指导教师姓名 : 倪子伟副教授专业名称 : 计算机技术论文提交日期 :2013

Size: px

Start display at page:

Download "学校编码 :10384 分类号密级学号 : UDC 硕士学位论文基于云的分布式机器学习框架 Cloud Based Distributed Machine Learning 蒋文瑞指导教师姓名 : 倪子伟副教授专业名称 : 计算机技术论文提交日期 :2013"

纭九计
4 years ago
Views:

学校编码 :10384 分类号密级学号 :23020101153007 UDC 硕士学位论文基于云的分布式机器学习框架 Cloud Based Distributed Machine Learning 蒋文瑞

1 学校编码 :10384 分类号密级学号 : UDC 硕士学位论文基于云的分布式机器学习框架 Cloud Based Distributed Machine Learning 蒋文瑞指导教师姓名 : 倪子伟副教授专业名称 : 计算机技术论文提交日期 :2013 年论文答辩时间 :2013 年学位授予日期 :2013 年月月月答辩委员会主席 : 评阅人 : 2013 年月 IV

2 厦门大学学位论文原创性声明本人呈交的学位论文是本人在导师指导下, 独立完成的研究成果本人在论文写作中参考其他个人或集体已经发表的研究成果, 均在文中以适当方式明确标明, 并符合法律规范和厦门大学研究生学术活动规范 ( 试行 ) 另外, 该学位论文为 ( ) 课题 ( 组 ) 的研究成果, 获得 ( ) 课题 ( 组 ) 经费或实验室的资助, 在 ( ) 实验室完成 ( 请在以上括号内填写课题或课题组负责人或实验室名称, 未有此项声明内容的, 可以不作特别声明 ) 声明人 ( 签名 ): 年月日

厦门大学学位论文著作权使用声明本人同意厦门大学根据中华人民共和国学位条例暂行实施办法等规定保留和使用此学位论文, 并向主管部门或其指定机构送交学位论文 ( 包括纸质版和电子版 ), 允许学位论文进入厦门大学图书馆及其数据库被查阅借阅本人同意厦门大学将学位论文加入全国博士硕士学位论文共建单位数据库进行检索, 将学位论文的标题和摘要汇编出版, 采用影印

3 厦门大学学位论文著作权使用声明本人同意厦门大学根据中华人民共和国学位条例暂行实施办法等规定保留和使用此学位论文, 并向主管部门或其指定机构送交学位论文 ( 包括纸质版和电子版 ), 允许学位论文进入厦门大学图书馆及其数据库被查阅借阅本人同意厦门大学将学位论文加入全国博士硕士学位论文共建单位数据库进行检索, 将学位论文的标题和摘要汇编出版, 采用影印缩印或者其它方式合理复制学位论文本学位论文属于 : ( )1. 经厦门大学保密委员会审查核定的保密学位论文, 于年月日解密, 解密后适用上述授权 ( )2. 不保密, 适用上述授权 ( 请在以上相应括号内打或填上相应内容保密学位论文应是已经厦门大学保密委员会审定过的学位论文, 未经厦门大学保密委员会审定的学位论文均为公开学位论文此声明栏不填写的, 默认为公开学位论文, 均适用上述授权 ) 声明人 ( 签名 ): 年月日

4 摘要摘要如今, 数据挖掘在生活中也扮演着越来越重要的角色, 不管是公共事业还是私人行业银行业, 保险业, 医疗业, 零售业大量的使用数据挖掘来发掘金融欺诈, 评估金融风险, 减少成本, 加强研究, 增加销售额等等然而激增的数据为传统的数据挖掘方式提出了严重的挑战商业巨头 Google, Yahoo 和 Amazon 需要浏览 TB 与 PB 级的数据来发掘哪些网站是最有吸引力的, 哪些书籍是最受欢迎的, 哪些广告应该呈现给浏览者传统的工具面对这些情形越来越显无能为力在这样的背景下,Google 提出了 MapReduce 处理模型,Doug Cutting 基于此开发了开源系统 Hadoop,CMU 提出了 GraphLab 处理模型这些模型与框架能有效地处理海量数据然而单纯的这种模型与框架并不能直接用于数据的分析在这样的背景下, 本文提出 CB-DML( 基于云的分布式数据挖掘 ) 模型, 利用 MapReduce 和 GraphLab 强大的并行机制, 并结合经典的数据挖掘算法, 提供可扩展的机器学习能力, 从海量数据中挖掘高价值量的重要信息本文事先充分研究了机器学习算法的可并行性, 并行方式及并行策略并研究了 Mapreduce 源代码, 框架并行特性, 使用场景及框架本身的性能优化策略最终实现了基于云的分布式机器学习框架 CB-DML, 提供 6 大类并行机器学习算法 : 聚类分类线性回归统计图处理相似项挖掘部分机器学习算法在并行化之前, 亦做了相关的改进与优化 CB-DML 最终在自建的分布式集群上测试通过, 性能表现优越, 与此同时, 框架最终还应用于实际的工业场景时间序列分析, 并表现出了优良的性能关键词 : 机器学习, MapReduce, GraphLab,CB-DML I

6 Abstract Abstract Today, Data mining is becoming increasingly common in both the private and public sectors. Industries such as banking, insurance, medicine, and retailing commonly use data mining to detect fraud, assess risk, reduce costs, enhance research, and increase sales. The exponential growth of data first presents challenges to traditional data mining tools. Businesses such as Google, Yahoo and Amazon need to go through terabytes and petabytes of data to figure out which websites were popular, what books are in demand, and what kinds of ads appeal to people. Existing tools were becoming inadequate to process such large data sets. Then Google was the first to publicize MapReduce, Doug Cutting developed an open source version of it called Hadoop and CMU developed GraphLab after then System they had used to scale their data processing needs. In this backgraoud, we propose CB-DML(Cloud based- Distributed Machine Learning) model, a scalable machine learning platform Leveraging the power of MapReduce and GraphLab. It gives scalable parallel machine learning services, making large data sets not a barrier any more. We researched parallelism, parallel way and strategies of the ML algorithms. Also researched MapReduce source code, parallel features of the framework and performance optimization strategy of the framework itself. CB-DML was realized ultimately, giving parallel machine learning algorithms like: clustering, classification, regression, statistical, graph processing, similarity mining. Part of the machine learning algorithms were improved and optimized before parallelization. CB-DML was tested giving perfect performance on our own cluster. At the same time, the model was applied to actual industrial scene - time series analysis, and exhibited excellent performance. Key Words: Machine Learning, MapReduce, GraphLab, CB-DML III

8 目录目录摘要... I Abstract... III 第一章概述研究背景数据挖掘与工业应用研究现状课题研究目的及意义本文主要工作及文章结构... 6 第二章 CB-DML 总体设计架构图及设计原则 CB-DML 整体架构图 CB-DML 功能模块 CB-DML 设计原则第三章分布式框架相关理论 MapReduce 概述 GraphLab 第四章机器学习算法详述 CB-DML 算法选取依据所选算法详述第五章分布式机器学习算法设计与实现并行化 K-means 并行 C 并行朴素贝叶斯并行 KNN 并行 TF-IDF 并行 PageRank 并行相似性挖掘系统 V

9 目录 5.8 并行回归模型第六章 CB-DML 处理大数据性能测试实验环境 Hadoop 集群搭建集群性能调优性能测试第七章总结与展望工作总结未来工作展望参考文献攻读硕士学位期间发表论文及科研情况致谢 VI

10 Contents Contents Abstract(CH)... I Abstract(EN)... II Chapter 1 Introduction Research Backgroud Data Mining and Industrial Application Research Status Research Purpose and Significance Main Research Contents and Outline... 6 Chapter 2 CB-DML Architecture and Design Principles CB-DML Architecture CB-DML Function Module CB-DML Design Principles Chapter 3 Distributed Framework Theory MapReduce GraphLab Chapter 4 Machine Learning Algorithms Overview CB-DML Algorithms Selection Introduction to the Selected Algorithms Chapter 5 Distributed ML Algorithm Design and Implementation Parallel K-means Parallel C Parallel Naïve Bayes Parallel KNN Parallel TF-IDF Parallel PageRank Parallel Similarity Mining System Parallel Regression Model VII

11 Contents Chapter 6 CB-DML - Performance Enviroment Hadoop Cluster Constrution Cluster Performance Tuning Performance Testing Chapter 7 Conclusion and Prospect Conclusion Prospects of Future Reference Publications Acknowledgements VIII

12 第一章概述第一章概述 1.1 研究背景数据挖掘与工业应用数据挖掘在工业与生活中扮演着越来越重要的角色, 不管是公共事业还是私人行业银行业, 保险业, 医疗业, 零售业大量的使用数据挖掘来发掘金融欺诈, 评估金融风险, 减少成本, 加强研究, 增加销售额等等数据挖掘诞生由来已久, 图 1-1 揭示了它的诞生图 1-1 数据挖掘的诞生数据挖掘在工业应用中的统计如图 1-2 所示 : 1

13 基于云的分布式机器学习框架 CRM/ consumer analytics Banking Health care/ HR Fraud Detection Direct Marketing/ Fundraising Finance Telecom / Cable Science Insurance Advertising Education Web usage mining Credit Scoring Retail Medical/ Pharma Manufacturing e-commerce Social Networks Search / Web content mining Government/Military Biotech/Genomics Investment / Stocks Entertainment/ Music Security / Anti-terrorism Travel / Hospitality Social Policy/Survey analysis Junk / Anti-spam Other 图 1-2 数据挖掘在工业中应用情况在工商业中, 数据的存在形式是丰富多样的, 其大小更是呈现飞速增长, 截至 2011 平均的数据吞吐量已按照 PB 级计算 1.2 研究现状 0.0% 5.0% 10.0% 15.0% 20.0% 25.0% 30.0% 数据挖掘在工业中扮演者举足轻重的角色, 然而, 激增的数据为传统的数据挖掘方式提出了严重的挑战, 如今, 数据无处不在, 而其增长速度更是超出人们的想象商业巨头 Google, Yahoo 和 Amazon 需要浏览 TB 与 PB 级的数据来发掘哪些网站是最有吸引力的, 哪些书籍是最受欢迎的, 哪些广告应该呈现给浏览者传统的工具面对这些情形越来越显无能为力图 1-3 揭示 2010 与 2011 待分析数据的增长情况 : 2

第一章概述图 1-3 2010 与 2011 数据增长统计在这样的背景下, 需要一些有力的工具或平台来存储分析与日俱增的大数据, 并且这些框架还必须要满足低成本的要求, 基于这样的一个需求, 接下来本文介绍分布式框架的研究现状, 着重介绍 Google Mapreduce [1], Apache Hadoop [2] 以及 CMU Graphlab [3] 等平台的研究与诞生

14 第一章概述图与 2011 数据增长统计在这样的背景下, 需要一些有力的工具或平台来存储分析与日俱增的大数据, 并且这些框架还必须要满足低成本的要求, 基于这样的一个需求, 接下来本文介绍分布式框架的研究现状, 着重介绍 Google Mapreduce [1], Apache Hadoop [2] 以及 CMU Graphlab [3] 等平台的研究与诞生 MapReduce 处理模型是由 Google 提出 [4], 基于此基础,Doug Cutting 此开发了开源系统 Hadoop [5] 这种模型与框架能有效地处理海量数据 Hadoop 的两大核心构件是 HDFS [6] 与 MapReduce, 其中 HDFS [7] 用于大数据的分布式存储, 其具有极强的低成本性和可扩展性, 能完美的满足云的需求, 而 MapReduce 则用于数据的高效实时分析, 在保证能应对大数据的前提下, 依然保持着运算高效率然而 MapReduce 和 Hadoop 并非是万能的, 这也就引出了本文所用的 GraphLab 平台 : MapReduce 适用于数据任务之间独立性强的计算, 对于那些富含迭代的运算或者数据任务之间有交互的计算不适合这个来源于 Mapreduce 的信息交互方式是 I/O 方式, 每轮迭代之间需要走 I/O 来传递信息, 这样的开销是比较大的由于大多数的机器学习问题包含迭代问题, 因此 Mapreduce 在处理迭代问题时并不能表现出完美地性能, 尤其是对于图问题,Mapreduce 表现出来的性能很一般 3

15 基于云的分布式机器学习框架为解决机器学习的流处理,Google 提出了 Pregel 框架 [8],Pregel 是严格的 BSP 模型, 采用计算 - 通信 - 同步的模式完成机器学习的数据同步和算法迭代 Goolge 曾称其 80% 的程序使用 MapReduce 完成,20% 的程序使用 Pregel 实现然后它的最大不方便之处正是在于不开源那么我们必须继续探寻其他适用于迭代运算的框架幸运的是,2010 年,CMU 的 Select 实验室提出了 GraphLab 框架,GraphLab 是面向机器学习的流处理并行框架 [1] 其对自然图的处理, 做出了显著的改进. 这种框架有效弥补了 Mapreduce 框架的不足之处, 能有效处理迭代问题, 其信息传递方式是信息共享, 这种框架实现了分布式共享内存, 故而在处理迭代问题和任务间交互性强的计算时, 性能表现优越因而他适合于机器学习的并行化, 更适于处理大图问题在处理大图问题时, 其对图有一套有效的图分割 - 分布式存储机制然而光有这些分布式框架还不行, 还需要将这些强大的分布式框架与传统经典的数据挖掘算法相结合, 才能诞生一个有效应对大数据的利器目前的一个研究现状是中国移动研究院的大云平台 :BC-PDM BC-PDM ( 基于大云的并行数据挖掘 ) 为云存储与分布式计算框架, 提供 SaaS 服务, 高效的存储处理海量数据包含常见 ETL 和数据挖掘算法平台采用 MapReduce,Hadoop,HugeTable 等大规模分布式处理技术 1.3 课题研究目的及意义如今大数据无处不在, 各种科学领域, 社交网络, 互联网, 工业应用, 商业中都会产生大量的数据 [9]. 而且大数据中也蕴藏着不可低估的价值, 这一点已是不可否认的事实既然大数据中蕴含着如此巨大的价值, 那么一个能有效存储分析大数据的平台也就迫在眉睫, 但是仍有人提出采用高性能服务器的方案来处理大数据, 高性能服务器相比云的方案有一个很大好处 : 不用部署分布式环境, 不必将原有的程序额外花时间扩展成分布式程序那么它的实际性能如何呢, 以下是高性能服务器与集群运行能力的一个对比 : 4

第一章概述 Time: 1600 Unix Servers 1400 1200 1000 800 600 400 200 0 BC-PDM(10 times data) BC-PDM(100 times data) 图 1-4 高性能服务器与集群运算能力对比图 1-4 中, 每种算法最左边为

16 第一章概述 Time: 1600 Unix Servers BC-PDM(10 times data) BC-PDM(100 times data) 图 1-4 高性能服务器与集群运算能力对比图 1-4 中, 每种算法最左边为 Unix 高性能服务器运行时间, 中间为集群处理 10 倍数据量时的时间, 最右边为集群处理 100 倍数据时的时间处理算法包括连接, 统计, 采样, 决策树, 聚类等算法, 从图中可以看出, 集群的处理性能优越于高性能服务器那么这两种架构的成本又如何呢? 表 1-1 对比了二者的成本 5

17 Degree papers are in the Xiamen University Electronic Theses and Dissertations Database. Full texts are available in the following ways: 1. If your library is a CALIS member libraries, please log on and submit requests online, or consult the interlibrary loan department in your library. 2. For users of non-calis member libraries, please mail to etd@xmu.edu.cn for delivery details.

2

10384 -------- 9601008 UDC---------------------- 1999 1999 1999 ------------------------ ------------------------ 1 2 .4...4 7 14.14..18..22..22..24 3 4.27.32.39 1 2 3 4 5 6 7 8 9 10 11 5 12 6 1 2 3 4

学校编码 :10384 分类号密级 学号 : UDC 硕士学位论文 基于云的分布式机器学习框架 Cloud Based Distributed Machine Learning 蒋文瑞 指导教师姓名 : 倪子伟副教授 专 业名称 : 计算机技术 论文提交日期 :2013

学校编码 :10384 分类号密级学号 : UDC 硕士学位论文基于云的分布式机器学习框架 Cloud Based Distributed Machine Learning 蒋文瑞指导教师姓名 : 倪子伟副教授专业名称 : 计算机技术论文提交日期 :2013